コンテストに参加した教訓をまとめていきます。

トップページへ 前のABC 参加記へ 次のABC 参加記へ

コンテスト41回目である。A,B,C,Dの4完である。E問題が全く分からず、2時間以上掛けて自力ACしたが遅かった。

コードはこちら

問題文通りに条件分岐を上から書く。

Rなら一行で書ける 。

cat(365+lubridate::leap_year(as.numeric(readLines("stdin", 1))))

コードはこちら

値 $A$ と添え字 $i$ を組にした $(A_i,i)$ を昇順にソートして、二番目に大きい要素を返す。公式解説は、 $A$ がそれぞれ相異なることを利用している。

コードはこちら

全員の交通費の和が $M$ 以下なら、交通費補助額に上限があろうがなかろうが全員の交通費を払える。このときは infinite を出力する。

$x$ を決め打ちして二分探索すると求まる。

コードはこちら

見るからに動的計画法である。

$i$ 番目およびそれまでにグー、パー、チョキで勝った回数をそれぞれ $DP[i][R,P,S]$ とする。 $i$ 番目の手について、 $DP$ を以下の通り遷移する。ここで青木君はグー $R$ を出すことにするが、それ以外の場合は手を読み替える。

• 高橋くんがチョキ $S$ を出すと負けるのでチョキは出せない。 $DP[i][S] = - \infty$ とする
• 高橋くんがグー $R$ を出すと負けないが勝った回数は増えない。同じ手は二度出せないので、 $DP[i][R] = max(DP[i-1][P], DP[i-1][S])$ とする
• 高橋くんがパー $P$ を出すと勝った回数が1増える。同じ手は二度出せないので、 $DP[i][P] = 1 + max(DP[i-1][R], DP[i-1][S])$ とする

$DP$ の取りうる値の最大値が答えである。じゃんけんの勝ち負けを関数にするのに手こずってしまった。英語の問題文には、じゃんけんの規則が書いてある。

コードはこちら

2時間15分ちょっと掛かってしまった。問題の構造を理解し間違えたのが敗因である。

すべてのビットについて独立に問題を考える。区間和であることから $A$ には順序があり順不同ではないし、 $A_j$ ではなく $A_i \oplus ... \oplus A_j$ の区間和に意味がある。このことを見抜けなかった。そもそも区間和ではなく連続しなくていい $A$ の和なら組み合わせなので答えが64-bitに収まらない。

2時間掛けてACした先のコードはそもそもこれで正しいのかどうか分からない。公式解説2を読んで実装したコードはこちら 。

コンテスト42回目である。A,B,C,Dの4完である。E問題は方針見えたが実装が進まず、2時間近く掛けて自力ACしたが遅かった。

コードはこちら

既に得票が過半数 $T,A \geq \lceil N/2 \rceil$ なら Yes 、そうでなければ No である。

コードはこちら

問題がとてもややこしい。13分近く掛かった。

要するに文字列を右90度回転して、回転後の文字列について

• 末尾の空白を取り除く
• 末尾以外の空白を * に置き換える

とする。回転後の文字列は長さ $N$ の空白だけの文字列を初期値にすると、条件判定が楽になる。

公式解説にある通り、空白の代わりに * を使う方が簡単である。

コードはこちら

B問題の後にこの問題がきて、3分掛からずに解けたので救われた。

key が count(key) 個あることを連想配列に載せて、連想配列のエントリ数が答えである。個数が0になった key を連想配列から削除する。 std::multiset を使おうとして思いとどまった。

公式解説はフラットな配列を用いている。

コードはこちら

多次元累積和の理解度テストである。

$Lx_{i}, Rx_{i}, Ly_{i}, Ry_{i}, Lz_{i}, Rz_{i}$ から成る立方体を考える。最初に三次元累積和を、 $z,y,x$ 座標について求める。これでクエリに $O(1)$ で答えられる。

二次元累積和の延長で、右端から座標を奇数個変えたものを引き、偶数個変えたものを足す、というのを繰り返す。具体的には、累積和のインデックスについて以下の通りにする。左端を1引くのを忘れない。

• $(Rx_{i}, Ry_{i}, Rz_{i})$ を足す
• $(Lx_{i} - 1, Ry_{i}, Rz_{i})$, $(Rx_{i}, Ly_{i} - 1, Rz_{i})$, $(Rx_{i}, Ry_{i}, Lz_{i} - 1)$ を引く
• $(Lx_{i} - 1, Ly_{i} - 1, Rz_{i})$, $(Rx_{i}, Ly_{i} - 1, Lz_{i} - 1)$, $(Lx_{i} - 1, Ry_{i}, Lz_{i} - 1)$ を足す
• $(Lx_{i} - 1, Ly_{i} - 1, Lz_{i} - 1)$ を引く

コードはこちら

マンハッタン距離なので45度回転だろうと思い違いしたままコンテストが終わってしまった。45度回転が要らないことが分かった後も実装に手間取り、結局解くまで2時間掛かった。

$X$ 座標と $Y$ 座標は別々に考えてよい。 $X$ を昇順にソートし、最小値を原点(0)として、それ以外の頂点までの距離の累積和を取る。ソート済の添え字で距離の累積和を $CX_i$ とする。 $Y$ も同様に累積和を $CY_i$ とする。

$x$ 座標の探索範囲は、 $[min(X)-D, max(X)+D]$ で十分である。制約からこれでTLEしない。 $y$ 座標の探索範囲も同様に $[min(Y)-D, max(Y)+D]$ にする。

$x$ 座標を全探索する前に、 $y$ としてありうる値を求めておく。 $y = [min(Y)-D, max(Y)+D]$ について、各点から $y$ までの距離の和 $s$ は、以下の通り求まる。

• $y < Y_i$ となる頂点数 $M$ を求める。これは std::ranges::upper_bound で求まる。
• $M = N$ なら $y$ の値が大きくはみだしているので、 $s = N \times (y - min(Y)) - CY_{N}$ である
• $M = 0$ なら $y$ の値が小さくはみだしているので、 $s = N \times (min(Y) - y) + CY_{N}$ である
• $0 < M < N$ なら $y$ より値が大きな頂点は $CY_{N} - CY_{M} - (N - M) \times (y - min(Y))$ 、 $y$ より値が小さな頂点は $M \times (y - min(Y)) - CY_M$ 、これらの和が $s$ である。

それぞれの $y$ について $s$ を求めると、ある $s \in [0..D]$ となる $y$ が何通りあるか求まる。 $y$ について距離 $s$ 以内で題意を満たすなら距離 $s+1$ 以内でも題意を満たすので、 $s$ の累積和 $CS[0..D]$ を取る。この意味は後で分かる。

