AtCoder Beginner Contest 180 F - Unbranched
各連結成分のサイズの最大値がちょうどという条件なので、最大値が以下の場合の数から最大値が以下の場合の数を引くことを考える。
を「サイズ以下の連結成分の集合で、頂点数が個、辺の数が本であるときの場合の数」とする。これに個の残りの頂点から点を追加していく遷移を考える。頂点の次数が2以下であるということは、各連結成分はループまたはパスになっている。そのため、素直に考えると個の点を新たに追加するときはパスの場合、ループの場合となる(ただし、の場合は別に考える)。しかし、この方針だと連結成分同士の順列の分の重複を考える必要が出てくるため、dpの状態として連結成分の状態を保つ必要があり、とかになってしまう。
そのため、個の新規に追加する頂点のうち1個は残りの頂点のうち最小のインデックスを持つ頂点にする、という制約を加える(他の頂点はなんでもよい)。すると連結成分同士の順列を考えなくて良くなる。この場合、パスの場合、ループの場合となる(同様にの場合は別に考える)。これは素直に書くとになり間に合う。
HHKB プログラミングコンテスト 2020 E - Lamps
よくある典型問題。あるマス目についてカウントされる回数を数える方法を考える。すると、そのマス目から上下左右に行った所に1個でもライトがあればそのマス目がカウントされるということがわかる。素直にマスごとに上下左右の散らかってないマス目をカウントして行くと とかになってしまうが、一つ隣のマスを使うDPみたいなことをすることでで数えられる。マス における上下左右に散らかってない連続したマスの数を、全体の散らかってないマスをとしたとき、そのマスは 回カウントされる。これを行と列で総和を取れば良い。計算量は
HHKB プログラミングコンテスト 2020 D - Squares
400点にしては難しいと感じた問題だった。
まず上下左右の自由度は独立して考えられること、及び全体から重なっている場合の組み合わせを引けば良いことに気づくのが重要。X軸方向にA, Bが重なっているとき、AとBの重なる幅 について全探索することを考えると、 のときはAまたはBの大きいほうが小さい方を完全に含んでおり、そうでないときは重なり方が2通りしかないことがわかる。いずれも幅 の間で動かせる範囲だけ自由度があるので結局いずれの場合もの一次式で表されることがわかる。この一次式の和なので、結局等差数列の公式を使って で計算できる。
あとはY軸方向は結局X軸と同じなので平方をとってやり、AとBのあり得るパターン全てから引けばよい。全体でも (テストケースの数は除く)。
TopCoder SRM789 Div1 ThreeDigits
int32の範囲のが与えられる。 の商の下位3桁及び小数点以下の上位3桁を求めよ。
問題では0埋めするとかしないとか余計な考察がついてるので若干あれだが、問題の本質はこんな感じ。小数点以下の上位三桁はなるPを計算してやり、を切り捨てればよい。問題は商の下位3桁だが、これはを計算すると良い。kmjp氏のブログ を参考にした。
TopCoder SRM 789: Div1 Easy Div2 Hard ThreeDigits - kmjp's blog
なぜかというと、と表したとき、となり、ここでなので、 かつであるから、はの下位3桁となっているのである。Pの定義よりこれは整数となるため、これが答え。
AtCoder Regular Contest 066 D - Xor Sum
今更書くまでもない超有名問題だけどかなり手こずったのでメモ。基本的に系は和ととても相性が悪い。
問題の性質を考えると、 を満たすとき、常に であるため、 だけ考えればよい。また、足し算の有名な言い換えがあります。これはつまり、とのbitごとの交換に関して不変です。つまり、との各bitはの3通りだけ考えれば良いです。
を上からi ビット目まで見たときに、だけより小さい場合の組み合わせ数と定義します。このとき、が2以上の場合は、i+1ビット目について、 となるため、例え今見ているビットがで、のビットがだったとしても以上より小さいことは確定します。そのため、は状態としての3通りだけ見るdpを考えればよいです。
なぜこんなdpが思いつくかというと、足し算の繰り上がりによりNを超えるギリギリの線を覚えておく、みたいな感覚になります。ここがちょっと難しいですが繰り上がり系のdpが出てきたときにはこの感覚を覚えておきたいです。
dpの遷移としては、をNのiビット目(0または1)と定義すると、 などとなります。
計算量は
AtCoder Regular Contest 092 D - Two Sequences
数列 が与えられるので、 のすべてのxorを求めよという問題。解法は愚直にやればよいので、 程度の解法を求める必要がある。
xorの値を求める問題はbitごとに独立して行うというのが鉄則。そこで下位bitから求めていこう。最下位ビットはの偶奇で4パターンに分かれるが、そのうち2パターンの数が奇数なら1、偶数なら0になることがわかる。上位bitも同じようにやりたいが、足し算なので繰り上がりが発生する。一般にxorの問題は足し算と組み合わせた瞬間難易度が跳ね上がる。
そこで を順次考えていく。これは直感的にいうと上位ビットを徐々に0に落としていくイメージである。するとk bit目が1になる条件は の上位ビットが11または01であればよいため、例えば をソートしておくことで、 を固定すれば二分探索で組み合わせのパターンを探すことが可能になる。具体的には 及び をカウントすればよい。
計算量は とやや重いが、制限時間3秒なので間に合う。