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

トップページへ ABC 参加記へ ARC 参加記へ

緑落ちしてARCにratedで出られないので、ABCに戻ってきた。ABC 3完まで5:56までの快走で、結局ABCD 4完の水パフォだった。

コードはこちら

forループで素直に書く。

コードはこちら

$(\sum A) - A_i = M$ を総当たりで調べる。

コードはこちら

数 $V_i$ が $C_i$ 個出現とする。ある $i$ について、 $V_i$ から $(V_i (V_i-1)) / 2$ 個、それ以外から $M-C_i$ 個選ぶ。

コードはこちら

添え字を整理するのに手こずった。

$M$ が大きいので連想配列が要る。

$A$ の昇順に見て、重複無しの $i$ 番目の位置を $P_i$ 、その位置の人数を $V_i$ とする。人数の累積和を $C_i$ とする。周回問題の典型通り、 $N+1$ 番目を1番目として、 $P$ は二周分、 $V$ の累積和も二周分求めておく。

$i$ 番目の位置に注目すると、 $\sum_{j=i}^k V_j$ が $C$ 以上になる最小の $k$ 番目を求めればよく、累積和を二分探索すると求まる。このような $i$ は、位置 $D_i = P_{i+1} - P_{i}$ 箇所に影響するので、答えに $(k-i)D_{i}$ を足す。

コードはこちら

72分あったがコンテスト中には解けず、翌朝解いた。

コンテスト中の間違った考察を記す。連結している安全な頂点をひとまとめにする。連結している危険な頂点もひとまとめにする。連結して危険な頂点について、隣接する安全な頂点から危険な頂点を多地点BFSして、一つまたは二つの安全な頂点までの最小距離を高々2個持つ。という方針で提出したらWAの山が返ってきた。この方法は、グラフ S-D-S-D を正しく扱えない。嘘解法で残り時間を全部溶かした。

翌朝自力ACしたが、公式解説1と方法は同じである。すべての安全な頂点から多地点BFSして、距離の下位2位までを持てばよい。こう書くと簡単だが、実装はかなりややこしい。同じ頂点からの距離は重複して持たないように気を付ける。

公式解説2にあると通りこの問題を乱択アルゴリズムで 解き 、さらに脱乱択することが できる 。こういう学びがあるから面白い。

コードはこちら

C問題が全くわからず、A,B,E,Dの順にACして4完だった。どうして正解者数と私にとっての難易度はこうも連動しないのだろうか。緑diffx2を解けて茶diffを落としたが、コンテスト中に茶diffを落としたのはABCは初めて、ARCは201-A以来である。

$C \geq A \land D < B$ なら Yes 、そうでなければ No である。

コードはこちら

総当たりで求める。

コードはこちら

コンテスト中はどうしていいか全く分からなかった。コンテスト後に累積和、という言葉がちらっと見えたので、自力ACは言い過ぎの気もするが、コンテスト中に得点できないなら自力も何もないだろう。

A の出現回数の累積和を $CA_{i} = \sum_{j=1}^{i} S_j IS a$ 、 B の出現回数の累積和を $CB_{i} = \sum_{j=1}^{j} S_i IS b$ とする。 $l = 1..N$ についてそれぞれ以下のように解く。

$l$ を起点に少なくとも $A$ 分運転する最小時間 $p$ は、もしあるなら $CA_{l-1} + A = CA_{p}$ を満たす $p$ である。これは二分探索で求まる。このような $p$ がなければ、 $l$ に関して答えは0通りである。

$l$ を起点に少なくとも $B$ 分休憩運転する最小時間 $q$ は、もしあるなら $CB_{l-1} + B = CB_{q}$ を満たす $p$ である。これは二分探索で求まる。このような $q$ がなければ $l \leq r$ を満たすあらゆる $r$ が答えであり、便宜上 $q = N+1$ としておく。

上記の両方の制約を満たす $r$ は、少なくとも $A$ 分運転した時点から、少なくとも $B$ 分休憩運転する時点の直前なので、 $max(0, q - p)$ 通りである。これを答えに加える。

コンテスト中は、 $S_l$ が a で始まる区間だけを数えようとして失敗した。 $S_l$ が b で始まる区間も0でない解があることに気が付かなかった。こうなった原因は、私が問題文を「トラック運転手は運転を開始したら、計A分以上運転する際には計B分以上の休憩を取らなければならない」と誤読し、運転開始前の休憩も区間 $[l,r]$ に含むのを見落としたからだ。アルゴリズムと実装を間違えたのではなく、問題文の意味を取り違えたことが敗因だった。

コードはこちら

E問題をACして気分が落ち着いたので解けた。

愚直に実装するだけで 1460 ms でACする。セグメント木とか色々考えたが、4秒制限なので凝ったことする必要はなかった。

これまで到着した人(人0を含む)の位置の順序付き集合を $P$ とする。人 $i$ の隣の人との距離を $D[i]$ とする。ただし隣の人が居ない場合は $D[i]$ を定義しない。これまでの答えの総和を $S$ とする。

人 $i$ が到着したら、 $X_i$ の前の人がもしいれば $a$ 、 $X_i$ の後の人がもしいれば $b$ として、以下の通り更新する。

• 人 $i$ と人 $a$ の距離は $D = X_{i} - X_{a}$ である。 $D[a] > D$ なら人 $s$ にとって最も近い人が変わるので $D[a] = i$ とし、 $S$ に $D - D[a]$ を足す。
• 人 $b$ についても同様である
• 人 $i$ についての距離は $D[i] = min(X_{i} - X_{P}, X_{Q} - X_{i})$ なので、 $D[i]$ を $a,b$ の近い方の人に設定する。 $S$ に $D[i]$ を足す。 $P$ に $X_i$ を追加する。

コードはこちら

C,D問題はさっぱりわからないが、E問題は問題文を読んだ瞬間ローリングハッシュだと分かった。

