アルゴリズム忘備録

競技プログラミングとかデータ分析とか

AtCoder Beginner Contest 180 F - Unbranched

atcoder.jp

 

各連結成分のサイズの最大値がちょうどLという条件なので、最大値がL以下の場合の数から最大値がL-1以下の場合の数を引くことを考える。

dp_L[n][m] を「サイズ L以下の連結成分の集合で、頂点数が n個、辺の数が m本であるときの場合の数」とする。これに N-n個の残りの頂点から点を追加していく遷移を考える。頂点の次数が2以下であるということは、各連結成分はループまたはパスになっている。そのため、素直に考えるとk個の点を新たに追加するときはパスの場合C(N-n, k) * k! / 2、ループの場合C(N-n, k) * (k-1)! / 2となる（ただし、k=2の場合は別に考える）。しかし、この方針だと連結成分同士の順列の分の重複を考える必要が出てくるため、dpの状態として連結成分の状態を保つ必要があり、O(LMN^2)とかになってしまう。

そのため、k個の新規に追加する頂点のうち1個は残りの頂点のうち最小のインデックスを持つ頂点にする、という制約を加える（他の頂点はなんでもよい）。すると連結成分同士の順列を考えなくて良くなる。この場合、パスの場合C(N-n-1, k-1) * k! / 2、ループの場合C(N-n-1, k-1) * (k-1)! / 2となる（同様にk=2の場合は別に考える）。これは素直に書くとO(NML)になり間に合う。

HHKB プログラミングコンテスト 2020 E - Lamps

atcoder.jp

 

よくある典型問題。あるマス目についてカウントされる回数を数える方法を考える。すると、そのマス目から上下左右に行った所に1個でもライトがあればそのマス目がカウントされるということがわかる。素直にマスごとに上下左右の散らかってないマス目をカウントして行くと O(HW \max(H, W)) とかになってしまうが、一つ隣のマスを使うDPみたいなことをすることで O(HW)で数えられる。マス (i, j) における上下左右に散らかってない連続したマスの数を a_{i, j}、全体の散らかってないマスを totalとしたとき、そのマスは (2^{a_{i, j}} - 1) * 2^{total - a_{i, j}} 回カウントされる。これを行と列で総和を取れば良い。計算量は O(HW) 

HHKB プログラミングコンテスト 2020 D - Squares

atcoder.jp

 

400点にしては難しいと感じた問題だった。

まず上下左右の自由度は独立して考えられること、及び全体から重なっている場合の組み合わせを引けば良いことに気づくのが重要。X軸方向にA, Bが重なっているとき、AとBの重なる幅 K (1 \le K \le \min(A,B)) について全探索することを考えると、 K = min(A, B) のときはAまたはBの大きいほうが小さい方を完全に含んでおり、そうでないときは重なり方が2通りしかないことがわかる。いずれも幅 N の間で動かせる範囲だけ自由度があるので結局いずれの場合も Kの一次式で表されることがわかる。この一次式の和なので、結局等差数列の公式を使ってO(1) で計算できる。

 

あとはY軸方向は結局X軸と同じなので平方をとってやり、AとBのあり得るパターン全てから引けばよい。全体でもO(1) (テストケースの数は除く)。

TopCoder SRM789 Div1 ThreeDigits

community.topcoder.com

 

int32の範囲の X, Y, Zが与えられる。 X^Y/Z の商の下位3桁及び小数点以下の上位3桁を求めよ。

 

問題では0埋めするとかしないとか余計な考察がついてるので若干あれだが、問題の本質はこんな感じ。小数点以下の上位三桁は P=X^Y \bmod ZなるPを計算してやり、1000P / Zを切り捨てればよい。問題は商の下位3桁だが、これは X^Y \bmod 1000Zを計算すると良い。kmjp氏のブログ を参考にした。

TopCoder SRM 789: Div1 Easy Div2 Hard ThreeDigits - kmjp's blog

 

なぜかというと、 Q * 1000Z + P' = X^Y - Pと表したとき、Q*1000 + P'/Z = (X^Y-P)/Zとなり、ここで P' ＜ 1000Zなので、 P'/Z ＜ 1000 かつ Q*1000 \bmod 1000 = 0であるから、P/Zは(X^Y-P)/Zの下位3桁となっているのである。Pの定義よりこれは整数となるため、これが答え。

AtCoder Regular Contest 066 D - Xor Sum

atcoder.jp

 

今更書くまでもない超有名問題だけどかなり手こずったのでメモ。基本的に xor系は和ととても相性が悪い。

 

問題の性質を考えると、 a \oplus b = u, a + b = v を満たすとき、常に u \le v であるため、 v \le N だけ考えればよい。また、足し算の有名な言い換え a + b = a \oplus b + a \ and \ b * 2があります。これはつまり、aとbのbitごとの交換に関して不変です。つまり、aとbの各bitは(0, 0), (0, 1), (1, 1)の3通りだけ考えれば良いです。

  

