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

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

バチャではなく、一問ずつ解いた。考えがまとまらない。

コードはこちら

$\lfloor S/100 \rfloor = 2$ なら Success 、そうでなければ Failure を出力する。

コードはこちら

状態 $in \in {False, True}$ を考える。初期状態は $False$ である。

• login なら $in$ を $True$ にする。前の状態は関係ない。
• logout なら $in$ を $False$ にする。前の状態は関係ない。
• public なら何もしない。
• private なら、 $in = False$ の時に答えを1増やす。 $in = True$ なら答えは変わらない。いずれにせよ状態を変えない。

コードはこちら

累積和だとすぐ分かったが添え字で悩んだ。

$N = 1$ なら答えは1である。このハードコーディングを間違えた。以下 $|A| > 1$ とする。 $A$ の値ではなく累積和 $C_i = \sum_{j=0}^{i}$ を持つ。

• $C_{-1} = 0$ である
• $0 \leq i < K$ のとき、 $C_i = i + 1$ である
• $i \geq K$ のとき、 $C_i = C_{i-1} + C_{i-1} - C_{i-K-1}$ である

答えは $C_N - C_{N-1}$ である。Modがいつもの素数ではないので、以下の通りにする。

atcoder::modint::set_mod(1000000000);
using ModInt = atcoder::modint;

実は累積和ではなく、スライディングウィンドウで解ける。 $Nlog(N)$ 解法でよければセグメント木が簡便らしい。

コードはこちら

方針はすぐ立ったが考えがまとまらない。

o の前後に . を置けないので、 o の前後を . で埋める。残った ? は o を置きたければ置ける場所であり、それらの値が o または . に一意に決まるならそのように決め、決まらないなら ? のままにする。

上記の通り埋めた後の $S$ に含まれる o が $C$ 個とする。 $C = K$ なら、残りの ? をすべて . に置き換えたものが答えである。以下少なくとも一個以上の ? を o にしなければならない状況を考える。

? をランレングス圧縮する。ラン $i$ が長さ $L_i$ として、 o を最大 $\lceil L_i/2 \rceil$ 個置ける。最大限 o を置くと $D = \sum L_i$ 個置けるが、 $D < K - C$ 個ならどの ? についても、 o に置き換えるか . にするか選択の余地があるので、すべての ? は ? のままである。

$D = K - C$ 個なら最大限 o に置き換える。奇数長のランは o.o.o と、 o で始まり o で終わり o. が交互に続くパターンしかないのでそのように ? を置き換える。偶数長のランは o 始まりと . 始まりの両方になりうるので、 ? のままである。

上記の通り $S$ の ? を置き換えたものが答えである。公式解説1の通りである。

コードはこちら

方針はすぐ立ったが考えがまとまらない。

問題を以下のように読み替える。

1. 頂点 $1..K$ だけからなるグラフ $G_k$ が連結かどうか調べる。連結ではない、つまり頂点1を含む連結成分 $S_k$ のサイズが $K$ 未満なら -1 を出力する。
2. 頂点 $1..K$ だけからなるグラフから、 頂点 $K+1..N$ に直接辺が出ているなら、その頂点集合 $R_k$ を求める。上記で -1 を出力しなければ、 $|R_k|$ を出力する。

$K = 1..N$ について、上記を求める。 $K = 1$ については、 $S_1 = {1}$ 、 $R_1$ は頂点1と直接辺でつながっている頂点 $2..N$ である。

頂点 $K-1$ まで求まっていて、 $K$ について求める。頂点 $K$ と直接つながっている頂点集合を $U$ とする。

• $j \in U$ について、 $j < k$ なら頂点1と 頂点 $j$ を連結する。
• $R_k = R_{k-1} \setminus k$ で初期化する。つまり $R_k$ から $k$ を除く。
• $j \in U$ について、 $j < k$ なら $R_k$ から $j$ を除く
• $j \in U$ について、 $j > k$ なら $R_k$ に $j$ を加える
• 頂点1の連結成分の大きさが $k$ なら(既述の通り頂点 $1..k$ が連結なら) $|R_k|$ を出力する。そうでなければ -1 を出力する。

計算コストは $R$ に辺を出し入れする回数で決まるので $O(Nlog(N))$ である(辺の数が $O(N)$ なので)。

コードはこちら

F問題はいつまで経っても解けないのにG問題は解けた。

答えは $(sx_i, sy_i)$ から $(gx_j, gy_j)$ までの距離のうちどれか一つである。それ以外の距離はわざわざ寄り道しているのでもっと短くできる。 $i,j \in 1..N$ の距離の二乗を整数で求めて $L[i,j]$ とする。これを座標圧縮する、つまり昇順に並べて同じ値は同じ順位にしたものを $D[i,j]$ とする。 $D$ が取りうる値を昇順に並べたものを $V$ とする。

$|V| = 1$ なら $L$ の唯一の値が答えである。そうでなければ $k \in 1..|V|$ で二分探索する。何を二分探索するかというと、 $D[i,j] \leq V[k]$ に限った $i,j$ だけで目標を達成できるかどうかを判定する。

具体的には $(i,j)$ の組を $N$ 個以上作れるかどうか判定すればよく、二部グラフのmax-flowを求めて $N$ かどうか判定する。 $(Soucre,i,j,Sink)$ というグラフを作り、 $(Source,i)$ , $(j,Sink)$ はすべての $i,j \in 1..N$ について容量1の辺を張り、 $(i,j)$ は $D[i,j] \leq V[k]$ なら容量1の辺を張る。 $(Source,Sink)$ の容量が $N$ かどうか判定する。

最後に、二分探索の結果 $k$ を $L$ に逆変換して平方根 $\sqrt{L}$ を求めると答えになる。

バチャではなく、一問ずつ解いた。

コードはこちら

$S$ の先頭から各文字を走査して、英大文字だったら出力する。

コードはこちら

これまでに案内した人数を $P = 0$ で初期化し、これまでに並んだ人の食券番号を先頭から $V$ とする。 $V$ は0-based indexingとする。

• クエリ1は $X$ を $V$ の末尾に追加する
• クエリ2は $V[P]$ を出力し、 $P$ を1増やす。

コードはこちら

初期状態で、 $C[i=1..N]$ は料理 $i$ に含まれる嫌いな食材の集合とする、 $F[j=1..M]$ は食材 $j$ を含まない料理の集合とする。 $B$ をまだ見ていないとき、答えは $C[i=1..N]$ のうち要素が空なものの数である。

$j = B_k$ について以下の操作を行う。

• $a \in F[j]$ について、 $C[a]$ から $j$ を除く
• この操作の前に $C[a]$ が空ではなく、この操作の後で $C[a]$ が空になったら、料理 $a$ を新たに食べられるようになったので答えを1増やす

コードはこちら

線分ではなく直線だった。問題を読み違えて時間が掛かった。

すべての直線の組が交わるとき、答えは $M(M-1)/2$ である。平行な直線は交わらないので、平行な直線の組を求めて答えを引く。

直線の向きは、 $S = (A - 1 + B - 1) mod N$ で一意に決まる。よって直線の向き $S = 0..(N-1)$ について、そのような直線が $L$ 本あるとき、答えから $L(L-1)/2$ を引けばよい。これをすべての $S$ について求める。

公式解説通りである。

コードはこちら

所持金 $x$ と、正解した問題の集合 $U \in 0..2^N-1$ の動的計画法 $DP[x][U]$ だと思ったが、何をDPに載せるのか分からなくなった。載せるべきは確率ではなく期待値で、答えが $DP[X][\emptyset]$ だと分からなかった。コストの和がちょうど $X$ でなくてもこの漸化式で解けることが分からなかった。よく考えたら $C_1=C_2=2, X=5, N=2$ でもこれで上手くいくと分かる($X > 1$ の奇数について非0の値が求める)。

コードはこちら

半分全列挙だとは分かったが、TLEに苦しんだ。おそらく想定解法ではないが、数時間かけてごり押した。E問題が解けなくてF問題を解けるのはなぜだろう。

座標を0-based indexingとする。対角線 $|X+Y| = N-1$ にある $N$ マス $(0,N-1)...(N-1,0)$について、取りうる $modM$ の値を全列挙すればよい。一番経路が多い $N-2 \choose (N-2)/2$ が ${18 \choose 9} = 48620$ なので、全経路を探索すれば全列挙が間に合いそうである。というより後で知ったが、二項係数の和 $\sum_{i=0}^N {N \choose i} = 2^i$ である。 $(1+1)^n$ の係数から導出できる。

$mod M$ はいつも通り求める。左上から桁を末尾に増やすときは $10accum + digit$ 、右上から桁を先頭に増やすときは $digit 10^{width} + accum$ で累積する( $width$ は右下からのマンハッタン距離)。このとき経路中で $modM$ 演算を取るとTLEする。高々10進数9桁なので、 $mod M$ を取るのは最後にまとめてで構わない。

ある対角線のマスについて、左上からの累積値が $a \in 0..(M-1)$ を取るとする。 右下からの累積値 $S$ について、 $(a + max(S)) mod M$ は常に候補になる。 $M - a$ 未満で最大の値 $b \in S$ があれば $a + b$ が答えの候補になる。これは二分探索で求まる。センチネルとして $min(S) + M$ を $S$ に加えておくと処理しやすい。

とにかく $mod M$ をできるだけ減らすとTLEを回避できる。だいたい公式解説通りだが、なぜTLEしたのだろう。

バチャではなく、一問ずつ解いた。解くのが遅い。

コードはこちら

添え字を2ずつ増やす。

コードはこちら

? を置き換える方法は必ず $26^4$ 通りなので、 $T$ を置き換えて $S$ にし、 $S$ が $U$ を含むかどうか調べる。

コードはこちら

$PS[X]$ をユーザ $X$ が閲覧できるページ、 $GS[X]$ をユーザ $X$ がすべてのページを閲覧できるかどうかとする。 $PS[X]$ の初期値は空集合、 $GS[X]$ の初期値は $False$ である。

• クエリ1は $PS[X]$ に $Y$ を追加する
• クエリ2は $GS[X]$ を $True$ にする
• クエリ3について $Y \in PS[X] \lor GS[X]$ なら Yes 、そうでなければ No である。

コードはこちら

色々見落としが多い。

$A$ に $a$ が現れる回数を $C[a]$ とする。 $|C|$ を $A$ に現れる数値の重複無し種類とする。

$D = 0$ のときは、答えは $N - |C|$ である。これを忘れるとTLEする。

$D > 0$ のときを考える。 $a$ を等差数列 $a, a+D, a+2D, ...$ に分解する。この分解は $O(N)$ でできる。分解した等差数列 $P$ について、等差数列のそれぞれの成分 $a$ が $A$ に現れる回数 $T = C[a] : a \in P$ を考える。

$\sum T$ が最大になるように $T$ を上手く間引く。これは動的計画法でできる。 $T$ の $i \in |T|$ 番目の要素を間引いた時の $T[1..i]$ の要素数を $DP[i][0]$ , 間引かないときの要素数を $DP[i][1]$ とする。二回連続で間引くことはできても、二回連続で間引かないのは許容されないので、

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

で更新する。このとき $(\sum T) - max(DP[|T|][])$ が、ある等差数列について求める答えである。これをすべての等差数列について求めた和が最終的な答えである。

コードはこちら

ローリングハッシュでまとめながら集合を管理と分かったが手こずった。

文字列 $T$ の先頭 $k=1..|T|$ 文字についてのローリングハッシュを $H(T,k)$ とする。

• $S_1$ に含まれる文字列 $T$ の $H(T,|T|)$ の集合を $X$ とする。 $S_1$ 丸ごとのハッシュである。
• $S_2$ に含まれる $j \in 1..|S_2|$ 番目の文字列 $T = S_{2,j}$ に注目する。値が $h = H(T,1..|T|)$ となるような文字列の添え字の集合を $Y[h]$ とする。 $S_2$ が持つ接頭辞の候補である。
• $S_2$ の $j$ 番目の文字列が、 $S_1$ のいずれかの要素が接頭辞になるかどうかを $U[j]$ として持つ。接頭辞なら1、接頭辞でなければ0である。 $U$ は0-based indexingとしてセグメント木として持つ。

クエリ $T_i = 2$ が来た時点で、 $|S_2| - \sum U$ が答えである。クエリ $X,Y,U$ を更新する方法を定める。

クエリ $T_i = 1$ をこう処理する。 $h = H(S, |S|)$ として、 $j \in Y[h]$ について、 $U[j] = 1$ とする。その後の $S$ に $h$ を追加し、 $Y[h]$ を空にする。空にし忘れるとTLEする。

クエリ $T_i = 2$ をこう処理する。クエリが来る前の $|S_2|$ を $L$ とする。

