📚

AtCoder Beginner Contest ABC408 解法メモ

2025/06/02に公開

Nim

AtCoder

tech

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

ABC408

ABC408A - Timeout

解法

$T$ の初項に $0$ を加え、 $i$ が1..Nのすべての項で
T[it]<=T[it-1]+SだったらYes、
そうでなけれはNoと出力すればよい
ACコード

メモ

$Ti$ が次の肩叩きまでの「間の時間」と誤読した

ABC408B - Compression

解法

$A$ をHashSetにしてからSeqに戻して、Sortすればよい
ACコード

メモ

A.sorted.deduplicateでもよい
ACコード

ABC408C - Not All Covered

解法

各城壁を守っている砲台の数を表す配列 $c$ を作れば、答えは、その配列の最小値となる
それには、逆に、各砲台の守る城壁の範囲にある各 $ci$ をカウントアップしていけばよく、
計算量を勘案すれば、
c[L]+=1; c[R+1]-=1
としてから、累積和をとるimos法を用いるとよい
ACコード

目標となる状態は、「 $0$ のかたまり」＋「 $1$ のかたまり」＋「 $0$ のかたまり」である
dp[先頭からi番目まで][どのかたまりにいるか]=変更しなければならない文字の数
とするDPを考えれば、
dp[0][0]=S[0]; dp[0][1]=1-S[0]を初期値に、
dp[i][0]=dp[i-1][0]+S[i]
dp[i][1]=min(dp[i-1][0]+1-S[i],dp[i-1][1]+1-S[i])
dp[i][2]=min(dp[i-1][1]+S[i],dp[i-1][2]+S[i])
と遷移させればよい
dp[^1].minが答え
ACコード

メモ

しばらく問題意図が全くわからなかった
題意からランレングス圧縮、制約から尺取り法を疑うも不能だった

ABC408E - Minimum OR Path

解法

すべての $wi$ のorを最小にするための経路とは、 $2$ 進数にして考えれば、
（左のビットがそれより右のビットに関係なく大小関係を左右するので）全 $wi$ の $30$ 桁目のorを可能なら $0$ にする（避けられなければ $1$ とする）経路のうち、 $29$ 桁目のorを可能なら $0$ にする経路のうち、と順番に $1$ 桁目まで狭めていった経路であるはずで、
そのときの各桁の結論（ $0$ にできれば $0$ 、そうでなければ $1$ ）を合わせたものが求める答えである
辺の採否を記録する配列を用意し、
$i$ を29..0としながら、
いちいちwi shr i and 1を重みとしたダイクストラをして各桁を決めていく
$0$ だった場合、 $wi$ の当該ビットが $1$ の辺は以降使わないため、不使用のフラグを立てていけばよい
ACコード

メモ

$wi$ の $2$ 進数での各桁は当然bitであるから、ダイクストラでなく、 $0$ のまま $0$ から $N-1$ まで行けるか否かのUnion-Findでもよい
具体的には、（未確定の桁は判断に入れないためにすべて $1$ にすべく）a=2^30-1を初期値に、
$i$ を29..0としながら、いちいち
一旦、a-=1 shl iにした（注目桁を一旦 $0$ にした）後に、
a or wi==aになれば（これまでの左桁もふまえつつ、注目桁もorをしても $0$ のままであれば） $u$ と $v$ をmergeする処理を全辺に対して行い、
結果、 $0$ と $N-1$ がsameでなければ（ $0$ のまま $0$ から $N-1$ まで行けないのであれば）、改めてa+=1 shl iとしていけばよい
最後の $a$ が答えとなる
ACコード

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