ほぼ同じことを $x$ について全探索する。 $x = [min(X)-D, max(X)+D]$ について、各点から $y$ までの距離の和 $t$ は、 $y$ と同様に求まる。距離の残り $W = D - t$ が $W \leq 0$ なら、その $x$ に対応する $y$ は $CS[W]$ 通りある。ここで $W$ が題意を満たすなら $W - 1 \geq 0$ も題意を満たすので、累積和 $CS$ が必要だった。

すべての $x$ についての、 $W$ の和が答えである。

とにかく累積和を取る処理が多い。と思ったら公式解説は尺取り法ですっきりしたコードである。確かに公式解説のコードなら早く 実装 できるし、私の実装は時間が掛かりすぎる。

コードはこちら

ソートしてDPだと思ったらやっぱりそうだった。

一次方程式 $f(x) = Ax + B$ は以下の行列演算 $Mv$で表現できる。

$$ M = \begin{pmatrix} A & B \\ 0 & 1 \\ \end{pmatrix} v = \begin{pmatrix} x \\ 1 \\ \end{pmatrix} $$

二つの行列演算の積は可換ではないので、どちらを先に掛けるかが重要である。

$$ L = \begin{pmatrix} A & B \\ 0 & 1 \\ \end{pmatrix} , R= \begin{pmatrix} C & D \\ 0 & 1 \\ \end{pmatrix} $$

の $LR, RL$ はそれぞれ

$$ LR = \begin{pmatrix} AC & AD + B \\ 0 & 1 \\ \end{pmatrix} , RL = \begin{pmatrix} CA & CB + D \\ 0 & 1 \\ \end{pmatrix} $$

なので、 $x=1$ のとき $LR > RL \Leftrightarrow B(1-C) > D(1-A)$ である。後から掛ける方が答えが大きくなる行列を後で掛けるような順序で行列をソートする。これを $M_{i=1..N}$ と置く。

行列をソートしたらDPする。 $DP[i=1..N][j=0..K]$ は、 $i$ 番目までの行列を $j$ 個掛けた時の行列である。初期値は恒等行列にしておく( $- \infty$ だと上手くいかない)。

$DP$ の更新式は $DP[i+1][j+1] = max(DP[i+1][j+1], M_{i+1}DP[i][j])$ として、 $max$ を $Mv$ つまり $A+B$ と定義する。最後に求まった $DP[N][K]$ の $A+B$ が答えである。

ソートの不等号の定義とDPの初期値に気を使うが、基本方針は見えていた。これはコンテスト中に獲りたかった。公式解説には、答えは行列の掛け方で決まるので $f_{i}f_{j}(x)$ と $f_{j}f_{i}(x)$ に依らないと書いてある。この点をコンテスト中に悩んでしまったのでE問題に戻ってしまったのが敗因である。先の $LR$ を考えると $LRx = ACx + AD + B, RLx = ACx + CB + D$ なので確かにそうなる。

コンテスト43回目である。A,B,C,Dの4完である。E問題は方針は見えたが実装が進まず、2時間近く掛けて自力ACしたが遅かった。F問題は15分で解けたがコンテスト後では手遅れで、解く問題を間違えた。

コードはこちら

入力例がどうしても合わなくて、先にB問題を解いた。

$B < C$ なら起きているのは、 $[0,B]$ または $[C,24]$ である。 $B > C$ なら起きているのは $[B,C]$ である。よく考えたら当たり前で、条件が or にすべきところ and と書いた間違いだったのだが、一度混乱すると間違いになかなか気が付かない。

公式解説のユーザ解説に不変量を使った解き方がある。確かに日付が変わるところは、起きているか寝ているかが不変量である。

コードはこちら

A問題と同様、ややこしく考えるとますます分からなくなる。A,B問題併せて10分43秒掛かっている。

やりかたは色々ありそうだが、素直な方法は . の前後で文字列を分割して、前を整数部、後を小数部にする。小数部は末尾から0が続いている限り削除する。小数部が無くなれば整数部だけ出力し、小数部が残っていれば整数部 . 小数部を出力する。この方針ですっきり再実装すると このよう になる。

公式解説を読むと、入力は必ず小数なので、整数部と小数部を分けなくてもよさそうである(末尾の . は除かなければならない)。

公式解説の方法で文字列表現の丸め誤差が問題になりそうなら、 boost::multiprecision::cpp_dec_float_100 を使う 。

コードはこちら

制約から $5^8 = 390625$ 通りしかないので全探索する。

$0..5^8-1$ を全探索し、5進数表記すると長さ $N$ の整数列が得られる。整数列の要素が0..4なので、1..5に読み替える。あとは題意を満たせば整数列を出力する。

この方法は公式解説の方針2と同じである。

コードはこちら

$modM$ を数え上げればいいと直観的に分かる。出発する休憩所が休憩所1のとき、累積和 $C(i) = (\sum_{j=1}^{i} A_j)$ として、 $C(i) modM = 0$ となる $C$ の数が答えである。具体的には $R[i=0..(M-1)]$ を、 $C(i) mod M = i$ となる要素数とし、出発する休憩所が休憩所1のとき $R[0]$ が答えである。以下 $R$ の添え字は $modM$ で考える。また $S=C[N-1]$ と置く。

出発する休憩所を時計回りに一つ移る。出発する休憩所が休憩所2のときに、先の累積和を再利用することを考える(そうしないとTLEするので)。休憩所2から休憩所1への要素を削除するために、 $R[A_1]$ を1減らす。次に休憩所Nから休憩所1への要素を追加する。 $S$ に $A[N]$ を加え、 $R[S]$ を1増やす。出発する休憩所が休憩所2のとき $R[C(1)]$ が答えである。

同様に休憩所 $i$ に移る。 $R[C(i-1)]$ を1減らし、 $S$ に $A[i-2]$ を加え、 $R[S]$ を1増やし、 $R[C(i-1)]$ が答えである。

公式解説のユーザ解説2は一周超えを用いてもっとすっきり表現している。

コードはこちら

2時間超えの泥沼だった。方針は見えているのに、いつまで経っても実装が終わらなかった。

基本方針は有向グラフのサイクル分解である。 $A_{X_i}$ を $B_i$ にするということは、 添え字だけみれば $X_i$ を $i$ にするということである。この向きが分からなくなったままコンテストが終わってしまった。

$X_i$ から $i$ に向かう辺について有向グラフを作る。この有向グラフを強連結成分分解すると、サイクルとそれ以外に分かれる。この有向グラフはサイクルを回るか、サイクルから出ていくかどちらかである。サイクル外に入ることはない。これは $X_i$ から $i$ への対応が一対多である(多対一ではない)ことから言える。この理解が逆だったために解けなかった。

サイクル $C$ の頂点については、 $|C| mod K$ 回前の操作を反映する。よって頂点 $v$ からサイクルを逆向きにたどり最初は頂点 $u$ から来たと分かると、操作結果 $P$ について、 $P[v] = A[u]$ と解る。この逆向きにたどるのがややこしい。