• $U[L] = 1$ なら既に $S_1$ の接頭辞なので何もしない
• $U[L] = 0$ かつ $h = H(S, 1..|S|)$ として、いずれかの $h$ が $X$ に含まれるなら $U[L] = 1$ とする。既に $T$ は $S_1$ の接頭辞である。
• $U[L] = 0$ かつ $h = H(S, 1..|S|)$ として、いずれの $h$ も $X$ に含まないなら $h$ それぞれについて $Y[h]$ に $L$ を 追加する。今は $T$ は $S_1$ の接頭辞ではないが、将来は接頭辞にされるかもしれない、という予約である。
• 上記のいずれの場合も、 $L$ に1足す

コードはこちら

$O(N^2)$ が許されるので総当たりする。 $N$ を式にした時の演算子の数は $O(log(N))$ である(同じ数字を10回程度しか足さないので)。

$N = A + B$ と $N = A \times B$ についてメモ化再帰しながら総当たりして、最も文字列長が短いものを返す。 1,11,111,1111 をそのまま文字列にしたものをあらかじめ用意しておく。 $A,B$ の文字列表現をそれぞれを括弧で囲むかどうか判定する。

$A op B$ の $B$ に括弧が要るかどうかは、 $A$ の先頭から以下の通り調べる。 $B$ も同様である。

• () 内は調べない。これは入れ子の深さが0以外かどうかで分かる。 ( で1深く、 ) で1浅くする。
• $op = \times$ で $+$ が出たら、 $B$ に括弧が要る。 $op = +$ は調べなくてよい。

バチャではなく、一問ずつ解いた。E問題がわからない。

コードはこちら

出現した文字を数え、出現するかもしれない文字 a-z それぞれについて出現しなかったものを出力する。

コードはこちら

色を変えてから回転することと、回転してから色を変えることは等価である(回転後の場所の色を変えればいいので)。よって $r = 0..3$ 回転した時の操作回数は、 $S$ を回転後に $S,T$ で色が違うマスが $C_i$ 個として、 $i + C_i$ である。この最小値を求める。

コードはこちら

グラフにサイクルがあるか、と問題を読み違えて時間を溶かした。いったい何をしているのだろう。

辺の数が $N$ で、頂点数 $N$ の唯一の連結成分を持ち、すべての頂点の次数が2なら Yes 、そうでなければ No である。次数を無視すると、結び目があるグラフをサイクルグラフを誤認する。

コードはこちら

STLの柔軟性に助けられた。

std::map は std::vector<int> をキーに持つことができる。これを利用してDPを作る。

$DP[V,C]$ は、動物 $1..M$ を見た回数のベクトル $V[1..M]$ のときに、動物園の最低入場料 $C$ という連想配列とする。ただし $V \in 0..2$ とし、2回以上見たら2回と同じとみなす。初期値は $DP[0] = 0$ 、それ以外は $DP[] = \infty$ とするが、 $DP[] = \infty$ なら $DP$ に載せない。

同じ動物園を二度までは見る(三度見る必要はない)ので、動物園を見る順番を $P[1..2N] = 1..N, 1..N$ とする。 $DP[0,0]$ は動物園を全く見ていなければコスト0という意味である。

動物園 $k=P[i]$ でコスト $C_i$ で動物 $U$ を見る。 $T$ はベクトルで、動物園 $k$ 動物 $j$ を見られるときに $U[j] = 1$ 見られないときは $U[j] = 0$ である。DPの更新式は以下の通りである。

• $S$ は、値が $\infty$ でない $DP$ のすべての要素とする
• $S+T = min(2, S[j] + T[j])$ とする
• $DP[S+T] = min(DP[S+T], DP[S] + C_i)$

答えは、動物を二回見たというキーに対する値 $V = (2,2,...,2) , DP[V]$ である。

$DP$ の要素は高々 $1+2^{2N}$ 個なので、制約から 1048577個である。計算量は $NN4^{N}$ だが間に合ってしまった(60 ms)。

実は動物園を $3^N$ の全探索すればよかった。

コードはこちら

何時間考えてもわからない。MSTを作る問題だと思ったら全く違った。公式解説をほぼそのまま実装して解説ACした。後ろから考える典型である。

MSTを作ればよいのだが、合流する頂点を任意だと思ったので計算量が多すぎた。頂点 $i$ に頂点 $i+1$ 以降をすべて合流させると公式解説と同じ考え方になる。

バチャではなく、一問ずつ解いた。発想は早いが実装が遅い。

コードはこちら

題意通り実装する。

コードはこちら

$i=1..M$ が $A$ に何個含まれるか示す連想配列 $T[i]$ を持つ。

値が非0の $T$ のエントリ数が $M$ 未満になるまで、 $A$ の末尾の要素 $A_j$ を $T[A_j]$ から1減らす。 $T[A_j]=0$ になったら $T$ からエントリ $A_j$を削除する。 $A$ を削除した回数が答えである。

コードはこちら

要素 $1..i$ までの累積和 $C_i = \sum_{j=1}^{i}$ をあらかじめ求める。答えは $\sum_{i=1}^{N-1} A_i(C_N - C_i)$ である。

コードはこちら

多地点BFSなのだが、実装方法を忘れてTLEした。

距離 $D$ の隣、距離 $D+1$ の地点をキューに積むとき、キューの先頭距離が $L$ なら、 $D + 1 < L$ ならキューの先頭に積み、そうでないならキューの末尾に積む。 $D + 1 \leq L$ にするとTLEする。

すべての出口をキューに積んでBFSし、それぞれの床についてある出口までの最短距離を求める。そのあとそれぞれの床について、自分より出口までの距離が短くなる方角を記入すると答えになる。

コードはこちら

組み合わせを高速に前計算すればよいが、実装方法を忘れて時間が掛かった。

並び方を列挙するのに、最も左にあるブドウに注目する。最も左にあるブドウより左に、バナナが $i = 0..C$ 個あり、最も左にあるブドウより右に、バナナが $C - i$ 個あるとする。このような $i$ について、取りうる組み合わせの数を足すと答えである。

この方法で題意のうち、以下の二制約を必ず満たす。これは $D - 1$ 個のブドウと $C - 1$ 個のバナナを並べる方法なので ${{D - 1 + C - i} \choose {C - i}}$ 通りである。

• リンゴはすべてブドウよりも左側に並べる
• オレンジはすべてブドウよりも左側に並べる

最も左にあるブドウより左について、リンゴを左に、バナナを右に寄せ、間にオレンジを挟む。そうすると残りの制約である、リンゴはすべてバナナよりも左側に並べる、を満たす。これは ${{A + B + i} \choose i}$ 通りである。

上記を前計算する。 ${D - 1 + C - i} \choose {C - i}$ について、 $C - i$ と $i$ を入れ替えて、 ${D - 1 + i} \choose {i}$ を求める。これは以下の通り、 $i$ について逐次的に求まる。

• ${{D - 1} \choose {0}} = 1$
• ${{D - 1 + i + 1} \choose {i + 1}} = {{D - 1 + i} \choose {i}} \times (D - 1 + i + 1) / (i + 1)$

${{A + B + i} \choose i}$ も $i$ について逐次的に求まる。

• ${{A + B} \choose 0} = 1$
• ${{A + B + i + 1} \choose {i + 1}} = {{A + B + i} \choose {i}} \times (A + B + i + 1) / (i + 1)$

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

コードはこちら

実装方法が全く分からなかった。

公式解説が何種類かあるが、線分 $C,D$ に飛び込む他の線分 $A,B$ を数え上げる方法なら分かる。この方法は公式解説2にあり、その通り実装した。セグメント木なのだろうとは想像したが、クエリ並び替えが要ることが分からなかった。

バチャではなく、一問ずつ解いた。相変わらず、他の方の難易度と私の難易度が逆転する。

コードはこちら

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

コードはこちら

任意精度整数を使って積を求め、積が $10^{K+1}$ 以上になったら1にする。

コードはこちら

方針はすぐ立ったが実装が進まなかった。

セグメント木 $U[i=1..N-1]$ の要素を、 $A[i+1] - A[i] > 0$ なら $1$ 、そうでなければ $0$ とする。同様にセグメント木 $D[i=1..N-1]$ を、 $A[i+1] - A[i] < 0$ なら $1$ 、そうでなければ $0$ とする。

$i=1..N-1$ について全探索する。

• チルダ型の1番目の点を $i$ とする
• チルダ型の2番目の点を $L$ とする。これは $U[i..L-1]$ がすべて1となる最大の $L$ である。セグメント木の max_right を使って求める。
• チルダ型の3番目の点を $M$ とする。これは $D[L..M-1]$ がすべて1となる最大の $M$ である。セグメント木の max_right を使って求める。
• チルダ型の4番目の点を $R$ とする。これは $U[M..R]$ がすべて1となる最大の $R$ である。 $[M,R)$ は題意を満たすので、 $R - M$ を答えに加える。

公式解説はランレングスで解いている。

コードはこちら

C問題と異なり、あっさり実装が終わった。

問題とは $y,x$ の定義を入れ替えて、 $y$ を縦=行、 $x$ を横=列とする。

行 $y$ にあるのごみの位置の集合を $R[y=1..h]$ とする。列 $x$ にあるのごみの位置の集合を $C[x=1..w]$ とする。

• クエリ1は、 $R[y]$ の要素数を答える。その後 $x \in R[y]$ について、 $C[x]$ から $y$ を除く。
• クエリ2は、 $C[x]$ の要素数を答える。その後 $y \in C[x]$ について、 $R[y]$ から $x$ を除く。

要素を除く回数は高々 $N$ 回なので償却計算量は $O(Nlog(N))$ である。

コードはこちら

全く分からなかった。公式解説6を読んでC++で実装したのが上記のコードである。

E問題は解けないのにF問題は解ける。

コードはこちら

オイラーツアーを使って部分木の包含関係を構築する。

オイラーツアーのパスつまり $i$ 番目に頂点 $v$ をたどったことを $P[i] = v$ とする。また頂点1を根としたときの頂点 $v$ の深さを $D[v]$ とする。これらをオイラーツアーで求める。

オイラーツアーにおける頂点の出入口を求める。頂点 $v$ を固定して $P[i] = v$ となる最小の $i$ を $In[v] = i$ 、 $P[i] = v$ となる最大の $i$ を $Out[v] = i$ とする。特に葉については、 $In[v] = Out[v]$ である。

オイラーツアーのパス長を要素数とするセグメント木 $T$ とする。 $T$ には頂点 $v$ の重みを載せるが、載せる場所は $In[v]$ とする。頂点 $v$ について区間和 $T[In[v],max(In[v],Out[v]-1)]$ が、頂点 $v$ を根とする部分木の重みの和である。この $max$ は、 $v$ が葉のときに頂点 $v$ 自身の重みを返すためにある。

あとはクエリを組み立てる。

• $T[In[i=1..N]] = 1$ で初期化する。すべての頂点の重みの和を、 $S = N$ で初期化する。
• クエリ1は、 $T[In[x]]$ に $w$ を加算する。 $S$ に $w$ を加える。
• クエリ2は、辺 $y$ の頂点 $u,v$ のうち深い(頂点1からの距離が長い: $D[u], D[v]$ の大きい)方を $z$ とする。深さが同じならどちらでもよい。部分木の重み $W$ と、残りの部分木の重み $S - W$ の差が答えなので、 $|S - 2 \times T[In[z],max(In[z],Out[z]-1)]|$ が答えである。

公式解説と同じ解き方である。

バチャではなく、一問ずつ解いた。

コードはこちら

$\lfloor A/B \rfloor$ と $\lceil A/B \rceil$ のうち $A/B$ との差が小さい方を出力する。

コードはこちら

二つのサイコロの出目を総当たりし、該当する場合を $6^2$ で割る。

コードはこちら

ボタンAを押す回数は $|S|$ なので、ボタンBを押す回数を求める。

$S$ の後ろから考える。これまでボタンBを押した回数を $C$ とする。 $S$ のある桁を $D$ にするには、 $0$ を $C$ 回押して、そこから何回か押して $D$ にする。この最小回数は、 $(D + 10 - C) mod 10$ 回である。これを $C$ に足して次の桁について求める。

答えは $|S| + C$ である。

コードはこちら

std::bitset<32>::set() が引数無しでコンパイルでき、しかもたまたま入力例が通ってしまったので1ペナした。

XORなので総当たりしかない。ドミノを既に置いた位置を std::bitset<32> で管理し、ドミノが置かれていないマスに書かれた整数すべてのビットごとの排他的論理和を $C$ で求めておく。

ドミノを置きたいマス $[y,x]$ を水平から垂直方向にスキャンしてDFSする。 $x$ を1ずつ増やし、 $x = W$ なら $y$ を1増やして $x = 1$ にする。

