⛳

AtCoder Beginner Contest ABC424 解法メモ

2025/09/21に公開

Nim

AtCoder

tech

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

ABC424

ABC424A - Isosceles

解法

a==b or b==c or c==aかどうかを判定すればよい
ACコード

メモ

怖くなってa+b<c and b+c<a and c+a<bも入れてしまったが、制約を見れば不要だった

ABC424B - Perfect

解法

制約から、問題番号によらず、各人が正解した回数を数えていき、 $M$ に達した瞬間だけ、答えの数列に加えていけばよい
ACコード

メモ

わざわざ問題別に消し込んで、答えの数列に加える際も、二重計上しないように「まだ答えの数列に入っていないなら」などと回りくどい処理をしていた

ABC424C - New Skill Acquired

解法

有向辺の多始点BFSで、到達できる頂点数が答え
問題文から、 $(Ai,Bi)$ とあれば、 $Ai$ か $Bi$ が習得できれば $i$ が習得できる、
すなわち $Ai\toi$ と $Bi\toi$ に辺を張ればよい
$(0,0)$ の $i$ が各々始点となるので、その $i$ を初めからHeapQueueに入れておけばよい
ACコード

メモ

なぜか早々にUnion-Findと信じ込み、ほとんどの時間を溶かしてしまった
問題文を落ち着いて読めば、いくらでも回避できた

$2 \times2$ の黒マスを避けつつ、塗り替えの最小数を答える、というところから、各行のbitDPを考える
$S$ の各行を、.を $0$ 、#を $1$ に置き換えた $2$ 進数とみる
dp[ $i$ 行目][状態の2進数]=そこまでに必要な塗り替え数
として、
dp[H][1 shl W]で初期値inf、ただしdp[0][S[0]]=0、とした配列を準備、
今の行の全状態 $j$ から、次の行の全状態 $k$ まで、各々の遷移を確認する
遷移としては、 $S[i]$ の $1$ を $0$ に変えるだけで $k$ ができること、状態 $j$ と状態 $k$ で $2 \times2$ の黒マスができていないことを条件に、
dp[i][k]=dp[i-1][j]+( $S[i]$ から $k$ に塗り替えるマスの個数)としていけばよい
dp[^1]の最小値が答え
ACコード

メモ

bitDPなど浮かばない
bitopsの諸関数の使い方がおぼろげ
集合 $a$ 、 $b$ のdifferenceが欲しければ、a and (not b)とすればよい

ABC424E - Cut in Half

解法

長い方から二等分を繰り返す、
つまり、進行しても、長さの種類は増えていかないので、同じ長さのものをひとまとめに処理することを考えれば、計算量は増えずに済む
(-実数の長さ,本数)のHeapQueueを用意して、 $K$ 回分シミュレートし、
その後、大きい方から $X$ 番目になる長さを答えればよい
ACコード

メモ

公式解説では、
すべてをある長さ以下にする回数は（元の長さをある長さを下回るまで $2$ で割り続けた回数の和として）計算できるから、
逆に、二分探索で $K$ 回直前の長さを求めることができ、
それを用いて $K$ 回分のシミュレート後のHeapQueueを作ることができるから、
あとは、大きい方から $X$ 番目になる長さをこたえればよい、
とされているが、圧倒的に面倒な上、二分探索において安易にwhileで構えてもACにならない
ACコード

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