サイクル外の頂点についてはそのまま求めるとTLEするのでDFSする。それぞれのサイクル $C$ の頂点 $v \in C$ を起点にDFSする。

• 今注目している頂点を $u$ とする。初期値は $u = v$ とする。
• サイクルの頂点は探索しない
• $v$ から $u$ へのパス $p$ を再帰の引数に持つ。DFSで葉に向かうときはパス $p$ の末尾に $u$ を加え、出た後にパスの末尾から $u$ を除く。
• $|p| \geq k$ なら、パスの後ろから $k$ 番目の頂点 $w$ の値が操作結果になる。 $P[u] = A[w]$ である。
• $|p| < k$ なら、サイクルを $v$ から $k-|p|$ 回逆向きにたどる。たどった先の頂点が $w$ なら、 $P[u] = A[w]$ である。

公式解説1はダブリングだった。 $N^2$ 要素の表が必要と勘違いして諦めてしまったのだが、ダブリングなら $Nlog(N)$ の表に収まる。このことに気が付かなかった。グラフよりもはるかに簡潔な コード で解ける。

公式解説2は (オフライン版の) level ancestor を用いた解法で、私の解法とほとんど同じである。公式解説2はfunctional graphのそれぞれの弱連結成分がサイクルをちょうど一つずつ持つことを利用しているが、実質的には上記と同じである。私の発想自体はよかったが実装力が足りなかった。

コードはこちら

E問題をコンテスト後に解いて、続いてF問題を解いたら15分3秒後に解けてしまった。何度目か分からないが、E問題に熱中するあまり解く問題を選ぶのを間違えた。参加者にとっての問題の難易度と自分にとっての問題の難易度がまた逆転していたのだが、それでも解く問題は上手く選ぶ必要がある。あるいはF問題を解けないという思い込みを捨てなければならないのだが、本番でF問題を解けないと解く自信がないという堂々巡りになっている。

$N$ が小さければ、整数列に現れる数値 $i=1..N$ について、整数列の添え字 $j=1..N$ に沿って登場回数の累積和を取ればいい。そうすればクエリの数と、整数列に現れる数値に種類に比例した回数で答えが求まる。しかしここでは $O(N^2)$ となってTLEする。

そこで累積和を高速に取る方法を考える。セグメント木に載せて区間和を取れば速そうである。セグメント木の添え字 $i$ に載せるものは $A_i, B_i$ そのものではなく $1..N$ に対応する乱数にすれば、ほぼ確実にACする。Zobrist Hashの発想である。自力で思いついたが、コンテスト中に提出しなければ得点はもらえない。

素数で割るのではなく、乱数の範囲を $1..2^{64}-1$ にしてもハッシュ衝突せずACできた。このことは公式解説2に説明がある。

コンテスト44回目である。A,B,C,D,Fの5完である。前回はすっ飛ばして泣いたF問題に今回は救われた。G問題は時間はあったが全く見当がつかなかった。

コードはこちら

回転操作なので std::rotate で書ける。0-based indexingで、元々の山の上から $N-K$ 枚目のカードが一番上に来る。公式解説にも std::rotate が紹介されている。

コードはこちら

問題文通りに実装してもTLEしない。 $A$ に $0$ を含めない、 $A$ の要素数が2未満になったら打ち切ることに注意する。

コードはこちら

入力例が合わずに焦った。

$T$ と、いま目の前にいる敵 $i$ の体力 $H_i$ が決まっているとする。敵を倒した時点で $T$ が $U$ に変化することを考える。 $U$ を決め打ちして二分探索すれば $U$ が求まる。 $i$ を1増やし、 $U+1$ を $T$ にして繰り返す。この状況を正確に読み取るのに苦労した。

$x \in [T,U]$ を固定したとき、敵に与えるダメージは以下の合計 $S_{U}$ である。

• 少なくとも $x$ 1種類について1ダメージを与えるので、 $U - T + 1$
• $x$ が3の倍数なら与える追加のダメージ $2 \times ( \lfloor U / 3 \rfloor - \lfloor (T - 1) / 3 \rfloor)$

$S_{U} < H_i$ を条件に二分探索すると、この条件を満たさない最小の $U$ が得られる。このような $U$ で敵を倒せる。

公式解説は、 $T$ 3セットで体力を5減らせることを利用して計算を簡略化している。たしかにこのように 実装 できるがややこしい。

コードはこちら

C問題が解けない焦りから、Auxiliary Treeのコードをよく理解しないまま適用し、入力例の一部は通ったがWAの山を築いた。というか入力例さえ合っていなかった。勇み足すぎるが、C問題が解けない、D問題も解き方が思いつかないと焦りすぎた。これがなかったらパフォーマンスはもっと良かったが、連敗中で自信が無いと負のスパイラルに入る。

解つまり $V$ の頂点を含み頂点数が最小の木の頂点集合を $S$ とする。初期値を $S = V$ とする。

$V$ が空でないので、 $V_1$ を根とする木を考えてDFSする。DFSの途中で $V$ に属する頂点があったら $S$ に加える。加えるタイミングは、木の葉から根に戻るタイミングである。 ${V_1, U_1, U_2, V_i}$ というパスがあったときに、 $U_2, U_1$ の順に $S$ に加える。より正確には頂点 $U$ の部分木に $V$ に属する頂点が一つ以上あったら $U$ を $S$ に加える。

DFSなので頂点をたどる回数は $O(N)$ である。

実は典型90-035のAuxiliary Treeのコードに1足したものが 正解 だった。だとすればほぼ正解だったのだが、わざわざ間違ったコードに変えて提出したのは、やはりC問題を解けない焦りからどうかしていた。

コードはこちら

久しぶりにGrundy数をABCで見た。ARC 水diffを最近解いたので、今回のような典型的なGrundy数問題に対処できた。もう少しGrundy数の問題を解く方がいいだろう。鉄則本に載っているかつARC 水diffで頻出かつABC 水diffであまり見ないアルゴリズムと言えば、Grundy数と不変量なので、不変量も鍛えた方がいいかもしれない。

始めは約数の数だと思って入力例が合わなかったので素因数の数に切り替えたらACした。確かに1以外で割るとき、最大で残り何回割れるかは素因数の数である。素因数1個で割れば残り回数が1減る。

そうと解ればこの問題はNimとGrundy数であり $A_i$ の素因数の数を $C_i$ とすれば、 $\oplus A$ が0なら後手必勝、そうでなければ先手必勝である。

ついにコンテスト中にF問題を正解できた。F問題を読む時間がもったいないと焦って問題文を読み忘れる、という癖をおわりにしたい。

コンテスト中には48分あったがなすすべが無かった。今日も6完は遠かった。