• $[y,x]$ にドミノがなければ置いてもよい
  • ドミノを横に置く。つまり $[y,x],[y,x+1]$ にはみ出さない範囲 ($x+1 \leq W$) で置く。 $C$ を $C \oplus A_{y,x} \oplus A_{y,x+1}$ で更新する。
  • ドミノを縦に置く。つまり $[y,x+1],[y,x]$ にはみ出さない範囲 ($y+1 \leq H$) で置く。 $C$ を $C \oplus A_{y,x} \oplus A_{y+1,x}$ で更新する。
• 置かないで次の位置を調べる

コードはこちら

公式解説を読むまで全く手掛かりがつかめなかった。

コードはこちら

相変わらず、E問題は解けないがF問題は解ける。

ある $A_i$ が最大値となりうる区間 $[L,R]$ を、 $A$ の降順に求める。 $[L,R]$ が求まったら、 $[L,R]$ に含まれる $i$ を含むすべての部分区間 $[l,r]$ の長さについて、 $A_i$ を足せばよい。いかにもセグメント木と遅延セグメント木である。

前準備として、セグメント木と遅延セグメント木を用意する。

• $i = 1..N$ のうち、 $A_i$ を既にみていたら1、まだ見ていないなら0に対応するセグメント木 $T$ を作る。一点更新、区間minを取ることで、ある位置 $i$ の前後にある、まだ見ていない位置が分かる。これは std::set でもよい。
• 答えを遅延セグメント木 $U$ に載せる。区間長 $j$ の答えを $U[j]$ とし、演算はすべて整数加算にする。公式解説によれば、普通のセグメント木といもす法でもよい。

$A_i$ を降順に並べる。値が等しいものは一括処理するので、値 $A_i = v$ となりうる位置 $i$ の集合を $S_v$ とする。以下 $S_v$ ごとに処理を繰り返す。

• $i \in S_v$ について、既に $S_v$ のうち見た位置を $M$ とする(なければ-1)
• $i$ の前後にある、まだ見ていない区間を $[L,R]$ とする。 $T$ を二分探索すると求まる。少なくとも一点区間 $[i,i]$ を含み、それより広いかもしれない。
• 他の $S_v$ で既にみた区間を無視するために、 $L = max(M+1, L)$ と更新する
• 一点区間 $[i,i]$ に対応する答えとして $U[1]$ に $a$ を加算する
• $i$ を右端とする区間に対応する答えとして、 $i$ を除く区間長 $WL = i-L$ について $U[2..(1+WL)]$ に $a$ を一括加算する
• $i$ を左端とする区間に対応する答えとして、 $i$ を除く区間長 $WR = R-i$ について $U[2..(1+WR)]$ に $a$ を一括加算する
• $i$ を左端でも右端でもなく含む区間に対応する答えとして $WL$ と $WR$ のすべての和 $w$ の組み合わせについて $U[w]$ に $a$ を加算する
• $M = R + 1$ と更新する

$U[w]$ を二重ループにして $a$ を加算すると大量にTLEする。そこで $WL$ と $WR$ の二重ループのうち、小さい方をループして、大きい方を遅延セグメント木の区間更新にする。 $WL < WR$ なら $j = 1..WL$ について $U[(j+1)..(j+WR)]$ に $a$ を足すと一重ループになる。ここで $WL,WR$ の小さい方をループにしないと1 TLEする。

上記を一通り行い、 $U[1..N]$ を出力する。

バチャではなく、一問ずつ解いた。翌朝ではなく4日間掛けて解いた。D問題で躓き、E問題の考察に時間が掛かり、F問題は実装が進まなかった。

コードはこちら

$T_0 = 0$ として、 $T_{i+1} - T_i > S$ となる $i$ が一つでもあれば No 、そうでなければ Yes である。

コードはこちら

std::set に入れて一つずつ出力する。

コードはこちら

$[L-1,R)$ をいもす法で足す。つまり増分 $C[i]$ について、 $C[L-1]$ に1を足し、 $C[R]$ から1を引く。 $C$ の累積和の最小値が答えである。

コードはこちら

コンテストの翌晩解いたら頭が回らなくて解けなかった。翌々朝に解いた。朝頭が冴えてないと考えがまとまらない。

$S$ が全部0なら答えは0である。

$S_{i=1..N}$ の累積和を $C_i$ とする。便宜上 $C_0=0$ とする。

連続する1の最左位置を $L$ にすると決め打ちする。連続する1の最右位置を $R$ にすると決め打ちする。 $L=1$ のとき、答えつまり01を反転する回数は、 $[L,R]$ に含まれる0の数と、 $[R+1,N]$ に含まれる1の数である。これは累積和から $R + 1 - L + C_R - C_{L-1} + (C_N - C_R)$ である。この値をセグメント木 $T[L]$ に載せて、一点更新区間minを求める。

$L=1$ のときは、 $min T[1..N]$ の最小値が答えである。 $L > 1$ のときは、 $[1,L)$ に含まれる1の数 $C_{L-1}$ を考慮して、 $C_{L-1} + min T[L..N]$ が答えである(これは $L=1$ でも成り立つ)。これをすべての $L=1..N$ について求めると最終的な答えが求まる。計算量は $O(Nlog(N))$ である。

公式解説によると、累積minを求めると $O(N)$ らしい。実装は こちら 。

コードはこちら

制約から察した。

3秒制限なのだから、 $w < 2^{30}$ から $30$ 回 $M$ 辺をBFSするのだろうと思った。実際その通りである。

答え $A$ をコストと呼ぶ。2のべき乗の指数 $P = 30..0$ を降順に見ていく。ある $P$ について、辺の重みは $C=2^P$ 桁成分だけ考えて他は考えない。

辺の重みを $w \land C$ とみなしてBFSする。頂点1からの距離は、未到達なら $\infty$ 、到達しているなら $C$ または $0$ の二値になる。頂点までの距離が減る方向だけ探索し、減らない方向には移動しない。そうするとダイクストラ法のような $O(Nlog(N))$ ではなく、 $O(N)$ で探索することができ、ループにもならない。

頂点 $N$ までの距離が $C$ なら、頂点1から頂点Nまでどういう経路をとってもコスト $C$ は避けられない。よって答え $A$ に $C$ を加算し、すべての頂点から $C$ 成分を除く( $w$ を $w \land (\lnot C)$ で更新する)。

頂点 $N$ までの距離が $0$ なら、頂点1から頂点Nまである経路を通ればコストは増えない。よって辺のうち $C$ 成分がある( $w \land C > 0$ ) 辺を除いてグラフを再構成する。このような辺は通るべきではないので除く必要があり、除いても頂点1から頂点Nには到達可能である。

上記のように辺の重みを変えるか辺を除いたグラフについて、 $P$ を1減らして同様に繰り返す。最終的な総コスト $A$ が答えである。公式解説とは少し異なる。

コードはこちら

遅延セグメント木を使うことは一目瞭然だが、そこからが大変である。

足場が高い順にみる。この配列を $V$ とする。 $D = 0$ として、足場 $H_j$ をみるときに、その前後の足場 $[j-R, j+R]$ までの移動回数 + 1にすればよいことは分かる。

これは遅延セグメント木 $T[i]$ を、足場 $i$ までの移動回数の最大値として、区間maxで求まる。 $T[i]$ の初期値は0でなく $- \infty$ で、ここを間違えると5 WAsする。

$D > 0$ を利用するには、 $H_j \leq H_i + D$ な足場 $i$ だけを移動回数に数えるようにする。これは遅延セグメント木を更新するタイミングを、 $V$ の要素 $H$ をみたときではなく、 $H$ を遅延要素 $U$ に積んで、 ある足場 $H_j$ に対して $H_j + D \leq H$ が成立した時にする。

コードを見た方が早いが、ループを以下の取り構成する。

• 足場が高い順に $V$ から足場 $H_j$ を取り出す
  • $U$ から $H_j + D \leq H_i$ なる $H_i$ をそれぞれ取り出す
  • $T[i] = \infty$ なら $T[i] = 1$ にする。そうでなければ $T[i]$ を1増やす。
• 答え $A$ を $max(A, T[j-R, j+R])$ に更新する

上記の答え $max(0,A)$ を出力する。よく考えたら遅延セグメント木ではなく普通のセグメント木でよかった。

バチャではなく、一問ずつ解いた。

コードはこちら

$T[i] = o \land A[i] = o$ を満たす $i$ があれば Yes 、なければ No である。

コードはこちら

$A$ が $C[A]$ 個あるという尺取り法で解いたらWAの山が返ってきた。二分探索にしたらACした。

コードはこちら

原点を入れ忘れて1ペナした。

$L$ が3の倍数で無ければ答えは0である。以下 $W = L / 3$ とする。

円周の位置 $P$ に頂点が $c$ 個あることを、連想配列 $C[P] = c$ とする。これは $D$ の累積和を $mod L$ すると求まる。原点を忘れないようにする。

正三角形とは位置 $P \in [0, W)$ にある頂点について、位置 $P+W$ の頂点と、位置 $P+2W$ の頂点を結んだものである。 $P$ を全列挙して、 $C[P] \times C[P+W] \times C[P+2W]$ の和が答えである。

コードはこちら

問題文を理解できず泥沼になった。

連続部分文字列は長さ1以上である。ということは $S$ 自身を返しても問題ない。これがわからなくてWAの山を築いた。

$N = 1$ なら、 $S$ 自身が答えである。 $N = 2$ なら、 $S$ 自身または二文字を入れ替えたものが答えである。以下 $N > 2$ とする。

$S$ が広義単調増加つまり非減少とする。このときは文字を入れ替えないのが得なので、 $S$ 自身が答えである。

そうではなく、 $S_i > S_{i+1}$ が成り立つなら、 $S_i$ 文字を後に送ると得する。よって $l = i$ である。少なくとも $S[l..(l+1)]$ は候補に挙がる。

$r > l$ を探す。 $S_i < S_r$ を満たす $r$ があるなら、 $S[l..(r-1)]$ を左シフトするのが最適である。そのような $r$ がなければ、 $S[l..N]$ を左シフトするのが最適である。これらの候補のうち、最も辞書順が小さい文字列を返す。

コードはこちら

D問題は全然わからないが、E問題はあっさりわかった。相変わらず、他人にとっての難易度と自分にとっての難易度が逆転する。

直感的にはこの通りである。葉つまり次数が1の頂点はどうにかして対消滅させなければならない。よって他の頂点を葉にするより、葉を他の頂点に移動する方がコストは同じか安いと考えられる。

よってキューに次数1の頂点を積んで、キューから取り出した頂点を隣に移動することを繰り返す。トポロジカルソートの要領である。

• 初期値は、元々次数1の頂点をすべてキューに積む。木なので、次数1の頂点は少なくとも一つある。
• キューから頂点を取り出し、隣の頂点に電荷を移動し、そのコストを足す。次数が1なので、隣の頂点は一意に決まる。
• 隣の頂点の次数を1減らし、次数が1になったらキューに積む。

これを繰り返すといつか頂点が無くなるので、コストを答える。

コードはこちら

マージテックっぽいがそうではない。AC or TLEで、TLEが取れないが、方針はあっているのに実装が悪かった。

連結成分そのものは、最大 $N+Q$ 頂点のunion-find木 $T$ に載せればいい。現在の頂点数を $C$ として、連結成分数は $T - C + 1$ 個である。初期値として、全頂点間の距離を、優先度キュー $S$ に載せる。ここは std::priority_queue が正しく std::set だとTLEする。頂点 $(i,j)$ の距離が $d$ なら、 $(d,i,j)$ を昇順に載せる。

クエリには以下の通り答える。

• クエリ1は、 $C$ を1増やし、頂点 $C$ について、初期値と同様に他の頂点までの距離を求めて $S$ を更新する
• クエリ2は、 $S$ を昇順に見ていく。
  • $(d,i,j)$ について、 $(i,j)$ が連結成分なら除いて無視する
  • $(d,i,j)$ について、 $(i,j)$ が連結成分でなければ、最小の $d$ について頂点 $(i,j)$ を $T$ でマージする。最小の $d$ 以外は見ない。
• クエリ3は、 $T$ において、 $(i,j)$ が連結成分かどうか返す

この方針でTLEが取れないので公式解説を読んだら、上記の方法で正しかった。 std::priority_queue だと591 msec、 std::set だと2秒制限に間に合わずTLEする。こんなに実行時間が違うのか。C++だからといって定数倍を気にしないとこうなる。

ABC 376以来、ものすごく久しぶりにABCにratedで出場した。パフォ1509の快勝で水コーダーに復帰である。

コードはこちら

$A_i \geq K$ な $A_i$ を数える。

コードはこちら

$N,Q$ が小さいので全探索で通る。箱 $i$ に入っているボールの数を $C[X]$ とする。

• $X \geq 1$ なら、箱 $C[X]$ を1加算する
• $X = 0$ なら、箱 $(C_i,i)$ を昇順にソートし、先頭要素の箱 $y$ について $C[y]$ を1加算する

コードはこちら

典型的な、カーソルを使った読み替えである。

