ABC 6,7,8問体制(126..最新)のD問題をだいたい解いたので、そこから得た教訓をまとめていきます。

トップページへ

コードはこちら

累積和を上手く使う。

二進数で $i \geq 0$ 桁目の $?$ を 1に置き換えられるかどうかは、

• $i$ 桁未満の $?$ をすべて $0$ に置き換えて全体が $N$ 以下になるなら1に置き換える
• そうでなければ、0に置き換える

よって $i \geq 0..len(s-1)$ 桁目について $S$ の $?$ を 0に置き換えたときの最低値を求めておく。 $S$ のすべての $?$ を0に置き換えて $N$ を超えるかどうかはこの時点で分かるので、超えたら -1 を出力して終わる。超えなければ $S$ を上の桁から順にみて、

• 0なら0に置き換えて一つ下の桁を見る
• 1なら1に置き換えて $N$ を超えてしまうなら打ち切り(これは発生しない)。超えなければ一つ下の桁を見る。
• ?は上記の方法で0にするか1にするか決める

ことで答えが求まる。

コードはこちら

Dを最小化するのではないことに注意する。

同じ価値の贈り物は一つにまとめる。 std::unique(), erase() イディオムを使う。

$A+D$ を決め打ちして std::upper_bound() で $B$ を探し、イテレータ前後の $B$ を贈り物に選べばよい。イテレータが begin() または end() を指しているときに注意する。

コードはこちら

Union-findではなかった。

連結成分の大きさとか、クエリ先読みとか、そういうことを考える必要はなかった。単に各頂点の入出次数を数えればいい。入出次数が0の頂点の数は、入出次数が0から1(クエリ1)、1から0(クエリ2)になるときにだけ変化する。

辺を std::vector<std::set<Num>> で管理すると、辺を削除するときの計算量が減る。

コードはこちら

本当は超頂点だが、距離を連想配列で持つ

最初に、集合 $S_{1..N}$ にどの数が含まれるかと、 数 $1..M$ がどの集合に含まれるかをまとめる。ここで $S_i$ に ${1,M}$ が両方含まれれば $S_i$ を選べばよく答えは0である。

$1$ を含む集合それぞれを起点にBFSして $M$ を含む集合までの最短距離を測る。合併可能な集合つまり共通した要素を一つでも持つ集合に遷移する。このとき以下に注意しないとTLEする。

• すでに求まっている最短距離より長くなったら探索を打ち切る
• 集合が合併可能かどうかはその場で求める。合併可能な $S_i$ を無向グラフで結ぶと辺の数が $O(N^2)$ になるので、全部求めるとTLEする。
• ある集合からの距離は std::vector<Num> dist(n, INF) ではなく、 std::map<Num, Num> で管理する。前者だと $1$ を含む集合それぞれについて $O(N)$ の初期化処理が走り、それが原因でTLEする。

$1$ を含む集合から $M$ を含む集合まで到達可能なら最短距離が答え、到達不能なら -1 が答えである。

想定解は数 $1..M$ を超頂点にすることで辺の数を $O(\sum A)$ にすることである。C++だから3秒制限に間に合ってしまった。

超頂点を明示すると こちら の実装になるが、TLE対策が大変である。

• 上記の通り、ある集合からの距離は std::vector<Num> dist(n, INF) ではなく、 std::map<Num, Num> で管理する。
• 1を含む集合は明示的にグラフに加えない。1を含む集合に含む整数=初手で到達する超頂点を初期状態としてBFSする
• 既に求まった答え以上の距離は探索を打ち切る

コードはこちら

場合分けを網羅できずに解けなかった。直観に頼らずすべての組み合わせを挙げよう。

問題自体は、CapsLockがoffかonかで動的計画法すれば解ける。問題は状態遷移を網羅することである。X (a), Y (Shift+a), Z (CapsLock) 単独では足りず、これらの組み合わせをすべて考える。

• X : CapsLockがoffならa, onならAを入力する
• Y : offならA, onならa
• Z : 単独では使い道が無い
• X → Y, Y → X : 二文字入力するので考えない
• X → Z, Y → Z : 以下で網羅できるので考えない
• Z → X : CapsLockがoffならA, onならaを入力する
• Z → Y : CapsLockがoffならa, onならAを入力する

Z → Y を思いつかないと解けない。

コードはこちら

問題文を読むと条件は簡単である。

問題文より、葉つまり次数が1の頂点同士しか連結しないことが分かる。よって葉を一つ見つけたら(必ず見つかる)、そこから辺をたどったときに葉-中心-葉-葉-中心-... という並びになる。これをBFSかDFSで探索すれば中心が見つかる。中心は連結しないので中心の次数が答えである。

頂点をたどる方法をいかに上手く実装するかで、速く解答できるかどうか決まる。公式解説の方法が美しい。中心-葉-葉をたどるところを二重forループにした場合、同じ頂点を二度たどらないようにしないとTLEする。

公式解説にある簡潔な実装を使うと こちら になる。

コードはこちら

座標圧縮する。

座標の取りうる値が $10^9$ と大きいので、座標軸に沿って調べるとTLEする。ケーキを切ると、X軸方向に $A+1$ 区間に分かれるので、X軸上の座標を区間 $0..A$ に圧縮する。圧縮した後の座標は、座標を二分探索して std::distance() で求まる。Y軸上の座標も $0..B$ に圧縮できる。

ピースに載っているイチゴの数は連想配列で管理する。圧縮した後のX,Y座標をキー、イチゴの数を値とする連想配列を用意すれば、座標圧縮しながらピースのイチゴを数えられる。連想配列に載っていないピースについてはイチゴの数は暗黙に0個だが、イチゴが0個のピースがあるかどうかは連想配列のエントリ数が $(A+1)(B+1)$ 未満かどうかでわかる。

コードはこちら

Union-find木の代表元を使う。

グラフの連結成分分解はunion-find木を使えばよく、連結成分(部分グラフ)の識別子として代表元を使うことができる。良いグラフではないというのは、xとyが異なる連結成分にあり、それらを併合してしまうことである。よってpとqを結んだ時、

• pとqが同じ代表元に属するなら、連結成分は変わらないのでよいグラフのまま
• pとqが異なる代表元に属するなら、xとyの結んではならない代表元を結ぶと良いグラフでなくなる。そのような代表元の組は、xとyそれぞれの代表元について集合を作ってテーブル参照すればよい。

コードはこちら

添え字の管理がややこしい。

$r_i-l_i$ は如何にも累積和なので、 $r_i$ を求める方法が分かれば同じ方法で $l_i$ も求まる。よって時刻 $t$ について、 $A_{j-1} < t \leq A_j$ な $j$ を二分探索で求める。

あらかじめ $A_j$ までの睡眠時間を累積和として求めて置く。Aの添え字を2で割った余りが0と1のどちらかで頭がこんがらがるので、問題文通り1-based indexingにするとよい。 $A_j$ が起床( $j$ が奇数)か就寝( $j$ が偶数)で場合分けする。

• 起床なら累積和から $A_j-t$ 引くと累積就寝時間が求まる
• 就寝なら累積和がそのまま累積就寝時間である

上記の通り実装すると このよう になる。

コードはこちら

初期化方法が大事。

各警備員が到達可能な範囲をBFSで網羅すればよい。このときいつものBFSの最短距離の代わりに警備員の体力を使うと、既に訪問したときの体力が多い頂点から先は探索せずに済む。

BFSで訪ねる頂点の管理は、残り体力が多い頂点を最優先で探索するように優先度キューを使う。このとき初期状態はすべての警備員の初期配置にする。1人目を配置してBFS、2人目を配置してBFSとするとTLEする。

コードはこちら

来た道を戻る。

インタラクティブな問題は質疑を上手く実装するのが大変である。上手くループを使う必要がある。それと質問回数は決め打ちで十分大きくすればいい。

頂点1から未探索の頂点をたどっていく。先に未探索の頂点が無いまま頂点Nを見つけられなければ一歩戻り、未探索の頂点があればそちらに向かう。未探索の頂点が無ければもう一歩戻り同様、というのを繰り返す。そうすればいつか頂点Nにたどり着く。頂点1から現在地までどうたどり着いたかは std::vector<Num> path で延ばしたり縮めたりする。それと探索済の頂点についても隣接する頂点を返すので、誤って二度登録しない。

コードはこちら

303-Dと同様に、2状態の動的計画法である。

状態遷移を網羅できるかどうかが肝心である。この問題は一ひねりあって、美味しさが負のときがあるので食べない方がよい場合がある。