問題文の太字の部分が重要な制約である。クエリ当たり乗算は60回しかできない。こういう制約の与え方はさっぱり分からなかった。公式解説1を読んで、セグメント木を使った解法は こちら 。セグメント木には、 $A$ を値の可算、 $B$ を値が2未満かどうかのlogical ANDを載せる。

クエリ1,2は $A,B$ およびそれらのセグメント木を更新する。クエリ3は、まず公式解説通り、答えの初期値を $S = A[l]$ にする。 $l$ を1増やしてから以下を繰り返す。

• $l \geq r$ なら終了する。解説にある通り60回ループすると終了する。
• $l$ 以上で $B < 2$ を満たす範囲の右端 $p \geq l$ を見つける。 segtree:max_right を使う。
• $S$ に $A[l..min(r-1 , p)]$ を足す
• $p < r$ なら $max(S + A[p], S \times B[p])$ で $S$ を置き換える
• $l$ を $p + 1$ にする

遅延セグメント木に載せようとして失敗したのだが、公式解説2の通り一次関数を載せて合成すればいいらしい。私にはとてもコンテスト中に完成させられる気がしない。

コンテスト45回目である。A,B,C,Dの4完である。E問題は制約を見落として解けず、F問題を読んだが分からなかった。

コードはこちら

$A \leq B$ とする(そうでなければ $A,B$ を入れ替える)。

$(x = A-(B-A), A, B)$ , $(A, x = (A+B)/2, B)$ , $(A ,B, x = A+(B-A))$ が等差数列の候補なので、 $x$ を重複なしで数えると答えになる。ただし $(A+B)/2$ が整数でない場合は数えない。

コードはこちら

左手と右手はそれぞれ独立に考えてよい。

左手で押す鍵盤だけ考え、その座標を $L = (L_1, ..., L_M)$ とする。 $|L| \leq 1$ なら疲労度は0である。 $|L| > 1$ のときは $L$ の隣同士の要素の絶対値の差を取って足す。つまり $\sum_{i=1}^{|L|-1} |L_{i+1} - L_{i}|$ が左手の疲労度である。

右手についても同様に求め、両手の疲労度の和が答えである。

コードはこちら

$A$ の差分 $D = (D_1 = A_2 - A_1, ... , D_{N-1} = A_{N} - A_{N-1})$ を取る。同じ差分 $D$ が続けば $A$ で等差数列を構成でき、そうでなければ等差数列を構成できない。

よって $D$ をランレングス符号化し、それぞれのラン長を $L_1, ... L_M$ とする。ラン長が $x > 0$ のとき、 $A$ の連続 $x+1$ 個の等差数列(差が $x$ 個)を1通り、 $A$ の連続 $x$ 個の等差数列を2通り、以下同様にして $A$ の連続 $2$ 個の等差数列を $x$ 通り作れる。これをまとめると $x(x+1)/2$ 通りである。

これらをすべてのランについて足し、長さ1の数列は常に等差数列なので $N$ を足すと答えである。

コードはこちら

いかにもDPである。

これまで倒したモンスターが偶数か奇数かで場合分けして状態遷移する。 $DP[i][jMod2]$ を、 $i$ 番目までのモンスターを相手にし、それまで $j$ 体倒したときの経験値とする。初期値は $DP[0][0] = 0, DP[0][1] = - \infty$ とする。

以下の状態遷移を行う。

• $DP[i+1][1] = max(DP[i][1], DP[i][0] + A_i)$ つまり逃がすと経験値が得られず、倒したら $X$ 経験値を得る。
• $DP[i+1][0] = max(DP[i][0], DP[i][1] + A_i + A_i)$ つまり逃がすと経験値が得られず、倒したら $X + X$ 経験値を得る。

答えは $max(DP[N])$ である。

コードはこちら

制約を見落とした。

$Q$ が大きいことに気を取られて $K \leq 5$ を見落とした。 $K$ が大きい時の解法を探して答えが出ず、F問題も解けず、解ける問題を落としてしまった。

$K$ が小さいので、端の渡り方は $K! \times 2^K = 3840$ 通りしかない。クエリを全部処理しても11520000通りである。それに比べてワーシャルフロイド法の計算は $N^3$ で 64000000回であり、ワーシャルフロイド法が間に合うならクエリも間に合うと予想できる。実際 1316ms でACする。

クエリを読む前に、ワーシャルフロイド法で任意の2頂点間の距離を求める。初期値は島自身への距離が0、直接橋でつながっている島は複数ある橋の最短時間、それ以外の島は無限大時間とする。

つぎに各クエリを独立に処理する。すでに述べた通り、 $B$ をどの順で渡るかの順列組み合わせすべて、端を $U$ から $V$ に行くか $V$ から $U$ に行くかのビット全探索を行う。 $B$ で与えられる橋は必ず1回渡るのでそのコストを最低値として、頂点1から最初の橋、橋から橋、最後の橋から頂点Nへの時間を足す。これらの最小値が答えである。

コードはこちら

全く分からないので解説ACした。

あるコインを拾った後に次のコインを拾うという前後関係を結べばいいのだが、上手い方法がみつからずTLEした。解説にあるようにLISで求める。

解説を言い換えると、ある位置 $(r,c)$ にあるコインを拾うならその前に拾えるコインは、 列 $1..c$ について、同じ行または上にある行である。前に拾えるコインのうちこれまで拾った数が最もコインを選ぶ。なお左上には必ずコイン $0$ が、右下には必ずコイン $N+1$ があるものとする。

ここで前のコインを選ぶのがLISだが、相変わらずLISの解き方が分からないのでセグメント木で解いた。

• 区間maxを返すセグメント木 $T$ を作る。要素数は $W$ で、要素はある列においてそれまで拾ったコインの数である。
• 今回はLISの長さだけでなくLISを再現するので、添え字 $i=0..(N+1)$ のコインの前に拾ったコインの添え字 $prevs[i]$ 、ある列で最後に拾ったコインの添え字 $cols[1..W]$ を管理する。
• 初期値は左上のコインを拾った状態である。 $T[] = 0, T[1] = 1$ , $prevs[] = -1, prevs[0]=-1$ , $cols[] = -1, cols[0]=0$ とする。

コイン $i=0..(N+1)$ が $(r,c)$ にあるとき、LISを求めながら上記のデータを更新する。

• LISを構成する、これまで拾った数が最も多いコインが $v$ 個であるとき v=segree.prod(0,c+1) で求まる
• $v$ となる最左列の添え字 $pos$ は 、 pos=segtree.max_right(0, x < v) で求まる
• 前に拾うコインは $prev = cols[pos]$ である
• このコインの前に $prev$ を拾うことを、 $prevs[i] = prev$ で設定する
• 列 $c$ でこのコインを拾ったことを、 $cols[c] = i$ で設定する
• 拾ったコインの数を segtree.max_right(c, v+1) で設定する