入力の $p$ を $C$ ずらすことを考える。初期値は $C = 0$ である。添え字は0-based indexingとして、 $mod N$ で考える。

• クエリ1は、 $A[p+C] = x$ にする。 $x$ は0-based indexingとし、入力から1引く。
• クエリ2は、 $A[p+C]$ を出力する。 $x$ は0-based indexingとし、入力から1引く。
• クエリ3は、 $C = (C + k) mod N$ に更新する

コードはこちら

$M$ が小さいので全探索が利く。ループしないようにガードを巧妙に設ける。

頂点 $i$ が経験した重みの集合を $S[i]$ とする。初期値は空集合である。

DFSですべての辺を探索する。 $DFS(i,W)$ は、頂点 $i$ をこれまでの重み $W$ で訪れることを示す。

• $DFS(0,0)$ を起点に探索する
• $W$ が $S[i]$ に含まれるなら、ループなので探索を打ち切る
• そうでなければ $W$ を $S[i]$ に加える。 $i$ から有向きな隣の頂点 $j$ について、辺 $(i,j)$ の重みを $w$ として $DFS(j,W \oplus w)$ で探索する。

XORなのでループを二周すると0になる。よっていつかこの探索は終了し、 $S[N]$ の最小値(なければ-1)が答えである。

想定解法は頂点倍化である。 $log(M)$ 余計に払ったがC++の力で押し切った。

コードはこちら

いかにもナップザックDPである。倒せるモンスターの数を二分探索する。

モンスター $T$ までを倒せるとする。 $T=0$ つまり一体もモンスターを倒せないのは真である。 $T > 0$ として、ナップザックDPを行う。

• $DP[i][j=0..H]$ はモンスター $i$ を倒した後、体力 $j$ のときの最低魔力を意味する
• 初期値は $DP[0][] = \infty, DP[0][0] = 0$ である
• $DP[i+1][j=0..H]$ を考える。体力を使い魔力を使わなければ、 $DP[i+1][j+A_i] = min(DP[i+1][j+A_i], DP[i][j+A_i])$ である。ただし体力 $H$ を超える更新はできない。
• 同様にを魔力使い体力を使わなければ、 $DP[i+1][j] = min(DP[i+1][j], DP[i][j] + B_i)$ である。ただし魔力 $M$ を超える更新はできない。

$DP[T][]$ が $M$ 以下なら、モンスター $T$ までを倒せる。そうでなければモンスター $T$ は倒せない。 $T$ を二分探索した答えを出力する。

この方針であっているが二分探索は要らなかった。 $log(N)$ 余計に払ったがC++の力で押し切った。

TLE解しか思いつかなかった。 #=1, .=-1 の二次元累積和をそのまま計算すると $O(H^2W^2)$ になる。

コードはこちら

問題文通り実装する。

コードはこちら

累積和を求めながら出力する。

コードはこちら

集合演算で解こうとして異常に長いコードを書いてWAし、一時間経ってそうではないことに気が付いた。

センチネルを両端に加えて、長さ $N+2$ の要素があるとする。

要素 $a$ を0から1にするとき、両隣がともに1なら区間がつながるので答えを1引き、両隣がともに0なら区間が生まれるので答えを1足し、それ以外は答えは変わらない。

要素 $a$ を1から0にするとき、両隣がともに1なら区間が分かれるので答えに1足し、両隣がともに0なら区間が減るので答えを1引き、それ以外は答えは変わらない。

コードはこちら

レジスタリネーミングの気持ちである。Tomasulo's algorithm で、 reservation stations がたくさん( $N+1+Q$ 個)ある場合に相当する。

サーバとPCの番号をまとめて機器と呼び、サーバを $0$ 、PCを $1..N$ する。データの世代を定義する。初期状態は機器の世代 $A$ に対して、機器番号 $A[a] = a$ とする。

クエリを読むごとに世代を1増やす。つまりクエリに対して $a=(N+1)..(N+1+Q)$ の世代番号を割り当てる。クエリに対して、機器の世代を更新し、世代間の依存関係のキュー $G$ を作る。また世代 $a$ で文字列 $s$ を追加したことを $S[a] = s$ とする。

• クエリ1に対して、 $A[p] = a$ と更新する。 $G$ に辺 $(a,A[0])$ を加えるよう $G$ に積む。
• クエリ2に対して、クエリ更新前の世代 $b = A[p]$ とし、 $A[p] = a$ と更新する。 $G$ に辺 $(a,b)$ を加えるよう $G$ に積む。
• クエリ3に対して、 $A[0] = a$ と更新する。 $G$ に辺 $(a,A[p])$ を加えるよう $G$ に積む。

キューを末尾から先頭に向かって再生し、依存グラフを更新する。

• 初期値は $a = A[0]$ とする
• 辺 $(from, to)$ について、 $a \ne from$ なら無視する
• 辺 $(from, to)$ について、 $a = from$ なら、答え $T$ に $S[to]$ の左右反転を加える。その後 $a = to$ に更新する

$T$ を反転した文字列を出力すると答えになる。

コードはこちら

なぜE問題の方がC問題より簡単なのだろう。

最大値となりうる数は面の数字の種類数なので、最大 $6N$ 個である。面の値 $A$ の重複無し集合 $M$ を昇順に一つ一つ試す。

• (((各サイコロの上を向いた面に書かれた数)の最大値)の最小値)は、((サイコロ面の最小値)についてすべてのサイコロの最大値)である。形式的には $L = max_i (min(A_{i,j=1..6}))$ である。
• サイコロ $i$ には、値が $a$ となる面が $c > 0$ 個含まれるとする。これを $(i,c)$ と表現する。面の値の集合 $F$ があり、 $F[a]$ は $(i,c)$ の集合とする。 $|F[a]|$ を $F[a]$ の要素数とする。

$F$ の要素を、 $a \in M$ の昇順に処理する。

• $S[i,a]$ を、サイコロ $i$ について、値が $a$ 以下となる面の数とする
• $b$ を、 $M$ にある数で $a$ 未満の最大値とする。ただし $a$ が $M$ の最小値であれば $b=0$ とする。
• $C[a]$ を、各サイコロのすべての面が $a$ 以下となる面の組み合わせ数とする。この値を $U$ として、 $a$ を処理するたびに更新する。便宜上 $C[0] = 0$ とする。
• $a < L$ なら $C[a] = 0$ である。 $F[a]$ に含まれる $(i,c)$ について、 $S[i,a]$ に $c$ を足す。この加算は以下でも行う。
• $a = L$ なら、 $U = C[a] = \prod S[i,a] > 0$ である。
• $a > L$ なら、 $U = C[a] = \prod S[i,a]$ である。これを愚直に計算するとTLEするので、下記の通り差分更新する。

$F[a]$ に含まれる $(i,c)$ ついて $P = S[i,a-1]$ に $c$ を足して、更新後の $S[i,a]$ を $P + c$ にすることを考える。このとき $U$ を $U(P+c)/P$ に更新する。こうすれば $a$ ごとに $N$ 回更新して $6N^2$ 回更新するのではなく、総更新回数を $6N$ 回に減らすことができる。

(((各サイコロの上を向いた面に書かれた数)の最大値)の最小値)が $a$ ちょうどになる面の数は $D[a] = C[a] - C[b]$ である。よって答えは $(\sum_a |F[a]| \times a \times D[a]) / N^6$ である。除算は最後に一回だけ行う。座標圧縮してもよいが、圧縮前に戻すのが一手間掛かる。

コードはこちら

$A < B$ となる組の数を数える。

コードはこちら

$T$ に含まれる文字の集合を $U$ とする。

$S$ の大文字の直前の文字 $C$ が、すべて $U$ に含まれていれば Yes 、そうでなければ No である。入力例3のように、 $U$ が空集合なら Yes である。

コードはこちら

両端を固定するのがややこしい。

いかにもDPである。区間最小セグメント木 $T[i]$ を、右からドミノ $i$ まで倒れるならその最小ドミノ個数(なければ $\infty$ )とする。

• $S_{2..(N-1)}$ を昇順にソートする。 $S_1$ と $S_N$ を固定することに注意する。
• 最初に $T[i=2..N]$ について、 $2S_1 \geq S_i$ なら $T[i] = 2$ 、 $2S_1 < S_i$ なら $T[i] = \infty$ とする。
• $i=3..N$ について、自分を倒せるドミノの位置を決める。これは $h = \lceil S_i / 2 \rceil$ として、 $h \leq S_{j=2..(i-1)}$ を二分探索する。
• $T[i] = min(T[i], 1 + min(T[h,i-1]))$ と更新する。

$T[N]$ が答えである。ただし $\infty$ なら -1 と出力する。

想定解法は貪欲法らしい。

コードはこちら

実装が重いのだが、たぶんもっと良い方法がある。

操作後の $G$ が連結である必要はない。これは入力例3から分かる。よって頂点を任意の組に分割する方法を網羅する。これはDFSでできる。ただし組の頂点数は3以上にする。組を固定して以下を考える。

頂点を組に分割したら、連結成分 $S$ をサイクルにする。 $S$ の順列は先頭を固定すれば $(|S|-1)!$ 通りである。順列を網羅すれば、それぞれの順列に対応した辺の集合 $E$ が得られる。

• $E$ に含まれて、 $G$ 含まれない無向辺を追加する。この操作回数を $A$ とする。
• $G$ の辺のうち、 $S$ に含まれる頂点からなるグラフ(誘導部分グラフ)を $T$ とする。 $T$ に含まれて、 $E$ 含まれない無向辺を削除する。この操作回数を $B$ とする。
• $S$ について $A+B$ の最小値を求める

この操作を行うと、ある組について、連結成分についての操作回数 $A+B$ が求まる。その後に、 $G$ のうち異なる連結成分を結ぶ辺を削除する。この操作回数 $C$ は、 $S$ が決まれば一意に求まるので、連結成分の $A+B$ の最小値を求めるときには考慮しない。

こうしてある組について $A+B+C$ が求まる。すべての組について $A+B+C$ を最小化したものが答えである。

公式解説1は、連結成分が2個以下であることを利用している。他の解説では $N$ 辺のグラフを全列挙する方法が示されていて、 ${{8 \times 7 / 2} \choose {8}} = 3108105$ 通りを効率よくC++で実装すれば205 msで 間に合う

コードはこちら

D問題が分からずE問題を先に解いた。エッジケースの作り込みに苦しんだ。

少なくとも答えは $L$ 自身の1種類ある。 $L = R$ なら答えは1である。 $L = 1$ なら最小公倍数1を数えて(答えの最低値を2にして)、 $L = 2$ として以下に進む。

$i = (L+1)..R$ について、 $A_i$ を考える。 $A_i$ の種類が増えるとは、ある素数 $p$ が存在し、 $p^k$ は $i$ 以下の数の約数にならないが、 $p^{k+1}$ は $i$ の約数である、という状況である。

$i$ を素因数分解するとTLEするので、 $p = 2.. \sqrt{R}$ について掃き出す。これを $2.. \sqrt{L}$ にすると2 WAsする。 $p$ のべき乗 $p^{k}$ を考えたとき、 $L < p^{k} \leq R$ を満たす $k$ の数(0以上)を答えに加える。同時にエラトステネスの篩の要領で、 $(L+1)..R$ のうち、ある $p$ の倍数である数に印をつける。

最後まで印が付かない数は素数である。よって素数の個数を答えに加える。これらの和が答えである。とにかく等号不等号の扱いがややこしい。

コードはこちら

荷物を詰めるたびに、カバンの容量を減らす。

コードはこちら

問題文通り総当たりする。

コードはこちら

ランレングスをキューに積んで順に取り出す。

コードはこちら

エッジケースを取りこぼすと29 WAsするマルチテストケースが容赦ない。

自明な例として、 $N = 2$ のときと、 $A$ が一種類のときは Yes である。

$|A|$ が一種類のときは、比が $\pm1$ のときを考える。これは $A$ のうち負になる要素が $\lfloor N/2 \rfloor$ 個または $\lceil N/2 \rceil$ 個なら Yes 、そうでなければ No である。

それ以外は比が $\pm1$ 以外である。 $A$ を絶対値の昇順に並べて、 $A_{i+1} / A_i = A_{i+2} / A_{i+1}$ つまり $A_{i+1}^2 = A_i A_{i+2}$ がすべての $i$ について成り立つなら Yes 、そうでなければ No である。

コードはこちら

敢えてE問題から解いてみたが、何を思ったか制約を読み違えて全探索したらTLEした。正しくは以下の通りである。

最初に上手くいかない方針を述べる。1がどこにあっても、左端に寄せることは可能である。 $P_i = 1$ とし、 $i = 11010b$ なら、 $[0,2^5)$ を反転すると $1$ の位置はビット反転の $i = 00101b$ になる。以下同様に、最上桁が $1$ のときに、それ以外の桁を反転するということを繰り返すと、いつか $i = 0$ になる。しかしこの方法で $1..2^N$ を左に寄せるとTLEする。

