サボった A[RG]C の under 2600diff が 18 問にまで上ってしまったため、潰します
https://kenkoooo.com/atcoder#/contest/show/4151fce3-bd45-485f-8373-74ec924d182e
1. B - Insert 1, 2, 3, ... (ばちゃ中1問目, 1663diff, 自力AC)
本番でめちゃくちゃ詰まって絶命した問題。
ひとまず、ある数列 $A$ に対してそれが valid かどうか判定することを考える。ここで嘘にハマりやすいので注意。
例えば (1,2,3,1,2,3,4,5,1,2) は valid だが、この後にひとつ要素が来るとしてその要素で場合分けする。
- $1$ が来たら valid。
- $2$ が来たら invalid になる。
- $3$ が来たら、この $3$ は 1,2 に続くので valid。
- $4$ が来たら、この $4$ は 1,2,3 に続くので valid。
- $5$ が来たら invalid になる。
- $6$ が来たら、この $6$ は 1,2,3,4,5 に続くので valid。
- これ以外が来たら invalid になる。
ここで、例えば $6$ が来た時は 1,2 はもう使えなくなる。
また、 (1,2,3,1,2,3,1,2,3,4) から 4 が来た時のように、続けられる列が複数通りある場合は最も後ろにあるものに繋げて損をしない (=そのように選ぶことで、 valid な列を最長化(最も好意的に解釈)できる)。
また、求める区間 $[L,R]$ を数えるにあたって当然 $A_L = 1$ であるが、どの $A_L = 1$ から始めても $A_1$ から判定した状態の接尾辞が現在の判定問題の状態となる(伝われ)。
よって、以下の解法が成立する。
- 最初、空の stack を用意する。
- $A$ を $1$ 要素ずつ読み込み以下の判定を行う
- $A_i = 1$ なら stack に $1$ を突っ込む。
- そうでないなら、 (取り出した要素) $+1 = A_i$ となるまで要素を取り出した後、 $A_i$ を stack に追加する。
- そのような要素が取り出せなければ stack を空にする。
- この後、答えに現在の stack のサイズを加算する。
Submission #50085600 - AtCoder Grand Contest 063
ハマりにくいとは言わない(後ろから考えてみたり、微妙に違う判定法に落ち込んだり、ある要素の次に来る要素がどこになるかみたいなことを考えたり…)が、なんで本番でハマり散らかしたんだろ…
本番での反省 : 判定問題を徹底的に詰めて、一般化する方針を取ればよかった
解説では後ろからやる方針だったので、そちらも一応実装。自分は前からの解法の方が自然と感じたが、こっちの方がちょっと証明が楽かも。
Submission #50086034 - AtCoder Grand Contest 063
2. C - Not So Consecutive (ばちゃ中2問目, 2005diff, 自力AC)
なんで落としたんだろこれ… ちょっと時間かけて冷静になれば詰め切れました
dp[ $i$ 個目まで決めた ][ 末尾の要素 $A_i$ ] = { 場合の数 } の方針で押せる。
いったん $k$ が $k+1$ 個以上並んではいけないという制約を無視して遷移をかけた後、 $i$ 項目を置いたせいで初めて $k$ が $k+1$ 個並んでしまうような場合の数を引く。
これは、 dp[ $i-(k+1)$ ] の総和を引いた後に dp[ $i-(k+1)$ ][ $k$ ] を足せば遷移ができる。但し、実際に $k$ が $k+1$ 個並べられるかの判定が必要。これは予計算で $O(N^2)$ かければできる。 (区間内の値が全て -1 か、区間内の値が全て (-1 or x) か、それ以外 を予計算で全区間に対して判定すればよい)
Submission #50087017 - estie Programming Contest 2023 (AtCoder Regular Contest 169)
もっと速い解法があるらしいがこれは後で勉強します(こういうことしてるからダメなんだろうなぁ)
3. C - Sequence Scores (ばちゃ中3問目, 2056diff, 自力AC)
主客転倒。操作回数に寄与しない項を数え上げる方針で行く。
- ある要素 $x$ について、それより前に $x$ がなければその要素は操作回数に寄与する
- そうでなくとも、その直前の $x$ との間に $x$ 未満の要素があればその要素は操作回数に寄与する
- そうでないとき、今着目する $x$ と直前の $x$ とはまとめて操作できるため、今着目している $x$ は操作回数に寄与しない。
ここまでくると場所 $i$ と要素の値 $j$ を固定して主客転倒できる。 $k$ を場所 $i$ の直前に出現する $j$ の位置として全ての $k$ に対する和を高速に求めたくなるが、これはちょっと式をいじると等比数列の和になる。
$O(NM \log \rm{mod})$ (TLE): Submission #50088601 - AtCoder Regular Contest 114
メモ化して $O(NM)$ に落としてAC: Submission #50088710 - AtCoder Regular Contest 114
これ本番提出すらないけどなんで解けなかったんだろ…
4. D - Binomial Coefficient is Fun (ばちゃ中4問目, 2078diff, 自力AC)
明らかに積の和典型。積の和を復習してから解いた。
$C(B_i,A_i)$ は $B_i$ 個の区別可能な球の中から $A_i$ 個を塗る場合の数である。
素直に考えると球 $ M $ 個、仕切り $N$ 個から各領域に対して $A_i$ 個の球を黒く塗るが、これだとうまく行かない。
順番を逆にしてみる。例えば $A=(3,1,2)$ だと xxx|x|xx| をまとめて ? というオブジェクト $9$ 個に置き換える。これを $M-6$ 個の oo...o の中に挿入すれば求めるべきものとの1対1対応が完成する。
結局、求めるべきものはひとつの二項係数になる。
Submission #50088870 - AtCoder Regular Contest 110 (Sponsored by KAJIMA CORPORATION)
5. D - Inc, Dec - Decomposition (ばちゃ中5問目, 2143diff, 自力AC)
割と大胆予想を当てた感がある。
ひとまず $A$ の差分に着目して、 $A$ が $+x (x>0)$ する時を考える。この時 $\Delta B = x+P, \Delta C = -P$ とするべきだが、実は $P=0$ の場合以外は考えなくてよいのではという予想が立つ。
この予想が成り立つと仮定すると、 $B$ の初項を固定すれば他も全部決まってしまう。
より具体的には $B$ の全項を $-1$ 、 $C$ の全項を $+1$ するだけしか自由度が残らず、要素の絶対値の和の最小化は中央値を使えば解けるみたいなやつになります(クソ雑)
多分先ほどの $P \neq 0$ の場合を扱うぐらいならこの自由度で調整した方がお得みたいなことが証明になるんでしょうけど正確には示せず、ただ AC は自力できました
Submission #50105793 - AtCoder Regular Contest 123
追記(?) : 背理法でやったらええんか… Editorial - AtCoder Regular Contest 123
6. D - Binary Representations and Queries (ばちゃ中6問目, 2282diff, 自力AC)
とりあえず問題を理解するためにこのような図を書いた。
$N=3$ の場合に、操作はこの立方体の軸をひとつ選んで、その軸に平行な全ての辺に沿って加算が行われる。
この図をギン目で睨みつけると、次のことがわかる。
- 操作を軸ごとに独立に扱えないだろうか?
dp[ $i$ bit目 ][ 操作元のbit ][ 操作後に辿り着くbit ] = { 寄与を表現する係数 } みたいな配列が求められる。
dp[ $i$ ][0][0]=1, dp[ $i$ ][1][1]=1, それ以外=0 と初期化して遷移は dp[ $X_i$ ][ $j$ ][ $Y_i \oplus 1$ ] += dp[ $X_i$ ][ $j$ ][ $Y_i$ ] とすればよい。
この dp 配列から操作後の配列を復元する必要があるが、これは下の bit から dp で表現されている寄与を実際にかけていけばよい。(ちなみに、どの順番で寄与をかけても結果は変わらない。)
説明が雑なのでこれ以上は実装見てください
Submission #50106548 - AtCoder Regular Contest 151
解説の言語化がかなりわかりやすかった、「軸ごとに独立に扱える」を「$X_i \neq X_{i+1}$ なら swap してもよくて、最終的に $X_i$ でソートできる」の換言、なるほどね: Editorial - AtCoder Regular Contest 151
記事が長すぎるので分割します