コードはこちら

集合を二つ用意する。

だけなのだが、なぜか実装に二時間掛かってしまった。挿入して後から辻妻を合わせるといい。

• 初期状態は0が $K$ 個の上位陣の集合と、 0が $N-K$ 個の下位陣の集合を作る。上位陣の総和は0である。
• $A_{X_i}$ が下位陣の集合に含まれれば除く。そうでなければ上位陣の集合に含まれるはずなので除く。
• 除いた方の集合に $Y_i$ を追加する。
• 上位陣の最下位と下位陣の最上位が逆転していたら入れ替える
• 上記の削除、挿入、入れ替えに伴って、上位陣の総和を更新する。

集合は std::multiset<Num> で管理する。 $K=N$ は別途実装する。

コードはこちら

座標圧縮

まず $A$ を座標圧縮する。次に $A_1$ 以外をすべてセグメント木に載せ、 $A_{i,1}..A_{i,M}$ を圧縮後の座標で昇順に並べ替えておく。

$A_{i,k}: 1 \leq k \leq M$ を順番に見ていく。 $f(S_i, S_j), i < j$ における、 $A_{i,k}$ の寄与分は、

• $A_i$ については、 $A_i$ のうち $A_{i,k}$ より少ない要素の数、つまり $k-1$ 個である。
• すべての $A_j$ については、 $A_j$ のうち $A_{i,k}$ より少ない要素の数である。これはセグメント木から分かる。

$A_{i+1}$ の寄与分は、 $A_{i+1}$ の各要素をセグメント木から除いてから同様に数える。順位が1から始まることを考慮して上記を足すと答えが求まる。なおセグメント木だと 2311 ms 、Fenwick tree だと 2801 ms 掛かった。4 sec制限には収まったのでどちらで実装してもよいと思う。

コードはこちら

C問題も時に水diffになる。

入力が小さいので6重forループでもTLEしない。なので素直にシートの重ね合わせ位置を一つ一つずらして総当たりすれば解ける。ただしコピーアンドペーストでコードを書くと、直し忘れてバグが起きる。共通するコードを上手く関数やマクロにまとめるとバグが起きなくなるだろう。地道な実装力が問われる。

シートをクラスにして実装すると こちら になる。やはり実装量は多い。

• マスの横一列は整数のビットパターンで表現し、C++20のビット走査で調べる
• 縦の列は整数のベクトルで表現する
• normalize は左と上の余白を削除する。左上は透明なマスかもしれない。
• merge は、 引数 rhs のマス X=left, Y=top が this のマス X=0, Y=0 に重なるように重ねる。 left と top は負の値でもよいが、負の値を上手く扱うのに工夫がいる。
• equal は normalize 済のシートが一致するかどうか調べる

コードはこちら

オイラーツアーと同様、実装がややこしい。

(, ) の対応をプッシュダウンオートマトンで取る、つまり ( をスタックに積んで ) でスタックから要素を取り出す、ということはすぐにわかる。しかし括弧の対応がずれているときの異常系処理の実装が大変である。

括弧に入っていない文字列を特別扱いするとバグの元になるので、特別扱いせずスタックの一段目に載せる。つまり初期状態を、空文字列を一つスタックに積んだ状態にする。

