AtCoder Beginner Contest 300 参加記

AtCoderさん300回目のABCおめでとうございます！

前回前々回とDDoS攻撃でunratedになって水色復帰を阻止されましたが、無事に水色復帰しました。

問題文なが！「頂点」の意味が分からず質問を投げました

とりあえず×印同士はくっつかないっていう認識でよさそうなので、すなおにDFSをして×印を1つずつ数えていく感じでなんとかします

本番ACコード

3つ選ぶやつは真ん中決め打ちしとけばなんとかなるのお気持ちで見ます

数式をこねこねすると考える素数の範囲は300000以下で十分そうなのでエラトステネスの篩で300000以下の素数とその2乗の値を前計算します、この時点で素数がだいたい25000個くらいと分かったのでaとbを全探索して間に合いそうの気持ちになります

そうなるとcは2乗した値から二分探索で求められて解けます

本番ACコード

これはもっと早く解けるべきでした

問題文を見てとりあえずNが2,3,5以外の素因数を持っていれば明らかに不可能なので0でよくて、それ以外は「2,3,5を何回出したか」を状態としてこねこねすればよさそうというところまでは分かります

で、ここからグダグダと通り数を数えようとしたり確率をO(1)で求めようとしたり迷走して20分くらい溶かします

そして「こういうのもなんかDPで解けるんだっけ」というのをふんわり過去の問題から思い出し（何の問題だったかな…）、ふんわりDPを書くもサンプルが合わなくて30分溶かします

ここで1回丁寧に遷移式を書きます、

N=2^a * 3^b * 5^cとして、

dp[i][j][k] := 2をi回、3をj回、5をk回出す確率（mod 998244353）

dp[a][b][c] = 1とすると、

dp[i][j][k] = (dp[i][j][k]+dp[i+1][j][k]+dp[i][j+1][k]+dp[i+2][j][k]+dp[i][j][k+1]+dp[i+1][j+1][k])/6

なので、右辺のdp[i][j][k]を左辺に持ってきて整理すると

dp[i][j][k] = (dp[i+1][j][k]+dp[i][j+1][k]+dp[i+2][j][k]+dp[i][j][k+1]+dp[i+1][j+1][k])/5

となります。ここで5で割るところをずっと6で割っていたのでサンプルが合わないことに気付き、5で割るとサンプルが通り、無事ACできました

DPの遷移式は丁寧に書きましょう

ちなみにN≤10^18ですがこれは2^70よりは小さいので、DPテーブルは70*70*70のサイズを取っておけば十分です

本番ACコード

F以降は見てないです