コイン $N+1$ から $prevs[N+1]$ を逆にたどることで、拾うコインの逆順が求まる。正順に戻してパスを出力する。

コンテスト46回目である。A,B,C,D,Eの5完である。E問題を苦しみつつACしてhighest、F問題を読んだが分からなかった。

コードはこちら

$(L,R)=(1,0)$ , $(L,R)=(0,1)$ 、それ以外で分岐して文字列を出力する。

コードはこちら

$A_{i,j}$ を読み込んだら $A_{i,j}, A_{j,i}$ の両方に設定する。 $A_{i,i}$ があるので忘れずに読みこむ。

後は $p=1$ を初期値として $p = A_{p,1..N}$ と状態遷移する。

コードはこちら

先週は制約を見落として泣いたので、今週は制約をよく読んだ。

$N = |S|$ と置く。 $S$ の文字を1文字書き換えてできる文字列は最大 $N$ 通りある。よって $S$ の文字を1文字書き換えてできる文字列群のうち、辞書順で最小のものを選んで遷移する。

1回遷移するごとに、 $S$ と $T$ と不一致な文字は一つ減るので最大 $N$ 回遷移すると $S=T$ になる。よって文字の置き換えは $O(N^2)$ 回、文字列をコピーするコストが $O(N)$ なので、計算量は $O(N^3)$ である。これを見抜いてC問題を7分7秒で解いたので、E問題を解く時間を捻出できた。

コードはこちら

データ構造はすぐ浮かんだので丁寧に実装した。ここで時間を稼いだのでE問題が間に合った。

std::vector<std::set<Num>> 型の変数を用意して、列 $r$ にある壁を $Rows[r]$ 、行 $c$ にある壁を $Cols[c]$ で保持する。あとは問題文通りに実装する。

• $(r,c)$ に壁があれば、列と行から除く。壁 $(r,c)$ は $Rows$ と $Cols$ の両方あるか、両方とも無いかどちらかなので、前者があれば後者の存在チェックは省略できる。
• そうでなければ $(r,c)$ の左右の壁を探して除く。 $r$ 行に注目する。 Rows[r].lower_bound(c) を使って $c$ の直後の列を見つけ、イテレータを一つ前にして $c$ の直前の列を見つける。無効なイテレータをアクセスしないように気を付ける。 $Rows$ から壁を除いた後に、 $Cols$ からも壁を除く。
• 同様に $(r,c)$ の上下の壁を Cols[c].lower_bound(r) で探して除く。

4方向をコピペで作ったコードは実装がややこしく、イテレータ周りの未定義動作を踏んでしまったが、落ち着いて捌いた。コピペを少し減らすと こうなる 。公式解説は std::prev を使い、壁の数は最後にまとめて数えることでコードを短くしている。

コードはこちら

C,D問題で稼いだ時間で解いた。

DPだと分かるが、累積和をいい感じに連想配列に載せないとTLEしそうだと分かる。

前処理として、累積和 $C_i = \sum_{j=1}^i A_j$ を求めておく。便宜上 $C_0 = 0$ とする。 $A_{i=1..N}$ を右端とする連続部分列として取りうる組み合わせの数を求める。

$l < i$ について、 $[l,i]$ を連続部分列として取れる条件は $\sum_{j=l}^{i} A_j \ne K$ のときである。いいかえれば $C_i - C_{l-1} \ne K$ のときである。これを $l=1..(i-1)$ について逐次的に求めるとTLEするので高速化する。

$A_1$ から $A_j$ までの連続部分列の和は $C_j$ であり、和が $S=C_j$ となる連続部分列が取りうる組み合わせの数を $T[S]$ とする。 $T$ は連想配列であり、 $T$ に載っていない要素については組み合わせの数が0とみなす。

右端が $1..(i-1)$ について連続部分列が取りうる組み合わせの総和を $accum$ する。 $S_i = accum - T[C_i - K]$ が、 $[l=1..(i-1),i]$ を連続部分列として取れる組み合わせの総数である。

最後に、 $[1,i]$ をまるごとつまりを連続部分列として取れる条件は $C_i \ne K$ のときである。この条件が成り立つときは $S_i$ を1増やす。

$accum = accum + S_i$ , $T[C_i] = T[C_i] + S_i$ と更新する。これらを $1..N$ について反復し、答えは $S_N$ である。

公式解説と同じ解き方だと思うが、直感的が働いても言葉とコードにするのが大変である。

コードはこちら

コンテスト中はなすすべが無く、20分間順位表を眺めるしかなかった。

解説を読んだが、題意を理解することも解法を理解することも難しい。他の方のコード例を参考に、0-based indexingに変更したが、4971 msでぎりぎり間に合った。二分探索の中でmalloc (std::vectorをnew)するとTLEするので、不必要にmallocを繰り返してはいけないことを学んだ。

コンテスト47回目である。A,B,C,D,Eの5完である。C問題に時間を掛け過ぎ、G問題は入力例だけ通った。C問題の余りの解けなさに挫けそうになったが、結果はhighestだった。勝負は最後まで諦めてはならない。

コードはこちら

入力に矛盾が無い、ということが重要である。よって $A > B > C$ , $A > C > B$ , $B > A > C$ , $B > C > A$ , $C > A > B$ , $C > B > A$ を網羅する。 $S_{AB}$ は $\lnot S_{BA}$ でもある。二番目に年上、というのを見落として焦った。

コードはこちら

フラグ $F[i]$ は家 $i$ に長男がいるかどうか示す。長男がいない家に長男が生まれれば Yes かつフラグを立てる。そうでなければ No である。

コードはこちら

頂点の読み替えは $N! = 40320$ 通りなので、それらを全部網羅する。 $G$ の頂点を読み替えて $H$ との辺の過不足があればコストを計上する。このコストの最小値が答えである。

$H$ の頂点を読み替えたらなぜか通らなかった。 $G, H$ は対称なのだが、辺のコストは頂点を読み替える前の頂点番号で求めなければ ならなかった 。これが分からなかった。こうするくらいなら、 $G$ の頂点を読み替えて $H$ と比較する方がコードが簡潔になる。

コードはこちら

$X$ が昇順なので前処理を省ける。

累積和 $C(i) = \sum_{j=1}^N P_j$ を求める。便宜上 $C_0 = 0$ とする。これまで何度も見たように $L$ は std::lower_bound , $R$ は std::upper_bound で位置が分かるので、位置から $[0,R]$ , $[0,L)$ それぞれの累積和を求め、両者の差が答えである。

座標圧縮するコードを使っていなかったが、使うなら こう 書く。

コードはこちら

セグメント木を取り出したがまるっきり違った。