• ( を見つけたら、 ( 自身をスタックに載せる。そうしないと ) の対応が取れないときに ( を出力できない。
• ) を見つけたらスタックを一段取り出して (...) を捨てる。ただしスタックが一段しかない、つまり ( がないときは取り出さず、代わりに ) 自身をスタックに載せる。
• (, ) の文字は、スタックトップの文字列の末尾に追加する

(, ) の対応がどうあれ、最終的には (, ) の対応が取れていない文字列がスタックに積まれる。これをスタックの底から順に連結すると答えになる。

コードはこちら

漸化式

落ち着いて漸化式を組めば分かる。

1番目の人に0を渡すと決め打ちして、i番目以降の人に0または非0を渡す組み合わせ $Z_i, NZ_i$ を数える。

• 初期値は $Z_1=1, NZ_1=0$
• 0を渡すならその前には非0しかないので $Z_i=Z_{i-1}$
• 非0を渡すならその前が0なら $m-1$ 通り、非0なら $m-2$ 通りあるので $NZ_i=Z_{i-1} \times (m-1) + NZ_{i-1} \times (m-2)$
• N番目の人は0を渡せないので、 $Z_{N-1} \times (m-1) + NZ_{N-1} \times (m-2)$ 通り

1番目の人に $M$ 通り渡せるので、最後の答えを $M$ 倍したものが答えである。 $N=2,3$ は特別扱いした方がよいかもしれない。

公式解説を読むと解析解がある。解析解を求めようとして上手くいかなかったからDPにした。

コードはこちら

BFSである。

出発点のマスが s 以外なら明らかにゴールに到達不能と解る。そうでないときは幅優先探索すればよい。 snuke はすべての文字が異なり、無限ループする意味は無いので、幅優先探索で一度でも訪れた場所は再度訪れないように印をつける。4方向をまとめると こちら のコードになる。

コードはこちら

累積和である。

$E,X$ が取りうる数字の組み合わせは9通りしかない。なので $i$ 以降の $E,X$ 9通りと、 $i$ 以降の $X$ 3通りについて、出現回数の累積和を取ればよい。以下のように表記する。

• $E,X$ 9通りの組み合わせの数 $\lvert j,k \rvert \quad j \in \lbrace 0,1,2 \rbrace , k \in \lbrace 0,1,2 \rbrace$
• $X$ 3通りの組み合わせの数 $\lvert k \lvert \quad k \in \lbrace 0,1,2 \rbrace$

累積和は $N..1$ について順に数えれば分かる。 $S_i=M$ を満たす $i$ について

$\sum_{j \in \lbrace 0,1,2 \rbrace} \sum_{k \in \lbrace 0,1,2 \rbrace} mex(A_i,j,k) * |j,k| * |k| $

の和を $i=1..N$ について取ると答えが求まる。コードをきれいにすると こちら。

コードはこちら

クーポンで何を買おうが割引額は同じ。

なのでクーポンを使える場面が狭いものを後で、使える場面が広いものを先に使って構わない。具体的は、以下の尺取り法で解ける。

• 値段の安い物から高い物を順番に買い、そのとき使える割引額が最も大きいクーポンを使う
• $P_i >= L_j$ を満たすクーポンはすべて使える。そのようなクーポンを優先度キューに入れて、割引額が最も大きいクーポンを取り出す。

コードはこちら

やはりBFSである。

出発点を固定して、他の点までの最短距離はBFSで求まる。頂点1から最も遠い点と、頂点 $N_1+N_2$ から最も遠い点を結べば題意を満たす。

コードはこちら

振り返りは大事。

この問題は、305-Eの実装を基に、無向グラフを有効グラフに変えるだけで解ける。こうして緑diffでも10分を切ることができる。

問題の制約として、親の番号は子の番号より小さいので、単に番号順にDPするだけ解ける。実装は こちら 。

コードはこちら

公式解説2と同じことをしたつもりだったのだが、結局ACできなかった。小さい箱から順にセグメント木に入れる、というのが違いだろうか。

コードはこちら

執念が足りないと負けることがある。

std::next_permutation() で解けると思って解けず、DFSというか再帰で解けるだろうと思って解けず、解き始めて2時間経過後にもしかしてチームに一人ずつ追加すればよいのではと思って諦めて解説を読んだらその通りだった。解けそうだと思ったら時間を置いて諦めずに解くべきだった。

解き方だが、 std::vector<std::set<Num>> でチームを作り、既存のチームに可能なら選手を一人追加するか、一人だけのチームを新たに作る、というのを再帰すればよい。選手を追加する順番を固定すれば、チームの一意性は担保できる。

計算量のオーダーが $N!$ だろうと思い、 $1..N$ の順列を $T-1$ 箇所で区切ったらTLEした。 $10!$ が意外と小さいことにとらわれ過ぎで、 $T-1$ 箇所で区切る方法を掛けると計算量が大きすぎる。

再帰で解けるが、再帰した先で std::vector がreallocされると未定義動作になる。なので再帰呼び出しの前後で、ベクタの要素への参照を使いまわさないようにする。実装は こちら 。std::vector::reserve でもreallocを回避できるが、可読性が悪く保守できないのでお勧めできない。

コードはこちら

執念があれば勝てることがある。

30分考えてようやく解法を思いついた。

$A_1 .. A_i$ を左結合でNANDした結果を順に見に行く。つまり区間 $[j,i], 1 \leq j \leq i$ をNANDした結果が $0$ になる区間の数 $Z_i$ と $1$ になる個数 $NZ_i$ を累積する。これは以下の通り求めることができる。

• $A_i=0$ なら、 $Z_i=1$ で $NZ_i=Z_{i-1}+NZ_{i-1}$
  • 左結合の結果がどうあれNANDは1になる
  • NANDが0になる区間は $[A_i,A_i]$ だけになる
  • NANDが1になる区間の累積数は、 $Z_{i-1}+NZ_{i-1}$ 増える(左結合の区間丸ごと)
• $A_i=1$ なら、 $Z_i=NZ_{i-1}$ で $NZ_i=Z_{i-1}+1$
  • 左結合の結果をNANDは反転する
  • NANDが1になる区間は、 $Z_{i-1}$ と $[A_i,A_i]$ になる
  • NANDが1になる区間の累積数は、 $Z_{i-1}+1$ 増える

上記を $i=1..N$ まで求め、1になる区間の累積数を答える。

コードはこちら

確率DPは解けると思ったら全くに手に負えず、解説を読んでもACできず、他の方のコードを読んでようやく一時間半掛かったACした。

確率ではなく分布の状態遷移を考える。なんだかεイプシロン遷移がある有限オートマトンで正規表現を解くかのようだ。

コードはこちら

時間を掛け過ぎた。

95分掛かってしまった。最初の1時間はなぜかセグメンテーションフォールトが取れず、あきらめて固定長配列 Num visited[209][209] にしたら直った。 boost::multi_array をローカル変数からグローバル変数に移動しようとして失敗したらしい。後の30分は、初期マスから動けないときの答えが1だということに気が付かなかった。

ここまで分かればBFSかDFSで解ける。解説にある通り移動中という状態を持てば $O(NM)$ 、私の実装通り、滑った先の壁を二分探索で求めれば $O(NM*log(max(N,M)))$ である。

公式解法1の通り、方向別に分けるとBFSしやすい。そのように改良したコードが こちら 。以下の点に気を付ける。

• BFSを深堀するかどうかは、候補をキューから抜いたときでよい。加えるときでもいいがコードが長くなる。
• 訪問済み座標は4方向+静止の5通りなので、ループ回数に気を付ける

コードはこちら

有名問題らしい。

穴が無い場所に正方形を広げるのに、上から、下から、斜めからの三通りを試して、その最小値+1にする。というのを解説を読むまで分からなかった。領域が重なってないかとか、広げた先に穴があったらどうするとか、気になって動的計画法できないのだが、最小値を取るのでこれで大丈夫という証明が載っている(簡単に言うと、三通りのどれかを満たさないなら正方形を広げることはできない)。

穴ではなく穴が無いところを広げるのだが、これがまるで分からなかった。二分探索だと こう 書ける。二分探索でない解き方は理解できなかった。

コードはこちら

見えざる手による需給曲線

C問題茶diffだが1時間掛かってしまった。需給が均衡するなら二分探索で求まる。しかし均衡しない場合をしっかり実装しないとWAする。

まず 売値 $A_i$ と 買値 $B_i$ をそれぞれ昇順に並び替える。以下の説明でインデックスは 1-based (先頭が1)とする。

a. すべての買値よりすべての売値が大きい、つまり買値の最大値より売値の最大値が大きいときは売買が成立しない。このときは買い手が売り手が0人という解について、答えつまり誰も買わないし誰も売らない値段の最小値は、買値の最大値+1すなわち $B_M+1$ である。

b. すべての売値よりすべての買値が大きい、つまり売値の最大値より買値の最大値が大きいとき、値段は気にせず買い手が売り手をマッチングできるかどうかだけで決まる。

• 売り手が買い手以上いれば全員買える。つまり答えは買値の最大値 $B_M$ である。
• 売り手の数 $N$ が買い手の数 $M$ より多ければ、 $N+1$ 番目に大きな買値をつけた人に諦めてもらう。よって答えは $B_{M-N} + 1$ である。

c. 上記以外なら均衡解 $v$ があるので、売り手の数が買い手の数より少ないという条件で二分探索する。収束範囲 $[L,L+1]$ の $L+1$ が、売り手の数が買い手の数以上いるときの $v$ の最小値である。同じ値段の売り手と買い手が複数いることに注意して std::lower_bound と std::upper_bound を使い分ける。

• $v$ 以下の売り手の数は、 std::upper_bound(aset.begin(), aset.end(), base) - aset.begin()
• $v$ 以上の買い手の数は、 bset.end() - std::lower_bound(bset.begin(), bset.end(), base)

解説を読んでから、実装から上記a,bを除いてcだけ残したら AC した。焦っていて自分が何をしていたのか分からなくなったのかもしれない。

C++20で書くと こうなる 。探索範囲を $[-1,max(A,B)+1]$ にしないとWAする。

コードはこちら

フラグを持ちつつDP

縦軸を $pos$ 文字目まで構成したか、横軸を ) と対応が取れていない ( が $i$ 個で $DP[pos][i]$ する。答えがmodintなので無効値にINF(infinity)は使えず、有効な数を持っているかどうかを別途フラグで管理する。

• 初期値は0文字目まで、未対応が0個のときが1通り、他はINF
• $i$ 文字目が ( なら $DP[pos+1][i+1] = DP[pos][i]$ ただし $i<|s|$ で、INF通りからは遷移しない
• $i$ 文字目が ) なら $DP[pos-1][i-1] = DP[pos][i]$ ただし $i>0$、INF通りからは遷移しない
• $i$ 文字目が ? なら上記の両方を数える

答えは最後に括弧の対応が取れている状況 $DP[|S|][0]$ である。公式解説のDPは上記と同じだがフラグを用いないので簡潔であり、コードにすると こちら になる。

コードはこちら

尺取り法

缶きりで缶を開けるかどうかはインデックスに依存しない。よって缶切り不要な缶の価値 $U_i$ 、缶切りが必要な缶の価値 $N_i$ 、缶切りで何個の缶を開けられるか $O_i$ をそれぞれ降順に並び替える。価値のある缶から入手し、たくさん開けられる缶切りから入手するのが得である。

最初に入手するものの集合に、缶切り不要な缶 $U_i$ を $min(M, |U|)$ 個詰める。次に缶切りを、開けられる缶の数の降順に1個ずつ適用する。

• 缶切りが $M$ 個以上なら缶は一つも入手できないので、これ以上缶切りは要らない。集合の大きさを $M$ から缶切りの数を引いたものに制限するとよい。
• 缶切りを1個追加すると集合が $M$ 個を超えるなら、集合から最も価値が低い缶を除く
• 缶切りを1個追加し、集合の大きさが最大 $M$ 個になるまで、まだ集合に入れていない、缶切りが必要な缶で最も価値の高い缶を入れる。これを缶を加えると価値が増える限り繰り返す。つまり
  • 缶を入れても集合が $M$ 個を超えないなら、無条件で缶を加える(価値は正の値なので)
  • 集合が $M$ 個を超えるなら、最も価値が低い缶を除く。除いた缶が入れた缶より価値が高ければ、除かなければよい。

缶切りが必要な缶の価値 $N_i$ を尺取り法で集合に入れるので、上記の操作は $N$ 回である。 std::multiset<Num> で集合を管理すると、全体の計算量は $O(NlogN)$ になる。ソート $O(NlogN)$ が律速なので気にせず std::multiset<Num> を使った。

公式解法は、缶切り不要な缶を $0..M$ 個、缶切りが必要な缶を $M..0$ 個選んだ場合を求めて足すことで、簡潔な実装にしている。その通り改良したコードは こちら

コードはこちら

対角線を眺める。

以下公式解説の再解釈である。 $K + 1$ 個の要素があるとき、一つを除いた残り $K$ 個について $K+1$ 回クエリを投げればそれぞれのパリティ(1が偶数個か奇数個か)が分かる。 $K+1$ 回のクエリには $K+1$ 個の要素 がそれぞれ $K$ 回反映されて、 $K$ は奇数なのでそれぞれの要素のパリティは $K$ 回も1回も同じである。よって $K+1$ 回クエリのXOR(パリティ)の合計と、一つのクエリのパリティの差を取れば $K + 1$ 個の要素については分かる。

あとは先頭 $K - 1$ 要素とその他一要素についてクエリを投げれば、先頭 $K - 1$ 要素は求まっているのだから残りの要素も分かる。

$A_1..A_K$ のパリティと $A_2..A_{K+1}$ のパリティの差を取ると、 $A_1$ と $A_{K+1}$ が一致するかどうか分かるので union-find木に載せて連結成分を0か1か塗分ける、という方法はダメだった。適応的だからだろう。

コードはこちら

ランレングス圧縮

まず1以外の数字が2連続する場合は無限に文字列が伸びるので-1を返す。以下、1以外の数字の後には必ず1がくる、1は連続するかもしれないという前提で話を進める。

$S$ に先頭に1以外の数字があったとしても差し当たり無視して、 $1$ が $len$ 個 の後 $rep>1$ が1個続くとき $[len,rep]$ とランにまとめる。 $S$ の最後が $1$ で終わるとき、最後のランは $rep=0$ とする。

$f(S)$ の操作は、最後のランから最初のランまで以下の処理を繰り返すことに等しい。ランの前後をひっくり返して、最初のラン( $S$ の最後のラン) から見ていく。

$rep=0$ なら $len$ 回操作を繰り返すと連続する1がすべて無くなる。 $rep>0$ なら最初の操作で連続する1が $len+rep-1$ 個になり、 $len+rep-1$ 回操作を繰り返すと連続する1がすべて無くなる。まとめると $len+rep$ 回操作するとランを消せる。このときの操作が終了した時点の累積操作回数を $count$ 回とする。

2番目以降のランがまるごと残っているとき、 $count$ 回の操作によって1が $count \times (rep-1)$ 個増えている。よって $len+count \times (rep-1)+rep$ 回操作を繰り返すと $rep$ と連続する1がすべて無くなる。 $count$ を更新して以後最後のランまで計算する。modintを計算するとき、途中の計算 $count \times (rep-1)$ もmodintにして桁あふれしないように注意する。 auto を使っているとうっかり間違えやすい。

全てのランを消化したあと、 $S$ の先頭が1以外なら累積更新回数そのもの、 $S$ の先頭が1なら累積更新回数から1引いた値が答えである( 1 一文字の文字列はそれ以上減らないので)。

公式解説1の楽な実装は こちら 。以下の点が巧妙である。

• ランレングス圧縮で、連続する1と、孤立した1以外を別のランとして扱う
• 最初と最後が1でも特別扱いしないで正しく答えが出る。そのために暗黙の1が末尾にあると仮定する。
• ランを全部消化するので、答えは和から1引く

公式解説2の楽な実装は こちら

コードはこちら

最終更新時刻を覚えて置く。

すべての文字を大文字にするのと、すべての文字を小文字にするのは、最後にいつだったか覚えて置く。それとは別に、文字列のそれぞれの位置にどの文字を設定したか覚えて置く。初期値はすべての位置の文字を時刻0に設定したことにする。

ある文字の位置について、その文字を更新した時刻(クエリ番号)が、すべての文字を大文字または小文字にするより後なら、更新した文字がそのまま生きている。そうでなければ更新後に大文字または小文字になっている。どの文字で更新したかは最後のものだけ覚えておけばよい。

コードはこちら

漸化式

漸化式をまったく想像できなかったので、公式解説を見るしかない。利得が0の遷移は削除できる、というのは知っておくほうがよい。

と書いたままになっていたのだが、後日 AtCoder Daily Training ALL 2024/04/10 20:00 start で解けた(60分制限には間に合わなかったが)ので説明を書く。

$M-1..0$ のときの最小コスト $dp[M-1..0]$ を求め、 $dp[0]$ が答えである。初期値は $dp[] = \infty$ とする。

$dp[i]$ は、ポイントが $i$ でルーレット $j = 1..N$ を選んだ時の最小コストである。あるルーレット $j$ を選んだ時のコストは出目が $S_k$ のときに

• $i + S_k \geq M$ ならこのルーレットを回すコスト $C_j^{'}$ (意味は後述)
• $i + S_k < M$ なら、このルーレットを回した後にポイント $i + S_k$ になるときのコスト $dp[i + S_k] + C_j^{'}$
• $1..k$ についての平均値、つまり上記の和を $k$ で割ったものが、 ポイントが $i$ でルーレット $j$ を選んだ時のコストである
• これをすべての $j$ について最小値を取る

$C_j^{'}$ は出目0を除いたときのルーレット $j$ のコストである。つまり非0の $S_{j,k}$ が $NZ_j$ 個あったとき、 $C_j^{'} = C_j / (P_j - NZ_j)$ とし、 $S_j$ から0を除く。あるルーレットを回すかどうかは、0を除いたルーレットを考えても結果は変わらないからである。

コードはこちら

木でも使えるいもす法。

結論から言うと、対戦トーナメントにおいて、対戦するチーム同士が隣り合っていると好都合である。隣り合っているとは、葉つまりプレーヤの番号が左から見た添え字順で、 $[P_L, P_R]$, $[P_R+1, Q_R]$ になっていることを意味する( $P_L > Q_R$ なら $p,q$ を逆に解釈する) 。こうなっていればプレーヤー $[a_L, a_R]$ と $[a_R+1, b_R]$ にそれぞれ $a/(a+b)$ と $b/(a+b)$ を足すという処理を、いもす法をつかって一回 $O(1)$ でできる。なぜなら両チームを合併すると $[a_L, b_R]$ になってやはりいもす法が使えるからである。

なのでこのような対戦トーナメント木を構成するのが本問題の山場である。対戦トーナメント木の部分木をいい感じに左右入れ替えればできそうな気がする。実装例は こちら 。

まずは対戦順通りに、ボトムアップに木を構成する。プレーヤー $1..N$ という頂点に対して、対戦 $(N+1)..(2N-1)$ という頂点を定義し、プレーヤーと対戦を辺で結ぶ。このときUnion-find木を作ってチームを構成し、代表要素に対戦を関連付けると、木を構成中にあるプレーヤーがどの対戦に属するかが分かる。

対戦トーナメント木を構成したら、トップダウンにプレーヤーの順序を決める。ある対戦の子頂点は必ず2つである。左子頂点をたどって得られる葉(プレーヤ)の添え字 < 右子頂点をたどって得られる葉(プレーヤ)の添え字、という関係を維持すればよく、子頂点をDFSして最初にみつけたプレーヤーから添え字を順番に振る。こうすると対戦トーナメント木に置けるプレイヤー $1..N$ の添え字 ${pos}_{1..N}$ が求まる。

後はプレイヤー $1..N$ を $pos_{1..N}$ に読み替え、 $a/(a+b)$ と $b/(a+b)$ をいもす法できるよう配列に足し引きして、チームの区間を合併すればよい。最初に述べた通り、この対戦トーナメント木においてチームの区間は必ず連続するようにしたのでこのようにできる。後は $pos_{1..N}$ を $1..N$ に読み替えて、いもす法から求めたプレイヤーの値を出力する。計算量はunion-find木を構成するのが律速でほぼ $O(N)$ である。

公式解説をみたら、普通にDFSで期待値を伝搬すれば $O(N)$ で解けるできることが分かった。しまった、その方法は時間計算量または空間使用量が $O(N^2)$ だと思い込んでしまった。実装すると こちら のように簡潔に書ける。

コードはこちら

Fenwick trees

Fenwick tree を行ごと、列ごと、文字ごとに作ればいい。文字は26種類しかないので、 atcoder::fenwick_tree<int16_t> にすればMLEしない。

あとは問題文通りシミュレーションすればよい。消したクッキーは二次元配列ではなく、Fenwick tree で管理すると一貫性を取る手間が省ける。ただし一度消去した行と列を以後調べないように印をつけておかないとTLEする。

行または列にある種のクッキーが2個あるかどうかは普通に調べればいいのだが、2種類以上ないことと、1種類だが2個以上あることをきっちり調べる。この判断を間違えるとWAする。

空間使用量は26種の文字を定数として $O(HW)$ である。シミュレーション一回ごとに必ず行か列が一つ以上減るので、時間計算量は Fenwick tree の操作コストが $log(max(H,W))$ として $O((H + W)^2 log(max(H,W)))$ である。

公式解説の通りある色のクッキーがいくつあるか管理すればよく、Fenwick treeを使わずとも普通の連想配列と二次元配列で管理できる。そのように改良したのコードは こちら

コードはこちら

トポロジカルソート

ある本を先に読むという依存関係をグラフにして、トポロジカルソートしたものを出力すればよい。ただし、本1そのものは出力しないのと、本1を読むために必要な本をBFSで調べて出力し、必要ない本は出力しないようフィルタリングする。

有向グラフなので、union-find木を使って本1から到達可能かどうか調べるとWAする。たとえば 本1に本3が要り, 本2に本3が要るとき、本2は本1に必要ないが、union-find木は無向なので必要と誤判定する。

整数のベクトルを空白区切りで出力するのは以下の通り書ける。以下を組み込んだのが こちら

std::ostringstream oss;
std::copy(books.begin(), books.end(), std::ostream_iterator<Num>(oss, " "));
os << oss.str() << "\n";

コードはこちら

DP

公式解説を読むと現在地と通過回数でDPとある。DPの最中は最短距離だけで更新して、ペナルティはDPの途中では足さない、ということが重要らしい。

すべての座標を通る状態から出発して、ペナルティを払っても一つ頂点を除けるなら最も距離が縮まる頂点を除く、というgreedyはWAする。この違いが分からない。

三平方の定理は std::hypot を使うと計算が楽になる。組み込んだのが こちら

コードはこちら

DPである。

$i$ 番目の選挙区まで鞍替えさせて、議席を $s$ 席確保したとき、何人鞍替えさせたかという二次元DP $dp[i][s]$ で解ける。 $s$ の上限は $win = \lceil (\sum Z) / 2 \rceil$ なので、 $s \geq win$ は一まとめにして構わない。

初期状態は選挙区無しで議席0なら鞍替えさせたの人数は0人であり、他は人数無限大とする。

選挙区 $i+1$ に対策するかどうかで場合分けする。

• コストを掛けて対策しないなら $dp[i+1][s] = dp[i][s]$
• 最低限の人数 $d=min(0, X_i - (X_i + Y_i) / 2)$ を鞍替えさせる。 $dp[i+1][min(win, s + Z_i)] = dp[i][s] + d$ で左辺より右辺が少なければ更新する。

答えは $dp[N][win]$ である。

DPの選挙区は直前と今だけ覚えておけばいいので、そのように改良したのコードは こちら

コードはこちら

計算量解析。

視線の先にあるマスを通行不可と印をつければいい。そうしても $O(HW(H+W))$ にはならない。なぜなら人もまた視線を遮るので、視線が向く空きマスを埋める回数はマスの数 $O(HW)$ にしかならないからである。

空きマスに4方向から視線を向けるときに、早まって他の視線を遮らないようにする。あとはいつも通りBFSでスタートからゴールの最短距離を求める。4方向から視線を向ける処理はまとめて上手く書ける。凝ったことをしなくても、毎行毎列4方向を調べればよく、せいぜい同じ空きマスを同一方向に2回調べるだけである。

4方向をまとめるように改良したコードは こちら

コードはこちら

何か見覚えがあると思ったら236-Dだった

完全グラフなので、ある頂点は残りのすべての頂点と組める。なので頂点の組を総当たりして、選んだ辺の重みの総和について最大値を求めればいい。まず頂点数は偶数とする。

総当たりを上手くやらないとTLEする。なので

• 頂点1を決め打ちして頂点 $2..N$ と組ませる
• 頂点1を頂点2と組ませたなら、頂点3を頂点 $4..N$ と組ませる
• そうでなく頂点1を 頂点 $i$ と組ませたなら、頂点2を頂点1および頂点 $i$ 以外と組ませる

と、まだ辺が無い番号の小さい頂点から順に組ませるとTLEしない。これをDFSで求める

頂点数が奇数なら、あらかじめ頂点 $1..N$ を一個抜いた状態で、同様に求める。 $N=16$ でTLEしないなら $N=15$ で頂点を一個抜いて、実質 $N=14$ を15通り試してもTLEしないので心配無用である。

上記の方法は公式解説2と同じである。公式解説1と同じbit DPで解いてみる。改良済のコードは こちら

• ビットパターンの順序は以下を満たしている
  • ある集合に頂点を2個追加したなら、追加前の重みの総和は既に求まっている(追加後の数は追加前の数より小さいので)
  • ある集合についての追加前の重みの総和を冗長に求めない
  • $N$ が奇数のときを特別扱いしなくて済むので簡単
• 辺の始終点が同じならコスト0なので、何もしないのと同じ。条件分岐で除く必要はない。

コードはこちら

$A$ について、同じ値のものを束ねて出現位置をまとめる。つまりある値 $v$ になる $A$ が $m$ 個あるならその位置 $P = { P_1, ... P_m }, q \in [1,m] s.t. A_{P_q} = v$ を求める。

$v$ の $q$ 番目の出現 $P_q$ について、題意を満たす組み合わせは、

• 開区間 $(P_{q-1}, P_{q})$ が問題の $A_j$
• $P_{1..q-1}$ が問題の $A_i$
• $P_{q..m}$ が問題の $A_k$

に相当する。よってある $v$, $q$ について、 $(i,j,k)$ の組は $(q-1)(P_{q}-P_{q-1})(m-q)$ 個である。 $P$ の先頭と末尾は適宜調整する。これをすべての $v$, $q$ について足し合わせると答えが求まる。別に累積和を使う必要はなかったので、きれいにしたコードは こちら

コードはこちら

9マスについて総当たりで求める。

実装上の工夫として以下がある。改良済のコードは こちら

• ベクトルの要素を一つずつ入力するのに for(auto&& e : vec) するとコードを短くできる
• ベクトル $0..(N-1)$ は std::iota() で作れる。
• 計算量が少ないので、縦横斜めの線を列挙すれば、マスがどの線に属するか全探索してよい。if文だらけになるよりよい。
• まだ見ていないマスは $-100..-92$ などありえない一意の値にする

コードはこちら

二分探索

普通に $W$ を決め打ちして二分探索すればいい。先頭の単語から順に並べていって、実際に $M$ 行に収まるかどうか調べればよい。

• $W$ より長い単語は収まらないので打ち切る
• 単語を追加したときの最下行の幅は、空行なら追加した単語の長さそのもの、それ以外は最下行の幅+追加した単語の長さ+1である。
• 最下行の幅が $W$ を超えるなら、改行して追加した単語だけの行を作る。そうでなければ改行しない。
• $M$ 行を超えたら打ち切る

二分探索の $left, right$ のうち、 答えは $M$ 行に収まる幅の最小値なので $right$ である。なお $right$ を1にするために、二分探索の下限は1ではなく0にする(そうしないとWAする)。二分探索の上限は十分大きな数でよい。

公式解説をみると、実装上の工夫として以下がある。改良済のコードは こちら

• ウィンドウの横幅の最小値は、単語の幅の最大値である。ウィンドウの横幅の最大値は、すべての単語の幅の和と空白の和である。
• すべての単語の前に空白があると考えて、空白分1だけ幅を足しておく。答えより1大きい値が得られる。
• C++20の std::ranges::partition_point が使える。C++20を使うために、Docker Image を ubuntu:22.04 にし、g++は元々11.4.0だが12.3.0もインストールする。
• 述語は無名関数にする。すべての変数をキャプチャしてよい。
• 述語を満たさない最初の数= $M$ 行に収まる最小のウィンドウの横幅を返す。ここから1引く。

コードはこちら

出発時刻から一意

最初のバス停についた時刻から、バス停での待ち時間は一意に求まる。よってありうる可能性を網羅して、クエリに備えればよい。

バスの出発周期でバス停での待ち時間が決まる。制約として $1 \leq P_i \leq 8$ があるので、 $8!=40320$ 通り探索すればよさそうである。しかしこれだとTLEとMLEするので、 $1..8$ の素因数に注目して $8 \times 7 \times 5 \times 3 = 840$ 通りに減らす。これでTLEしない。

あとは最初のバス停に着いたときの時刻 $(q + X) \quad mod \quad 840$ を $0..839$ まで決め打ちして、青木君の家までたどり着くまでの時刻をあらかじめ網羅しておく。クエリに対しては、 $\lfloor (q + X) / 840 \rfloor \times 840$ に出発したとして、 $(q + X) \quad mod \quad 840$ のときの経過時間と $Y$ を足すと到着時刻になる。

上記でACできるが、他の方のコードを見て以下の工夫をすると実装が簡潔になる。改良済のコードは こちら

• 外ループをmod 840, 内ループをバス停にする(私は逆にしていた)
• mod 840の起点は出発地にする(私は最初のバス停にしていた)

それと1..8の最小公倍数は以下で求まる。

std::vector<Num> vec(8);
std::iota(vec.begin(), vec.end(), 1LL);
const Num cycle = std::accumulate(vec.begin(), vec.end(), 1LL, std::lcm<Num, Num>);

コードはこちら

ついに橙diffが解けた。まだ公式解説を読んでいないので、以下の考察には誤りや抜けがあるかもしれない。

足掛け3日間、数時間掛かったが解けた。何段もの考察がいる。

薬について貪欲法、つまり効果 $g$ が大きな薬(あるいは敵を倒せる範囲で小さな薬の組み合わせ)から順に飲むのは、容易に反例が見つかりそうである。薬の効果は倍で効くので、薬を飲んで敵を倒したその先に、稼ぎのいい( $g$ が大きい)敵がいると成長し損ねるからである。よって薬の飲み方を順列総当たりするのが基本戦略である。 $10!=3628800$ なので、探索を早めに打ち切ってならし1回当たりの処理が小さければTLEしなさそうである(一工夫すればそうなる)。

敵を倒した時の成長つまり強さの増加 $g$ は加算なので、倒せる敵が複数いるときにどういう順番で倒すかは成長に関係しない。なので、敵は倒せる(高橋くんの強さ以下)か倒せない(高橋くんの強さを超える)かだけ区別すればいい。

問題文によると、薬がある頂点に高橋くんが初めて訪れたとき高橋くんは薬を飲むことになっているが、薬をその場で飲まず手元に取っておいて構わない。 $g \geq 1$ なので薬を飲めば強くなるか強さが変わらないかどちらかなので、その薬を飲まずに倒せる敵はその薬を飲んでも倒せるからだ。後で述べるように、今の強さで敵を倒せるだけ倒して進めばいい。

薬の強さが $g = 1$ の薬は何もしないのと同じなので無視する。便宜上 $t = 1, s = 0, g = 0$ の敵に置き換える。

上記を考察すると、薬を飲む順番を決め打ちして、頂点1から敵を倒せるだけ倒して、倒せない敵だけになったら倒せるようになるまで薬を飲み、再び倒せるだけ倒す、というのを繰り返す。ある順番ですべての敵を倒せたら Yes 、すべての順番で倒せない敵がいて薬が尽きてしまったら No である。

現在の頂点(初期値は頂点1)から、倒せる敵を探索する。頂点についてBFSで、探索する頂点は敵の強さ $s$ の昇順で優先度キューで管理する。薬は $s = 0$ なので優先度キューでは敵より先頭側に来る。

• 探索する頂点が薬なら手元に保存する。今すぐ飲まない。
• 探索する頂点が敵で倒せる(敵の強さが高橋くんの強さ以下)なら倒して成長し、その頂点から隣に移動できる頂点を移動先に加える。木構造なので親頂点に戻る必要はない。
• 探索する頂点が敵で倒せないなら探索をいったん打ち切る

この探索を中断したとき、すべての敵を倒したか、今の強さでは倒せない敵がいるかどちらかである。すべての敵を倒したら Yes と出力して終了する。

今の強さでは倒せない敵がいるなら薬を飲むのだが、この薬を飲む順序を決め打ちしておく。決め打ちした順序に反するなら薬は飲めないのでその順列では勝てない。薬を一本飲んで強くなり、再度探索を再開する(薬の強さは $g &gt; 1$ に前処理したので必ず強くなる)。再び倒せない敵しか残らないかもしれない(それまで敵を一匹も倒せないかもしれない)が、構わず繰り返す。

なお薬を飲んで成長した結果、高橋くんの強さが最強の敵以上になったら残りの敵は全部倒せるので Yes である。これを忘れると強さがオーバーフローする。

ここまでの考察を実装すると、1 TLE以外はACする。この打開策を考える。上記の反復は、今の強さで敵を倒した範囲を頂点1から徐々に拡大していくのであった。薬を飲む順番を決め打ちして薬を先頭から一定数飲んだときの敵を倒した範囲は、探索順序によらず同じになる。倒せない敵がいるときにまだ飲んでいない薬の集合も同一になる。そうであれば、この範囲の中で $g$ が等しくまだ飲んでいない薬は同一視して構わないということになる。

これより厳しめの条件として、敵を無視して薬同士を木構造のグラフで表現したとき、頂点1からの深さで同じで $g$ が同じ薬は同一視できる。これを利用して順列の数を圧縮できる。 $g$ が等しい薬が $n$ 個あれば順列の数を $1/n!$ にできる。先の 1 TLE を回避してACできる。

この圧縮がなぜ効くのかを考察する。敵の強さは最大 $10^9$ なので、成長しすぎると探索を打ち切れるのがミソである。薬は $g &gt; 1$ で $g = 2$ のとき1024倍にしか成長できない。敵は最大489匹いて全部 $g = 1$ なら489しか成長できない。なので頂点1の隣が $g = 2$ の薬だらけ、薬の先に敵がいるという状況では、順列の総当たりx頂点の総当たりが発生し、計算量が $10! \times Nlog(N)$ になってTLEするだろう。この場合は薬を同一視することを減らせる、というか一通りにできる。この詳しい洞察が必要である。

順列による圧縮が効かない、つまりすべての薬の強さが異なることを考える。このときは $g = 2..11$ なので少なくとも39916800倍強くなる。敵を一匹倒すと強さが1増えるので成長はもっと早く、薬を飲むのと敵を倒すのを交互に繰り返せば少なくとも $(((2 + 1) \times 3) + 1) \times 4) ... = 68588311$ 倍強くなる。

acc = 0
2.upto(11) do |x|
  acc = (acc + 1) * x
end

探索が最も大変なのは、薬を飲んで最後の一匹以外は全部倒したが最後の一匹が $s = 10^9$ という順列ばかりのときである。雑に考察すると、488匹の敵をどの順列でも探索し、薬を9本飲み、最後の一匹に会ったときの強さは、下記から $1780718500 &gt; 10^9$ である。つまり薬を10本飲む前に強さがオーバーフローというかカンストして勝ちが確定する。薬を9本飲む順列は $9! = 362880$ 通り、一順列当たり $Nlog(N), N \leq 500$ の探索コストが掛かるので、C++ならぎりぎり間に合うような気がする(601 ms)。

acc = 488 + 1
2.upto(10) do |x|
  acc = (acc + 1) * x
end

一つ前の例に戻ると、薬の $g$ が一個だけ重複つまり $g = 2,2..10$ のとき、9本だと $356245929 &lt; 10^9$ , 10本だと $3562459300 &gt; 10^9$ なので、10本を飲まないと倒せないが全部の順列 $10!/2!$ を試す前にいずれかの順列で強さがカンストしそうである。薬の $g$ の重複が多ければ順列の組み合わせ数が減るので、強さがカンストしなくても(つまり答えが No でも)順列総当たりでも解ける。

acc = 488 + 1
[2,(2..10).to_a].flatten.each do |x|
  acc = (acc + 1) * x
end

公式解説によると、薬を取る順番を総当たりする代わりにBitDPすることで、計算量を圧縮している。ということは、強さがカンストするのが早いと言う問題設定のために、私の解法がたまたまTLEしなかった可能性がある。

コードはこちら

決め打ちで総当たり

リールの数字を0..9のどれにするか、3本のリールのどの順番で止めるか6通り、計60通りを決め打ちして総当たりすればいい。時刻 $t$ およびそれ以降でいつボタンを押すかを求める。

• リールの文字列を2回繰り返すと、文字列中に文字 d が出る位置を求めるのが楽になる。
• std::string::find(d, pos) で pos およびそれ以降に d が出現する位置が分かる
• 位置が std::string::npos なら文字は出ないので、その組み合わせでは目標を達成するのは不可能である
• 位置は0-based indexである。位置を mod M で管理する。
• 最初に止めるリールは d の位置 $p$ を探す。止めた時点で時間が $p$ 経過している。0秒目で止めたら1文字目で止まるのでこれでいい。
• 二番目以降に止めるリールは $q = (p + 1) \quad mod \quad M$ およびそれ以降の位置 $r$ を探す。このとき $1 + r - q$ だけ時間が経過している。
• 経過時間の和が答えである

公式解説2の通り、3周しても文字がみつからないなら目標を達成するのは不可能と言えれば、少し実装が楽になる。リールを3回繰り返したものを順に std::string::find(digit, cursor+1) で調べる。カーソルを符号あり整数にして cursor=-1 を初期値にすればいい。実装は こちら

コードはこちら

DFS

$A_i$ を基準とした $B_i$ の相対位置が $(X_i,Y_i)$ なら、 $B_i$ を基準とした $A_i$ の相対位置は $(-X_i,-Y_i)$ である。この対称性を忘れないようにする。

相対座標を連想配列に入れ、相対関係をグラフで管理する。後は $(X_i,Y_i)=(0,0)$ を基に、人1からDFSして、相対座標を累積していく。DFSで到達不能な人は undecidable である。

コードはこちら

時間軸

そうめんが流れてくる時間と人が戻ってくる時間をイベント $(time,event)$ として優先度キューで管理する。ある時刻に戻った人はそうめんを食べられるので、人が戻るのをそうめんが流れるより優先する。以下のようにすればいい。

• そうめんが流れてくるのはイベント $(T_i,i),i \geq 1$
• 人が戻ってくるのはイベント $(T_i,-p),p \geq 1$

あとは問題文通りに実装する。列の元の位置に戻ってくる、つまり戻った人は列の最後につくのではないことに注意する(ここを間違えると入力例1が解けないので分かる)。

• 最初は人 $1..N$ が列 std::set<Num> にすべて居る
• そうめんが流れてくるイベントを std::priority_queue<Event, std::vector<Event>, std::greater<Event>> に入れる
• イベントのうち最も時刻が早い(同時刻なら番号が小さい)ものを取得する
• イベントが人なら、列に戻す
• イベントがそうめんなら、列の中で最も番号が小さい人が(もしいれば)食べる。食べた人は列から外れ、時刻 $T_i+S_i$ に戻ってくるイベントに追加する

最後に人 $1..N$ が食べたそうめんの量を出力する。

コードはこちら

累積和

如何にも累積和である。定食の価格は上限がある(最初下限と読み間違えた)ので、主菜の値段を固定したら、ある値段より高い副菜は一律同じ値段とみなすことができる。よって同じ値段とみなさない部分は累積和、同じ価格とみなす部分は定数の掛け算で求まる。

$B_{1..M}$ をソートしてから、累積和 $cumsum_{1..M}$ を求めておく。 ある主菜 $A_i$ について、以下を満たす最大の $j : 0 \leq j \leq M$ を std::upper_bound で求めて、

• $B_j \leq p-A_i$ な副菜については $A_i \times j + cumsum_j$
• $B_j &gt; p-A_i$ な副菜については $p(m-j)$

を足すと $O(Nlog(M))$ で合計が求まる。

コードはこちら

std::bit_width

頂点 $X$ から距離が $K$ ちょうど( $K$ 以下の全てではない)である頂点の数は、 $X$ から葉に向かうか、 $X$ を根に向かったときのきょうだい(sibling node)から葉に向かうか、両方を数えればよい。

根からある頂点 $v$ までの距離は $dist(v) = 1 + \lfloor log2(v) \rfloor$ で求まり、木の高さは $height=dist(N)$ である。C++20が使えるので std::bit_width で求めることができる。

ある頂点 $v$ から葉に向かう方向で距離 $K$ ちょうどの頂点の数は以下の通りである。

• $dist(v) + K &gt; height$ なら無し
• $dist(v) + K &lt; height$ なら $2^{K}$ 。特に $K=0$ なら自分自身なので1個。
• $dist(v) + K = height$ なら $N$ 以下の到達可能なすべての葉。葉の最小値 $left$ は $v$ を繰り返し2倍したもの、葉の最大値 $right$ は $v$ を2倍して1足すのを繰り返した値である。葉の最小値から最大値に含まれる葉の数を、 $N$ が含まれるかどうか気をつけて数えると $max(0,min(right,N) - left + 1)$ となる。

ある頂点 $v$ から根に向かう方向で距離 $K$ ちょうどの頂点の数は、 $v$ を根に向かってたどる。

• $K \leq 0$ なら探索を打ち切る
• $v=1$ つまり根にいるなら探索を打ち切る
• $K=1$ なら親だけなので1個。
• $v$ のきょうだいは $v XOR 1$ なので、きょうだいから葉に向かう方向で距離 $K-2$ ちょうどの頂点の数である。きょうだいから葉に向かう処理は上記と同じなのでまとめる。
• $v$ の親は $\lfloor v/2 \rfloor$ なので $v$ を親に、 $K$ を $K-1$ に置き換えて繰り返す。

上記の合計が答えである。

コードはこちら

和をDPする

タイプ1は普通にDPなのだが、タイプ2つまりボールを除くときに $dp[K+1]$ 以降の値が $dp[K]$ 以前に影響しないことが分からなかった。

タイプ1で $dp[K+1]$ 以降の値を数えなくても困らない。タイプ2のクエリつまりボール $x$ を除く時点で、箱の中にあるボールの部分集合 ${a,b,c}$ を考える。

$c=x$ のとき、

• $a + b &lt; K$ かつ $a + b + x \leq K$ なら、 ${a,b,x}$ についてDPで数えていたので ${a,b,x}$ の寄与分を引く。足す順と逆順に引かないと依存関係が壊れる。
• $a + b \leq K$ かつ $a + b + x &gt; K$ なら、 ${a,b,x}$ についてはDPで数えていないのでDPから引くべき値はない

$a,b,c \neq x$ のとき、そもそもこの ${a,b,c}$ から $x$ を除く状況はない。 $a + b + c \leq K$ でも $a + b + c &gt; K$ でも ${a,b,c}$ について $x$ に関する寄与分はないのだからDPから引くべき値はない。

いずれにしても、 $dp[K+1]$ 以降の値から $x$ について寄与分を引くことはないので、 $dp[K+1]$ 以降の値を保持する必要はない。というより保持すると $1 + Q \times max(x)$ 種類の値があるのでTLEするはずである。これは ${a,b,c}$ だけでなく任意のボールの集合について成り立つ。

この種のDPには珍しく、更新元と更新先をダブルバッファリングすると解けない。引くときは引いた後の値を使うので、シングルバッファで値を持って更新しなければならない。

コードはこちら

総当たり

C++なら総当たりでも105 msで解ける。落ち着いて実装しよう。

ポリオミノの回転は最初に一回だけ行えばいい。90度回転前の $(X,Y)$ が $(3-Y,X)$ に変わる。180度,270度回転も連鎖的に求まる。4重配列、ポリオミノ $1..4$, $Y=0..3$, $X=0..3$, $rotation=0..3$ で、マス $(X,Y)$ にミノがあるかどうか管理する。

ポリオミノの左上の位置は縦横とも $ofs=-3..3$ の7x7通り、回転は4通りである。よって3ポリオミノの位置は $7^6=117649$ 通り、3ポリオミノの回転は $4^3=64$ 通りである。位置 $7^6=117649$ 通りは7進数だと思えばいい、つまり $ofs(i,X)$ をポリオミノ $i$ を相対座標 $X$ に置く意味と定義すれば、 $ofs(3,X),ofs(3,Y),ofs(2,X),ofs(2,Y),ofs(2,X),ofs(2,Y)$ が7進数の各桁に対応する。 $0..6$ から3引いて相対座標 $-3..3$ に読み替える。回転も4進数だと思えばいい。

これを全部試せばいい。試すときは解ではないものを早めに打ち切る。

• 4x4マスからはみ出した位置にミノを置こうとしたら打ち切る
• すでにミノが置かれているマスにミノを置こうとしたら打ち切る
• ポリオミノを3つおいて、すべての16マスが埋まらなければ次の候補に行く
• 答えが見つかったら即 Yes を出力して終わる

なおポリオミノのミノが合計16でなければ、どう配置しても条件を満たさないので探索するまでもない。

コードはこちら

今度は6進数

$K,P \leq 5$ から $P=0..5$ より、6進数5桁の数値7776通りでパラメータを表現する。これを開発案で動的計画法(DP)すればよい。

$DP[i][q]$ を、 $i$ 番目までの開発案の採否を決めた後のパラメータ $q$ を実現するコストとする。実現不可能な場合のコストは無限大とする。初期状態は $DP[0][0]=0$ である。

開発案 $i-1$ までの採否が決まり、6進数最大5桁のパラメータ $q=[q_1,...,q_K]$ のコストが $DP[i-1][q]$ であるとき

• 開発案 $i$ を採用しなければ $DP[i][q]=DP[i-1][q]$
• 開発案 $i$ を採用すれば $DP[i][r]=min(DP[i][r], DP[i-1][q]+C_i)$ である。ここで更新後のパラメータは $r=[min(p,q_1+A_{i,1}),...,min(p,q_K+A_{i,K})]$ である。

$DP[N][r],r=[p,..,p]$ が答えである。コストが無限大なら -1 を出力する。

コードはこちら

遅延評価セグメント木

というのを知らなかったので全く解けなかった。公式解説通りに実装し、 atcoder::lazy_segtree のドキュメント通りに、テンプレートの引数を順に説明する。

1. セグメント木のノードに評価したいものを載せる。ここでは連続する1と連続する0である。隣同士のノードを合併するために巧妙なデータ構造が必要である。詳しくは公式解説を参照。
2. 隣同士のノードを合併する。巧妙にデータを組むと、二つのノードの連続する0/1の最大数から、合併したノードの連続する0/1の最大数を求めることができる。
3. ノードの単位元。幅0の区間を定義する。
4. セグメント木に加える操作の形。ここでは区間の反転を指示する整数にする。
5. セグメント木に加える操作の結果、ノードがどう変わるか。ここでは0/1が1/0に反転する。
6. セグメント木に加える操作を合成する。反転の反転は元通りなのでXORである。
7. セグメント木に加える操作の恒等写像。元通りなので0である。

atcoder::lazy_segtree のテンプレートは自由関数なので、引数に対するメンバ関数に転送する。基本的に値を返すので、コンストラクタ以外は const メンバ関数である。ついでにコンストラクタに explicit をつけておくのがベストプラクティスである。

このようにすると、クエリに基づいて遅延評価セグメント木を操作するコード自体は短い。

コードはこちら

シミュレーション

スライムを合成すると必ず大きくなるので、スライムは合成して減るか、合成できずに減らないかどちらかである。合成できないのはサイズ $S_i$ のスライムが1匹のときだけである。よって以下を繰り返す。

• ある時点でスライムの集合にサイズ $S_i$ のスライムが $C_i$ 匹いることを、サイズの昇順に管理する。 std::set<std::pair<Num, Num>> を使う。
• 集合で最も小さいサイズ $S_i$ のスライムが $C_i$ 匹いたら合成して、サイズ $2S_i$ のスライムを $\lfloor C_i/2 \rfloor$ 匹つくり、集合に加える。
• $C_i$ が奇数ならサイズ $S_i$ のスライムが1匹余るがもう合成する相手はいないので、余りを1匹増やす。なので集合で最も小さいサイズ $S_i$ のスライムは $C_i$ が奇数でも偶数でも必ず取り除く。
• 上記を集合が空になるまで繰り返す。

余ったスライムの匹数が答えである。

公式解説は不変量を用いた興味深い証明である。実装は こちら

コードはこちら

確率DP

時刻 $t$ ちょうどに新しく曲を再生しはじめるか、それとも前の曲がまだ流れているので待つのかは、前の曲 $i$ が $t-Ti$ ちょうどに始まったかどうかで決まる。これを引くDPで更新する。 $DP[t][i]$ を、時刻 $t$ ちょうどに曲 $i$ を再生開始できる確率とする。 $0 \leq t \leq X$ , $1 \leq i \leq N$ である。

• 時刻0以前に曲は掛からないので、便宜上 $DP[t][]=0 \quad for \quad t &lt; 0$ とする。
• 時刻0にはどの曲も等しい確率で掛けられるので、 $DP[0][]=1/N$ とする。
• 時刻 $t$ に新たに曲を掛け始められる確率は上記の説明から、 $p=\sum_{i=1}^{N} DP[t-T_i][i]$ である。このとき次の曲を掛けられる確率はそれぞれ等しいので $p/N$ である。つまり $DP[t][]=p/N$ である。

時刻 $X+0.5$ に曲1が再生されている確率は、曲1を掛け始めた時刻が $[X-T_i+1,X]$ のときなので、 $\sum_{t=X-T_1+1}^{X}DP[t][1]$ の和が答えである。

基本的に上記であっているが、公式解説によると $1/N$ は最後にまとめてする方が計算時間が短い。C++なら毎回 $1/N$ しても51 msecで解けるが、問題によっては注意した方がいい。

コードはこちら

場合分けが多すぎて何をしているか分からなくなって諦めた。公式解説2を読んでようやく理解した。一般的に以下の処理をするとコードが簡潔になる。

• どれかを原点に平行移動する
• 残りのどれかを第一象限に固定するよう反転する
• XとYの処理を対象にして、引数を入れ替えることで両方調べる

コードはこちら

E問題のヒント

編集距離(レーベンシュタイン距離)を正確に求める必要はない。もっと軽い実装をする。

• 文字列長が2以上異なるなら、 $T^{'}$ は $T$ に戻せない
• 文字数が一致する場合は、同じ位置で相異なる文字が1個以下なら $T^{'}$ は $T$ に戻る。2個以上なら戻せない。

文字数が1だけ異なる場合、短い方の文字列を $S$ 、長い方の文字列を $L$ とする。先頭から順に比較する。

• カーソルを $S_i=1$, $L_i=1$ で初期化する
• $S[S_i] = L[L_i]$ なら $S_i, L_i$ ともに一個進める
• $S[S_i] \ne L[L_i]$ なら $L_i$ だけ一個進める
• これを $S_i \leq |S|$ かつ $L_i \leq |L|$ の間繰り返す

$S_i = |S|$ かつ $|L|-1 \leq L_i \leq |L|$ なら $T^{'}$ は $T$ に戻る。そうでなければ戻らない。 $L$ の先頭 $|S|$ 文字が $S$ と一致することがあるのに注意する(入力例3)。

公式解説2を見て直したコードが こちら 。 $T^{'}$ を $N$ 回コピーするとTLEするので参照渡しにする。

コードはこちら

TLEに注意。

$N!$ が大きいので、 $S$ のすべての順列組み合わせを調べるとTLEする。なので制約条件として平方数の最大値で制約する。 $S$ を並べ替えてできる数は $10^{14}$ 以下であり、その平方根は $i=0..10^7$ なのでそのような $i$ を調べる。

$S$ を降順に並べ替えた $T$ を数値として解釈した $d$ が、平方数の最大値である。よって、それぞれの $i=0..{\sqrt{d}}$ について先頭0埋めした文字列表記を作り、それが $S$ の並び替えと一致するかどうか調べればよい。 $S$ をあらかじめ昇順か降順に並び替えておき、 $i$ を昇順か降順に並び替えて文字列を一致比較する。これでもC++なら1秒掛からないのでTLEしない。

0埋めにマニュピュレータを使ったが、snprintfの方が速いかもしれない。

std::ostringstream oss;
oss << std::setfill('0') << std::right << std::setw(n) << x;

コードはこちら

最長共通部分列ではなかった。

最長共通部分列(LCS: Longest Common Subsequence)は動的計画法で求まるが、空間使用量と計算量が二つの文字列の長さの積なので、今回の問題ではTLEかMLEする。なのでもっと軽い方が必要である。

C問題を応用して、 $T$ を先頭から一文字ずつ見ていき、 $S$ に最大何文字含まれるか数える。同様に $T$ を反転させた文字列 $revT$ が $S$ を反転させた文字列 $revS$ に最大何文字含まれるか数える。

$S_i,S_j$ について題意を満たす物は、文字列長 $L=0..|T|$ について、 $S_i$ が $T$ の先頭 $L$ 文字ちょうどを部分文字列として含み、 $S_j$ が $T$ の末尾 $|T|-L$ 文字以上を部分文字列として含むものである。

前者は $T$ の先頭 $L$ 文字ちょうどを部分文字列として含む $S_{1..N}$ の数として連想配列に記録する。後者は $S_{1..N}$ が $T$ の末尾何文字を含むか数えて昇順に並び替え、ある文字数以上の要素がいくつあるかを std::lower_bound で求める。

std::lower_bound を使わず、 $S_{1..N}$ が $T$ の何文字以下を含むか累積和を求めると $O(log(N))$ 分速くなる。少しややこしい。そのように改善した実装が こちら

コードはこちら

二分探索だとは思わなかった。

深さ優先探索をすると組み合わせ、パスが多すぎてTLEしそうな場合は、二分探索にすると解けることがよくある。ここでは始点からのコストを最大化する。枝の終点は始点より番号が大きいと決まっているので、実は始点ごとに到達可能な隣の終点のコストを更新すればいい。終点と $b$, $c$ をまとめてタプルにする。連想配列にするとTLEする。

実装方針としてはこれだけだが、実装の細部が繊細で少しでも間違えるとWAとTLEする。他の方の実装を参考に何度も書き直した。