dp[i][s] を上からi ビット目まで見たときに、 s * 2^iだけNより小さい場合の組み合わせ数と定義します。このとき、sが2以上の場合は、i+1ビット目について、 s * 2^{i+1} \ge 4*2^i となるため、例え今見ているビットが (1,1)で、Nのビットが0だったとしても 2*2^i以上Nより小さいことは確定します。そのため、sは状態として0,1,2の3通りだけ見るdpを考えればよいです。

 

なぜこんなdpが思いつくかというと、足し算の繰り上がりによりNを超えるギリギリの線を覚えておく、みたいな感覚になります。ここがちょっと難しいですが繰り上がり系のdpが出てきたときにはこの感覚を覚えておきたいです。

 

dpの遷移としては、N[i]をNのiビット目(0または1)と定義すると、 dp[i][min(2, 2s + N[i] -(a[i] + b[i]) ] += dp[i][j] などとなります。

 

計算量は O(\log_2 N)

AtCoder Regular Contest 092 D - Two Sequences

atcoder.jp

 

数列 a_i, b_i (1 \le i \le n) が与えられるので、 a_i + b_j (1 \le i, j \le n) のすべてのxorを求めよという問題。 O(n^2)解法は愚直にやればよいので、 O(n \log{n}) 程度の解法を求める必要がある。

 

xorの値を求める問題はbitごとに独立して行うというのが鉄則。そこで下位bitから求めていこう。最下位ビットは a_i, b_i (1 \le i \le n)の偶奇で4パターンに分かれるが、そのうち2パターンの数が奇数なら1、偶数なら0になることがわかる。上位bitも同じようにやりたいが、足し算なので繰り上がりが発生する。一般にxorの問題は足し算と組み合わせた瞬間難易度が跳ね上がる。

 

そこで a_i, b_i \mod 2^k (k=1,2,...,28) を順次考えていく。これは直感的にいうと上位ビットを徐々に0に落としていくイメージである。するとk bit目が1になる条件は (a_i \mod 2^k) + (b_j \mod 2^k) の上位ビットが11または01であればよいため、例えば b_i \mod 2^k をソートしておくことで、 a_i を固定すれば二分探索で組み合わせのパターンを探すことが可能になる。具体的には  2^{k-1} - (a_i \mod 2^k) \le b_j \le 2^k - (a_i \mod 2^k) - 1  及び   (2^k + 2^{k-1})  - (a_i \mod 2^k) \le b_j をカウントすればよい。

 

計算量は O(n \log{n} \log{n}) とやや重いが、制限時間3秒なので間に合う。

AtCoder Grand Contest 038 C - LCMs

 
A_iが与えられるので、 \sum lcm(A_i, A_j) を求めるというシンプルな問題。 i, jはいずれも1からnを動くとしてよい。(tex: i = j]のときは簡単に計算できるので、後から引けばよい)
 
一般に、 \sum c_{i,j} A_i A_j という形式の値を求める場合、 O(N^2) が間に合わないなら、 (\Sigma A_i) (\Sigma A_j) の形にしたいなと思うのが定石である。
 
まず考えることとしては lcm(A_i, A_j) = A_i * A_j / gcd(A_i, A_j) であろう。一般に最小公倍数よりも最大公約数のほうが考えやすい(気がしている)。
 
そこで、与えられた式を \sum_d f(d) \sum_{d|A_i, d|A_j} A_i A_j = \sum_d f(d) (\sum_{d|A_i)} A_i)^2 という形に表す、ということを考えよう。(この発想は解説を見た)
 
すると A_i A_jの係数(元の式では \frac{1}{gcd(A_i, A_j)} )に着目すると、 \frac{1}{gcd(A_i, A_j)} = \sum_{d|A_i, d|A_j} f(d) = \sum_{d|gcd(A_i, A_j)} f(d) であるため、結局 X = \sum_{d|X} f(d) を求めれば良いことがわかった。
 
この値であるが、これはいわゆる約数メビウス変換という式になっている。すべての X (1 \le X \le \max{A_i}) に対して約数列挙して f(d)を求めることも可能といえば可能だが、定数倍高速化を頑張らないと無理であろう。ということで高速約数メビウス変換を使うことで時間内に収まる。この計算量は \max{A_i}=Mとおくと、O(M \log{\log{M}})だそうである。(詳しくは証明したことはない)
 
 
残るは \sum_{d|A_i} A_i の計算であるが、これはまず c_y = |\{A_i | A_i = y\}| という値がyであるような A_iの数というものを計算しておこう。すると \sum_{d|A_i} A_i = \sum_{y=d, 2d, 3d,...} c_y * y と計算できる。これをすべてのdについて計算するには、 O(M \log{M})で計算できる。
 
 問題設定はシンプルなのに式変形が高速ゼータ/メビウス変換の勉強になるという良問。