後ろから考える。 $g(i) = \sum_{j=i}^{N} f(i,j)$ とする。便宜上 $g(N+1) = 0$ とする。 ある $i$ について $a = A_i$ として、 $a$ の寄与を考える。 $B_i$ を、 $A_j = a, j > i$ を満たす最も小さな値 $j$ があればその値、なければ $B_i = N + 1$ とする。これは $f(i,i..(B_i-1))$ については $a$ が $g(i+1)$ から種類数を1増やし、 $f(i,B_i..N)$ については $g(i+1)$ から種類数を増やさないことを意味する。

このことから $g(i) = g(i+1) + B_i - i$ である。これを $i=N..1$ について繰り返すと答えが求まる。 $A$ の内、値が $a$ になる位置 $i$ は前処理で求めておき、そこから $B_i$ を二分探索で求める。

公式解説は 余事象 である。上記も余事象であるがDPらしい。

コードはこちら

挑んだが解けなかった。

$P$ の要素に一意性があることから、 $A_i$ を $A_{P_i}$ に置き換える操作は $\vec{i,P_i}$ への有向グラフである。よってサイクルがある。この有向グラフをサイクル $C$ に分解し、それぞれのサイクルの中でサイクルの成分 $A_{Ci}$ を回転して先頭に寄せると答えになる、と思ったのだがWAだった。複数のサイクルを矛盾なく寄せる方法が分からなかった。

公式解説1そのままを実装すると上記のリンク通りになる。

コンテスト48回目である。A,B,C,D,Eの5完である。REにTLEとボロボロだった。F問題を翌朝解いた。

コードはこちら

$S$ の . 以外を出力する。

コードはこちら

3進数にして、 $j$ 桁目が $k$ なら $j$ を $k$ 回出力する。

コードはこちら

変更した文字の周辺だけ更新すればよい。

初期値として、 $i = 1..(N-2)$ 文字目から3文字取って ABC かどうか調べる。この和が初期解である。

クエリで $X_i$ 文字目を $C_i$ 書き換えたら、影響が及ぶのは $(X_i-2)..X_i$ 文字から3文字が ABC かどうかである。これを差分を取って更新する。この3文字が $S$ をはみ出してREしたので、対策したらACした。

実装をきれいにすると このように なる。

コードはこちら

LISかスタックか全く分からず、先にE問題を解いた。

$j$ を固定して考える。 $i < j$ かつ $H_i > H_j$ なら、そのような $i$ より小さな $k$ は題意を満たさない( $H_k < H_i > H_j$ なので)。よってそのような $i$ のうち $j$ 未満の最大値(なければ1)を求める。そうすれば $k \in [i,j)$ は $j$ について題意を満たす方法が1通りずつある。いもす法で、 $i$ で1加算、 $j$ で1減算するよう準備する。

後はいもす法を再生して、 $Answer[1..n]$ の累積和を求めると答えである。

公式解説は スタック を用いている。 $H_i$ の隣 $H_{i+1}$ が壁になるのはどこまでかをスタックで求める、と解釈する。壁の向こうはLISなので、スタック長がLISの長さつまり答えである。スタック長に全く考えが至らなかった。

コードはこちら

D問題より簡単だった。

頂点同士が到達可能であることはUnion-find木から、到達可能な頂点番号の集合は std::set で管理する。頂点番号の集合はUnion-find木の代表元に持たせる。

クエリ1については、ここでマージテク、つまり大きな std::set を小さな std::set を吸収して、 std::swap するのが定石である。のだが、 $k < 10$ なので両集合を大きな方から10要素ずつ計20要素集めて、そこから大きな方から10要素ずつ集めればよい。これを忘れてTLEした。

クエリ2にpolicy based ordered setを使うとコードが短くなる。が、 $k < 10$ なので std::set::rbegin() からイテレータを回しても 間に合う 。

コードはこちら

A..E問題があまりに遅くコンテスト中に解く時間が無かったので、翌朝解いた。

ダブリングだと思ったら違ったのだが、これは制約から分かることである。相変わらず、制約から出題意図を読み取れない。

グラフが周回していることに注目する。追加の $M$ 辺がなければ、 $j$ 回移動したときに各頂点に移動する方法 $C_j[1..N]$ があったとして、 $j+1$ 回移動したときに各頂点に移動する方法は一個ずらし $C_{j+1}[2..N,1]$ である。 $C$ をコピーしないように添え字を逆に読んで、 $j$ 回移動したときに各頂点に移動する方法は $C[(1-j)..(N-j)]$ とする。ただし添え字は周回を考慮した $modN$ である。

ここまで分かれば、追加の $M$ 辺を考慮する。 $j = 1..K$ 回目に移動するとき、 $X_i$ から $Y_i$ に行くのを、 $X_i - (j - 1)$ から $Y_i - 1 - (j - 1)$ に行くと読み替える。ただし添え字は周回を考慮する。

このとき $j = 1..K$ 回目の移動後に頂点 $1..N$ に行く方法を $DP[j][1..N]$ として、移動先に配るDPする。 $DP[0][1] = 1$ 、他は0で初期化する。周回を回るときは頂点を読み替えるだけなので配る必要はなく(なのでTLEしない)、追加の $M$ 辺について $DP[j][from]$ を $DP[j+1][to]$ に足す。 $from, to$ は、 $X_i, Y_i$ を前記の通り読み替える。

最後に $DP[K][1..N]$ の和が答えである。

コンテスト49回目である。A,B,C,Dの4完である。D問題は整備しておいたライブラリに救われた。E問題は2時間経っても解けなかった。

コードはこちら

文字列が12個固定であることに注意する。

コードはこちら

A..Z = 1..26 が $S$ の何番目に出るかの逆順列 $P[26]$ 作る。この逆順列を走査して、 $\sum_{i=1}^{25} |P[i+1] - P[i]|$ が答えである。

コードはこちら

$max(A) + max(B)$ が答えである。

コードはこちら

考察が拙かったが、整備しておいたPotential DSUライブラリに救われた。ライブラリをユニットテストしていつでも使えるようにしておく、というのはプログラマとして真っ当な振る舞いであった。ドキュメントをしっかり書いておけば、差分の向きがどっちか分からず入力例が正しいかどうか悩むのを避けられたかもしれない。

連結成分についてある頂点の値を0に決め打ちして、グラフをDFSすれば残りは求まると分かった。しかしグラフの向きに囚われてどうすればよいか分からなくなった。仕方が無いのでPotential DSUのスニペットを取り出してACした。重みの差の向きを逆に解釈してしまい危うくWAするところだったが、提出前に気が付いてACした。Potential DSUを使うなら使うでもっと早く提出すればパフォが上がったが、ペナルティを避けるにはこれくらいの慎重さが必要である。

