🦁

AtCoder Beginner Contest ABC433 解法メモ

2025/11/25に公開

Nim

AtCoder

tech

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

ABC433

ABC433A - Happy Birthday! 4

解法

$X+x=(Y+x)\times Z$ なので、
$x=(X-Y\times Z)\div (Z-1)$
つまり、 $X\geqq Y\times Z$ で、 $X-Y\times Z$ が $Z-1$ で割り切れればよい
ACコード

メモ

非常に長い年数後まで、実際に $Z$ 倍になるかシミュレートしてもよい

:::

ABC433B - Nearest Taller

解法

答えを $-1$ に仮置きした上で、
0..<Nの各A[i]につき、先頭から自分の真左まで、自分より背の高い人がいる度に、その番号で更新していけばよい
ACコード

メモ

一人ひとり、自分の真左から先頭まで、自分より背の高い人を順に探していき、いたらその番号を答えていってもよい
ACコード

ABC433C - 1122 Substring 2

解法

連続する数字を固まりで見ていけばよく、
ある固まりの数字から、次の固まりの数字にかけて1が足されていたら、
双方の文字数の少ない方が、その箇所でできるの1122文字列の種類の数といえる
これは、 $S$ をランレングス圧縮すればよく、
その後、先頭から次の固まりとの間で、先ほどの確認、計算をしながら、足し合わせていけばよい
ACコード

A[i]とA[j]を組み合わせると、
A[i]*10^((A[j]).len)+A[j]となる
これが $M$ の倍数、つまりmod Mが $0$ になるということは、
A[i]*10^((A[j]).len)のmod MとA[j]のmod Mを足した数のmod Mが $0$ になればよい
事前に、すべてのA[i]対して、10^1..10^10を掛けた、つまりj=1..10に対して、A[i]*10^jをmod Mした数mjとの組(mj,j)の個数をテーブルcにカウントしておけば、
各A[i]に対して、M-(A[i] mod M)となるmiにおけるc[(mi,A[i].len)]を足し合わせていけば答えとなる
ACコード

メモ

事前に10^j別にテーブルでmod Mを求めておく、という発想には至らず、逆元など、計算で対応するものと信じながら時間を溶かした

ABC433E - Max Matrix 2

解法

この問題では、 $1～N\times M$ の数字を $1$ つずつ $N\times M$ のマスに配置していくことになる
一旦、各要素をmin(X[i],Y[j])としてみると、
X[i]==Y[j]となるマスは、その値で確定となるが、
同じ値のマスが複数ある箇所については、その中の一箇所にだけその数字を置き、後は、それ以下の数字を置いていくことになるとわかる
この作業をうまく実現するため、
m[min(X[i],Y[j])]=座標を格納していくDeque
を用意し、初めに全マスにわたって格納していく
その際、X[i]==Y[j]であれば、addFirstし、そうでなければaddLastしておく
ここから実際に、 $i$ をN*Mから1まで降順にして、答えとなるマスに入れていくが、
まず、m[i]のDequeからpopFrontした座標に $i$ を置く（これで、X[i]==Y[j]となるマスがあった場合、 $i$ が入る）
ここで、まだm[i]に座標が残っていたら、その余りを格納するDeque $d$ にaddLastしておく
$i$ を進めていく中で、m[i]が空だった場合は、この余りを入れたDeque $d$ から、popFirstして充当していけばよい
降順にみている以上、この際に $d$ の在庫が足らなくなったら、条件を満たす答えが存在しない、ということになるので $-1$ を出力すればよい
ところで、そもそも、 $X$ や $Y$ に、同じ数字が含まれているとこうした考え方は使えないが、異なるマスに同じ数字が入ることはないので、その場合も $-1$ を出力すればよい
ACコード

メモ

工夫してソートすることで何とかしようとしてしまい、min(X[i],Y[j])の値毎に座標を管理していき、不採用の場合は別に退避しておく、という発想に至らない

ABC433F - 1122 Subsequence 2

解法

求めていく $1122$ 文字列の $2$ 番目の $1$ の位置にくる文字S[i]に着目して固定し、そのときの $1122$ 文字列の数を数えることを考える
それはつまり、左側の0..<iの文字の中からS[i]と同じ数字になっている箇所（ $l$ 箇所）と、右側のi+1..<S.lenの文字の中からS[i]+1の数字になっている箇所（ $r$ 箇所）からなる組み合わせを考えることとなる
これは、（可能であれば）一番短くて、 $l$ から $0$ 個、 $r$ から $1$ 個選ぶ形で、一番長いと、 $l$ から $l$ 個、 $r$ から $l+1$ 個選ぶ形である（左右同数の形）
これをよく観察して言い換えると、 $l+r$ 個の中から $l+1$ 個を選んだときに、「 $l$ の中から選ばれなかったもの」と、「 $r$ の中から選ばれたもの」と「S[i]」とを使えば、一意の $1122$ 文字列が作れるということになる
それはつまり、S[i]に対して $_{l+r}C_{l+1}$ 個の $1122$ 文字列が作れる、ということであり、これを $i$ が0..<S.lenまで足し合わせていけばよい
その計算にあたっては、各数字の累計和をとっておくとよく、
また、mod 998244353での組合せ計算も用意しておく必要がある
ACコード

メモ

公式解説を読んでも、初め、証明2が何を言っているのかまるでわからなかった

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