$A$ を二周したものを $A$ と再定義する。まず $B$ 全体のハッシュ値 $H$ を取る。ハッシュ値 $A[i,i+|B|) = H$ となる 最小の $i$ があればそれが答えで、無ければ -1 が答えである。

Baseをランダム化し、Modを $2^{61}$ 付近にし、複数のハッシュをまとめて取ると こう なる。素数表は Primes just less than a power of two の値を使った。

コードはこちら

マス目の値を0-based indexingで考える。マスの値の依存関係を有向グラフにする。

$S_i$ が R なら $i$ から $i+1$ 、 L なら $i+1$ から $i$ に向く有向グラフを $G$ とする。 $G$ の辺をすべて逆向きにしたグラフを $\bar{G}$ とする。

$G$ において、ある $i$ 頂点に到達可能な頂点数を $IN_{i}$ とする。これはマス目の並びにおいて、 $i$ に先行する他の頂点が少なくとも $IN_{i}$ 個という意味である。これは、 $G$ で入次数が0の頂点を起点にBFSすることで求まる。実はDFSの方が素直である。

$\bar{G}$ において、ある $i$ 頂点に到達可能な頂点数を $OUT_{i}$ とする。これはマス目の並びにおいて、 $i$ に後続する他の頂点が少なくとも $OUT_{i}$ 個という意味である。これは、 $\bar{G}$ で入次数が0の頂点を起点にBFSすることで求まる。

ある頂点 ${i}$ について、マスの番号として取りうる値は $[IN_i,N-Out_i)$ である。これを区間加算遅延セグメント木に乗せると答えが求まる。区間加算遅延セグメント木に乗せるまでもなく、いもす法する方が計算量が少ないと後で知った。

コンテスト中に A,B,C,D問題の4完、22:59:02にE問題をACした。E問題は割と早く方針が立ったが、詰めが甘くて69分で実装が終わらなかった。画竜点睛を欠くとはこのことか。

コードはこちら

max(0, H-B) が答えである。

コードはこちら

部品が付いているかどうかを $T_i$ で保持してシミュレーションする。 $T[i]$ は部品 $i$ をロボットに取り付けていれば1, そうでなければ0である。

$T[P_i] = 0$ ならロボットの重さが $W[P_i]$ 増えて、 $T[P_i] = 1$ ならロボットの重さが $W[P_i]$ 減る。その後 $T[P_i] = 1 - T[P_i]$ にする。

コードはこちら

頭パーツが軽い順に、重さ $H_i$ 以上の $B_j$ を組み合わせるgreedyでよい。 $H$, $B$ をそれぞれ昇順にならべて尺取り法で解く。

公式解説は尺取り法よりずっと簡単である。

コードはこちら

制約を見切るのが遅くて時間を無駄にした。

$NW \leq C = 250000$ より、体の重さ $WB$ から頭の重さ $WH$ を引いた差 $D = WB - WH$ は、 $-C \leq D \leq C$ になる。 $C$ を定数として候補を全部持つDPで解く。

$DP[i][D]$ は、ロボットに部品 $i$ まで取り付け重さの差が $D$ の時の、うれしさの最大値とする。 $DP[][] = -\infty$ , $DP[0][0] = 0$ である。後は頭と体に部品 $i$ を取り付けたときのうれしさを更新する。 $j = -C..C$ として以下のように更新する。ただし添え字が範囲外なら無視する。

• $DP[i+1][j-W_i] = min(DP[i+1][j-W_i], DP[i][j] + H_i)$
• $DP[i+1][j+W_i] = min(DP[i+1][j+W_i], DP[i][j] + B_i)$

答えは $max(DP[N][0..C])$ である。実装上は添え字に $C$ 下駄を履かせておく。

コードはこちら

E,F問題どちらにしようか迷った末、E問題に時間を振った。その判断は正しかったが、実装方針を間違えた。

結論から言えば、01-BFSかダイクストラ法で解ける。マスではなくマスを囲む辺について互いの距離を求める。コンテスト中はマスの距離を求めようとして正解を出せなかった。

辺の番号を付ける。縦の辺の数は $V=(W+1)H$ 本である。0-based indexingで、マス $(y,x)$ を囲む辺について、左辺を $y(W+1)+x$ 、右辺を $y(W+1)+x+1$ 、上辺を $V+yW+x$ 、下辺を $V+yW+x+w$ という番号で名付ける。

辺の間を移動するコストを、鏡を切り替えるコストとみなす。鏡を切り替えるなら1、切り替えないなら0である。マス $(y,x)$ 内を移動するコストを、以下のように定義する。

• マスの上辺から
  • 下辺に移動するとき、マスが A ならコスト0、そうでなければコスト1である
  • 右辺に移動するとき、マスが B ならコスト0、そうでなければコスト1である
  • 左辺に移動するとき、マスが C ならコスト0、そうでなければコスト1である
• マスの下辺から
  • 上辺に移動するとき、マスが A ならコスト0、そうでなければコスト1である
  • 左辺に移動するとき、マスが B ならコスト0、そうでなければコスト1である
  • 右辺に移動するとき、マスが C ならコスト0、そうでなければコスト1である
• マスの左辺から
  • 右辺に移動するとき、マスが A ならコスト0、そうでなければコスト1である
  • 下辺に移動するとき、マスが B ならコスト0、そうでなければコスト1である
  • 上辺に移動するとき、マスが C ならコスト0、そうでなければコスト1である
• マスの右辺から
  • 左辺に移動するとき、マスが A ならコスト0、そうでなければコスト1である
  • 上辺に移動するとき、マスが B ならコスト0、そうでなければコスト1である
  • 下辺に移動するとき、マスが C ならコスト0、そうでなければコスト1である

このように辺を張ったグラフをダイクストラ法か01-BFSすると、グラフの頂点 $0$ から頂点 $V-1$ までの最小距離が答えである。

参加せず翌朝解いた。相変わらず、正解者数と私にとっての難易度に連動性がない。

コードはこちら

$A,B,C$ を降順に出力する。

コードはこちら