E問題以降が解けなかったので、結局これが最後の1問になった。グラフには向きが重みがあるが重さの関係は逆向きにできることに全く気が付かなかった。Potential DSUのスニペットが手元にあるという運だけでレーティングが下がらずに済んだ。とはいえ、準備ができていたから運が向いたともいえる。

公式解説通り、逆向きの枝を張るとBFSで 求まる 。

コードはこちら

二分探索と累積和をいじくり回したが、結局自力では解けなかった。上記のコードは、解説を std::ranges::partition_point で書き直しただけである。

公式解説のコードを読み解きながら、自分の言葉で 言い換える 。 $N = M$ なら全員当選なので答えは0sである。

前処理として $A$ を昇順にソートし、ソート済の添え字が元の $A$ のどの添え字に相当するか対応表を作る。次にソート後の $A$ の累積和を取る。残りの表を $R$ とする。

それぞれの候補者 $i$ について、二分探索で閾値を求める。この閾値は、候補者が $i$ が現在 $A_i$ 得票していて、追加で $x$ 票取ると当選確実になるなら、その最小値 $x$ である。一票も追加しなくても既に当選するなら0、残り $x > R$ 票を全部集めても当選しないなら-1、それ以外なら正の整数 $x$ が答えである。

このような $x$ を二分探索で求める。二分探索の候補 $y \in [0,r+2)$ について、ボーダーを $b = A_i + y$ と決め打ちする。 $b$ が意味するのは、 $b$ 票を超える候補者を $M-1$ 人集め、候補者 $i$ が $b$ 票得るために各候補者が追加で獲得する票数の合計 $s$ が、 $R$ 票以下で済むということである。 $s$ を以下の通り求める。

• 現在得票が $b$ 以下の候補者の数を $right$ とする。これは $A$ を二分探索すると分かる。
• 票を追加したい候補者の数を $N$ から引いた数を $left$ とする。これは累積和を除く範囲の右端である(1ずらすことに注意)。
  • 候補者 $i$ が圏外つまり上位 $M$ 位に入っていなければ $N - M$ とする。圏内の人 $M-1$ 人を $b+1$ 以上になるようにかさ上げして、候補者 $i$ は $b$ 票で $M$ 位になる。
  • 候補者 $i$ が圏内つまり上位 $M$ 位に入っていれば $N - M - 1$ とする。候補者 $i$ を除く圏内の人 $M-2$ 人と $M+1$ 位の人を $b+1$ 以上になるようにかさ上げして、候補者 $i$ は $b$ で $M$ 位になる。
• $left < right$ なら、候補者 $i$ 以外で $left$ 以降の候補者が $b$ 票をぎりぎり超える( $b+1$ 票得る)ための票数 $s$ を求める。これは $s = (right - left)(b + 1) - (cumsum[right] - cumsum[left])$ である。
• $left \leq i < right$ なら、候補者 $i$ も上記で $b+1$ 票になってしまったので、 $s$ から1引いて $b$ 票にする。そうでなければ、候補者 $i$ が $y$ 票獲得して $M$ 位になるので、 $s$ に $y$ を加える。

$s > r$ を満たす最小の $y$ が二分探索で求まるのでそれが $x$ である。

コンテスト50回目である。A,B,C,Dの4完である。E問題は78分掛けて解くことができず、コンテスト後にACしたが時すでに遅しである。

コードはこちら

std::string::rfind で解ける。入力が4文字以上なので、 std::string::substr でよかった 。

コードはこちら

$S=T$ なら答えは 0 である。そうでなければ $L=min(|S|,|T|)$ として、 $i=1..L$ 文字目までに不一致な最初の文字があれば $i$ 文字目が答え、そうでなければ $L+1$ が答えである。 $S \ne T$ なら、文字列の末尾にNUL文字があると考えてよい。

コードはこちら

$2^N$ 通りのグループ分けをすべて探索する。単一グループしかできない(0sと1s)ときは調べても調べなくてもよい。

コードはこちら

順列総列挙、再びビット全探索である。

どの線分をどの順番で描くかを、 $1..N$ の順列を総列挙する。それぞれの線分をどちらから描くかを、 $2^N$ 通り列挙する。これらの組み合わせを全部調べる。順列の総列挙を忘れて時間を掛けてしまった。

コードはこちら

78分あるのに正解できず、コンテスト後に正解した。

製造能力 $W$ を決め打ちして、製造能力 $W$ を達成する最小コストを求める。コストが $X$ 以内の最大の製造能力が答えである。これは二分探索で求まる。

問題は製造能力 $W$ を達成する最小コストの求め方である。それぞれの装置のコストは独立なので、それぞれの装置のコストを最小化して単に足せばよい。なので装置 $i$ の添え字を省略する。

コンテスト中に WAした 解法を記す。 $L=LCM(A,B)$ として、製造能力 $L$ をコスト $C=min(PL/A, QL/B)$ で実現できる。製造能力 $L$ を $U = \lfloor W/L \rfloor$ 単位、残りの製造能力 $R = W mod L$ を装置 $S$ を $a$ 台、残りを装置 $T$ でまかなう。これを $a = 0.. \lceil R/A \rceil$ について全探索する。 $a$ を固定したら、コストは $Pa + Q \lceil max(0,(R-Aa)/B) \rceil$ である。この解法は入力例が通るが 14 WAsが返ってくる。

反例は、 $N=1, X=24, A=3, P=10, B=2, Q=7$ である。このときの $S$ を1台、 $T$ を2台購入してコスト24で製造能力7を得ることができる。しかし上記の解法では、 $min(20, 21) + min(10, 7) = 27$ なので最小コストを間違えている。よって正解は7だが6を返す。

どうやらコスト $LU$ で製造能力を $CU$ 買うのが最適とは限らないようである。 $L$ のことは忘れて、 $a = 0..10000 \geq AB$ について全探索するとACする。10000はC++でごり押しにもほどがあり、公式解説通りループ回数を書くと こう なる。

公式解説を言い換えるとこうなる。機械 $S$ を $a=[0..B)$ 台購入して、残りを機械 $T$ にする。機械 $T$ を $b = \lceil max(0,(W-Aa)/B) \rceil$ 台購入する。 $b < A$ ならこれが答えの候補である。そうでなければ機械 $S$ を $B$ 台と、機械 $T$ を $A$ 台交換してどちらのコストが低いか下記の通り選ぶ。

• $PB \geq QA$ なら上記の方がコストが安いのでこれが答えの候補である。
• $PB < QA$ なら機械 $S$ だけ買って機械 $T$ を買わない。これは機械 $T$ を $b=[0..A)$ 台購入して、残りを機械 $S$ にする探索の一部である( $b=0$ が該当する)。

同様に機械 $T$ を $b=[0..B)$ 台購入して、残りを機械 $S$ にする場合を探索する。これですべての場合を網羅できる。このことに気が付かなかった。