よって一気に左に寄せる方法を考える。全区間のちょうど半分ずつ、 $L = [0,2^{N-1})$ と $R = [2^{N-1}, 2^N)$ をまとめた区間 $LR$ を反転するのが得か損か考える。 $min(L) > min(R)$ なら得といえる。なぜなら今後の操作がどうあれ、全区間のちょうど半分ずつを反転するのは、反転しないか一回反転するかどちらにするかを適切に選べば $min(L) > min(R)$ になるからだ。

同じことがすべての $L = [a \times 2^b, a \times (2^b + 2^{b-1}))$ , $R = [a \times (2^b + 2^{b-1}), (a+1) \times 2^b)$ 区間についてもいえる。区間幅 $b = N..1$ の降順について、取りうるすべての $a$ について区間を考え、 $min(L) > min(R)$ なら $LR$ を反転する。

この方法は公式解説2,3とだいたい同じである。

コードはこちら

青diffなのにE問題より簡単である。相変わらず、正解者数と自分にとっての難易度に連動性がない。

$(1,1)$ から $(H,W)$ への経路を障害物の鎖で断ち切ることができるか考える。断ち切るというのは、上下左右斜めにつながっている障害物をまとめて、障害物の鎖を作る。鎖はunion-find木で作る。

ある障害物の鎖 $G$ で経路を断ち切れるのは、以下のいずれかに該当する場合である。

• $G$ が上から下まで詰まっている。つまり障害物が取り得る行番号が $H$ 種類ある
• $G$ が左から右まで詰まっている。つまり障害物が取り得る列番号が $W$ 種類ある
• $(1,1)$ 付近を上から左まで覆っている。障害物が取り得る行番号が1から昇順で連番、障害物が取り得る列番号が1から昇順で連番である。
• $(H,W)$ 付近を下から右まで覆っている。障害物が取り得る行番号が $H$ から降順で連番、障害物が取り得る列番号が $W$ から降順で連番である。

公式解説の補足とだいたい同じ解き方である。

コードはこちら

$X \leq L \land R \leq Y$ なリスナー数を答える。

コードはこちら

問題文通り実装する。文字列が長すぎるときは、文字列を構成する前に打ち切る。

コードはこちら

10進数で12桁以下の回文数を全列挙する。その中で $A$ 進数で回文かつ $N$ 以下の数を合計する。

10進数で12桁以下の回文は、10進数で6桁以下の数字の文字列表記 $S$ について、以下の通りである。 $S$ の先頭は 0 ではない。

• $S$ が1桁なら $S$ 自身
• $S$ の反転 $R$ について $SR$
• $S$ が2桁以上なら、 $S$ の反転から最後の桁を除いた $R$ について $SR$

コードはこちら

相変わらず問題の意味を取り違える癖が治らない。

$M = 1$ なら $max(X) - min(X)$ で全域を覆う。 $M = N$ なら全戸に基地局を置くので答えは0である。

家の間隔の集合を昇順に $D[1..(N-1)]$ とする。 $R = N - M > 0$ 個だけ基地局が不足している。このときは $D[1..R]$ 個の間隔について、自分の家ではなく隣の家の基地局から電波を受ける。よって $\sum_{i=1}^R D[i]$ が答えである。

コードはこちら

公式解説2のようなことを考えて、結局分からず諦めた。公式解説1は理解できていない。

コードはこちら

問題文通り実装する。

コードはこちら

問題文通り実装する。

コードはこちら

解法はすぐ思いつくが、添え字の扱いが難しい。

薬品が空の時は常に安全で、このことは $S$ には明示していない。ここが分からなくて答えが合わなかった。

薬品の状態 $i$ について、 $V_i = 0$ はその状態が安全、 $V_i = 1$ はその状態が危険であることを示す。これは $S$ の $i$ 文字目(1-based indexing)が 0 か 1 かに対応する。ここがややこしい。

薬品の状態 $i$ について、 $R_i = 1$ はその状態に到達可能、 $R_i = 0$ はその状態に到達不可能であることを示す。これは0-based indexingであり、 $R_0 = 1$ である。

$i = 0..(2^N-2)$ について、今の状態が到達可能、混ぜてない薬品を0-based indexingで $j = 0..(N-1)$ を混ぜた後の状態が安全なら、到達可能にする。混ぜた後の状態は $i \lor 2^j$ である。

$R_{2^N-1}$ が1なら Yes 、そうでなければ No を出力する。

コードはこちら

$A_i - B_i$ が小さいものほど交換効率がいい。 $A_i / B_i$ が小さいものではない。

入力を $(A_i - B_i, A_i, B_i)$ の昇順でソートし、この順番に $N$ 本のコーラを交換していく。交換すればするほどコーラの本数 $N$ は減っていつか交換不能になる。

ある $(A_i - B_i, A_i, B_i)$ について、 $N < A_i$ なら交換不能である。そうでなければ $C_i = 1 + \lfloor (N - A_i) / (A_i - B_i) \rfloor$ 回交換する。 $N$ を $C_i \times (A_i - B_i)$ 減らして、答えに $C_i$ を加える。

コードはこちら

すべての経路について、あるマスまでの最小累積コイン数(負になりうる) $C_{r,c}$ を求めたあと、あるマスまでの最小累積コイン数の最大値 $M_{r,c}$ 求める。 $max(0, -M_{H,W})$ が答えのはずなのだが、2 WAsする。

正解はゴールからスタートに向かって、必要な余力をDPすることだった。

コードはこちら

D問題とE問題を解く前に、F問題が解けてしまった。どうして相変わらず、正解者数と私にとっての難易度に連動性がないのだろう。

いかにも遅延セグメント木である。遅延セグメント木 $T$ のノードとして以下を載せる。

• ノードの文字列幅 $W$
• ノードの最左文字 $C_l$
• ノードの最右文字 $C_r$
• ノードの最左から連続する文字長 $L_l$
• ノードの最右から連続する文字長 $L_r$
• ノードで同じ文字が連続する最大長 $M$
• 単位元は空文字列

作用素は、以下のようにする。

• 文字 $C$ を持つか持たないかいずれかにする
• 文字 $C$ を持たないなら何もしない。これは単位元というか恒等変換である。
• ノードに対する作用は、ノードの文字列幅 $W=1$ なら、文字を $C$ に置き換える。それ以外は何もしない。
• 作用素の合成は、文字 $C$ があれば置き換える後勝ちにする

ノード $A,B$ を合成して $U$ にするとき、以下の通りにする。

• $U.W = A.W + B.W$
• $U.C_l = A.C_l$
• $U.C_r = B.C_r$
• $U.L_l$ は仮に $U.L_l = A.L_l$ とする
• $U.L_r$ は仮に $U.L_r = B.L_r$ とする
• $U.M$ は、 $A.M$, $B.M$ が候補になる。下記も考慮した、候補の最大値にする。
• $A.C_r = B.C_l$ なら以下を考慮する
  • $U.L_l$ は、 $A$ が全部 $C_l$ ならくっつける。つまり $A.W = A.L_l$ なら $U.L_l = A.L_l + B.L_l$ である。
  • $U.L_r$ は、 $B$ が全部 $C_r$ ならくっつける。つまり $B.W = B.L_r$ なら $U.L_r = A.L_r + B.L_r$ である。
  • $A.C_r$ と $B.C_l$ をくっつけた文字列の長さ $A.L_r + B.L_l$ も $U.M$ の候補にする

クエリ1は単一ノードを書き換える。クエリ2は $T[L,R]$ のノード $M$ を返す。

遅延セグメント木ではなく、普通のセグメント木でよかった 。遅延セグメント木だと作用素の設計がめんどくさい。

コードはこちら

0-based indexingに気を付けて数える。

コードはこちら

連続する . のうち、どれか一つだけ o に変える。最も左にすると実装が簡単である。

コードはこちら

$N$ 進数 $K$ 桁の数を網羅して、各桁に対応する $S_i$ を結合する( $i$ は0-based indexing)。これらの小さい方から $X$ 番目の文字列が答えである。

コードはこちら

よくわからないWAをして、よくわからないままACした。

$(A + B) mod M$ を対消滅できるならしておく。残った $A$ , $B$ について考える。

$A$ は降順のベクトル、 $B$ は昇順の多重集合として、各 $A_i \in A$ について処理する。

答えについて $A_i mod M$ 成分の和と $B_j mod M$ 成分の和は、 $A_i, B_j$ の組み合わせに依らず同じである。よって $A_i + B_j$ が $M$ を超えるような組み合わせをできるだけたくさん作ると、答えを最小化できる。

これは $A_i$ を固定した時、 $b = M - A_i$ として、

• $B$ が $b$ 以上の値を含むときは、 $b$ 以上の値の最小値
• $B$ が $b$ 以上の値を含まないときは、 $B$ の最大値

を $B_j$ として選ぶ。答えに $(A_i + B_j) mod M$ を加え、 $B$ から $B_j$ を1個除く。対消滅を除けば公式解説と同じである。なぜこんなに手間取ったのだろうか。

コードはこちら

超頂点というヒントを見てしまったのでその通り実装したのだが、WAの山が返ってくる。解けないまま公式解説を読んでも、やはり超頂点だった。多重辺の最短距離を取るのも、上空を経由する方法が2通りあるのも、他の方のコードをみるまで分からなかった。

コードはこちら

s.substr(a, n - a - b) を出力する。

コードはこちら

$A$ を std::multiset で持つ。

コードはこちら

std::multiset を使ったらTLEした。 std::map を使う。

$m = i - A_i$ が何個あるかを $M[m]$ として持つ。 $A_{i=1..N}$ について以下を繰り返す。

• $m = i - A_i$ が $M$ にあれば1減らす。ただし0未満にはしない。
• $p = i + A_i$ が $M$ に何個あるかを答えに加算する

コードはこちら

プレゼントを末尾から逆再生しながら、あるテンションになる元を探す、明らかに大きすぎるテンションは単調減少、と思ったがそれ以上考えがまとまらなかった。

諦めて公式解説を読み、公式解説をC++17で書き直しただけのコードが上記である。

コードはこちら

D問題より先に解けてしまった。確かにD問題よりも正解者数は多いが。

頂点番号の小さい順にDFSなのだが、そのまま実装するとTLEする。二段階のDFSが要る。

一段階目は、頂点 $X$ からDFSして頂点 $Y$ にいつかたどり着けるかどうか調べて、 $Y$ にたどり着いたパスのすべての頂点に印をつける。 $R[i]$ は頂点 $X$ から 頂点 $i$ を通って頂点 $Y$ に到達可能かどうかを示す。

二段階目は、頂点 $X$ からDFSして頂点 $Y$ に対するパスを全探索し、到達可能なパスが見つかったら即答えを返す。頂点 $u$ からたどる頂点は、頂点 $v$ に隣接する頂点 $u$ について、 $R[u] = true$ で $u$ の小さい順とする。

コードはこちら

D問題より先に解けてしまった。D問題よりも正解者数は少ないのに。

変数を一か所typoしていることに気が付かず、時間が掛かってしまった。如何にも遅延セグメント木である。遅延セグメント木 $T$ の要素を区間の平均値にすればよい。

• $T$ の $i$ 番目の要素 $T_i$ は、区間の幅と平均値にする。ただし平均値は std::optional<ModInt> として、幅0の時は値を定義しない。
• 区間を合併するときは、区間の加重平均を取る。ただし幅0の区間は対になる区間の値そのままにする。
• 作用素は std::optional<ModInt> とする。作用は後勝ち、つまり後から作用して最初に値が定義されている作用素を使う
• 初期値は $T_i = A_i$ で tree.set(i,a) する
• $[L,R]$ の平均値 $avg$ は tree.prod(l, r) で求める。これを区間 $[L,R]$ にインラインで作用する。 tree.apply(l, r, avg) を使う。

最終的な $T_i$ が答えである。

コードはこちら

$S$ の各文字 $d$ をスキャンし、 $d$ を出力し、 $d = c$ ならもう一回 $d$ を出力する。

コードはこちら

初期状態で行と列は $1..N$ すべて使えるものとする。 $r, c$ について、行 $r$ 、列 $c$ を使えないようにして、 $r-c$ と $r+c$ を登録する。

まだ使える行と列について 行 $R$ と列 $C$ を全探索する $R-C$ と $R+C$ の両方が未登録なら答えは $(R,C)$ である。そのような配置が見つからなければ答えは -1 である。

コードはこちら

方針はすぐ立ったのに、詰めが甘くペナルティを食った。

頂点 $u,v$ 間の最短距離を $D(u,v)$ とする。最初に $D(S,j=1..N)$ と $D(T,j=1..N)$ をDFSで求める。

ある $j$ について $D(S,T)$ となる最短経路から寄り道できるかどうか考える。