$S$ の各文字の順列を昇順に検索し、先頭が 0 でない最初の文字列を返す。順列は $5!=120$ 通りしかないので全探索でよい。

コードはこちら

D,E問題より時間が掛かった。

$A$ を昇順に並べる。つまり $A_1$ を最小にする。 $D = Y - X$ とする。

子供1は大きな飴しか持っていないと仮定する。実はこう仮定していい。 $A_i \geq A_1$ として、重さが同じまま飴をたくさん持つには、大きな飴を小さな飴に持ち替えるしかない。 $V = A_i - A_1$ とする。

大きな飴 $U$ 個を小さな飴 $U+V$ 個に置き換える。このとき、 $YU = X(U+V)$ が成り立つ。式変形して、 $U = XV/D$ である。よって、 $XV$ を $D$ で割り切ることができなければ解無しである。また $U > A_1$ も解無しである。解があるなら子供 $i$ について、 $A_1 - U$ 個の大きな飴を持つ。

こうして求めた、すべての子供の、大きな飴の数の和が答えである。

コードはこちら

一度分かれた連結成分が、後からつながることはない。よって $N$ 回シミュレーションすると、 $S = 2^{N} - 1$ 個の矩形に分かれる。あとは矩形同士が重なるかどうか判定し、重なるなら連結成分にする。連結成分にある矩形は重ならないので、連結成分にある矩形の面積の和が連結成分の面積である。

$S(S-1)/2 = 134209536$ 回の判定が間に合うと思ったら、公式解説にある通り、分割後の矩形はとても少ないので、1ミリ秒で解ける。X座標で並び替えて区間分割問題を器用に解こうとして時間を 溶かした 。モートン順序のような凝ったアルゴリズムは不要だった。

コードはこちら

C問題は分からない、D問題は後回しにしたが、E問題は分かった。

Fenwick treeに、数 $a =A_i$ が何個乗るかと、 $a$ の区間和を乗せて、クエリを更新する。

$C[i]$ は、 $A$ に数 $i$ が何個乗っているか保持する。 $S[i]$ は、 $A$ に数 $i$ が $c$ 個乗っているなら $ic$ とする。

クエリ1にはこう答える。旧 $a = A_i$ として、 $C[a]$ を1減らし、 $S[a]$ を $a$ 減らし、 $C[y]$ を1増やし、 $S[y]$ を $y$ 減らし、 $A_i = y$ とする。

クエリ2にはこう答える。 $r < l$ なら答えは $l \times N$ である。 $l \leq r$ なら以下の和が答えである。

• $r$ より大きい数についての和 $C[r+1..] \times r$
• $l$ より小さい数についての和 $C[0..l-1] \times l$
• $l$ 以上 $r$ 以下の数についての和 $S[l..r]$

コンテストに出て、A,B,C,D の4完だった。

コードはこちら

A問題にしてはとても難しい。

$P \geq 0$ 年経過したとして、 $X+P = (Y+P)Z$ である。式変形して、 $X-Y = P(Z-1)$ である。 $D = X - Y$ として、 $D$ を $Z-1 > 0$ で割り切れなければ答えは No である。 $(D / Z-1)Z < X$ なら歳を取りすぎているので、答えは No である。それ以外の場合は Yes である。

式を上手く整理すれば公式解説通り、 $P = (X - YZ)/(Z-1) \land P \geq 0$ と分かる。焦ってパニックになりかけた。

コードはこちら

A問題とは違ってみてすぐ解けた。 $O(N^2)$ の総当たりを実装する。

コードはこちら

A問題とは違ってみてすぐわかった。1122文字列の1に相当する文字の最も右の位置つまり値が切り替わる直前の位置 $i$ を固定する。

• $S[i] + 1 \neq S[i+1]$ ならその位置で1122文字列は作れない
• そうでなければ左右の1122文字列を伸ばせるだけ伸ばして数える

$i = 1..(N-1)$ を総当たりしても、1122文字列は互いに重ならないので $O(N)$ で求まる。

コードはこちら

F,E,D問題の順にみたために着手が遅れ、実装を間違えて2ペナ返ってきた。痛すぎる。

前処理として、 $x$ の $w$ 桁と、 $M$ で割った余り $r = xModM$ を数える。

基本的な考え方は、ある $x$ について、 $r = xModM$ なら $p = (M-r)modM$ に該当する $y$ の個数を数えて組み合わせる。これを拡張して、桁数 $w=1..10$ 桁について、 $r = (x \times 10^w)modM$ のときに余りが $p = (M-r)modM$ かつ $w$ 桁となる数の個数である。これを $x$ と桁数について全探索すると答えが求まる。

std::map に対する aMap[key] は、 aMap に key が無いとその場で要素を作る。これが原因でTLEが発生して2ペナ食らった。 std::map::at を使って書き直したものが こちら 。

• C++の std::map::operator[] は、キーがなければその場で挿入する。非constなので、右辺に置いたときもデフォルトコンストラクタが実行されて挿入される。
• C++の std::map::at は、キーがなければ例外を出す。入力例1が失敗するので、ここは std::map::contains が必要なのだと分かる。 std::map を二度走査するのは時間の無駄なので、実行効率を考えたらイテレータを使いまわすのが正しいが、二度走査してもTLEしないのでよしとする。

コードはこちら

あと一歩考察が足りなかった。

$X$ に重複があれば答えは No である。 $Y$ に重複があれば答えは No である。これを忘れれると4 WAsする。それと $X,Y$ の最大値が $HW$ 未満なら答えは No である。

$X$ が降順になるように行を入れ替えて考えて構わない。出力時に行入れ替えの逆変換をすればよい。同様に $Y$ が降順になるように列を入れ替えて考えて構わない。以下、入れ替え後の行列で考える。まだ使っていない要素を $S = 1..(HW)$ で初期化する。

$a = X_i = Y_j$ な要素があれば、 $A_{ij} = a$ にする。それ以外の $X_i$ の要素は $A_{i1}$ に置く。それ以外の $Y_j$ の要素は $A_{1j}$ に置く。置いた要素を $S$ から $a$ を除く。