コンテスト51回目である。A,B,D 3完の惨敗である。C問題を捨ててE問題に賭けたのが裏目に出た。

コードはこちら

先頭から $1..(N-2)$ 文字目から3文字を調べる。累積すべきところを代入にしたので答えが合わない。この時点で今日は何かおかしいと思う。

コードはこちら

入力の最後に原点を加えて、線分間の距離を足していく。 $N+1$ 要素を $(0,0)$ で初期化すると、最後に原点を足す処理を省略できる。

コードはこちら

初見で全く解けずにD,E問題に行った。これが完全に裏目に出た。

座標軸を反転して左右に反転する操作は、時計回りに90度回転するのと同じである。この回転は外から $i$ 周目のマスについて $i Mod 4$ 回行う。後はこれを $i=1..N/2$ 回行う。回転は高々4回なので、時計回りに90度回転だけ実装して繰り返せばよい。

E問題に賭けたら時間切れになってしまい、コンテストが終わった後に上記に気がついた。完全に問題選びを間違えたのだが、D問題に時間を掛け過ぎて余裕がなかった。

コードはこちら

文字は26種しかないのでそれぞれ別に考えてよい。例えば A が出現する位置が $P = (P_1, P_2, ... ,P_k)$ と $k$ 個あるとする。 $k < 2$ なら AxA という回文は作れないので0通りである。そうでなければ $(P_1,.,P_2), (P_1,.,P_3), (P_1,.,P_k), ... (P_k-1,.,P_k)$ という回文を作れる。

累積和を上手く使って $i=1..(k-1)$ について組み合わせを求める計算量を削減する。最初に $i=1$ について $S = \sum_{j=2}^{k} P_j - P_i - 1$ 通り作れることを求める。これを再利用する。 $i+1$ について区間 $[P_i,P_{i+1}]$ が $k-i$ 個無くなり、区間 $[P_{i+1},P_{i+2}]$ が1個無くなるので $S$ から引く。このような $S$ を $i=1..(k-1)$ について求めると A について答えが求まる。後は文字26種について数えて足すと答えである。

別の見方をすると こう なる。区間 $(P_i,P_{i+1}]$ について何回足すかを考える。

• $P_i$ より左からきて $P_{i+1}$ より右で終わる回文。左に $i-1$ 個の $P$ 、右に $k-i-1$ 個の $P$ 、区間長が $W_i = P_{i+1} - P_i$ なので、組み合わせは $(i-1)(k-i-1)W_i$ 通りである。
• $P_i$ より左からきて $P_{i+1}$ で終わる回文。左に $i-1$ 個の $P$ 、区間長が $P_{i+1} - P_i - 1$ なので、組み合わせは $(i-1)(W_i-1)$ 通りである。
• $P_i$ で始まって $P_{i+1}$ およびそれより右で終わる回文。右に $k-i$ 個の $P$ 、区間長が $P_{i+1} - P_i$ 、ただし $(P_i,P_{i+1}]$ について1引くので、組み合わせは $(k-i)W_i-1$ 通りである。

上記の式を導出するのに手間取り、21:47:48にACした。累積和を使わない答えがコメントアウトされて残っているのが生々しい。これで残り時間が無くなり、E問題で逆転するかC問題を遅解きするかの二択になり、前者を選んで共倒れに終わった。

上記のアルゴリズムは $O(N)$ である。回文の両端ではなく真ん中に注目するとはるかに簡単に 解ける。 std::lower_bound(position) と begin(), end() の差を求めると $O(Nlog(N))$ になるがコードは簡潔になる。この解法は、252-Dの公式解説1そのものである。

コードはこちら

コンテスト中に方針は立ったが、設計が上手くいかなかったので翌朝ACした。

$sum B \leq 1500$ から、チーム2,3の強さを $0..1500$ としてDPすればよい。4秒制約なのでC++でごり押せば解ける(3510 ms)。

まず選手の強さの和を $W$ とする。 $W$ が3の倍数でなければ解なしなので -1 を出力する。以下、全チームの強さを $W/3$ にすることを目標にする。

$DP[S][T]$ を、チーム2の強さを $S$, チーム3の強さを $T$ としたときの、総移籍回数の最小値とする。チーム1の強さはチーム2,3の強さから求まるので(ゼロサムだから $W - S - T$ である)、明に状態として持つ必要はない。

初期状態のチーム2の強さを $S0$, チーム3の強さを $T0$ として、 $DP[][] = \infty$ , $DP[S0][T0] = 0$ で初期化する。あとは各選手を移籍させてDPを状態遷移する。初期状態でそれぞれのチームの選手を移籍し、移籍する選手の強さを $B$ とする。チーム1の強さは明記しないことに注意する。

• チーム1からチーム2に移籍する。 $DP[S+B][T] = min(DP[S+B][T], DP[S][T] + 1)$ である。
• チーム1からチーム2に移籍する。 $DP[S][T+B] = min(DP[S][T+B], DP[S][T] + 1)$ である。
• チーム2からチーム1に移籍する。 $DP[S-B][T] = min(DP[S-B][T], DP[S][T] + 1)$ である。
• チーム2からチーム3に移籍する。 $DP[S-B][T+B] = min(DP[S-B][T+B], DP[S][T] + 1)$ である。
• チーム3からチーム1に移籍する。 $DP[S][T-B] = min(DP[S][T-B], DP[S][T] + 1)$ である。
• チーム3からチーム2に移籍する。 $DP[S+B][T-B] = min(DP[S+B][T-B], DP[S][T] + 1)$ である。

答えは $DP[W/3][W/3]$ である(ただし $\infty$ なら解なしなので -1 )。

移籍するのではなく、各メンバをチームに割り当て、初期値以外なら移籍回数を数えるという方針にすると、DPの添え字が $W/3$ になるので、500 msまで 減る 。これが公式解説の想定解法である。強さが暗黙のチーム(上記ではチーム1)の強さを遷移するのがややこしい。

コードはこちら

翌朝解いた。E問題と同様、なんとなく解法が見えただけでは正解できない。

ワーシャルフロイド法を分割実行するとWAとTLEを回避できる。最初にクエリ先読みして、通行止めの道路が確定した状態で、都市間の距離をワーシャルフロイド法で求める。次にクエリを逆再生する。

クエリ1は道路の通行止めを解除する。 $A,B$ 経由の最短距離をワーシャルフロイド法で更新する。このとき二都市 $x,y$ について、 $x,A,B,y$ と $x,B,A,y$ の最短距離だけを更新する。それ以外を更新するとTLEする。

クエリ2は都市間 $x,y$ 間の最短距離を求める。最低距離の上限は既に求まった $x,y$ の最短距離である。これにワーシャルフロイド法の続きを実行する。つまり $x,z,y : z=1..N$ で最短距離を更新する。