今日の精進
毎日格上の問題を倒すやつの61日目です。 問題リンク atcoder.jp 問題概要 四隅に色がついたタイルが 枚あるよ。 これを組み合わせて隅に集まる色が同じ立方体を作りたいよ。 どのタイルにも向きがあるとき、作れる立方体が何通りか答えてね。 解法 上のタイ…
毎日格上の問題を倒すやつの58日目です。 問題リンク atcoder.jp 問題概要 すべての数が 回ずつ出る長さ の数列のうち、以下のようなものを見つけるか、そんなものはないと宣言してね。 番目の は全体で の位置にある 解法 非常に単純明快です。 の小さい順…
毎日格上の問題を倒すやつの57日目です。 問題リンク atcoder.jp 問題概要 を満たすすべての に対して、 となるような に対する の総和の最大値を求めてね。 解法 とりあえず、 のビットが立っている場所と同じ場所にしかビットが立っていないものを考えたく…
毎日格上の問題を倒すやつの56日目です。 問題リンク atcoder.jp 問題概要 ゲームのやりすぎで腰を痛めた*1 人の高橋くんたちを、数直線上の の位置にある 個の椅子に座らせようとしてるよ。 ただ、 人目の高橋くんには座標 より左か、座標 より右の椅子に座…
毎日格上の問題を倒すやつの55日目です。 問題リンク atcoder.jp 問題概要 グラフが与えられるよ。 すべての辺を1回ずつ使って三つのサーキットを作れるか判定してね。 解法 明らかにオイラーグラフであることが必要条件です。これはすべての頂点の次数が偶…
毎日格上の問題を倒すやつの54日目です。 問題リンク atcoder.jp 問題概要 頂点のグラフがあるよ。 いくつか辺を取り除いて2つ以下の完全グラフを作るとき、残す辺の本数の最小値を求めてね。 解法 補グラフについて考えると見通しが良くなります。 こうする…
毎日格上の問題を倒すやつの53日目です。*1 コンテストリンク https://kenkoooo.com/atcoder/#/contest/show/172ff02f-aef7-48c8-8f65-0de9b8643797?activeTab=Standings 結果 道案内...45/100(ooo-) ドラゴン2...100/100(ooo) 防犯ゲート...12/100(oo--) 合…
毎日格上の問題を倒すやつの50日目です。*1 問題リンク*2 atcoder.jp 問題概要 人の子供がいるよ。 人目のはしゃぎ度を 、 人目に配るキャンディーの量を として、幼稚園の活発度を とするよ。 人目のはしゃぎ度が から を動き、 個のキャンディーを配るとき…
毎日格上の問題を倒すやつの49日目です。*1 問題リンク*2 atcoder.jp 問題概要 頂点の木のうち、すべての頂点の次数が に含まれているようなものの個数を で割った余りを求めてね。 解法 2日前にやった次数制限付きケイリーの公式を利用します。 同じように…
毎日格上の問題を倒すやつの48日目です。*1 問題リンク atcoder.jp 問題概要 長さ の数列 が与えられるよ。 和が 以下のすべての数列 に対して、 を求めて、その総和を で割った余りを求めてね。 解法 負の二項定理を使って解くのが簡潔です。 これは、 とい…
毎日格上の問題を倒すやつの47日目です。 もとい、FPSウィークの2日目です。飽きたら終わります。*1 問題リンク atcoder.jp 問題概要 個の部品があって、 番目の部品には 個の穴があるよ。これらの穴は区別できるよ。 また、 個の接続用部品があるよ。 これ…
毎日格上の問題を倒すやつの44日目です。 問題リンク atcoder.jp 問題概要 以下の条件をすべて満たす整数の組を考えるよ。 あり得るすべての組に対して、 の総和を求めてね。 解法 以下の記事にFPSの基礎が詳しく載っています。 私もこれを参考に解いたので…
毎日格上の問題を倒すやつの43日目です。 問題リンク atcoder.jp 問題概要 数列が与えられるよ。 選んだ2数の積が立方数にならないように最大限選んだときの個数を求めてね。 解説 明らかに筋が悪いですがG - Cubic?みたいな感じで解きます。 数を素因数ごと…
毎日格上の問題を倒すやつの42日目です。 問題リンク atcoder.jp 問題概要 本の木があるよ。 ある木を伐採するコストは、その木と両端の木の高さの合計だよ。 コストの最小値を達成する伐採方法の数を で割った余りを求めてね。 解法 となりあわせになってい…
毎日格上の問題を倒すやつの41日目です。 問題リンク atcoder.jp 問題概要 グラフが与えられるよ。 指定された辺はちょうど1回、それ以外は何回でも通っていいような経路が存在するか判定してね。 解法 何回でも通っていい辺がごちゃごちゃしていると見通し…
毎日格上の問題を倒すやつの40日目です。 問題リンク atcoder.jp 問題概要 横 マスのグリッドがあり、それぞれ数字が書かれてるよ。はじめ、カエルが マス目にいるよ。 を決めて、「 歩進んで 歩下がる」ことを繰り返すよ。 同じマスに2度立ち入るか、範囲か…
毎日格上の問題を倒すやつの39日目です。 これはこどふぉバチャになるので、必ずしも「格上の問題を倒す」ではない気がしますが。 コンテストリンク codeforces.com 結果 AB2完・Score1236・Perf1890相当 A...00:13 B...01:14(+1) D...(-4) うーん[バーチャ…
毎日格上の問題を倒すやつの37日目です。 問題リンク atcoder.jp 問題概要 頂点 辺のグラフがあるよ。 はじめ、王様が頂点 にいるよ。長さ の数列 を決めて、 回以下の行動を繰り返すよ。 今いる頂点から頂点 の向きに辺を張り、 に移動する このとき、どの…
毎日格上の問題を倒すやつの36日目です。 問題リンク atcoder.jp 問題概要 木が与えられるよ。 すべてのパス について、 と のLCAの最大値を類似度として、これを最小にする順列 を構築してね。 解法 明らかに、類似度を0にすることは不可能です。*1 そのた…
毎日格上の問題を倒すやつの35日目です。 問題リンク atcoder.jp 問題概要 草が 本あって、 番目の草の高さは だよ。 高橋くんは、以下のようにして草を全部抜くよ。 を残っている草の中で最も高い草の高さとして、 より高い高さの草を一斉に抜く 青木くんは…
毎日格上の問題を倒すやつの34日目です。 問題リンク atcoder.jp 問題概要 長さ の数列 と が与えられるよ。 長さ の全ての順列 に対して、 の総和を求めてね。 解法 見た目が見た目ですが、DPできます。 大きい順に見て行った時、 番目で余りをとる場合、か…
毎日格上の問題を倒すやつの33日目です。 問題リンク atcoder.jp 問題概要 「数列 を 回シフトしてから一様に をxorしたら に一致する」ような の組をすべて求めてね。 解法 いつものbitごとに考えるあれです。 各bitごとにみると、シフトはローリングハッシ…
毎日格上の問題を倒すやつの23日目です。 問題リンク atcoder.jp 問題概要 「所属大学も得意分野も異なる 人の強さの合計の最大値」をありえるすべての に対して求めてね。1 解法 いわゆる重み付き二部マッチングです。 コストを負にして最小費用流をしたい…
毎日格上の問題を倒すやつの22日目です。 問題リンク atcoder.jp 問題概要 集合の列に対して、隣り合う要素で片方にしかないものがちょうど1つであるものを、「素晴らしい整数の列」とするよ。 また、「素晴らしい整数の列」のスコアを、 を含む集合の個数を…
毎日格上の問題を倒すやつの21日目1です。 初めての橙後半の難問です。 問題リンク atcoder.jp 問題概要 以下の条件をすべて満たす の組の数を で割ったあまりを求めてね。 解法 とします。 重要な事実として、以下が成り立ちます。2 このとき、累積和の考え…
毎日格上の問題を倒すやつの20日目です。1 問題リンク atcoder.jp 問題概要 無向グラフが与えられるよ。 頂点 から行ける頂点数が になるように辺に向きをつけてね。 解法 から に辺を張るとき、明らかに から行ける頂点は から行ける頂点数以上です。 その…
毎日格上の問題を倒すやつの19日目です。 問題リンク atcoder.jp 問題概要 スケート場があって、何マスかにとどまれるよ。 どのマスからでもすべてのマスに行けるように、とどまれるマスを増やしたいよ。 増やすマスの最小値を求めてね。 解法 からすべての…
毎日格上の問題を倒すやつの16日目です。 問題リンク atcoder.jp 問題概要 個の飴があるよ。 「この中から 個選んだ時の種類数の期待値」をすべての に対して求めてね。 解法 主客転倒テクです。 個ある飴を選ぶ確率を全部に関して足せば期待値になります。1…
毎日格上の問題を倒すやつの15日目です。 問題リンク atcoder.jp 問題概要 一辺が の正 角形に白黒の石を置くとき、すべての辺の黒い石の数が同じ置き方の数を で割ったあまりを求めてね。 解法 一辺に置く黒石の数を決め打つ余裕はありますが、愚直なDPで計…
毎日格上の問題を倒すやつの14日目です。1 問題リンク atcoder.jp 問題概要 人でリーグ戦をするよ。 すでに何戦かは終わらせてるから、このあと単独優勝する可能性がある人を列挙してね。 解法 が小さいため、多項式時間なら割と何でも間に合います。 なので…