余った行列要素に $S$ を、下の行から上の行に、同一行は右の列から左の列に向かって置いていく。 $A_{ij}$ の要素は、 $S$ の $min(X_i,Y_j)$ 以下の最大要素にする。置いたら $S$ から除く。これが分からず、単に1から順に置いていったら 11 WAsが返ってきた。

上記の通りに行列要素を埋めて、制約を満たしたら Yes と行列を出力する。制約を満たさなければ No である。

コードはこちら

解説を見て実装した。この発想は無かった。

コンテストに出て、A,B,C,D の4完だった。C問題の答えが合わずパニックになって4ペナしてしまった。

コードはこちら

風船を $S$ 個として、 $SB > 1000W$ を全探索する。

コードはこちら

種類 $i$ の大きさの合計 $W_i$ と、個体数 $C_i$ を求め、 $W_i/C_i$ を出力する。

コードはこちら

C問題のWAが取れず、D問題を先に解いた。4ペナして大きく順位が下がった。

最初の区間を $[H,H]$ とする。後ろから考える。後の区間 $[L_{i+1}, R_{i+1}]$ があるとする。そのひとつ前までの到達時間は $D = T_{i+1} - T_{i}$ である。

後の区間に来ることができる前の区間は $[max(0, L_{i+1} - D, R_{i+1} + D]$ である。この区間と $[L_{i}, R_{i}]$ の制約の重なり $S = [L_{o}, R_{o}]$ を求める。重なりが空なら答えは No である。ただし一点区間は認める。空でなければ $S$ をこの前の区間と読み替えて、同様の処理を繰り返す。

$S$ をこの前の区間と読み替える処理を忘れても、入力例は通ってしまう。そのため間違いになかなか気が付かなかった。この勘違いで4ペナし、しかもE問題で勘違いが悪化する。

公式解説にある通り、 前から後ろ でも解けるし、その方が実装は楽である。

コードはこちら

あるマスに雲が何個重なっているか $C[2000][2000]$ は、 $\pm 1$ の二次元いもす法で求まる。 $C[u][l]$ で1足し、 $C[u][r+1]$ で1引き、 $C[d+1][l]$ で1引き、 $C[d+1][r+1]$ で1足す。まず横方向にいもす法して、次に縦方向にいもす法すると全体が求まる。

次に、雲が少なくとも一つ重なっているマスの総数 $S$ を求める。

あるマスにある雲の番号の和 $W[2000][2000]$ を求める。これは雲の番号を $i$ として、 $\pm (i + 3 \times 10^{5})$ の二次元いもす法で求まる。オーバーフローしないように気を付ける。公式解説にあるが、実は下駄を履かせる必要はない。

雲が1個だけ重なっているマスについて、その雲が何かは $i = W[2000][2000] - 3 \times 10^{5}$ で求まる。よってある雲 $i$ を除いたとき、 $D[i]$ 個マスが空くというのを1増やす。

答えは雲 $i$ について $2000^{2} - (S - D[i])$ である。

雲の重ね合わせを Zobrist hashing してもTLE しない 。具体的には、雲 $i$ に0ではない符号なし64-bit乱数 $R_i$ を割り当てる。雲の重ね合わせを $R_i$ のXORにすると、雲がないマスは0、雲が一つのマスは $R_i$ のいずれか(これは $R_i$ から $i$ への逆引きテーブルを作る)、それ以外はほぼ確実に $R_i$ 以外で非0の数になる。いもす法もXORで求める。計算量は $O(HW+Nlog(N))$ である。

コードはこちら

問題文を見てmax flowだと思ったが答えが合わない。考え方は完全にあっていて、コンテスト中は実は一か所 typoした ことに気が付かなかった。コンテスト後に見直したら分かったが時すでに遅し。

答えから言えば、グラフのmax-flowである。以下のグラフ $G$ を構成すればいい。

• うさぎのジャンプ先を座標圧縮して連番を振っておく
• 始点からそれぞれのうさぎ $1..N$ に最大流1の辺を張る
• それぞれのうさぎから $i$ 、それぞれのジャンプ先 $X_i-R_I, X_i+R_i$ に最大流1の辺を張る
• うさぎのジャンプ先から終点に最大流 $N$ の辺を張る

コンテスト中は入力例が合わないのを承知で備忘録代わりに提出したのだが、なんと以下のコードが間違っていた。

for(Num i{0}; i<serial; ++i) {
    graph.add_edge(n+serial, sink, 1);
}

n+serial ではなく、正しくは n+i である。5完なら水色に戻れたので、完全に勝ち試合を落としてしまった。C問題のグダグダを最後まで引きずってしまった。うさぎの数 $N$ より最大流が多いのは変だと思ったが、typoに気が付かなかった。

公式解説にある別解はエレガントで、思いつく気がしない。

コンテストに出て、A,B,C,D,E の5完だった。E問題で遅れ、F問題は解けなかった。それでも水コーダーに戻った。

コードはこちら

$N(N+1)/2$ である。初めて提出まで1分を切った。

コードはこちら

問題文通り $O(N^3)$ 回計算する。

コードはこちら

焦りすぎて、B問題に入力例を食わせて不正解だと勘違いした。

ドミノが届く場所+1を $M$ とする。

• 少なくとも1番目のドミノは倒れ、 $M = 1 + A_1$ である。
• ある $i$ について $M \leq i$ ならドミノはもう倒れないので答えは $i-1$ である。そうでなければ $M = max(M, i + A_i)$ にする。

コードはこちら

有効グラフを逆向きにして、頂点を塗ったらDFSで到達可能な頂点をすべて黒く塗る。ただし黒い頂点から先は塗る必要はない。これでTLEしない。

コードはこちら

遅延セグメント木で区間和、max更新だろうと思ったら全然答えが合わない。仕方ないので互いに素な区間を std::set<std::pair<Num,Num>> に入れて解いた。座標圧縮は必要ない。

クエリを先読みして、マス番号として取り得る値 $P$ の集合を見つける。 $P$ には $0,N,L,R$ を入れる。 $R$ は $R+1$ に置き換える。その後 $P$ を昇順にならべて、互いの疎な区間 $[A,B)$ の集合 $S$ を作る。

答えを $N$ で初期化する。クエリ $[L,R)$ を読むごとに、 $S$ から $[L,R)$ と重なる区間を除いていく。この操作は全体で $2N$ 回なのでTLEしない。より具体的には、クエリごとに以下のようにする。

• $[L,-1)$ より辞書順で大きな最初の区間 $[A,B)$ を求める。そのような区間がなければクエリの解が求まったので終了する。
• $[L,R)$ と $[A,B)$ に重なりがなければ、つまり $R \leq A$ なら終了する
• $[L,R)$ が $[A,B)$ を包含すれば、つまり $B \leq R$ なら、答えから $B - A$ を引き、区間 $[A,B)$ を取り除いて先頭に戻る。
• $[L,R)$ が $[A,B)$ と一部重なれば、つまり $B > R$ なら、答えから $R - A$ を引き、区間 $[A,B)$ を取り除き、区間 $[R,B)$ を追加して終了する。

遅延セグメント木解法は、公式解説通りに 実装 した。コンテスト中に思いつく気がしないのは、典型を知らないからだ。

コードはこちら

40分あったが正解できなかった。ある猫の位置から左右どちらに移動すると距離が長いかをDFSした。方針自体は合ってたが、境界値のバグが取れず数日かかった。実装力が足りない。

ある範囲で最も高いタワーの位置は、セグメント木に $(H_i,i)$ を載せて区間maxすれば分かる。便宜上、単位元を $(-1,-1)$ として負の値なら該当するタワーがないことを示す。

今注目している区間を $[L,R)$ として、その局所解を $f(L,R)$ とする。 $[L,R)$ で最も高いタワーの位置を $C$ とする。 $C$ が存在しないならもう移動できないので答えは0である。

そうでなければ区間 $[L,C)$ で最も高いタワーの位置を $P$ とする。 $P$ が存在しないなら移動距離0とする。 $P$ が存在するなら、左側に移動した時の距離は $D_{l,L,R} = |C-P| + f(L,C)$ である。ここで $f(L,C-1)$ とすると、入力例は合うが大量にWAする。

同様に区間 $[C,R)$ で最も高いタワーの位置を $Q$ とする。 $Q$ が存在しないなら移動距離0とする。 $Q$ が存在するなら、右側に移動した時の距離は $D_{r,L,R} = |Q-C| + f(C,R)$ である。よって $f(L,R) = max(D_l, D_r)$ である。

これを区間 $[1,N+1)$ から再帰的にDFSすることで答えが求まる。セグメント木操作の計算量から $O(Nlog(N))$ である。公式解説は計算量が $O(N)$ だが、方針自体は同じである。

コードはこちら

得点 $S_i$ を取った人が $P_i$ 人いるとする。これを $P_i$ の降順に並べ、以下の操作を行う。

得点 $S_j$ 以上を取った人が累積 $P_j$ 人いるとする。このときクラス間の人数の差は $D_j = |N - 2P_j|$ である。これをタプル $(D_j, P_j, S_j)$ とする。

このタプルを昇順に並べ替え、辞書式最小順の値 $S_1$ が答えである。

コードはこちら

団子を色の昇順に一直線上に並べて、左から順に消化していく。便宜上、色 $N+1$ の団子は0個とする。

串団子の素材が $R_1 = A_1$ 個あるとする。色1,2を組み合わせて串団子を作る素材は $R_1 + A_2$ 個である。よって作れる団子の数は $U_2 = \lfloor (R_1 + A_2) / 3 \rfloor$ 個である。この時点で色2の団子は残り $R_2 = max(0, min(A_2, R_1 + A_2 - 3U_2))$ 個である。

色2,3を組み合わせて串団子を作るとき、色1の団子は何個あっても使うことができず、色2は残り $R_2$ 個である。上記と同様に $U,R$ を求める。これを色 $N,N+1$ を組み合わせて串団子を作るまで繰り返す。

コードはこちら

$S$ の OI を x と置き換える。 J で始まり、 J または x が続く文字列は、操作によって x を左に寄せて x..xJ..J にすることができる。これを尺取り法で行うと $O(N)$ で解ける。後は x を OI に戻して出力する。 $S$ の終端にセンチネルを置くと処理しやすい。

コードはこちら

$k$ を三分探索すると、AC or TLEで39点取れる。

コードはこちら

ACLを使ってACした。

ある頂点からの移動回数を $d$ して、頂点倍化した行き先をグラフ $G$ にする。頂点番号を0-based indexing にして(つまり入力の $A,B$ から1引いて)、奇数回目に移動した後の頂点を $A+N$, 偶数回目に移動した後の頂点を $B$ として、 $G$ は $\vec{B,A+N}$ と $\vec{B+N,A}$ から構成する。

$G$ をSCC(強連結成分分解)して、サイクル群を見つける。あるサイクル $C$ において、頂点 $i$ と頂点 $i+N$ を同一視したときの頂点数 $W$ が、そのサイクルにある頂点が到達可能な頂点数 $C_i = W$ である(同一視を忘れると大量にWAする)。あとはサイクルの各頂点からBFSして、頂点をたどるごとに $W$ を1増やしながら走査し、 $C$ を更新する。 $W$ が小さくなるようなら走査を打ち切ってよい。

頂点 $i$ についての答えは $min(N, max(0, N - C_i))$ である。

$O(N^3)$ 解でAC or TLEして62点取った。

$N$ が偶数なら、船 $i$ と 船 $i + N/2$ の最小距離が答えである。以下 $N$ は奇数とする。

$N$ が奇数なら、船 $i$ を含む船 $l,j,r$ が等差数列を構成可能か総当たりする。構成可能なら残りの船は偶数なので上記と同じ考察をし、船 $l,j,r$ の距離と小さい方が答えの候補である。

具体的には $l,r$ を $1..N$ の二重ループにして(ただし $l < r$ )、以下が $i$ の候補である。

• $A_r - A_l$ が偶数かつ $A_i = (A_r + A_l) / 2$ を満たす $i$ がある
• $A_i = A_l - (A_r + A_l)$ を満たす $i$ がある
• $A_i = A_r + (A_r + A_l)$ を満たす $i$ がある

コンテストに出て、A,B,C,D,E,F の6完だった。初めての6完である。ABC最高パフォだが、青色には届かなかった。しかしE問題よりF問題を先に解くべきだったのは猛反省である。

コードはこちら

$N - |S|$ 文字の o を出力してから $S$ を出力する。

コードはこちら

問題文通り実装するのだが、ややこしい。

コードはこちら

ブロックのマス集合 $S$ をすべて集合 $T$ に載せる。 $S$ が $T$ に一つでも載っていればそのブロックを置くことはできず、そうでなければ $T$ の $S$ を加える。答えは $|T|/4$ である。

コードはこちら

超頂点 a..z を用意する。

無向グラフ $G$ を以下の通り構成する。

• 空きマス . と ワープマス a-z は、上下左右が障害物または枠外でなければ、距離1で隣接する
• ワープマス a-z は、超頂点と行きは距離1で、帰りは距離0で隣接する

マス $(1,1)$ から $(H,W)$ にダイクストラ法すると答えが求まる。

コードはこちら

先にF問題を見たのに、E問題の方が簡単だと思って飛びついてしまった。正解者数が積みあがっていくのを見て、この問題は解かなければと思ったが、いつも通り正解者数と私にとっての難易度は異なることが多い。

転倒数に注目して30分溶かした。答えは連結成分分解である。

$(i,P_i)$ が連結成分なら、 $P_i$ と $P_{P_i}$ をいつか交換しなければならない。この関係は推移的なので、union-find木の連結成分として表現できる。

ある連結成分 $G$ があり、成分数が $|G|$ のとき、意味のある操作は $|G|(|G|-1)/2$ 通りの組み合わせがある。特に $|G|=1$ のときは自分自身を交換するので0通りである。

すべて連結成分について $|G|(|G|-1)/2$ を求めた和が答えである。

コードはこちら

E問題より先に見たのに、難しいと思って後回しにした。結果的には、E問題よりずっと簡単だった。

$b = 1..N$ 番目ちょうどに明るい星と、 $b$ よりも明るい星だけを撮る方法が何通りあるか逐次的に求める。セグメント木 $T$ は、位置 $i$ に星があれば1、なければ0として、区間和は星の数である。

1番明るい星だけ撮る方法は1通りである。 $B_i = 1$ を満たす $i$ について、 $T[i] = 1$ とする。

$b$ 番およびそれより明るい星だけ撮る方法を求める。 $B_i = b$ を満たす $i$ があるとき、左側から $L=1+T[1,i)$ 通り、右側から $R=1+T(i,N]$ 通り選べるので $LR$ 通りである。これを答えに足す。その後、 $T[i] = 1$ とする。

上記の和が答えである。もしかしたらE問題で転倒数をセグメント木で求めたので、F問題にその発想を持ち込めたのかもしれない。

コードはこちら

問題文通りシミュレーションする。

コードはこちら

BFSする。 $Q$ を要素を $(i,C)$ とし、ボール $i$ を落とした残りの集中力が $C$ とする。ボール $j$ を落とした後の最大集中力 $V[j]$ を-1で初期化する。

いつでも落とせるボール $i$ について $(i,X-A_i)$ を $Q$ に入れる。ただし $X < A_i$ なら入れない。

$Q$ の要素 $(i,C)$ を以下の通り処理する。

• $V[j] \geq C$ ならこの先を探索する意味はないので $Q$ に入れない
• そうでなければ $V[j]$ を $C$ にする
• ボール $i$ を落としたら落とせるようになるボール $j$ について、 $(j,C-A_j)$ を $Q$ に入れる。ただし $C < A_j$ なら入れない。

これを繰り返すといつか処理が終わるので、 $V[j] \leq 0$ を満たす最大の $j$ (なければ-1)を出力する。

コードはこちら

満点解法が分からないので、部分点を67点取った。

$A,B$ を総当たりすると残りは $C$ を最適化することになる。

• $A_i$ を決め打ちして、下記の最大値が答えである。
• $B_j$ を決め打ちして、下記の最小値が答えである。
  • $A_i + B_j \geq P$ なら、 $max(C)$ を加えるのが最適である
  • $A_i + B_j < P$ なら、 $min(C), max(C)$ を加えて解 $|A_i+B_j+C_k - P|$ が大きい方を採用する

コードはこちら

満点解法が分からないので、部分点を57点取った。

小課題1は総当たりで求める。

小課題2,3,4 ($B=1$) は、 $A$ を昇順に並べ替えておく。この並び替えは、 $(A_i,i)$ の組で行う。つまり同じ値 $A$ なら $i$ が後にくるようにし、並べ替え後の順序から元の添え字が分かるようにする。後で出る $B$ も同様。

$i=N..1$ の順に、組めるシェフの数の累積和 $C_{N-i}$ を求める。クエリに対して $X-1$ を超える最小の累積和 $C$ のインデックスから $A_i$ の $i$ が分かる。答えは $A_i + 1$ である。

小課題5 ($Q=1, X=1$) は、 $A,B$ をそれぞれ昇順に並べ替えておく。 $i=N..1$ の順に $A_i$ を探索する。同じ $i$ の中では、 $j=N..1$ の順に $B_i$ を探索する。この探索で最初に組めるシェフが答えである。

コードはこちら

まさか解けるとは思わなかった。

初めからほぼ満点解法を目指す。小課題4つまり $A$ が狭義単調増加で重複がない、 $B$ が狭義単調増加で重複がない場合を考える。マスの位置を0-based indexingで考える。

$A$ を行方向つまり横方向に塗っていくとき、マスの色は $A$ の累積max $U$ である。列 $i$ を縦に見ていくと、 $U_i$ より大きい値が出るまで $U_i$ で塗り、それより先の行は塗れないと分かる。

そこで同様に $B$ を列方向つまり縦方向に塗っていくときの累積maxを $V$ とする。行 $j$ を横に見ていくと、 $V_j$ より大きい値が出るまで $V_j$ で塗り、それより先の行は塗れないと分かる。

$U,V$ をランレングス圧縮して、 $RU, RV$ にする。そうすると、色 $C$ が連続 $L$ マスあることが分かる。 $U,V,RU,RV$ を利用して、上記を求める。よく考えたらランレングス圧縮は要らないのだが、解法を考察するために必要だった。

縦方向に同一色で塗ることを考えると、 $RU_i = (C_i, L_i)$ について、 $U$ に $C_i$ より大きい値が最初に出る位置(なければ枠外 $N$ )を $p$ とすると、 $p \times L_i$ だけ塗ることができる。同様に、横方向に同一色で塗ることを考えると、 $RV_i = (C_i, L_i)$ について、 $V$ に $C_i$ より大きい値が最初に出る位置(なければ枠外 $N$ )を $p$ とすると、 $p \times L_i$ だけ塗ることができる。

上記を繰り返すと、どの色で何マス塗ったか数えられる。数える回数は $2N$ 回、連想配列に載せるコストが $O(log(N))$ なので、計算量は $O(Nlog(N))$ である。

この方針で小課題4だけ正解する。これをすべての課題を解けるように拡張する。

最上行と最左列は塗らないので、あらかじめ色の出現頻度を数えておく。 $A_1$ と $B_1$ を二度数えないように注意する。

後は縦横 $N-1$ マスだと思って上記を慎重に実装すると正解して満点が取れる。行は upper_bound にして $C_i$ より大きな色で止め、列は lower_bound つまり $C_i$ と同色で止めると、縦横のマスの塗り方が重複しない。

コードはこちら

1秒制限とはなんだろうと思ったが、セグメント木でACした(328 ms)。

$N$ を二周して長さ $2N$ にしておく。あるモンスター $j$ から倒し始めたとして、以下のようになる。

• 最初のモンスターを倒すのに強さ $A_j$ 必要である。
• 次のモンスターを倒すのに強さ $D[j+1] = A_{j+1} - (A_j + B_j)$ 必要である。ここで $D[j+1]$ が負の値でも0でも気にしないことにする。
• モンスター $p > j$ を倒すのに強さ $D[p] = A_{p} - (A_j + \sum_{k=j}^{p-1} B_j)$ 必要である。やはり $D[p]$ が負の値でも0でも気にしないことにする。

このときの答えは、 $max D[j..j+N-1]$ である。空集合のmaxを、0ではなく $-\infty$ にする(そうしないと答えが合わない)。

$j = 1..N$ についてそれぞれ $O(log(N))$ で求める解法を導入する。まず $B$ の累積和 $C_i = \sum_{k=1}^{i} B_i$ を求める。次に $j=1$ のときの上記の操作を $i=1..2N$ , $D_i = A_i - C_{i-1}$ として、区間最大セグメント木に $T$ に $T[i] = D_i$ を載せる。 $j=1$ なら答え $S_1 = T[1..N]$ である。

$j > 1$ のときの上記の操作は、 $j$ より前のモンスターを倒して強くなっていない状態なので、答え $S_j = T[j..(j+N-1)] - C_{j-1}$ である。 $S$ の最小値が答えである。

30点しか取れないので、嘘解法なのか実装が間違っているのかわからない。

ロープウェイの目的地 $B = 2..N$ を網羅すれば、駅1から他の駅に到達可能である。特に $B_2$ には $A_1$ からしか行けない。

ロープウェイ会社番号を座標圧縮して $D_i = C_i$ とする。セグメント木の添え字は座標圧縮した番号を用いる。クエリも座標圧縮すればいいことに気が付いた。

区間最大セグメント木 $T[i=2..N]$ は、駅 $B_i$ に到達できる最小番号のロープウェイ会社(を座標圧縮した番号)とする。該当する会社がなければ $-\infty$ とする。そうすると $T[2..N]$ は、ある会社 $D_i$ からみて、フリーパスで全駅を網羅するには $T[]..D_i$ をフリーパスに含まなければならない($T < 0$ ならフリーパスを構成不可能である)。

これを $D_{r=0..N-1}$ について繰り返す。会社 $r$ が運営するロープウェイの到着地 $B$ について、 $T[B] = r$ に更新する。その後 $T[] \leq 0$ なら、会社 $r$ を区間右端とするフリーパスの左端 $l = T[]$ を $L[r] = l$ とする。同様に $R[l] = max(R[l])r$ とする。

クエリ $L,R,X$ に対して、 $L$ 以上の最小の会社を $l$ とすると、 $R[l] \leq R+X$ ならフリーパスを構成可能である。同様に $R$ 以下の最小の会社を $r$ とすると、 $L[r] \geq L-X$ ならフリーパスを構成可能である。この少なくともどちらか一方が成り立てば答えは Yes 、そうでなければ No である。

28点しか取れないので、たぶん嘘解法である。

観客の唱えた数を2回連続無視できないので、おそらく以下の動的計画法が成立する。

$DP[i][0]$ は、 $i$ 番目の観客が $A_i$ を唱えたとき、反応した後の状態である。 $DP[i][1]$ は、 $i$ 番目の観客が $A_i$ を唱えたとき、無視した後の状態である。状態遷移を考えると、以下が成立する。

• $DP[i+1][0] = min(DP[i][0], DP[i+1][1])$
• $DP[i+1][1] = DP[i][0]$

問題は $DP[i]$ の定義をどうするかである。 $A_i \leq 21$ より、ネクタイの長さ $j$ のモデルの数を要素数21のベクタで表現する。この解法で28点取れる。

• $DP[0][0]$ を $(0,..,0)$ 、 $DP[0][1]$ を $(0,1,0,..,0)$ する。
• $DP[i][]$ に $A_i$ 以下のモデルでネクタイの最も長いモデルがいたら置き換える。いなければ $A_i$ のモデルを一人増やす。
• $min(DP[i][0], DP[i+1][1])$ の定義を辞書順とする。より正確にはモデルの人数が少ない方、モデルが同数ならネクタイが最も長いモデルから人数を順に比較した結果とする。おそらくここが間違っている。
• $min(\sum DP[N][0], \sum DP[N][1])$ を答えとする。

3完茶パフォで大敗した。C問題を解けない焦りから完全にペースが乱れ、D問題は2ペナ、E問題はコンテスト中に間に合わないのに解答時間を使い、あっさり解けるF問題をうっかり捨ててしまった。辛うじて水色には残ったが、A,B,D,F 4完だったら水パフォだったので問題選びを間違えすぎである。

コードはこちら

$12A + B$ が答えである。

コードはこちら

問題文がややこしいが、多重ループで解ける。

• $A_{i=1..H,}$ それぞれについて
• $A_{i,j=1..W}$ それぞれが
• $B$ に含まれる回数を数える

$A_{1..H,}$ についての回数の最大値が答えである。

コードはこちら

トナカイの損失が小さい順に、ソリを引く側からソリに乗る側に移ればいい。

トナカイ $i$ をソリを引く側からソリに乗る側に移ると、引く力が $P$ 下がり、重量が $W$ 増えるので、 $P + W$ だけ損する。コンテスト中は $P - W$ と思い込んで最後まで解けなかった。

トナカイを $(P + W, P, W)$ の昇順にソートする。最初は全トナカイを引く側にして、引く力 $S = \sum P$ 、重量 $T = 0$ にする。トナカイをソリに乗せるたびに、 $S$ から $P$ を引き、 $T$ に $W$ を足す。 $i$ 頭載せて $S < T$ になったら、 答えは $i - 1$ である。

コードはこちら

なぜか実装を間違えて2ペナした。

$A$ , $B$ をそれぞれ昇順にソートしても答えは変わらないのでそうする。それと $N > M$ なら $N,M$ および $A,B$ を入れ替える。

$B$ を二分探索して、 $A_i$ 以上の要素が $j$ 番目およびそれ以降にあるとする。 $j$ 番未満の要素について答えは $(j-1)A_i - \sum_{k=1}^{j-1}$ であり、 $j$ 番およびそれ以降について答えは $\sum_{k=j}^{N} - (N-j+1)A_i$ である。これを128-bit整数を用いて、値が負にならずオーバーフローしないように求める。累積和は事前に求めておく。

答えが0以上998244353未満になるように細かく正規化すれば、 __int128 ではなく int64_t で 解ける 。

constexpr Num Mod = 998244353;
Num normalize(Num x) {
    return (Mod + (x % Mod)) % Mod;
}

任意精度整数を使っても 解ける が、 boost::multiprecision::cpp_int のまま正規化してから long long int にキャストしないとオーバーフローする。

コードはこちら

ビームサーチっぽく実装する。ただし同じ深さで同じ値の部分木を同一視する。

探索対象の頂点集合を $S$ とする。 $S$ は std::deque にして挿入順序を保持し、前からも後ろからも挿入できる。

辺が $(x,y)$ であるようなグラフ $G$ を構成する。最初に根つまり頂点0からの距離が1の各頂点 $i$ について、 $(1,y_i,i)$ の昇順に $S$ の末尾に追加する。これは根からの距離が $L$ , 頂点の値が $v=y_i$ , 頂点番号が $i$ のときに $(L,v,i)$ を要素とする。併せて、答えの頂点番号列 $W$ に、 $i$ を順番に末尾に加える。

$S$ のうち先頭から、 $L$ および $v$ が等しい要素をまとめて扱う。

• 要素 $(L,v,i)$ を $S$ から取り除いて、別途 $T$ に保存する。各 $i$ を $W$ の末尾に追加する
• $T$ の各要素 $(L,v,i)$ について、頂点 $i$ の子頂点 $u$ それぞれについて $(L+1, y_u, u)$ を探索候補 $U$ に加える
• 最後に $U$ を $S$ の先頭に加える。 $U$ の末尾から順に $S$ に std::deque::push_front する

これを繰り替えして、 $S$ が空になったら、答え $W$ を出力する。

std::list を使い、ビームの範囲を区切るフェンスを導入すると、 実装 の見通しがよくなる。

公式解説通りTrie木を使うと こう 実装できる。 ポインタ を使ってもいいが std::vector 上にTrie木を構築できる。しかしTrie木解法を自力で思いつく気がしない。

コードはこちら

コンテスト中は、C,E問題を解けず、残り時間が少ない状態で問題文を読んだ。もしかしたら解けないかと思ったが、コンテスト後に17分で解けてしまった。十分残り時間で間に合ったし、そもそもC,E問題を捨ててF問題から解くべきだった。結果的に問題選びを間違えてパフォを500下げてしまった。

いかにもセグメント木に何を載せるかである。マンハッタン距離の定番通り、 $S = x + y$ 、 $D = x - y$ と変換する。 $min(S), max(S), min(D), max(D)$ を載せる。セグメント木の区間合成は $min$ は $min$ , $max$ は $max$ を取る。 $min$ の単位元を $\infty$ 、 $max$ の単位元を $-\infty$ にする。

クエリ1は $X,Y$ を使って、上記の値の組を一点更新する。

クエリ2は区間 $S = x + y$ 、 $D = x - y$ と変換する。区間 $[L,R] $の $min(S),max(S),min(D),max(D)$ に対して $|S - min(S)|, |S - max(S)|, |D - min(D)|, |D - max(D)|$ の最大値が答えである。