• $j = S$ または $j = T$ なら答えは1である
• 往復で $C = D(S,j) + D(T,j) - D(S,T)$ だけ寄り道することができる。特に $j$ が $D(S,T)$ となる最短経路上なら $C = 0$ である。寄り道上にある点は題意を満たし、寄り道の両端の点を含むので答えは $1 + C / 2$ である。

コードはこちら

if文で判定する。

コードはこちら

連想配列を作る。

コードはこちら

$DP[i][j]$ を、時刻 $i$ までに $j$ 回乗ったときに濡れた量とする。初期値を $DP[][] = \infty$ , $DP[][0] = 0$ とする。 $DP[i=0..(N-T)][]$ を以下のように更新する。

• 時刻 $i$ に乗ったときは、 $DP[i+T][j+1] = min(DP[i+T][j+1], DP[i][j] + \sum_i^{i+T-1} P_i)$ 。 $\sum$ の部分は累積和を求めておく。
• 時刻 $i$ に乗らなかったときは、 $DP[i+T][j] = min(DP[i+T][j], DP[i][j])$

答えは $min(DP[][K])$ である。

コードはこちら

ダイクストラ法っぽいが、TLEを連発した。

イベントを早い順に並べ替え、 $i$ 番目のイベントは時刻 $t_i$ に地点 $c_i$ ですると決める。便宜上、時刻0分にイベント0を地点1で開催するとする。

$DP[i=0..K][j=1..N]$ を、 $i$ 番目に早いイベントが終わった時点で、地点 $j$ にいるときの時刻とする。

初期値を $DP[][] = \infty$ 。あるイベント $i=0..N$ について、イベント終了直後に動き出したときの移動先を考える。 $DP[i][c_i] = t_i$ を起点としてダイクストラ法で探索すると、任意の頂点 $DP[i][]$ について最短でたどり着く時刻が分かる。

すべてのイベントの組 $(from,to)$ について、イベント $from$ が終わった後にイベント $to$ を見られるか判定する。見られるのは $from = to \lor DP[from][c_{to}] \leq t_{to}$ である。見られるときは $from$ から $to$ に有効グラフ $G$ の辺を張る。

$G$ について、地点1からの最長距離を求めると答えになる。ここでTLEした可能性がある。

コードはこちら

$(month,day)$ の昇順にソートしてから出力する。

コードはこちら

スキル $A$ の人が $C[A]$ 人いるとする。

$S$ が偶数なら、スキル $S/2$ の人が $M$ 人いるとして、 $M(M-1)/2$ 組作る。

あるスキル $A$ の人と、 $B = S - A > A$ の人を組ませる。この組み合わせは $C[A] \times C[B]$ 組作れる。これらの和が答えである。

コードはこちら

包除原理である。

椅子が空いていれば、来た人を座らせても答えは変わらない。なぜなら椅子に座らせずにそのまま会場に案内しても、いったん椅子に座らせてぎりぎりまで会場に案内しなくて、整理券に書かれた番号が小さい順に $N$ 人の人を会場に案内できることに代わりはないからだ。

1番目の人を案内できないのは、 $K+1$ 番目より後に来た場合である。これは $(N - (K+1)) \times (N-1)!$ 通りである。

1番目の人を案内できて、2番目の人を案内できないのは、2番目の人が $K+2$ 番目より後に来て、1番目の人が $K+1$ 番目以内に来た場合である。これは $(N - (K+2)) \times (K+1) \times (N-2)!$ 通りである。

同様に $i-1$ 番目の人を案内できて、 $i$ 番目の人を案内できないのは、これは $(N - (K+i)) \times (K+1)^{i-1} \times (N-i)!$ 通りである。

この和を $N - K - 1$ 番目まで求めて、 $N!$ から引くと答えになる。

想定解法は包除原理ではなかった。このエレガントさはARCっぽい。

コードはこちら

$K$ が固定値なので、平均体力消費量 - $K$ が非負であればよい。この方針で尺取り法する。

まず $D_i = K - A_i$ を求め、 $D_i$ の累積和 $C_i = \sum_1^{i} D_i$ を求める。このままではメモリ消費量が大きすぎるのでセグメント木に載せる。

値の昇順に並べた $L = C_i$ を座標圧縮し、 $L$ を座標 $P_j : 1 \leq j \leq N$ にする。初日を1と数えて $i$ 日目に累積和が $L$ になることを、区間最大セグメント木に $set(P_j,i)$ を載せると表現する。同じ値 $P_j$ については $i$ の最大値を載せる。またベクトル $V[P_j] = L$ として、 $P$ から圧縮後の座標 $L$ を二分探索できるようにする。

初日から特訓を開始して、平均体力消費量 - $K$ が非負であることは、ある $j$ が存在し、 $P_j \geq 0$ であることと同じである。このような $j$ は $V$ を $0$ で二分探索すれば求まる。 $j$ が存在するなら、セグメント木に $prod(j,\infty)$ を適用すると、初日から最も遠い日 $l$ が求まる。 $l+1$ は答えの候補になる。 $j$ が存在しなければ無視する。

二日目以降の $l$ 日目は、 $V$ を $C_{i-1}$ で $j$ を二分探索すれば、 $j$ があるなら $j + 1 - l$ 日と求まる。 $j + 1 - l \leq 0$ かもしれないが、答えの最低値が1であることは制約から保証されているので気にしない。これらの最大値が答えである。

この解法は決勝の優勝者と同じである(minとmaxの違い)。想定解法はLISっぽいが、座標圧縮とセグメント木は要らないらしい。

コードはこちら

$i = 1..N$ に順に処理する。

$B_i$ のすべての約数の集合を $S_i$ として、 $F \in S_i$ について、 $A_i mod F$ を求める。ある $F$ について、 $A_i mod F$ が二種類取り得るなら、それらのアイドルのブレスレットは周期 $F$ のまま重ならない。よって答えは No である。これを検出したらすぐに処理を打ち切らないとREする。

このような組がなければ答えは Yes である。

最大公約数を使おうとして1ペナ、ここで3秒制限なら約数列挙だろうと気づき、REしてもう1ペナもらった。厳密な証明は公式解説通りで、約数ではなく素因数だけ考えて差し支えない。

頂点倍化だと思ったが、公式解説2を読む限り幾重の考察が必要だった。これは自力では思いつかない。

コードはこちら

std::string::rfind("tea") + 3 が $|S|$ なら接尾語は tea である。念のため、位置が std::string::npos かそれ以外か調べる。

コードはこちら

総当たりのはずがなぜかWAした。

コードはこちら

水平スキャンだと分かったが手こずった。

値 $a = A_i$ を取るティーバックが $c$ 個あることを、 $C[a] = c$ と表現する。

$a$ の昇順に $C$ を処理する。先頭要素について考える。

• ティーバックを1個選ぶためには、 $x = 1$ とする。これを $S[1] = 1$ とする
• ティーバックを $j = 1..a$ 個選ぶためには、 $S[1..a] = 1 + N \times (j - 1)$ とする

$M = |C|$ として、 $C[a_{i=1..M}]$ について繰り返す。

• 上記の通り $N$ 種類のティーバックを $C[a_1]$ 個選ぶ。これを $S$ について累積して、 $S[1..a_1]$ とする。
• $N - C[a_1]$ 種類のティーバックを $C[a_2]$ 個選ぶ。これを $S$ について同様にする。
• $N - C[\sum_{1}^{i-1} a_i]$ 種類のティーバックを $C[a_i]$ 個選ぶ。 $S$ について同様にする。

$B > max(A)$ なら解無しなので -1 、そうでなければ $S[B]$ が答えである。

コードはこちら

DPで畳み込む。

$DP[i][j=0..1]$ を、 $i$ 文字目で終わる部分文字列で、 $j \in 0..1$ になる部分文字列が何通りあるかとする。 $DP[0][] = 0$ とする。以下の漸化式で更新する。

• $S_i = 0$ なら、 $DP[i][0] = DP[i-1][1] + 1$, $DP[i][1] = DP[i-1][0]$
• $S_i = 1$ なら、 $DP[i][0] = DP[i-1][0]$, $DP[i][1] = DP[i-1][1] + 1$

答えは $\sum DP[][1]$ である。

コードはこちら

C++で3370 msecもかかる。

広義の台形の数 - 広義の平行四辺形の数の半分、が答えである。広義の台形を構成する頂点を列挙するとTLEする。

辺の方向 $\vec{v}$ を求め、その方向上にある辺の集合 $E$ を列挙する。辺の方向は、 $\vec{v} = (x,y)$ について、 $(x,y)$ が規約になるように $GCD(x,y)$ で割り、 $x$ が非負になるよう符号反転する。

ある方向 $\vec{v}$ の辺の集合 $E$ について、広義の台形の数は $(|E|(|E| - 1)) / 2$ 個である。異なる二辺 $(u,v) \in E$ について、頂点を $P$ と表記して $u = P_{u0}-P_{u1}$ , $v = P_{v0}-P_{v1}$ とする。この4頂点が平行四辺形であることは、以下を満たすことである。

• $|u| = |v|$
• $|P_{u0}-P_{v0}| = |P_{u1}-P_{v1}| \lor |P_{u0}-P_{v1}| = |P_{u1}-P_{v0}|$

コードはこちら

あらかじめ連想配列というか辞書を作る。

コードはこちら

昇順の優先度キューに入れる。

コードはこちら

問題を誤読し、全員の移動回数の和を1ノルムで求めるのかと思ったら全然違った。中央値には違いなかったが。

行について、 $D = max(R) - min(R)$ として、少なくとも $\lceil D/2 \rceil$ 寄れば一か所に集まることができる。列についても同様であり、列移動は行移動とは独立に行うことができる。

よって答えは、 $max(\lceil (max(R) - min(R)) / 2 \rceil, \lceil (max(C) - min(C)) / 2 \rceil)$ である。もっとすっきり実装すると こう なる。

コードはこちら

C問題よりずっと簡単だった。

$M = 0$ なら答えは $S$ である。 $V[i=1..(N+1)]$ について、 $V[i] mod 2 = 1$ なら、 $V$ の $i$ 文字目以降は、 $S$ ではなく $T$ を読むとする。

$(L,R)$ についていもす法して、 $V[L]$ に1足し、 $V[R+1]$ から1引く。

$V[i]$ の累積和 $C[i]$ を求める。答えの $i$ 文字目は、 $C[i] mod 2 = 0$ なら $S[i]$ であり、そうでなければ $T[i]$ である。

コードはこちら

不変量っぽい。

$A_i$ と $A_{i+L}$ は常に同じにしなければならない。よって $A_{i=1..L}$ をそれぞれ $j=0..(M-1)$ に決め打ちし、その時のコストを $C[i][j]$ とする。

$C[i][j]$ について動的計画法することで、連続する要素が $modM$ を達成する最小コストを求める。 $DP[i][j]$ を、 $A_1$ から $A_{i=1..L}$ までの和の $modM$ が $j$ であるときの最小コストとする。初期値を $DP[][] = \infty, DP[0][0] = 0$ とする。

DPの遷移元を $from = 0..(M-1)$ 、 $A_i = rem$ のときのコストについて $from, rem$ を総当たりして $DP[i][(from+rem)modM] = min(DP[i][j], DP[i-1][from] + C[i][rem])$ でDPを更新する。答えは $DP[L][0]$ である。

コードはこちら

$1 + (X - 1 + Y) mod 12$ が答えである。

コードはこちら

$1..N$ 人目に対する得票を数え、少数派にそれぞれ1足せばよい。 $X = 0$ または $Y = 0$ のときは、誰が答えかには影響しないので無視する。

コードはこちら

クエリに対して、答えを差分更新する。

コードはこちら

着想は早いが実装が遅い。

頂点倍化である。表面 $R \times C$ グリッド、裏面 $R \times C$ グリッド、を作る。以下のようにマスの間に辺を張る。

• .So からは表面で隣接する .SGo? に行ける。実は行った先が # なら行き止まりなので行っても差し支えない(以下同様)。
• .Sx からは裏面で隣接する .SGx? に行ける
• ? からは、同座標の表面と裏面同士を行き来できる。正確には ? とは反対面にある ? に隣接するマスに行ける。

辺を張ったら、スタート地点から優先度キューで探索して、スタート地点からの最短距離を求める。表面または裏面のゴールまでの最短距離が答えである。

コードはこちら

着想は早いが実装が遅い。

辺が減らないので如何にもunion-find木である。連結成分の代表元に、黒い頂点の数を持たせる。頂点 $v$ の色を $C[v] \in {0,1}$ 、代表元 $v$ の連結成分の黒頂点の数を $B[v]$ とする。頂点 $v$ の代表元を $L[v]$ とする。

• クエリ1は、 $u,v$ が連結なら何もしない。非連結なら連結し、 $L$ を連結後の $u,v$ の代表元として、 $B[L] = B[u] + B[v]$ で更新する。
• クエリ2は、頂点 $v$ の色を $C[v]$ からを $\overline{C[v]} = 1 - C[v]$ に変えるとする。さらに $B[L[v]]$ に $\overline{C[v]} - C[v]$ を足す
• クエリ3は、 $B[L[v]]$ が正の数なら Yes 、0なら No である。

