💬

AtCoder Beginner Contest ABC426 解法メモ

2025/10/06に公開

Nim

AtCoder

tech

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

ABC426

ABC426A - OS Versions

解法

"Ocelot", "Serval", "Lynx"を配列とし、
$X$ 、 $Y$ それぞれをfindして比較すればよい
ACコード

ABC426B - The Odd One Out

解法

$S$ のCountTableをとり、
valueが $1$ のkeyを答えればよい
ACコード

メモ

Yes、Noだけと思い込み、toCountTableなどを始めてしまった

$Xi$ 以下の台数合計が計算できれば、 $Yi$ の台数に足し合わせることを繰り返していけばよい
次の $Xi$ 以下の台数合計の計算の際には、これまでの $Xi$ の最高値 $m$ 以下のバージョンは存在しないことを考えれば、
（ $m$ 以下の部分は無視して） $m$ より大きく、 $Xi$ 以下の台数の合計を計算して答え、それを $Yi$ に足していけばよい（ $Xi$ が $m$ 以下なら当然 $0$ 台）
これはフェニック木 $f$ を使えば簡単で、初めのバージョンの台数と合わせて
a=Xi-m+f[m+1..Xi]
として $a$ を出力し、
f.add(Yi,a)
とすればよい
ACコード

メモ

バージョンは $Xi$ の最高値 $m$ を下限に上がっていくだけなので、単純にシミュレートしたところでTLEにはならない
ACコード

ABC426D - Pop and Insert

解法

$S$ をいくつかの $0$ と $1$ の塊が続いている状態と捉え直す
仮に、すべてを $0$ にしようとした場合、
操作が可能な両端に1の塊があれば、操作によって、既存の $0$ の塊と合体することができる
一方、両端に $0$ の塊があった場合、操作によって、既存の $1$ の塊と合体することができ、その後、いつかその塊が端に来た際に、改めて操作によって他の $0$ の塊と合体することができる、すなわち、 $2$ 回の操作が必要とわかる
合体先となる $0$ の塊はどれでもよく、その塊には操作が不要なので、最も長い塊を選んで、それに合体していけばよい
つまり、ランレングス圧縮して、
すべて $0$ にしようとして、（ $1$ の塊の長さ合計） $\times 1$ ＋（ $0$ の $2$ 番目に長い塊以降の長さ合計） $\times 2$
と、
すべて $1$ にしようとして、（ $0$ の塊の長さ合計） $\times 1$ ＋（ $1$ の $2$ 番目に長い塊以降の長さ合計） $\times 2$
の、小さな方が答え
この考え方は、そもそも $1$ 種類しかなかったり、各々 $1$ 塊ずつしかないといったケースでも一般性を失わない
ACコード

メモ

なぜか初めに「中央」にこだわってしまい、中央から左右端に向けて $1$ 個か $2$ 個ずつ足していけばよい、と誤認してしまった

ABC426E - Closest Moment

解法

各スタート地点からの $t$ 秒後の位置を算出し、その $2$ 点間の距離を $t$ で表せるようにした上で、三分探索すればよい
ただし、どちらかがゴールに到達して停止してしまうことで、 $t$ の推移による $2$ 点間の距離は極小点が $1$ つになるとはいえなくなる
よって、「スタートからどちらかがゴールするまで」と、
「そこから両方がゴールするまで」に時間を分け、
各々で三分探索して最小値を求め、その $2$ つの最小値を答えればよい
ACコード

メモ

片方が止まろうと極小値は $1$ つだろうと高を括り、無理に $2$ 点間距離をシミュレートしたが、ほとんどがWAとなった

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