🍣

AtCoder Beginner Contest ABC412 解法メモ

2025/10/09に公開

Nim

AtCoder

tech

文中で使用しているのは、PythonライクでAtCoderに最適な言語の1つNimです

ABC412

ABC412A - Task Failed Successfully

解法

(0..<N).toSeq.countIt(Ai<Bi)
ACコード

ABC412B - Precondition

解法

(1..<S.len).toSeq.allIt(S[it].isLowerAscii or (S[it].isUpperAscii and S[it-1] in T))
評価は $2$ 文字目から行えばよい
ACコード

着目しているドミノで最後のドミノが倒せるかを判定、
駄目なら、着目しているドミノの大きさの倍以下で最大の大きさのドミノを貪欲に選択し続けていけばよい
間にある $N-2$ 個のドミノの大きさをソートした配列を $s$ とする
着目するドミノの大きさをhとし、初期値として左端のドミノの大きさS[0]とする
答えである使うドミノの個数を $a$ とし、初期値を左端分の $1$ とする
以下を繰り返していけばよい
・h*2>=S[^1]であれば、右端のドミノ分の $1$ を足して答えである $a+1$ を出力して終了
・次のドミノs[i]（ $2$ 番目からなので）が $h\times 2$ より大きくて倒せないか、（ $i=N-2$ となって） $s$ を最後までみてしまった（それなのに右端のドミノが倒れなかった）ときは、 $-1$ を出力して終了
・ $i$ を二分探索でs[i..^1].upperBound(h*2)+iに更新する
ACコード

メモ

while内の条件不足で無限ループを作ってTLEしているのに、計算量過多と誤認して無駄な考察を繰り返した
$2^{30}=1073741824>10^9$ ゆえ、ちょうど倍々の大きさのドミノがあれば $30$ 個、最悪でもその間を繋ぐドミノを置けばよいから必要なドミノは高々 $60$ 個程度となる。それゆえ、ソートもせずに、都度都度全てのドミノの大きさを確認して回ったところで、充分に間に合う
ACコード

ABC412D - Make 2-Regular Graph

解法

頂点数が高々 $8$ なので、全ての次数が $2$ の、輪を形作る場合、連結成分（輪）が $1$ つか $2$ つに限られる
その完成形に対して、すべての頂点の組み合わせを列挙し、与えられた辺との差分をとればよい
具体的には、 $1〜N$ のすべての順列に対し、
①最初と最後を繋ぐ（連結成分 $1$ つ）
② $N=6$ なら、 $3$ 番目と $1$ 番目、 $6$ 番目と $4$ 番目を繋ぐ（頂点 $3$ つずつの連結成分 $2$ つ）
② $N=7$ なら、 $3$ 番目と $1$ 番目、 $7$ 番目と $4$ 番目を繋ぐ（頂点 $3$ つと $4$ つの連結成分 $2$ つ）
または、 $4$ 番目と $1$ 番目、 $7$ 番目と $5$ 番目を繋ぐ（頂点 $4$ つと $3$ つの連結成分 $2$ つ）
② $N=8$ なら、 $3$ 番目と $1$ 番目、 $8$ 番目と $4$ 番目を繋ぐ（頂点 $3$ つと $5$ つの連結成分 $2$ つ）
または、 $4$ 番目と $1$ 番目、 $8$ 番目と $5$ 番目を繋ぐ（頂点 $4$ つずつの連結成分 $2$ つ）
または、 $5$ 番目と $1$ 番目、 $8$ 番目と $6$ 番目を繋ぐ（頂点 $5$ つと $3$ つの連結成分 $2$ つ）
の各々の辺の集合 $s$ と、入力で与えられる辺の集合 $e$ に対する、
((e-s)+(s-e)).lenの最小値が答え
ACコード

メモ

グラフでの解決にこだわり過ぎた

ABC412E - LCM Sequence

解法

出力例 $1$ でわかる通り、 $Ai$ は、前項と同じか、大きくなる
同じ、ということは、新たに加わる数がそれまでの素因数分解の組み合わせの範囲内で表現できるということで、逆に増えるタイミングというのは、素因数分解の指数の上限が上がるか、新たな素数が加わるタイミングだといえる
そのタイミングとは、素数冪（ $1$ つの素数の冪乗だけで表される数）が加わるとき、と言えるので（そうでなければそれより手前で出現しているはずだから）、区間内の素数冪の数を求める問題、と言い換えることができる
これはいわゆる区間篩で、通常のエラトステネスの篩同様、
$\sqrt{R}$ までの素数を列挙し、
（ $1$ から $R$ までの配列は大き過ぎて用意できないので）区間の幅である $R-L$ （初項は別に素数冪でなくとも必ず答えの中に入るので $L+1$ から $R$ の間）の要素を持つ配列を用意、
列挙した素数 $p$ それぞれについて、 $p^2$ 以降の $p$ の倍数（つまり合成数）を篩にかけて落としていく（ $p^2$ 未満は、 $p$ より小さい素数の篩にかかる）
もちろん、 $p^2$ が $L+1$ より小さければ、 $L+1$ 以降の $p$ の倍数をみていけばよい
篩にかける際、並行して $p^n$ となる場合をカウントし、篩に残った素数に加えればよい
ACコード

メモ

区間内の素数冪の数を求める問題、との言い換えができない
区間篩という実装の工夫を知らない

反復学習にはmochiがおすすめ
全問入ったdeckはこちら