AtCoder Beginner Contest 300 参加記
AtCoderさん300回目のABCおめでとうございます！
前回前々回とDDoS攻撃でunratedになって水色復帰を阻止されましたが、無事に水色復帰しました。
C - Cross
問題文なが！「頂点」の意味が分からず質問を投げました
とりあえず×印同士はくっつかないっていう認識でよさそうなので、すなおにDFSをして×印を1つずつ数えていく感じでなんとかします
本番ACコード
D - AABCC
3つ選ぶやつは真ん中決め打ちしとけばなんとかなるのお気持ちで見ます
数式をこねこねすると考える素数の範囲は300000以下で十分そうなのでエラトステネスの篩で300000以下の素数とその2乗の値を前計算します、この時点で素数がだいたい25000個くらいと分かったのでaとbを全探索して間に合いそうの気持ちになります
そうなるとcは2乗した値から二分探索で求められて解けます
本番ACコード
E - Dice Product 3
これはもっと早く解けるべきでした
問題文を見てとりあえず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以降は見てないです
AtCoder Beginner Contest 250 参加記
三連続で冷えてるのでいい加減温まりたいな～って思ってたら少し温まりました
本番では4完1491位、パフォーマンス1220でした
C - Adjacent Swaps
右端のボールは左端と交換してよ
N,Qどちらも2×10⁵以下なので愚直にシミュレーションで良さそう、ちょっと実装が面倒
本番では「整数iのボールがある場所」と「左からi番目にあるボールの整数」の2つの配列を持ってこねくり回した。
本番ACコード
D - 250-like Number
p×q³≤10¹⁸であることを考えるとp,qとして考えられる素数は10⁶までを考えておけば十分っぽい感じがするので、まずは10⁶までの素数を列挙しておく
こういう「数式と制約から新たな制約範囲を考える」手法、ABC246 - Dで学んだのが役に立ってる（よく見たらどっちの問題も物理好きさんWriterじゃん）
コンテスト直後のTLではpを決め打ちしてqを二分探索する解法しか流れてこなかったけど（そんな解法思いついてないけど？）、素数定理より10⁶以下の素数の個数は17万未満（実際は78000程度）なので全探索で間に合うんですよね
本番ACコード
余談：最初100万までの素数を埋め込もうとしたらAtCoderに怒られました（それはそう）
E - Prefix Equality (本番未AC)
実行時間制限が4秒だということにコンテストが終わってから気付きました
2WAで分からん～ってなってたけど方針は合ってたみたいで、setを3つくらい使って集合を比較する方法でやってた、んですがクエリを何故かソートして先頭から処理すればええやん！という思考に至りWAと。（xで昇順ソートしましたが、x_i < x_(i+1)のときにy_i > y_(i+1)だと破滅します）
総評
E、勿体ね～のお気持ち（Dまで50分なので十分時間はあった上に基本的方針は合っていたので）あとはDも実装に時間かかりすぎ（34分）ですね（最初OEISでググったらなんかヒットしたのでそれに食いついたのが明らかにロス）
まあ温まったので良いです、また頑張ります