コードはこちら

ABC 420-Gは、両辺を二乗した後の式変形が分からず、 $\sqrt{X}$ の範囲で尺取り法したらWAの山が返ってきてお手上げだった。

コードはこちら

$S[i]$ は $i$ 号室の住人の名前、という一覧表を作る。

コードはこちら

問題文通り実装する。

コードはこちら

バブルソートして定位置にするしかない。定位置とは ABAB... または BABA.. のどちらかである。

定位置における先頭の A は1番目か2番目である。これを $p=1,0$ と置く。 $i=1..N$ 番目の $A$ の位置が $P_i \in 1..2N$ であり、位置 $2i - p$ に移動するとき、移動する総コストは $\sum_i |P_i - (2i - p)|$ である。それぞれの $p$ についてコストの和を求めて、小さい方を答える。

コードはこちら

着想は早いが実装が遅い。

$S, T$ の動きの差 $V$ についてランレングス圧縮する。ここがややこしいが、尺取り法で以下のように実装する。

• あるランを終えた後の移動回数について累積和を取る。つまり $i$ 回移動した後で、 $CS[i] = \sum_{j=1}^{i} S_j$ $CT[i] = \sum_{j=1}^{i} T_j$ 回移動したとする。
• $CS, CT$ について、重複無し集合 $U$ を求める
• $U$ の昇順に、ランをリプレイする。 $U[j], U[j+1] , j+1 \leq |U|$ を区間とするランを作り、そのランは $S, T$ の差分である。具体的には以下のように求める。便宜上 $U[0] = 0$ , $V[0]$ の移動回数を0とする。
  • $S$ で注目しているランを $p = 1..M$ とする
  • $T$ で注目しているランを $q = 1..L$ とする
  • $j$ を差分ラン $V$ の番号とする。このランまでの移動回数の累積和を $U[j]$ とする
  • $CS[p] \geq U[j]$ を満たす最小の $p$ まで、 $p$ を増やす。つまり $CS[p-1]..CS[p]$ が $U[j]$ を含むようにする。
  • $CT[q] \geq U[j]$ を満たす最小の $q$ まで、 $q$ を増やす。つまり $CT[q-1]..CT[q]$ が $U[j]$ を含むようにする。
  • 差分ランは $V[j]$ は、移動回数 $V[j] - V[j-1]$ について、移動方向の差分 $CS[p] - CT[q]$ からなる

差分ラン $V$ が求まったので、初期位置の差分 $(R_r - R_a, C_t - C_a)$ からリプレイする。処理量はランの長さに比例し、移動回数に比例しないよう効率よく行う。それぞれのランについて以下の通り答えを更新する。

• 位置の差を $R_d, C_d$ とする。初期値は $R_d = R_r - R_a$, $C_d = C_t - C_a$ である。
• $V[i] = (l, r, c)$ とする。これは移動方向の差分 $(r,c)$ を $l$ 回繰り返すという意味である。
• 差分がない、つまり $r = 0 \land c = 0$ のときを考える
  • $R_d = 0 \land C_d = 0$ なら、二人は常に行動を共にする。よって答えに $l$ を足す
  • そうでなければ二人は決して同じ位置に居ない。答えは変わらない。
• 二人が同じ位置に居る可能性を求める。 $l$ 回移動後の位置の差を $R_e = R_d + l \times r$, $C_e = C_d + l \times c$ とする。
  • 適宜大小を入れ替えて、 $[R_d + r, R_e]$ , $[C_d + c, C_e]$ が0を含まなければ、二人は決して同じ位置に居ない
  • $r \ne 0$ のとき、 $R_e - R_d$ が $r$ の倍数で無ければ、列の差は0にならない。 $|r| \in {0,1,2}$ であることに注意する。
  • $c \ne 0$ のとき、 $C_e - C_d$ が $c$ の倍数で無ければ、行の差は0にならない
• 上記でなければ、二人が同じ位置に居る可能性が高々1回ありうる
  • $r = 0$ のとき、 $C_e - C_d$ が $c$ の倍数なら、二人は1回同じ位置に居る
  • $c = 0$ のとき、 $R_e - R_d$ が $r$ の倍数なら、二人は1回同じ位置に居る
  • そうでなければ、 $C_d + c(-R_d / r) = 0$ のとき、二人は1回同じ位置に居る

コードはこちら

遅延セグ木という言葉がちらっと見えてしまったので、純粋な自力ACかというと割引が要る。でもまあ自力AC扱いしておく。

クエリを先読みする。クエリ2は削除しないことにして、クエリ1について $x$ が最終的に置かれる位置を確定する。これは boost::multi_index_container で std::set 兼 set::list を作ればよい。

using SetAndList = boost::multi_index_container <
    Num,
    boost::multi_index::indexed_by <
        boost::multi_index::ordered_unique <
            boost::multi_index::tag<order>,
            boost::multi_index::identity<Num>
            >,
        boost::multi_index::sequenced <boost::multi_index::tag<seq>>
        >>;

リストを先頭からなぞって、最終的に $x$ は $P[x]$ に置くものとする。先読みしたクエリを再生する。遅延セグメント木 $T$ で、区間和、区間更新を行う。

• クエリ1は、 $T[P[x]] = x$ とする
• クエリ2は、 $L = P[x]$, $R = P[x]$ として、 $T[(L+1)..(R-1)]$ の区間和を出力する ($L > R$ なら $L,R$ を入れ替える)。その後、 $T[(L+1)..(R-1)]$ を0に更新する。

boost::multi_index_container を使っても1018 msecで間に合う。

コードはこちら

問題文通り桁繰り上がりをする。

コードはこちら

端に注意して、問題文通り実装する。

コードはこちら

ARC 201-Aの屈辱を思い出し、同様に解いたら間違えた。 $r = min(a,c)$ , $min(r, (a-r) + b + (c-r))$ はWAの山が返ってくる。二分探索するのが正しい。

コードはこちら

$W = 2^N$ とする。 $B$ の成分として、少なくとも $D = \lfloor K/W \rfloor$ にして、 $R = K - DW$ を1ずつ $B$ の要素に付け加える。どこに付け加えるのが最適なのか考える。

$W$ の左右に割り当て、左右の左右に割り当て、というのを繰り返すと最適である。例えば $W = 8$ なら、0-based indexing で 0 4 2 6 1 5 3 7 である。この配列は、マージソートの要領で作ることができる。

• 初期行列を $P$ とする
• $P$ と $P+|P|$ をzipして、新たな $P$ を作る
• これを $N$ 回繰り返すと $W = 2^N$ になる

このようにした求めた $P$ の先頭 $i=1..R$ 番目の位置 $P[i]$ について、 $B[P[i]]$ に1足す。

上記は葉から構築したが、根から構築することも できる 。区間 $[L,L+W)$ に $R$ 個の要素を置くとき、左側 $[L,L+W/2)$ に $\lceil W/2 \rceil$ 個、右側 $[L+W/2,L+W)$ に $\lfloor W/2 \rfloor$ 個置けばよい。

コードはこちら

ABCでも乱択アルゴリズムが出る。

決定的アルゴリズムが全く分からず、乱択アルゴリズムで押し切ったら、実は乱択アルゴリズムが想定解だった。

任意の二点を通る直線 $S$ が、解の直線 $L$ に載る確率は1/4以上ある。よって $S$ を100万個集めて多数決を取り、上位10位までが $L$ を満たすかどうか調べればよい。満たすならそれが答えの一つであり、満たすものがなければ答えは No である。

コードはこちら

$N = 1000$ として、 $N + C$ 単位で引き出せるので、答えは $N \lfloor X / (N+C) \rfloor$ である。

コードはこちら

左端から行ける最右の部屋を $L$ , 右端から行ける最左の部屋を $R$ とする。これは扉を順に調べると分かる。答えは $max(0, R - L - 1)$ である。

コードはこちら

解法は見えたのに実装で手こずった。

センチネルを置いて、 $L_0 = 1, L_{N+1} = 1$ とする。最左の開いている扉を $left$, 最右の開いている扉を $right$ とする。以下の動きが最適である。区間は両端を含む。

• $R$ から $left$ まで、閉まっている扉を開ける
• $left$ から $R$ まで、扉を全部閉める
• $R+1$ から $right$ まで、閉まっている扉を開ける
• $right$ から左に向かって、開いている扉を閉める。閉まっている扉を見つけたら終了する

コードはこちら

C問題と同様のシミュレーションだが、実装で手こずった。

店の容量が足りないときは、誰かが退店するまで必ず待たされる。これを利用して上手く時計を進める。

• 店に入るグループの待ち行列 $P$ に要素 $(A_{i}, B_{i}, C_{i}, i)$ を $A$ の昇順に入れる
• 店から出るグループの待ち行列 $Q$ に要素 $(T_{i} + B_{i}, C_{i})$ を $T_{i} + B_{i}$ の昇順に入れる。ここで $T_{i}$ はグループ $i$ が入店した時刻である。

$P,Q$ の両方が空になるまで、以下を繰り返す。時刻を $T$ 、空き容量を $S = K$ とする。

• $P$ の先頭から空きがある限りグループを入れる。 $T = max(T,A)$ , $S = S - C$ で更新する。
• $Q$ の先頭からグループを退店させる。 $T = max(T,A)$ , $S = S + C$ で更新する。

コードはこちら

累積和で求めようしたが、全く答えが分からなかった。公式解説2をそのまま実装したがやはり分からない。

メビウス変換ってなんでしょう。

コードはこちら

$A = B \lor B = C \lor C = A$ なら Yes 、そうでなければ No である。

コードはこちら

正解した問題の番号を集合で管理して、正解した数を数える。

コードはこちら

トポロジカルソートしようとして思いとどまった。

依存関係をグラフにして、先行条件なしのスキルからBFSする。

コードはこちら

DFSで全探索する。要領よく実装しないとTLEする。Bit DPという言葉がちらっと見えたが、自力AC扱いにしておく。

• 解の最大値は $HW$ で、実際にはもっと少ない(白は4マスに一つ置けばいい、公式解説を参照)。よって既知の最小解を共有し、それ以上白く塗ったら枝刈りして探索を打ち切ってよい。
• $(R,C)$ が元々白なら、塗らないしか選択肢が無い
• ある $(R,C)$ マスに注目して、 $(R-1,C-1),(R-1,C),(R,C-1),(R,C)$ が全部黒なら、 $(R,C)$ は白く塗るしか選択肢が無い
• そうでなければ塗るか塗らないか両方試す
• BitSetのオフセットは $RW + C$ より、制約から $2^3W+C$ にする方が速いかもしれない。乗算の代わりにシフト命令を使える。制約から右と下の余分な列はすべて白と仮定して構わない。
• 黒いマスの数は std::bitset::count() で求まる

解の上限を $\lceil H/2 \rceil \lceil W/2 \rceil$ にしても速くならなかった。

コードはこちら

D問題より先に解けてしまった。制約を読み違えてTLEし、方針を立て直してから実装に時間が掛かってしまった。

愚直にシミュレーションするとTLEするので、元々は同じ棒だったものとひとまとめに扱う。 $A_i$ は $(A_i,1)$ つまり長さ $A_i$ の棒が一本として扱い、これを分割して $(A_i/2, 2)$ にする。同様に $(A, C)$ を $(A/2, 2C)$ に分割するのだが、オーバフローを防ぐため、 $(A/2, min(10^{15},2C))$ とする。この定数を $10^{15}$ ではなく $2X$ にすると大量のWAが返る。

$(A_i, 1)$ を優先度キューに載せてシミュレーションする。

• $K$ 回分割する。残り操作回数 $R = K$ を $(A, C)$ について $C$ ずつ減らしていく
• 優先度キューの先頭を $(A, C)$ とする
• $(A, C)$ を取り除く
• $C \geq R$ なら、未分割分 $(A, C - R)$ 、分割分 $(A/2, 2R)$ をキューに載せる
• $C < R$ なら、分割分 $(A/2, 2C)$ をキューに載せる

先頭 $X$ 番目の要素は、残り操作回数 $R = X$ を $(A, C)$ について $C$ ずつ減らしていく $R \leq 0$ になったら終わりで、その時の $A$ を出力する。

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

コードはこちら

D問題より先に解けてしまった。セグメント木に載せればよいのは一目瞭然だが、そこからかなり時間が掛かった。

線分 $[A,B]$ と他の線分が交差するとは、以下の通りである。

1. 区間 $[A,B]$ において、他の線分の出入りの和が0。ここで出を1, 入を-1とする。
2. 区間 $[A,B]$ において、他の線分のからの飛び込みが0。線分 $[C,D]$ において、 $D$ に飛び込み元を $C$ とすると、区間 $[0,A)$ からの飛び込みが $[A,B]$ にならない。

