atcoder.jp 各連結成分のサイズの最大値がちょうどという条件なので、最大値が以下の場合の数から最大値が以下の場合の数を引くことを考える。 を「サイズ以下の連結成分の集合で、頂点数が個、辺の数が本であるときの場合の数」とする。これに個の残りの頂…

atcoder.jp よくある典型問題。あるマス目についてカウントされる回数を数える方法を考える。すると、そのマス目から上下左右に行った所に1個でもライトがあればそのマス目がカウントされるということがわかる。素直にマスごとに上下左右の散らかってないマ…

atcoder.jp 400点にしては難しいと感じた問題だった。 まず上下左右の自由度は独立して考えられること、及び全体から重なっている場合の組み合わせを引けば良いことに気づくのが重要。X軸方向にA, Bが重なっているとき、AとBの重なる幅 について全探索するこ…

community.topcoder.com int32の範囲のが与えられる。 の商の下位3桁及び小数点以下の上位3桁を求めよ。 問題では0埋めするとかしないとか余計な考察がついてるので若干あれだが、問題の本質はこんな感じ。小数点以下の上位三桁はなるPを計算してやり、を切…

atcoder.jp 今更書くまでもない超有名問題だけどかなり手こずったのでメモ。基本的に系は和ととても相性が悪い。 問題の性質を考えると、 を満たすとき、常に であるため、 だけ考えればよい。また、足し算の有名な言い換えがあります。これはつまり、とのbi…

atcoder.jp 数列 が与えられるので、 のすべてのxorを求めよという問題。解法は愚直にやればよいので、 程度の解法を求める必要がある。 xorの値を求める問題はbitごとに独立して行うというのが鉄則。そこで下位bitから求めていこう。最下位ビットはの偶奇で…

atcoder.jp が与えられるので、 を求めるというシンプルな問題。はいずれもからを動くとしてよい。(tex: i = j]のときは簡単に計算できるので、後から引けばよい) 一般に、 という形式の値を求める場合、 が間に合わないなら、 の形にしたいなと思うのが定石…

atcoder.jp 1,2,3->0,1,2と読み替えて良い。(N>=2、かつ2段目以降は+1分が相殺されるため) こういう問題はまずは偶奇を見る。 するとパスカルの三角形的に考えて、Σ n-1Ck a[k] の偶奇であることがわかる。これが奇数なら答えは1であることが確定する。 次に…

yukicoder.me ちょっと複雑な累積和。次のような状況を想定する。 [左の荷物群の初期位置] 運びたい位置X [右の荷物の初期位置] 累積和を取ることで、「左の荷物群をその荷物群の中での右端まで異動するためのコスト」のテーブルが構成できる。 あとは「左の…

yukicoder.me ダブリングの練習。 まず「次の場所 % n」の値をダブリングテーブルを前処理しておく。 for (int i = 1; i < m; i ++) { for (int j = 0; j < n ; J++) { table[i][j] = table[i-1][table[i-1][j]] } } ダブリングテーブル自体はこんな感じで更…

atcoder.jp 二次元のある長方形領域 (r1≦y≦r2, c1≦x≦c2) の中の yCx の和を計算する問題。 とりあえず2次元の中の何かの和を考えるときは、包除原理を使うことにより 0≦y<≦r, 0≦x≦c で計算するルーチンを書いておき、あとから余計な部分を引くのが定石。 で…

atcoder.jp 桁DPの典型的な問題。非常にNの大きい問題で、N以下で条件を満たすものの数を数えよ、という場合はだいたい桁DPでやるのがよい。 DPは上位の桁(文字列でIndex 0の文字)から見て、状態として「ある桁まで見たとき、0以外の数がK個」「ある桁まで見…

atcoder.jp 構築ゲーなので「こうすればいい」ではなく発想法をメモ。 まず2でも5でも連結サイズが小さいことに着目する。HやWが大きい場合、例えば角や辺以外に2を配置するとその周囲8マスには2が1個しか置けないことから残りが5であることが確定する。する…