1は区間和セグメント木 $T$ 、2は区間最小値セグメント木 $W$ で分かる。具体的には以下の通り設定する。

• $T[A]$ に1を足す。単位元は0である。 $T[B]$ から1を引く。区間和 $[A,B]$ が0である。
• $W[B]$ を $A$ にする。単位元は $\infty$ である。区間最小 $[A,B]$ が $A$ 以上である。

ARC 206で緑落ちしたので、ratedで参加した。水色に戻した。

コードはこちら

符号 $S_i$ は $i$ が偶数なら $1$ 、奇数なら $-1$ である。 $S_i \times i^3$ の総和を求める。

コードはこちら

最初に集合 $S$ を $1..N$ 全部入りとする。

$A$ を一通り見る。

• $A_i$ が $-1$ なら無視する
• $A_i$ が $S$ に含まれるなら $S$ を消費する。つまり $S$ から $A_i$ を除く
• $A_i$ が $S$ に含まれなければ値 $A_i$ が重複するので答えは No である

$A = -1$ の場所に、 $S$ を一つずつ当てはめると答えになる。

想定解法は全探索だったらしいが、公式解説2と同じ解き方である。

コードはこちら

いつものカーソルである。

0-based indexingでカーソルを $P$ とする。クエリ1は $P$ を $(P+C) mod N$ にする。

クエリ2は $L$ を $(L+P) mod N$ 、 $R$ を $(R+P) mod N$ と読み替える。

• $L = R$ なら答えは $A_L$ である。入力例に救われた。
• $L < R$ なら答えは $\sum_{i=L}^R A_i$ である。あらかじめ累積和を求めておく。
• $L > R$ なら答えは $\sum_{i=0}^R A_i + \sum_{i=L}^{N-1} A_i$ である。

場合分けしなくても、長さ $2N$ の累積和を求めればよかった。この辺の実装テクニックをすっかり忘れている。場合分けを減らせばデバッグせずに済み、3分で 実装 できなければならない。

コードはこちら

答えはすぐ分かったが詰めが甘かった。マスを塗りつぶす操作は一斉に行わなければならない。

最初に条件つまり隣接する黒マスが1個のマスの集合 $S$ を求める。 $S$ を求めてから、 $S$ のすべてのマスを塗りつぶす。求めながら塗りつぶすと答えが合わない。

$S$ のそれぞれ要素について、隣接するマスが条件つまり隣接する黒マスが1個なら、そのマスを集合 $T$ に加える。 $T$ が確定したら $T$ のすべてのマスを塗りつぶす。そして $T$ を $S$ にする。同じマスを二度見ないようにガードする。

最後に黒マスを数えて答える。

コードはこちら

5ペナ + 2000 msきっちりでACした。運に助けられた。

制約 $\sum C \leq 5000$ を見落としていた。これに気が付かず20分くらい無駄にした。 $L = 5000$ とする。

最初に $2..L$ の約数を求め、 $i=2..L$ について $i!$ の素因数を求める。つまり $i!$ にある素数が何個含まれるか数える。これは std::unordered_map<Num,Num> にする。 std::map<Num,Num> だと間に合わない。

いったん $mod M$ を忘れる。 $S = \sum C$ として、答えは $S!/\prod C_{i=1..N}!$ である。 $M$ が素数で無いときにフェルマーの小定理を使った逆元は求まらない。

なので $S!/\prod C_{i=1..N}!$ の求め方として、素因数を減らす方法で求める。そうすると残った素因数が $P_i^{C_i}$ という形で表現できるので、 $C_i < L$ より、あらかじめ求めておくことで $N$ 回の乗算で求まる。 $mod M$ は乗算のたびに取ればよい。

これで2000 msきっちりでACした。この方法は公式解説3と似ているが、公式解説3は遥かに速い。あらゆる素因数ではなく、 $M$ の素因数を使う。

おそらくもっと良い解法があるはずだと思い、公式解説を読んだら多項係数の除算を無くす式変換と、二項係数の漸化式が載っていた。 この方法 は全く思いつかなかった。

コードはこちら

名前をバージョンに対応するテーブルを固定で持つ。

コードはこちら

文字を出現回数に対応するテーブルを作って、出現回数が1の文字を返す。

コードはこちら

尺取り法しようとして単調性が無いので(バージョンの追い越しがある)、遅延セグメント木で解いた。

と思ったら、やはり尺取り法で 解けた 。

コードはこちら

1時間を超えてしまった。

$S$ を0か1かどちらにそろえるか決め打ちして両方試す。

$v \in 0..1$ に決め打ちする。 $v$ のランレングスつまり $v$ が位置 $P_i$ から連続 $C_i$ 個出現するという数列を $L$ とする。 $(P_i,C_i), i = 1..|L|$ について以下が成り立つ。

• 寄せる先の位置は $[P_i, P_i + C_i)$ である
• $P_i$ より左の数をすべて寄せる。どの数も寄せる必要があり、その個数は $P_i - 1$ 回である
• $P_i$ より左 $v$ は寄せたあと反転する必要がある。その個数は $\sum_{j=1}^{i-1} C_j$ 回である。これは累積和を求めておく。
• 右から寄せる場合も同様にする

ランレングスは高々 $N$ 個なので、 $O(N)$ で求まる。公式解説を読んで分かったが、累積和を使うまでも なかった 。

コードはこちら

決定的解法を検討して2時間を超えてしまった。実は三分探索を二回やるだけである。

高橋君は青木君以上に移動時間が掛かるとみなして一般性を失わない。そうでなければ入れ替える。

高橋君の移動時間は $L_{T} = \sqrt{{(TG_{X} - TS_{X})}^2 + {(TG_{Y} - TS_{Y})}^2}$ 、青木君の移動時間は $L_{A} = \sqrt{{(AG_{X} - AS_{X})}^2 + {(AG_{Y} - AS_{Y})}^2}$ である。前提より $L_{T} \geq L_{A}$ である。

単位時間の移動距離は、高橋君のX方向について $TD_{X} = (TG_{X} - TS_{X}) / L_{T}$ , $TD_{Y} = (TG_{Y} - TS_{Y}) / L_{T}$ である。青木君も同様に $AD_{X} = (AG_{X} - AS_{X}) / L_{A}$ , $AD_{Y} = (AG_{Y} - AS_{Y}) / L_{A}$ である。

時刻 $0 \leq t \leq L_{A}$ において、青木君が止まるまでの二人の距離は $\sqrt{{(TS_{X} + tTD_{X} - AS_{X} + tAD_{X})}^2 + {(TS_{Y} + tTD_{Y} - AS_{Y} + tAD_{y})}^2}$ である。この最小値を三分探索で求める。

時刻 $L_{A} \leq t \leq L_{T}$ において、青木君が止まるまでの二人の距離は $\sqrt{{(TS_{X} + tTD_{X} - AG_{X})}^2 + {(TS_{Y} + tTD_{Y} - AG_{Y})}^2}$ である。この最小値を三分探索で求める。

念のため時刻 $0, t, L_{A}, L_{T}$ の距離を求め、これらの最小値が答えである。

距離の二乗は $at^2 + b^t + c$ と表現でき、この最小値を与える $t$ は $-b/2a$ である。これは計算で求まるが、なぜか誤差が大きすぎる。

コードはこちら

0-based indexing で、 $S$ の $\lfloor |S|/2 \rfloor$ 文字目以外を出力する。

コードはこちら

$A_i$ の値は保存するが、 $f(A_i)$ の和は直近の累積和 $C_i$ だけ持てばよい。

$A_0 = 1$, $C_0 = 1$ とする。 $A_{i+1} = C_{i}$ とする。その後 $C_{i+1} = C_{i} + f(A_{i+1})$ とする。 $A_{N}$ を答え、 $C_{N}$ は使わないが構わない。

コードはこちら

$N = 10$ なので、二部グラフの左右にどの頂点を割り当てるか総当たりする。左同士、右同士をつなぐ頂点を削除する必要がある。そのような削除回数の最小値が答えである。

コードはこちら

問題文を読み取れなかった。

最初はAliceはどこから出発してもよいと思って解けなかった(出発点は頂点1固定だった)。次に、AliceとBobの手番は合計 $K$ 回だと思っていた($K$ 回ずつ計 $2K$ 回だった)。解けるわけがない。

解説を読んで問題文を盛大に誤読していると分かった。ここまで分かれば、部分木のうち自分の必勝手があれば選び、なければ他人の勝ちである。

コードはこちら

周期 $C=\lfloor X/(A+B) \rfloor$ 、余り $R = min(A,X-C(A+B))$ だけ移動するので、答えは $(CA+R)S$ である。

コードはこちら

総当たりするだけなのだが、異常に時間が掛かった。

コードはこちら

B問題もC問題も時間を掛けすぎである。

差分 $D$ を ( を1、 ) を-1とする。累積和をセグメント木 $T$ に載せる。括弧列の長さを $L$ とし、初期状態は $L=0$ で累積和が $T[0] = 0$ とする

• クエリ1に対しては、 $T[L+1] = T[L] + D$ として、その後 $L$ に1を足す
• クエリ2に対しては、 $L$ を1引く

$min(T[0..L])$ が0以上かつ $T[L]$ が0なら Yes 、そうでなければ No である。セグメント木に載せて、 $log(N)$ 余計に払った。

コードはこちら

E問題緑diffは半日掛かるのに、水diffは数分で方針が立つ。

$C+x$ は高々10桁なので、決め打ちして全探索する。 $W$ を $C+x$ の桁数とする。

$W = 1..10$ を全探索する。 $f(C,y)$ の候補は $W$ の視点では $y = [10^{W-1},10^{W}-1]$ である。 $x$ の視点では $[C+1,C+D]$ である。よって両区間の重なる部分を、両端を込みで $[L,R]$ とおく。

$[L,R]$ が空集合なら $x$ も空集合であり、したがって $x$ は0個である。そうでなければこの区間にある平方数を数える。 $R$ 以下の平方数は $\sqrt{C10^{W}+R}$ 個、 $L$ 未満の平方数は $\sqrt{C10^{W}+L-1}$ 個あるので、両者の差が $x$ の個数である。

これを $W$ について一通り求めると答えが求まる。計算量は $O(Tlog(C+D))$ である。ばっちり公式解説通りである。

コードはこちら

明らかに木DPで解ける問題に半日掛かった。

始めにオイラーツアーで解こうとして解けず、木の直径で解こうとして解けず、1パスの木DPで解けず、2パスの木DPでようやく解けた。

後処理を楽にするため、次数が1の点を根 $r$ としておく。以下の処理で、頂点 $V$ について、根からの距離つまり深さを $D[V]$ とする。これはDFSと同時に求まる。

そこからDFSして、各頂点 $V$ について、部分木の $(L_C,M_C,C)$ を求める。ここで $C$ は $V$ と直接つながる子頂点、 $L_C$ は $C$ を頂点とする部分木 $T_C$ における根から最深の葉までの深さ、 $M_C$ は $T_C$ における最深の葉の最大頂点番号とする。このタプルを並べ替えると、昇順で最大要素のタプルの $M$ が、 部分木 $T_V$ のなかで $V$ から最も遠い頂点の最大番号である。根 $r$ についてはこの処理で求めた $M$ が答えである。

次に子に対してDFSで木DPを行う。まず根 $r$ の直接の子については、 $(L=0,M=r,-1)$ とする。つまり親と直接つながる子にとって、親には距離1で行けるという意味である。この処理を特別扱いしたくて、根の次数を1とした。

この木DPを平たく言えば、 $V$ から全方位を見たときの最長距離にある頂点のうち、最大番号のものを選ぶ。DFSで葉に向かえば、親方向から伝搬する最長距離は延びて、葉方向の最短距離は縮まる。

ある頂点 $V$ を根とみなしたとき、DFS探索の親つまり元々の根の方向についての答え $(L_p,M_p,-1)$ を距離1延ばしたもの $(L_p+1,M_p,-1)$ と、子頂点 $(L_C-D[V],M_C,C)$ についての答えの、最大のタプル $(L,M,C)$ が求まる。このような $M$ が頂点 $V$ についての答えである。特に葉については、親から伝搬したタプルそのものである。

実装上の注意として、 $V$ から見て $C$ が最長距離なら、 $C$ に向かってDFSするときは $C$ を除いた方向から伝搬する必要がある。要するにDFSで $V$ から $C$ に向かう時は $V$ のタプル集合から $(,,C)$ を除いてDFSし、DFS後に除いたタプル集合に戻す。

これで全頂点について答えが求まった。実装効率が悪すぎて2秒制限が危なかった。

公式解説には木の直径を用いた解法が載っている。木の直径を満たす二点のどちらかしか答えがないことは直感的には分かった。しかし頂点番号最大を導く方法が分からなかった。確かにこの方法で 正解 するが、注意深い実装が要る。