ABC 6,8問体制(126..最新)のD問題をだいたい解いたので、AGCを解いてみます。AGCにも灰diffがあります。

コードはこちら

丁寧に場合分けする

• $0 < a \leq b$ なら積は正
• $a \leq b < 0$ なら、a以上b以下の整数の数 $b-a+1$ が偶数個なら積は正、奇数個なら積は負
• 上記以外、つまり $a \leq 0 \leq b$ なら積は0

コードはこちら

丁寧にシミュレーションする

不確定なのは赤白どちらのボールを渡すかであって、それぞれの箱に何個ボールがあるかは決定的である。よって操作 1..M を順番に実行して、箱に赤いボールがあるかもしれない、もしくはそうではない(箱が空か、白いボールしかない)かを伝搬する。

• 箱 $X$ に赤いボールがあるかもしれないなら、操作後の箱 $Y$ も赤いボールがあるかもしれない
• 箱 $X$ に赤いボールがなければ、操作後の箱 $Y$ に赤いボールがあるかどうかは変わらない
• 操作後に箱 $X$ が空になったら、箱 $X$ に赤いボールは無くなる
• 操作後に箱 $X$ が空でなければ、箱 $X$ に赤いボールがあるかどうかは変わらない

コードはこちら

逆から考える。

短いロープから順に結合して、最後に $N$ 本のロープを結合したものを考える。

隣り合う2本ロープを結合して長さ $L$ 以上になるものがなければ、結合して $L$ 以上の2本のロープをほどくことができないので、答えは Impossible である。

そうでなければ答えは Possible である。隣り合う2本ロープを結合したときの長さが $L$ 以上になるようなロープの組 $(i,i+1)$ を、結合する候補として優先度キューに載せる。

キューから最も長さが短いロープの組 $(p,p+1)$ を取り出す。これはロープ $[l,..p]$ と $[p+1,..r]$ を結合することを意味する。

• $(p,p+1)$ を結合済なら何もしない
• $(p,p+1)$ を未結合なら結合する。ロープの組は一まとまりの区間 $[l,..p,p+1,..r]$ を成すので、左右の区間と結合することを候補としてキューに載せる。
  • $l > 1$ なら $l-1$ を含む区間 $[a,l-1]$ , $[l,r]$ を結合するように、候補 $(l-1,l)$ をキューに載せる。
  • $r < N$ なら $r+1$ を含む区間 $[l,r]$ , $[r+1,b]$, を結合するように候補 $(r,r+1)$ をキューに載せる

ロープを結合済かどうかは、union-find木で管理する。あるロープにどのロープを結合したかは、ロープの代表元に std::set<Num> で持たせて、結合しているロープの最小値と最大値と長さが分かる。ロープを結合したとき、要素数の少ない方を要素数の多い方にマージして、結合したロープの代表元に関連付ける。

これを $N-1$ 回繰り返すと $(p,p+1)$ の結合順が求まるので、逆順にしてほどく順番が答えである。

公式解説を読むと、優先度キューを使うまでもなく、隣り合う2本ロープを結合したときの長さが $L$ 以上になるようなロープの組 $(i,i+1)$ から左右に結合すればよかった。

コードはこちら

東西のうち、一方に0回、他方に1回以上移動するなら逆方向に打ち消し合うことができないので家に戻れない。南北も同様である。

コードはこちら

GreedyではWAすると思ったのだが。

DPが正解である。 $(i,i), (i+1,i+1)$ と $(i,i+1), (i,i+1)$ でペアの数は同じである。よって $(i,i+1)$ を1つ作るか作らないどうかでDPする。

$DP[i][0]$ を $i$ まで見た時 $(i,i+1)$ を作らないときのペアの最大数、 $DP[i][1]$ を $i$ まで見た時 $(i,i+1)$ を一つ作るペアの最大数とする。初期値 $DP[0][] = 0$ とする。また $(i,i+1)$ をペアにしないときの $A$ を $A0$ 、 $(i,i+1)$ をペアにしたときの $A1$ とし、 $A0 = A1 = A$ で初期化する。

$DP[i][0]$ は $max(DP[i-1][0] + \lfloor A0_i / 2 \rfloor, DP[i-1][1] + \lfloor A1_i / 2 \rfloor)$ である。

$DP[i][1]$ は $max(DP[i-1][0] + 1 + \lfloor (A0_i - 1) / 2 \rfloor, DP[i-1][1] + 1 + \lfloor (A1_i - 1) / 2 \rfloor)$ である。ただし $(i,i+1)$ をペアにできないときを考え、前者は $A0_i < 1 \lor A0_{i+1} < 1$ なら0、後者は $A1_i < 1 \lor A1_{i+1} < 1$ ならで0ある。

上記の操作 $i$ について終わったら組んだペアの分だけ $A0_i,A0_{i+1},A1_i,A1_{i+1}$ を減らす。上記の操作が $i=1..(N-1)$ について終わったら $N$ だけでペアを組み、 $max(DP[i][0] + \lfloor A0_N / 2 \rfloor, DP[i][1] + \lfloor A1_N / 2 \rfloor)$ が答えである。

公式解説はgreedyである。視点が違った。実装は こちら 。

コードはこちら

最初に $A$ を $1..N$ に座標圧縮する。

$A$ の一つ飛ばしの要素は操作2だけで昇順にソートできる。つまり $A_{2i}$ , $A_{2i+1}$ をそれぞれソートする。

$A_{2i}$ と $A_{2i+1}$ を一つの $A$ にするときの、操作1の回数を考える。 $A_{2i}$ にある奇数は $A_{2i+1}$ に移す必要があり、 $A_{2i+1}$ にある偶数は $A_{2i}$ に移す必要があり、このような要素の和が操作1の回数の最小値つまり答えである。要素を1個移すのに操作1が1回要るが、定位置に移すには操作2だけでよい。

コードはこちら

最小の断面

偶数長の辺があればそこで切れば差は0になる。すべての辺が奇数長なら、最も小さい断面積(x1)が答えである。

コードはこちら

最終的に色 $i$ のスライムを飼うとする。魔法を $j$ 回唱えた結果色 $i$ になったなら、元の色は $(N + i - j) mod N$ である。

魔法を最大 $k$ 回唱えられるとする。 $0 \leq K \leq N$ である。それぞれのスライムに唱える魔法は $K$ 回以下の任意の回数である。そこで以下のDPを考える。

• 魔法を $i$ 回唱えてスライムを色 $j$ にするための、元のスライムの最小のコストを $DP[i][j]$ と置く
• 魔法を $0$ 回唱えたとき、 $DP[0][j] = a_j$ である
• 魔法を $i+1$ 回唱えたとき、 $DP[i+1][j] = min(DP[i][j], a_{j + N - i})$ である。右辺の左側を選んだ時、魔法を $i$ 以下しか唱えたら止めにすることを意味する。
• 魔法を $i$ 回唱えたときのコストは $ix + \sum_j DP[i][j]$ である。この値の、すべての $i$ についての最小値が答えである。

コードはこちら

構築問題(constructive problem)は難しいが、ABC 387-Eでも出るのでARC/AGCに出場するなら解けなければならない。

ヒントになるのはヒューズROM (One Time Programmable ROM) の構造である。ワード線とビット線の交点を溶断するかどうかで情報を保持する。同じ要領でこの問題を解く。つまりワード線とビット線を一通り塗ってから、要らない部分を塗らなかったことにする。

両端を除く偶数行、偶数列を赤く塗る。両端を除く奇数行、奇数列を青く塗る。最左列をすべて赤く塗り、最右列を青く塗る。これで赤いマス、青いマスは一つの連結成分を構成する。これを初期配置にする。最上行と最下行以外のマスは、赤か青かどちらか一方で塗られている。

このままだと入力した紫色のマスと不一致になる。入力は紫色だが、初期配置では赤か青かどちらか一方でしか塗られていない場合を考える。このときは足りないほうの色を塗ればよい。新たにマスを塗るので、赤、青それぞれのマスが一つの連結成分であることに変わりはない。

入力は紫色ではないが、初期配置では赤と青の両方で塗られている場合を考える。このとき行の塗り方を維持し、列で塗った色を塗らなかったことにする。列で塗った色に関して、このマスを塗らなかったとしても、このマスの上下の行は最左列(赤)か最右列(青)で連結するので、赤、青それぞれのマスが一つの連結成分であることに変わりはない。

最外周に紫のマスは無いので、これをすべてのマスについて繰り返すと答えが求まる。

この方法は公式解説と同じである。列のことは考えずに初期配置から塗り足す分、上記より公式解説の方がわかりやすい。

どうしても答えが合わない。

首都からすべての町を距離の近い順を、テレポートを逆向きにしたグラフで探索する。 $K=1$ なら、首都までの距離1でない頂点の数である。特に首都も含む。

そうでなければ、首都から自己ループがなければ追加する。それ以後は、首都を起点に、首都までの距離の短い順に探索する。町 $v$ が首都からの距離 $K$ 以内なら何もしない。距離 $K+1$ になったら町 $v$ から首都への直行路を1本追加する。追加したら町 $v$ から首都への距離は1になる(0ではない)。いずれにしても $v$ にテレポートできてまだ訪れていない町を探索する。

公式解説通りのはずだが、なぜか 23 WAs が返ってくる。

コードはこちら

括弧

S,T を (,) 、さらに 1,-1 だと思えば典型問題である。括弧の対応が取れないつまり累積して0未満なら削除できず、そうでないところの区間を削除できる。

Rubyで再帰正規表現を使うと部分点が獲れる。

p gets.chomp.gsub(/(S(?:\g<-1>)*T)/, "").size

コードはこちら

数 $i=1..N$ が最小値として何回数えられるか求める。

1の位置を $P_1$ として、1が最小値となる区間は、左端が $[1,P_1]$ 、右端が $[P_1,N]$ の区間である。

2の位置を $P_2$ として、2が最小値となる区間は、番兵を $0,N+1$ として、 $0 < P_2 < P_1$ なら 左端が $(0,P_2]$ 、右端が $[P_2,P_1)$ の区間である。 $P_1 < P_2$ なら 左端が $(P_1,P_2]$ 、右端が $[P_2,N+1)$ の区間である。

この操作を一般化する。既に出現した数字の集合を $S = [0,N+1]$ で初期化する。数値 $i$ について、 $S$ において $i$ を超えない最大値を $L$ 、 $i$ を超える最小値を $R$ とすると、区間の数は $(P_i - L)(R - P_i)$ である。 $i$ の答えに対する寄与 $i(P_i - L)(R - P_i)$ を答えに足して、 $S$ に $P_i$ を加える。

これを $i=1..N$ について繰り返すと答えになる。

コードはこちら

木の直径、つまり二頂点間の距離の最大値 $D = max(A)$ を求める。直径となる両頂点を横一線に張って、その枝を張ることを考える。この直線状は両端を含めて、左端から数えた頂点 $i=0..D$ について距離は $L_i = max(i,D-i)$ になる。これらを一つずつ $A$ から除く。除くことができないつまり $L_i$ が $A$ に含まれないなら答えは Impossible である。

残った $A$ について、直線から枝を張る。枝の距離は少なくとも $H = 1 + \lceil D/2 \rceil$ なので、これを下回る $A$ の要素があれば、答えは Impossible である。そうでなければ枝の長さが1になる場所から枝を生やせばよく、答えは Possible である。同じ頂点から複数の枝を生やしても構わない。

コードはこちら

総当たり

$S$ の先頭 $0..N$ 文字に $T$ をつなげて条件を満たすかどうか調べる。 $S+T$ は必ず条件を満たすので、こうすれば条件を満たす最小の文字列がみつかる。

コードはこちら

実験して法則性を見いだす。

$N = 4$ で総当たりすると、以下のことが推測できる。 $X > N$ は $X$ を $2N - X$ に反転して同様に解く。

• $X = N$ なら $1..(2N-1)$ が解の一つである
• $X = 1$ 解なしである
• $1 < X < N$ なら、左から順に中央まで $N, N-1, ..., X+1, 1, 2, ... , X$ 、中央から右端まで $N+1, ... , (2N-1)$ である

コードはこちら

やはり総当たり

右または下への移動しかできないなら、そのような移動の総当たりを求める。この組み合わせの数は ${h+w-2}C{w-1}$ 通りである。そのような組み合わせを全部作って、可能なマスの組み合わせを列挙する。入力がどれかの組み合わせ一致すれば Possible 、そうでなければ Impossible である。

公式解説を読むと、「問題文および $a$ で与えられる情報と整合するような駒の動き方が存在する」という制約から、入力中の文字が $H+W-1$ 個かどうか調べればよかった。私の解法は、このような制約が無いときに該当する。

コードはこちら

$A_i + B_i$ は定数、 $|A_i - A_{i+1}|, |B_i - B_{i+1}| > n$ 、 $ord(P_i)$ で差を付けるという方針は思いついたが、それ以上どうすればよいか分からなくて諦めた。なんと正解は、 $A_i = Si, B_i = (n-i)S, S = 20005$ だった。難しく考え過ぎである。

コードはこちら

対称性が無い

$x,y$ に対称性がないので場合分けが大変である。数直線上に $x,y$ を置き、 $x,y$ の符号と絶対値から、符号反転をしない、一回する、二回するという場合分けに帰着する。

コードはこちら

最後だけに意味がある。

最後に塗ったところだけは、 $K$ マス連続で白か、 $K$ マス連続で黒か、どちらかでなければならない。それ以外のマスはどのような色でも塗れる。どのようにも塗れるのだから、正の数だけ塗ればいい。

よって最後に塗ったマスの左端を $i$ として、塗る区間を $[i,i+K)$ に決め打ちする。すべての $i$ について調べたものと0の最大値が答えである。

• 最後に白で塗るなら、 $j \in [1,i)$ の正の数 $a_j$ の合計と、 $j \in [i+K,N]$ の正の数 $a_j$ の合計の和である
• 最後に黒で塗るなら、 $j \in [1,i)$ の正の数 $a_j$ の合計、 $\sum_i^{i+K-1} a_i$ 、 $j \in [i+K,N]$ の正の数 $a_j$ の合計である

コードはこちら

見た目に反してとても難しい。

O形はどこに置いてもよいので、最後に $a_O$ を答えに加える。T,S,Z形は使い道がない。よって $a_I, a_J, a_L$ の組み合わせを考える。

1. I同士、J同士、L同士、2つずつ組み合わせる
2. I,J,Lのうち、最も少ない物 $M = min(a_I, a_J, a_L)$ を組み合わせる。残りを同じものを2つずつ組み合わせる。
3. $M > 0$ のとき、 $M-1$ 個の I,J,Lを組み合わせる。残りを同じものを2つずつ組み合わせる。

3番目を忘れるとWAする。

コードはこちら

実は区間スケジューリング問題。単なるgreedyだと上手くいかない。

以下0-based indexingを読み替える。答えの長さを $L = N^2$ とする。数字の置き場所を $P[0..(L-1)]$ 、 $P$ の候補を集合 $S = 0..(L-1)$ と置く。

最初に入力の値を固定し、置き場所 $P[x_i] = i$ とし、 $S$ から $x$ を除く。

次に $P$ に左から順に(添え字の昇順に)数字を詰める。このやり方は区間スケジューリングそのもので、 $(x_i,i)$ の昇順に、 $S$ から小さい順に $i$ を $x_i$ 要素取り出して $P$ に詰める。途中で $x_i$ より大きくなったら手詰まりなので No を返す。

次に $P$ に右から順に(添え字の降順に)数字を詰める。 $(x_i,N-i)$ の昇順に、 $S$ から大きい順に $i$ を $N-x_i-1$ 要素取り出して $P$ に詰める。途中で $x_i$ より小さくなったら手詰まりなので No を返す。

手詰まりにならなければ $P$ の内容が確定するので、1-based indexingにして出力する。

上記の区間を $(x_i-i,i)$ つまりここから連続して並べればぎりぎり間に合う最大の添え字にしたらWAした。

コードはこちら

非対称

ボタン $N$ の影響は $A_{N-1},A_{N}$ に及ぶが、ボタン $N-1$ の影響は $A_{N}$ には及ばない。なのでボタン $N..1$ の順に何回押すか決めればよい。

ボタン $N$ を押す回数は $(N - (A_N \quad mod \quad B_n)) \quad mod \quad B_N$ である。ボタン $N..(i+1)$ までを $d$ 回押したとして、ボタン $i$ を押す回数は $(N - ((d + A_i) \quad mod \quad B_i)) \quad mod \quad B_i$ である。

コードはこちら

トーナメントの決勝を根、初戦を葉として、根から葉までの深さを距離と定義する。題意を満たすつまりトーナメント木全体の深さを最小にするには、深い部分木を浅い頂点につなげればよい。これはDFSで求まる。

今DFSで注目している人を $p$ として、初期値を $p=1$ として以下の通り探索する。

• $p$ に直接負けた人の集合を $S$ とする。 $l \in S$ それぞれについて、部分木の高さを $H_l$ とする。
• $H_i$ を降順に並べる。 $i = 1..|S|$ について、 $min(i + H_i)$ が、 $p$ に関する部分木で深さ最小のものである。
• $H_i$ は、 $i$ 自身の部分木の高さに、根から $p$ までの高さ $t$ を加えたものである。よってDFSの呼び出しを $DFS(l, t)$ として、 $t + H(l)$ を返す。特に最初の呼び出しは $DFS(1,0)$ で、その返り値が問題の答えである。

コードはこちら

偶数+偶数は偶数、奇数+奇数も偶数、したがって偶数はいくつあっても1個に縮約でき、偶数個の奇数は偶数に縮約できる。奇数+偶数、奇数+偶数は奇数なので奇数の数を減らすことはできない。よって奇数が奇数個あったら NO 、偶数個あったら YES である。

公式解説では、すべての数の和が奇数と表現している。確かにその方が判定が速い。

コードはこちら

差分に注目する。

$N=1$ なら常に YES である。これを忘れると 2 WAs する。以下 $N > 1$ とする。

石は $U = \sum_{i=1}^N i = N(N+1)/2$ 個単位でしか取り除くことができない。よって $S= \sum_{i=1}^N A_i$ が $U$ の倍数でなければ NO である。

逆操作つまりまっさらな状態から石を置くことを考える。ある $i$ について $A_i$ から順番に石を $1..N$ 個置くと、 $A_i - A_{i+1} = -1$, $A_{i+1} - A_{i+2} = -1$, ... $A_i - A_{i-1} = N - 1$ になる。これは $A$ の隣接差分 $D_i = D_{i} - D_{i-1}$ のさらに差分を取ると、 $N - 1$ 要素が0、 1要素が $N$ になることを意味する。同様の $j$ について $A_j$ から順番に石を $1..N$ 個置くと、 $D_j$ が同様に加算される。

よって逆操作が存在するなら $D_i = A_{i} - A_{i-1}$ は上記の規則に従って作られたものに限る。 $D_i$ から $min(D)$ を引いて最低値を0に正規化する。このとき以下の条件を満たせば YES 、そうでなければ NO である。

• $D$ はすべて $N$ の倍数である
• $S = U \sum D / N$

コードはこちら

Greedy

$T_1$ に到着した人について、バスの出発時間を $T_1 + K$ まで遅らせることができるのでそのようにバスを手配する。

• $T_1 + K$ までに $C+1$ 人集まらなければ出発する。その次の人について同様に、 $T_1$ と同様にバスを手配する。
• $T_1 + K$ までに $C+1$ 人集まったら、乗り切れなかった人が到着した時刻を $T_i$ として、その人のために出発時間が $T_i + K$ のバスを手配する。 $C$ 人きっちり集まった時点ではまだ手配しない。これも $T_1$ と同様である。

コードはこちら

Union-find木でマージ

std::set<std::pair<Num,Num>> で、 生き物の大きさと色を管理する。小さい生き物同士を組み合わせた方が、そうでないより色数が増えるので、集合中最も小さい生き物2種類を合体する。

片方が他方を一方的に吸収できるなら色集合は増えない。そうでなければ双方の色集合を合併したものになる。これはUnion-find木でマージすることで表現できる。合体したら、大きさと色の代表元を再度集合に載せる。合体は最大 $N-1$ 回なのでこの繰り返しは終了し、Union-find木なので計算量も大きくならない。

公式解説は大きさだけに注目して解いている。

コードはこちら

上に寄せる

$a$ を降順に並べて、上から $2i$ 番目までに一位と二位を選ぶとすれば、 $2,4,..,2i$ 番目を二位にすることでそれぞれ二位であり和が最大になる。三位は残りから選べるので気にしなくてよい。

コードはこちら

よくあるクエリ逆再生。

イカが塗った頂点は後の操作で上書きされる。塗る順番をクエリ $t=1..Q$ の順番に対応し、逆順 $t=Q..1$ に塗る。 $D \leq 10$ に注目し、頂点を塗るのを上手く打ち切るBFSを考える。

各頂点 $v$ の状態を、最後に塗るときの残り距離 $D_v$ , 最後に塗った色 $C_v$ , 最後に塗った時刻 $T_v$ の組で表現する。初期状態は $(D_v,C_v,T_v) = (0,0,0)$ であり、クエリ $t=1..Q$ の順番に上書きする。

すべてのクエリについて、時刻、残り距離、色、頂点の組 $(t,d,c,v)$ を、時刻 $t$ が遅いものが先頭に来る優先度キューに積む。キューから $(t,d,c,v)$ を取り出して、隣接する頂点をたどる、という処理をキューが空になるまで続ける。

• $d = 0$ なら隣の頂点には行けない
• 隣の頂点 $u \in adj(v)$ それぞれについて、以下の処理を行う
  • $t > T_u \lor d-1 > D_u$ なら、隣の頂点に行くので、 $(t,d-1,c,u)$ をキューに積む
  • $t > T_u$ なら、頂点 $u$ を塗る。つまり $C_u = c$, $T_u = t$ にする

隣の頂点に行くが塗らないで通り過ぎることがある、というのがミソである。これは距離が短く時刻が後のクエリを正順に適用する場合に対応する。

コードはこちら

三方比較

本当は整数を <=> で比較したい。間違って > で比較してWAしてしまった。増減方向が変わったら区切ればよい。それより速く区切っても区切る回数は同じか増えるだけである。

• 初期値の方向は0(横這い)とする
• $A_{i} = A_{i+1}$ なら方向を変えない
• $A_{i} < A_{i+1}$ は増加で1、 $A_{i} > A_{i+1}$ は減少で-1とする
• 方向が変わる、つまりこれまでの方向と $A_{i},A_{i+1}$ の方向(1,-1)の積が負なら、区切りを一個足して方向を0(横這い)にする

コードはこちら

未証明のままAC。

次数1の頂点が二つあるならそれら二頂点を結ぶ任意のパスが答えである。そうでなければループがあるはずだから、輪を切ってパスにすればいい。

輪を切ってパスにする方法がわからないが、次数が一番小さい頂点 $i$ を始点に、以下の制約を満たすパスをDFSするとACする。これは次数1の頂点が該当するなら $i$ として選ぶ。

• これまで通ったパス上の頂点集合を $S$ とする
• 現在の頂点を $v$ とする
• 初期値は $S = i$, $v = i$ である
• $i$ の隣接する頂点で、 $S$ に含まれないものを選ぶ
• $i$ の隣接する頂点で、 $S$ に含まれないものを選べないなら、以下の判断を行う
  • $v$ に隣接する頂点がすべてパス上にあるなら、それが答えの一つである。これ以上探索する必要はないので、探索を打ち切る
  • そうでなければこのパスは答えではないので、パスを一つ戻って探索を続ける

上記でWAもTLEもしない理由がわからない。そして公式解説の反復で詰まない理由もわからない。

コードはこちら

やってみる

実際にやってみると回数が分かる。問題は無限に続くときいつ打ち切るかである。

$A,B,C$ は $(B+C)/2,(A+C)/2,(A+B)/2$ になる。つまり $A,B,C$ に素因数2があれば、操作を一回すると素因数が2が1個減るかもしれないと予想できる。減らないのであれば、無限に続く。なのだが証明を思いつかなかった。

公式解説によれば、クッキーの個数の最大と最小の差が、一操作ごとに半分になると書いてある。そうだったのか。

コードはこちら

オイラーツアー

木をオイラーツアーして頂点番号を $1..N$ を割り当てる。このような木において、頂点 $a,b (a < b)$ へのパスを考えると、最短パスにある辺は1回、そうでない辺は0または2回通る。よってオイラーツアーによって辺を通る回数をいもす法てきに、 $a$ で1足し、 $b$ で1減らす。

すべてのクエリ $(a,b)$ について上記を前処理する。辺を通る回数をいもす法で求め、奇数回通る辺があれば答えは NO 、そうでなければ答えは YES である。

公式解説ではオイラーツアーとは明言していないが、LCAを考慮しているので実質的に上記と同じである。

コードはこちら

どうして解けなかったのかわからない。

初手で移動できる範囲は、初期位置からマンハッタン距離が $K$ 以内で閉じられていない部屋である。

二手目は以降は、問題文と逆に操作を行う。つまり部屋を $K$ 箇所開けて、今開けたか元々開いていたかに関わらず、マンハッタン距離が $K$ 以内で閉じられていない部屋に移動する。これは部屋が開いているかどうかに関わらず、単に距離 $K$ 移動すればよい。

はずなのだが、部屋を $R < K$ 回以内開けて開いている部屋に移動したら、 $K - R$ 回余分に開ける回数を持ち越せるとしてループを組んだらWAした。どうして間違ったのかわからない。解説を読んでも 3 WAs するのがわからない(多地点BFSなので、一手目の初期化を変えたら通った)。

コードはこちら

場合分けが大変

$A \leq B$ ではない入力に対処しなければならない。

• $A > B$ なら0通り
• $A = B$ または $A < B \land n = 2$ なら1通り
• $A < B \land n = 1$ なら0通り
• それ以外なら $1 + (b - a)(n - 2)$ 通り

コードはこちら

端まで行く

直行できなければ最上階か最下階まで行けばいいので、エレベーターに乗る回数は1回または2回である。2回乗るのは、行きたい方向にボタンがないときである。よって $i=1..N$ 階にいるとき、

• ボタンが U なら今より下の階 $i-1$ 通り
• ボタンが D なら今より上の階 $N-i$ 通り

は2回乗る。

コードはこちら

1時間6分で解けた。

二次元累積和の実装で手こずった。いい感じに二次元累積和を前計算すると、クエリ当たり $O(1)$ で解ける。座標系を入れ替えて行つまり縦方向を $Y$ 、列つまり横方向を $X$ を読む。

問題文の制約が重要である。田の字 $(y,x),(y+1,x),(y,x+1),(y+1,x+1)$ の4マスを同時に青く塗ることは無い。このことから、ある矩形領域 $(Y1,X1)-(Y2,X2)$ の連結成分数は、 $X1 \leq c \leq X2$, $Y1 \leq r \leq Y2$, $X1 \leq x < X2$, $Y1 \leq y < Y2$ として、

• $C = (Y1,X1)-(Y2,X2)$ にある青マス $(c,r)$ の数
• $V = (Y1,X1)-(Y2,X2)$ で、左右が青マスの境界の数、つまり $(y,x),(y,x+1)$ が両方青マスとなる $x$ の数
• $H = (Y1,X1)-(Y2,X2)$ で、上下が青マスの境界の数、つまり $(y,x),(y+1,x)$ が両方青マスとなる $y$ の数

として、 $C - V - H$ である。 $C,V,H$ は二次元累積和を前計算しておく。実装がややこしかった。この解き方は公式解説通りである。

コードはこちら

決め打ち

最後の文字列は、 $S$ に含まれるいずれかの文字 $c$ と決め打ってよい。 $c$ について $c$ 以外をランレングス圧縮したときの最大長が、 $c$ と決め打ったときの操作の最大回数である。なぜなら一操作ごとに、それぞれのラン長が一つ減るからだ。

すべての $c$ の候補について上記の最小値が答えである。

コードはこちら

徹底して理詰め。

N匹の猫が被っている帽子の色の種類数はちょうど $K$ であるとする。ある猫 $i$ が色 $C_i$ の帽子をかぶっているとする。このとき猫 $i$ 以外の猫がかぶっている帽子の色の種類数 $a_i$ は、

• $C_i$ の帽子をかぶっている猫が猫 $i$ 以外にいれば $a_i = K$
• $C_i$ の帽子をかぶっている猫が猫 $i$ 以外にいなければ $a_i = K - 1$

である。よって $a$ は $K$ のみか、 $K-1,K$ の二種類かどちらか一方しかない。それ以外は No である。このことは $a$ のヒストグラムを作れば分かる。

$a$ が1種類のときを考える。このようになるのは、すべての帽子の色が異なる $a_i = K-1$ か、どの色の帽子も2匹以上の猫がかぶっているかどちらかである。後者が成り立つ条件は、 $1 \leq a_i \leq \lfloor N / 2 \rfloor$ である。それ以外は No である。

$a$ が $K-1, K$ の2種類のときを考える。 $a = K-1$ の猫が $M$ 匹とする。この $M$ 匹の猫から見て帽子の色は、他の $a = K-1$ の猫 $M-1$ 色と、 $a = K$ の猫の少なくとも1色分が必要である。つまり $K - 1 < M$ なら色が足りないので答えは No である(これは下記とまとめる)。

同じ色の帽子をかぶった他の猫がいる $N - M$ 匹の猫に、 $K - M$ 色を割り当てることが可能か考える。これが成り立つ条件は $a$ が1種類のときと同様に、 $1 \leq K - M \leq \lfloor (N - M) / 2 \rfloor$ である。それ以外は No である。

公式解説はaloneな猫という表現で、上記と同じことを述べている。

コードはこちら

ARCにしては珍しく入力例がヒントである。

$H mod \quad h = 0 \land W mod \quad w = 0$ のときは、 $h$ 行 $w$ 列の長方形を隙間なく $H$ 行 $W$ 列に敷き詰めることができる。このとき $H$ 行 $W$ 列の全要素の和は必ず負になるので答えは No である。それ以外は Yes であり、以下の通り構成する。

$H=1$ のときを特別扱いする。 $R = W mod \quad w$ とする。要素の単位 $C$ と定める。0-based indexing つまり最左列を0列目として、 $x$ 列目の内容を、 $x Mod \quad w = w-1$ のとき $-C(w-1)-1$ 、それ以外のときは $C$ とする。このとき任意の連続する $w$ 列について、和は-1になる。すべての要素の和は $RC - \lfloor W/w \rfloor$ であり、 $C > W/w$ となるように例えば $C = 1000$ にすればすべての要素の和は正になる。

$W=1$ のときは行と列を入れ替えれば同様にできる。

$H,W > 1$ のときも同様に考える。 $y$ 行 $x$ 列目の内容を、 $y Mod \quad h = h -1 \land x Mod \quad w = w-1 \land$ のとき $-C(hw-1)-1$ 、それ以外のときは $C$ とする。このとき任意の $h$ 行 $w$ 列の長方形について、和は-1になる。 $T = H mod \quad h$ , $R = W mod \quad w$ とする。すべての要素の和は $C(T \lfloor W/w \rfloor + R \lfloor H/h \rfloor + TR) - \lfloor W/w \rfloor \lfloor H/h \rfloor$ であり、例えば $C = 1000$ にすればすべての要素の和は正になる。

コードはこちら

パリティ

偶数な $A$ はどう組み合わせてもよい。なので偶数な $A$ が $E$ 個あったら、 $C_e = 2^E$ 通り選べる。奇数な $A$ は $P = 0$ なら偶数個、 $P = 1$ なら奇数個選べる。よってなので奇数な $A$ が $D$ 個あったら、 $C_o = \sum_{i=P..M} {D \choose i}$ 通り選べる。ただし $M$ は、 $P = 0$ なら $D$ を超えない最大の偶数、 $P = 1$ なら $D$ を超えない最大の奇数である。答えは $C_e C_o$ 通りである。

公式解説はもっとエレガントである。そういえば出力例4は2のべき乗である。

コードはこちら

足し引きについて対称なので、最初に正規化する。つまり $A=0, B=|A=B|$ にする。足した数の幅を $W = |D-C|$ とする(この定義を間違えてしばらく解けなかった)。数 $C \leq a \leq D$ を足して $S$ を作れるなら $-S$ も作れるので、 $S \geq 0$ だけ考える。また $N$ を何回足すかと再定義し $N-1$ で置き換える。

最初に、 $N = 1$ のとき、 $C \leq B \leq D$ なら YES 、そうでなければ NO である。以下 $N > 1$ とする。

$2C \leq D$ なら、二回足すと $[0, 2D]$ の任意の数を作れる。 $S$ の上限は $DN$ なので、 $2C / D \land B \leq DN$ なら YES である。

$2C > D$ なら $S$ は単一区間ではなく隙間がある。二回足すと $[W, 2D], W > 0$ の任意の数を作れることが鍵である。 $H = \lfloor N/2 \rfloor$ とする。 $N$ が偶数のとき、 $i = 1..H$ について、 $[C,D]$ を $2i$ 回足すと $[2iC,2iD]$ なり、ここから残り $r = N - 2i$ 回の操作で区間を左右に伸ばして、 $[2iC - rW, 2iD + rW]$ を作れる。 $N$ が奇数のときは最初に $[C,D]$ にするので $[(2i+1)C - rW, (2i+1)D + rW]$ である。

これらの区間のいずれかに $B$ が入っていれば YES 、そうでなければ NO である。計算量は区間の数で決まり $O(N)$ である。

コードはこちら

ゲーム木だと思ったらGrundy数だった。Min-maxだと思ったのでまるっきりわからなかった。

証明はほぼGrundy数の定義から導けるようである。部分木 $T$ のGrundy数が $N$ なら部分木の部分木 $T^{'}$ のGrundy数は $0..N$ の値を任意を選べる、よって $T$ の根に一辺加えた木のGrundy数はそれらのどれでもない値 $N+1$ である。と言われれば分かるが自力では思いつかない。

コードはこちら

最大公約数

$A_i$ 以外の最大公約数 $gcd(i) : S = A \setminus A_i$ を求める。ある $i$ について $A_i - C \times gcd(i) = k$ なる整数 $C$ が存在すれば答えは POSSIBLE である。 $gcd(i)$ は、操作はGCD, 単位元を0とするセグメント木を使えば求まる。 $N = 1$ のときに注意する。

なんとなく予想できた通り、公式解説は $gcd(A)$ を直接使っている。

コードはこちら

まさかgreedyが通るとは思わなかった。

何の制約もないときの一番人気のスポーツ $k$ の参加人数 $c$ を求める。次に $k$ がないときの一番人気のスポーツ $k^{'}$ の参加人数 $c^{'}$ を求める。これを繰り返して順にスポーツを除き、 $c$ の最小値が答えである。ある人 $i$ の参加意欲を std::set<std::pair<Num,Num>> に $(j, A_{ij})$ を載せると、スポーツ $k$ を除く操作は一人当たり $log(M)$ なので、総計算量は $O(NMlog(M))$ である。想定解法は $O(NM^2)$ だった。

コードはこちら

単価で並べる

まず買う量を0.25リットル単位にする。これは量をすべて4倍にすればよい。

量が増えるなら単位量あたりの価格が安くなければ意味が無い。そうなるようにボトルを、2リットル当たり価格、ボトルの価格、ボトルの量、というタプルで表現する。最初はボトルを量の昇順で並べ、2リットル当たり価格が単調増加にならないようなボトルを取り除く。

こうすると量が増えるなら単位量あたりの価格が安くなる。後は量の多いボトルから順に買えるだけ買って、端数はより量が少ないボトルを買う、と言うのを繰り返す。

コードはこちら

Manacher's Algorithm だと思ったら全然違った。

コードはこちら

不変量

アリスとボリスが両方動けるなら、 $A$ と $B$ の差の偶奇は同じである。同じ方向に動けば差は同じ、違う方向に動けば差は2開くか2縮まるからである。

これが成り立たないのは一方が端に追い込まれたときである。アリスが先手なので、

• $A-B$ が偶数なら差を1にしたところでボリスは動けなくて負ける。アリスはボリスの方に向かっていき、端に追い込めばいい。
• $A-B$ が奇数なら差を1にしたところでアリスは動けなくて負ける。ボリスはアリスの方に向かっていき、端に追い込めばいい。

コードはこちら

最後が2でなければ解なしである。これを忘れてWAした。

$A$ を逆順にして、先頭から末尾に向かって反復する。初期値は $min(N) = 2$, $max(N) = 3$ である。

• $newmin(N) = A_i \lceil min(N) / A_i \rceil$ つまり $\lfloor newmin(N) / A_i \rfloor$ が $min(N)$ となる最小値
• $newmax(N) = A_i (1 + \lfloor max(N) / A_i \rfloor) - 1$ つまり $\lfloor newmax(N) / A_i \rfloor$ が $max(N)$ となる最大値

で更新する。 $min(N) \leq max(N)$ ならそれが答え、そうでなければ解なしである。

コードはこちら

入力例を見直す

入力例2 9995 に対する 9989 は正しい例だが、並び替えた 8999 の方が素直である。つまり右側(trailing)に9をできるだけ寄せて、最上位桁は9以外でも仕方がない、という例を作ればよい。

• $N < 10$ つまり一桁なら $N$ そのものが答えになる
• $N=d9...9$ つまり最上位桁を除いて9が続くなら、 $N$ そのものが答えになる。これ以上各桁の和を増やす余地はない。
• そうでなければ $N=a:b..c$ を $(a-1):9..9$ に置き換えればよい。 $a=1$ なら最上位桁が0になるがそれで構わない。

最上位桁以外は9が並ぶというのが、意外と実装が大変である。

コードはこちら

実数でいもす法していいのか、という疑問はあるが多分大丈夫だと思う。

ある穴 $A$ から360度を見回して、他の穴 $B$ が見えるかどうかを調べる。視点の方向 $\pm 90$ 度を視野として、他の穴 $B$ が視野に入ったら、その方向にある点(実質無限遠)から穴 $B$ に落ちて穴 $A$ には落ちない。そうでなければ、その方向にある点から穴 $A$ に落ちる。

穴 $A$ から見えない視野 $R$ を求める。穴 $B \in 1..N \setminus A$ について、 $B$ に塞がれる視野を $R$ に追加していく。これは $\theta = atan(y_B - y_A, x_B - x_a)$ として、 $[l,r] = [\theta - \pi / 2, \theta + \pi / 2]$ を塞ぐよう、いもす法を準備する。ただし角度が $[0, 2 \pi]$ に収まるよう、視野を $[l,r]$ または $[0,r],[l,2 \pi]$ にする。角度のオフセットは $atan$ の返り値次第だが、すべてのケースについてそろっていればどんなオフセットかは気にしなくてよい。

上記が求まったら、視野 $R$ をいもす法して、カウントが0の区間の総延長を求める。これが穴 $A$ から見える視野の角度である。すべての穴について視野の角度を求め、総和が1になるように正規化すると答えになる。

公式解説は凸包を $O(NlogN)$ で求めている。確かに凸包はこの通り速く求まるが、この問題では効率的な凸包の求め方を知らなくても上記の通り $O(N^2)$ の方法で構わない。

コードはこちら

辞書順なら並べ替え

$S$ が26文字以下なら、 $S$ で使われていない文字のうち最も順序が小さい物を $S$ に一文字付け加える。

$S$ が26文字なら、 std::next_permutation で $S$ の次の辞書順 $U$ を求める。 $U$ のうち、先頭から $S$ と一致する 接頭辞全てと、最初に $S$ と異なる一文字を出力する。それ以降は要らない。 $S$ が辞書順で最後なら std::next_permutation はfalseを返すので分かる。

偶数を3の倍数個、3の倍数だが偶数ではない数を偶数個並べる。そうすれば、2の倍数の数からみると他の数の和は偶数である(偶数は単独で偶数、3の倍数は2個ずつ組み合わせると偶数)、3の倍数の数からみると他の数の和は3の倍数である(3の倍数は単独で、偶数を3個ずつ組み合わせる)。この組を $(p,q)$ と表現する。

30000を超えない範囲で偶数を3の倍数個、3の倍数だが偶数ではない数を偶数個並べる。最初に偶数を6個単位で並べ、30000を超えたら3の倍数だが偶数ではない数を並べる。

6個単位でならべて $r = N mod 6$ のときに、2の倍数と3の倍数を組み合わせて $r$ を作る。 $r = 0..5$ について、 $(0,0),(3,2),(0,1),(1,0),(0,2),(1,1)$ 個並べる。 $r=1$ のときは $r=7$ とみなすので6個組を一つ減らす。微調整として、30000を超えた偶数を6個、3の倍数だが偶数ではない数に置き換える。このあと3の倍数だが偶数ではない数が1個もなければ、偶数を6個増やし、3の倍数だが偶数ではない数を6個減らす。これで両方の組はともに空ではない。

境界例をコードに書くのは難しいのでハードコーディングする。 $N < 5$ は問題からコピぺする。 $N = 19998$ は $(6,8,...,30000, 3,9,...,29997)$ にする。 $N = 19999$ は $(6,8,...,29998, 3,9,...,29997)$ にする。

コードはこちら

累積和

$A_0 = 0$ として、 $\sum_{i=l..r} A_i = \sum_{i=0..r} A_i - \sum_{i=0..(l-1)} A_i$ である。よって累積和 $\sum_{i=0..i} A_i$ が $S$ となるような位置 $i$ を求めて置く。 $l=1..N$ について、 $\sum_{i=l..r} A_i = \sum_{i=0..r} A_i$ となるような $r$ の個数を std::lower_bound で求めて足すと答えが求まる。

公式解説はこれを一歩推し進めて、累積和が等しい数の組から答えを導出している。

コードはこちら

$O(N^4)$ を $O(N^3)$ に下げる。

元々の盤面の対角線 $(1,1) ... (N,N)$ が盤面かどうかは総当たりで分かる。同様に左に $i$ 回転した盤面の対角線 $(i,i) ... (i-1,i-1)$ が盤面かどうかも総当たりで分かる(頭がこんがらがってコピーしたが、適切に添え字を取ればコピーは要らないはず)。

マス $(i,j)$ を $(i+A,j+B)$ にずらすのは、対角線の位置を $A+B$ ずらすことと同じである。盤面の対称性は対角線の位置をどうずらすかで決まり、これは $A+B$ で決まるが $(A,B)$ 個々の値には依らない。

よって対角線をずらす量を $i=0..(N-1)$ の総当たりして、よい盤面に該当する $i$ の数を $N$ 倍したものが答えである。

コードはこちら

手を動かす

実際に操作すると、 $K$ が奇数なら $B-A$ 、 $K$ が偶数なら $A-B$ だと分かる。

コードはこちら

色々考えたが諦めた。

最後に思いついたのがLISだったのだが、もう一歩だった。 $i=1..N$ がある位置を $Q_i$ と置く。区間 $[L,R]$ について、 $Q_i < Q_{i+1} : \forall i \in [L,R)$ が成り立つような、最大の区間を求める。これはLISより簡単に逐次的に求まる。 $i=2..N$ について、区間長 $L_i$ を求める。

• $Q_{i-1} < Q_{i}$ なら $L_i = L_{i-1} + 1$
• $Q_{i-1} > Q_{i}$ なら $L_i = 1$

$N - max(L)$ 個の整数を端に寄せるので答えである。

コードはこちら

$A_1$ は増やせないので、 $A_1 \ne 0$ なら答えは -1 である。そうでない場合を考える。

丁寧に場合分けする。いま注目する $A$ の $i=2..N$ 番目の要素を $h = A_i$ とする。

• 隣からは1より多く増やせないので、 $A_{i} - A_{i-1} > 1$ なら答えは -1 である。
• 隣から1増やす操作は一回でできるので、 $A_{i} - A_{i-1} = 1$ なら操作回数を1増やす。
• 隣と同じかそれより低い場合 $A_{i} - A_{i-1} < 1$ は、 $h = A_i$ にするため左から順に $1,2,..h$ と積み上げる必要があるので操作回数を $h$ 増やす。

コードはこちら

総当たり

$A=1..N-1, B=N-1..1$ を総当たりする。0と $N$ を含まないので注意する。

$P$ 進数の桁を足すコードは頻出なのですぐに書けるようにする。 $A$ を $P$ で割った余りが最下位桁 $0..P-1$ で、 $A$ を $P$ で割って余りを切り捨て、 $A > 0$ の限り繰り返す。

公式解説は、 $N$ が10のべき乗かどうかで場合分けして求めている。計算量はこの方が少ないが、 $N \leq 10^5$ ならこの洞察をするより上記のコードを書く方が早く提出できる(どちらにせよ桁を足す必要があるので)。

コードはこちら

やはり総当たり

この問題は $A$ を $p=0..N$ 個、 $B$ を $q=0..N$ 個割り当てて $Ap + Bq = K$ となる組み合わせは何通りあるか、と読み替える。ただし $0 \leq p,q \leq N$ とする。 $p=0..N$ と固定すれば $Bq = (K - Ap)$ より、整数の $q$ があるなら一意に定まる。 $0 \leq p,q \leq N$ なる整数 $p,q$ の組があれば、 ${N \choose p} \times {N \choose q}$ 通りを加算する。

拡張GCDを持ち出したが使い道が無く、単に解答時間の無駄だった。

コードはこちら

解けそうで解けない。

移動方向を左、右、左、右と決め打ちする(逆順については座標の符号を反転して同様に調べる)。このとき左への移動はまだ使っていない区間で $L$ の最大値、右への移動はまだ使っていない区間で $R$ の最小値を選べばよい。

これで解けると思ったがWAが取れなかった。全区間を使わず、途中の区間を通過したことにすればよい、というのが正解だった。つまり決め打ちした移動回数 $0..N$ 回の最大値が答えである。通過するのを上手く扱えなかった。

コードはこちら

ランレングス

同じ色のスライムが $i \ge 2$ 匹以上連なったら、一つ違いに $\lfloor i/2 \rfloor$ 匹の色を変える。 $N \leq 100$ なので色は 9900色から好きに選べばいい。

センチネルを使うと左右の端のスライムを特別扱いしなくて済む。左端に色 $a_0=-1$ 、右端に色 $a_{N+1}=-10000$ のスライムが居るとする。左右の端の色は $a_{1..N}$ とは異なり、したがって左右の端のスライムに魔法を唱える必要はないので問題の答えには影響しない。右端のセンチネルは $a_{N-1}=a_{N}$ のときにこれらに魔法を唱えるためである(色が連続したまま列が終わると魔法を唱えるのを忘れてしまうので、色違いで終わる)。

コードはこちら

プログラミングというより数学である。丁寧に場合分けする。まさか18分で解けるとは思わなかった。

1. $A < B$ なら初日に買えないので No
2. 上記ではなく、 $D < B$ ならいつか在庫が尽きるので No
3. 上記ではなく、 $C \geq B$ なら常に補充されているので yes
4. 上記ではなく、 $Rem = A mod B$ とする。 $Rem > C$ ならその日補充されず次の日に足りないので No

$C < B$ で、在庫が $C$ より多く $B$ 未満の状態ならその日補充されないまま次の日に足りないので No である。このような状態が発生するか確かめる。

原点を $R$ だけシフトして、 $Left = C - R$, $Right = B - R$ とする。 $S = D mod B$ 刻みで原点から動き、 $Left < p < Right$ にならないことを確認する。 $S = 0$ ならずっと原点なので Yes である。

周回を考慮すると、原点から $U = GCD(B,S)$ 刻みで動くと読み替えて構わない。 $p = \lfloor Left/U \rfloor$ として $p \leq Left \land (p + U) \geq Right$ なら、 $Left < p < Right$ にならないので Yes 、そうでなければ No である。

コードはこちら

$2^N$ で作れる何かだとは思ったが、ハッシュダイジェストだとは気が付かなかった。

公式解説を読んで、 $S$ を左右に分割して、ハッシュダイジェストが一致する組み合わせを数える。

コードはこちら

Greedy

$a_i$ が少ない子供から順に配ればよい。 $a_i$ を昇順にソートして累積和を取り、順に子供 $1..N$ とする。

• 全員にお菓子をきっちり配る、つまり $sum(a) = N$ なら答えは $N$ である。そうでなければ以下。
• 累積和を std::upper_bound して、累積和が $X$ を超える最初の子供が $1 \leq i \leq N$ 人目なら、 $i-1$ 人までは喜ばすことができ、 $i$ 人目以降を喜ばせることはできない。余ったお菓子を $N$ 人目の子供に全部配れば(公式解説の表現だと押し付ける)、 $N$ 人目の子供は喜ばないが他の子供は喜ぶ可能性がある。よって答えは $min(N-1, i-1)$ である。

コードはこちら

方針は立ったが実装方法が分からなかった。

値 A を取る頂点群 $G_A$ と 値 B を取る頂点群 $G_B$ があるとする。 ${a,b} \in G_A$ と ${c,d} \in G_B$ という頂点があり、 $a-b, b-c, c-d, d-a$ が結ばれていればこのループを使って任意の文字列を作れる。 $a \ne b$ は常に選べて、 $a = b$ は $a$ に自己ループがあるときはそのようにしてもよい( $c$ も同様)。具体的にはループ上を以下のように動く。

• AA は $a-b$ を行き来する
• BB は $c-d$ を行き来する
• AB は $(a,b)$ から $(c,d)$ に行く
• BA は $(c,d)$ から $(a,b)$ に行く

このループを検出する方法が分からなかった。公式解説を読んでようやく分かった。ある頂点 $a$ について、隣接する頂点がないか、隣接する頂点の値が一種類しかないとする。このとき頂点 $a$ を除く。 $a$ に隣接する頂点 $b$ について、 $a$ の値を取らなくなるかもしれないので、その時は頂点 $b$ を取り除く。これを繰り返す。具体的には以下の通り再帰する。

• 頂点 $v$ に隣接する頂点 $U_v$ について、 A を $C_A[v]$ 個、 B を $C_B[v]$ 個取ることを数える
• $C_A[v] = 0 \lor C_B[v] = 0$ な頂点をキューに入れる
• キューから取り出した頂点 $v$ の値を $K$ とする。頂点 $v$ に隣接する頂点 $u \in U_v$ について、 $C_K[u]$ を1減らす。減らした後に0になったら、キューに頂点 $u$ を入れる
• これを繰り返して頂点が無くなったら答えは No 、頂点が残ったらループがあるので答えは Yes である

トポロジカルソートと言われればその通りである。

コードはこちら

条件がややこしい

解があるなら $N,M$ の最小公倍数である。解があるかどうかの場合分けが大変である。

• $N=M$ なら、 $S=T$ のとき解は $N$ 、そうでなければ解なし -1 である
• $S,T$ の最初の文字が異なるなら解なしである
• $N$ が $M$ で割り切れるもしくは $M$ が $N$ で割り切れるとき、 $S,T$ の最後の文字が異なるなら解なしである
• $N,M$ が互いに素なら、 $S,T$ の文字を互い違いに $X$ に組み込めるので解がある
• それ以外は実際に $X$ を作ってみる。上記のフィルタリングなしに $X$ を作るとRE/MLEする。

コードはこちら

やってみる

白石の左に黒石が並んでいれば、並んでいる黒石の左端にその白石を置ける。並んでいないつまり左が白石なら何もできない。よって、既知の黒石の場所をカーソルとして覚えて置き、白石を左に寄せていく。 $S_{1..N}$ について、

• 初期状態ではカーソル $c$ は $NA$
• $S_i=B$ かつカーソル $c=NA$ なら、カーソルを $i$ にする。
• $S_i=B$ かつカーソル $c \ne NA$ ならば何もしない
• $S_i=W$ かつカーソル $c=NA$ なら何もしない
• $S_i=W$ かつカーソル $c \ne NA$ なら $i-c$ を操作回数に加算する

公式解説は上記を上手く整理していて、白石の左にある黒石の数であることを導出している。

コードはこちら

実はgreedyで解ける。

大きな数字は相手のペアが自分以下の数字に限られるが、小さな数字は相手のペアが自分以上なら何でもいいので使い勝手がいいと分かる。よって大きな数字から順にペアを組む。

重複を許して大きな数字 $A$ から順に、ペアが組めるかどうか考える。

• $A$ が2のべき乗、つまり立っているビットが1個なら、もう一個 $A$ を組めるなら組ませる。
• $A$ が2のべき乗以外なら、 $A$ のビット幅が $w$ として $2^w-A$ と組めるなら組ませる
• ペアを組めたかどうかにかかわらず、 $A$ を1個削除する。ペアを組めたらなら組んだ相手を削除する。

こうするといつかボールが尽きるので答えが求まる。

コードはこちら

一つ多い

解毒できる回数は $A+B$ なので、クッキーCは $min(C, A+B+1)$ まで容認される。 +1 をうっかり忘れやすい。それとは独立にクッキーBは食べたいだけ食べればいいので、答えは $min(C, A+B+1)+B$ である。

コードはこちら

文字 $C$ が $D$ 回出現するなら、 $C$ を使わないのが一通り、使うのが $D$ 通り、計 $D + 1$ 通りの使い道がある。これを a..z について掛けたものから1引く(空文字列なので)と答えである。

コードはこちら

制約からDPだと思った。

$DP[i=1..N]$ を、石 $i$ までみたときの石の色の列としてありうるものの個数とする。 $DP[0] = 1$ とする。石 $i$ について、その左側を新たに塗れるなら塗り、塗れないなら塗らないことをDPする。 $C_j = C_i \land j < i$ を満たす最大の $j$ が存在するかどうか調べる。これは色 $C_i$ となる石の位置を std::lower_bound から分かる。

• このような $j$ がなければ塗れない。 $DP[i] = DP[i-1]$ である。
• $j = i-1$ なら塗っても何も変わらない。 $DP[i] = DP[i-1]$ である。
• $j < i-1$ なら塗らないときと塗ったときの両方を考慮して、 $DP[i] = DP[i-1] + DP[j]$ である。

$DP[N]$ が答えである。

コードはこちら

後ろから再帰

順操作 $1..N$ を終えた後に $b$ になったのなら、 $b$ の中に定位置のものが少なくとも一つあるはずである。つまり $\exists i : b_i=i$ である。定位置のものがなければそのような順操作は存在しないので、答えは -1 である。

定位置にある $b_1..b_N$ からもっとも右にある ($i$ が最も大きい) ものは、最後に挿入されたはずである。なぜなら $i$ より小さい定位置によって、右に押し出されなかったからである。よって最も右側にある定位置を除く逆操作を行う。

逆操作を繰り返して空集合にできたなら、この逆操作の逆順が順操作の順番つまり答えである。途中で定位置の $b$ が見つからなかったらそのような順操作は存在しないので、答えは -1 である。

コードはこちら

手を動かす

とても時間が掛かったが、手を動かすと状況が見えてくる。例えば $N=8$ なら足して同じ数になる組は $(1,9),(2,7),(3,6),(4,5)$ なので、2を足すなら7も足す、3を足すなら6も足す、という対称性を持たせると上手くいきそうである。

$N$ が偶数のとき $H=N/2$ とおく。 $S = (N+1)(H-1)$ である。 $i=2..N$ および $\bar{i} = N+1-i$ について以下の通りにする。

• $1,N$ と結ぶ
• $i \ne j, \bar{i} \ne j$ なら $(j,N+1-j)$ と結ぶ

$N$ が奇数のとき $H=(N-1)/2$ とおく。 $S = N(H-1)$ である。最初に $(1,N)$, $(N-1,N)$ を結ぶ。 $i=2..N$ および $\bar{i} = N-i$ について以下の通りにする。

• $1,N-1,N$ と結ぶ
• $i \ne j, \bar{i} \ne j$ なら $(j,N-j)$ と結ぶ

辺が重複するので並び替えてから std::unique, std::erase で重複を除いてから出力する。

公式解説はもっと簡潔に説明していて、奇数のときは $N$ を除いて偶数個の場合を拡張している。

コードはこちら

BFSで求まる。開始点は距離0で初期化することを忘れない。

コードはこちら

Greedyだと1 WAが取れないまま諦めた。

正しくは最終状態から考える。こちらの 記事 通りに実装したが、有効な区間は $[Left,right)$ の半閉区間であることに注意する。

コードはこちら

最終提出が2019-05-05 (コンテストの翌朝)とあり、当時は競技プログラミングをするとは思わず、ちょっとやってみて手に負えなかったらしい。木の直径という言葉を知らなかったし、 $O(NlogN)$ ダイクストラ法も木の直径を求めるライブラリも作っていなかったので、手に負えなくて当然だと思う。

今解いたら15分程度で解けてしまった。

頂点をつまんでコインを吸い上げることを考える。木の直径を $D$ としたとき、この吸い上げで、コインのある頂点だけからなる木の直径を、1または2減らすことができる。こう考えればよくある石取りゲームであり、 $D+1$ を3で割った余りが2なら後手必勝、そうでなければ先手必勝である。なぜなら石もとい直径の遷移は、先手番を有利にするなら以下の通りだからである。

• 1は0にしかできず先手必勝である
• 2は1にしかできず後手必勝である
• 3は1または2にできて、2にすれば先手必勝である
• 4は2または3にできて、2にすれば先手必勝である
• 5は3または4にできるが、どちらを選んでも後手必勝である
• 上記を拡張し、一般的に $3i+0,1$ は先手必勝、 $3i+2$ は後手必勝である

コードはこちら

どこで追い越すか

最初に $A \leq B$ として一般性を失わない( $A > B$ なら $A$ と $B$ , $C$ と $D$ を入れ替える)。 $C=D$ なら明らかに操作は達成不可能である。と思ったら元々 $A < B$ だった。

$A < B$ かつ $D < C$ なら、すぬけ君はどこかでふぬけ君を追い越さなければならない。そうでなければ、先にふぬけ君が $D$ に移動した後にすぬけ君が移動すればよい。

追い越し可能かどうかは、以下の三パターンを調べる。1,2,3をすべて満たすなら追い越し可能ではなく、操作は達成不可能である。

1. Bで追い越す。つまり $B+1$ は岩ではなく、 $B > 1$ なら $B-1$ は岩ではない
2. Dで追い越す。つまり $D-1$ は岩ではない、 $D < N$ なら $N+1$ は岩ではない(これがなくても AC できてしまった)
3. 途中で追い越せない。つまり $[B,D]$ に何も置かれていないマス目が三連続している箇所がない

追い越し可能または追い越す必要がなければ、すぬけ君とふぬけ君が移動可能か調べればよい。これは動的計画法で1,2歩先に進めるかどうか調べ、進んだ先でも同様に調べるのを $C,D$ に到達するか移動不能になるまで繰り返す。

公式解説をみると、もっと条件が簡単だった。実装すると このように になる。

1. $[A,C]$, $[B,D]$ に岩が二連続していない
2. $C > D$ なら途中で追い越せる場所がある。つまり $[max(0,B-1),min(N,D+1)]$ に何も置かれていないマス目が三連続している箇所がある。境界値の取り方が公式解説は巧妙である。

コードはこちら

Rubyで string#scan は思いついたが、そこから文字列置換して転倒数は思いつかなかった。

コードはこちら

ACできてしまった

問題を読み違えたのとSTLの使い方を間違ったので75分掛かった。

最初に簡単な例に対処する。 $a$ がすべて0なら明らかに置けるので Yes 、 $a$ が0ではなくすべて同じ数なら0が必要なので No である。

$a_{1..N}$ の集合を $S$ とし、 $S$ の 最大最小値など何でもいいから $a$ から二数を選んで $A_{init},B_{init}$ とおく。 $A_{init} = B_{init}$ でも構わない。 $A = A_{init}$ , $B = B_{init}$ とおいて、 $S$ から $A,B$ を除く。この処理が間違っていて、本当は $A \oplus B = C$ を満たす $C$ が存在する $A,B$ を選ばなければならなかったので、公式解説の前提が無いとTLEする。

$A \oplus C = B \Leftrightarrow A \oplus B = C$ から、 $S$ に $C$ があるかどうか調べる。なければ題意を満たすことはできないので No である。あれば $B$ を $A$ に読み替え、 $C$ を $B$ に読み替え、 $S$ から $C$ を除いて $S$ が空になるまで繰り返す。

最後にラクダは循環しているので、 $A \oplus B = A_{init}$ かつ $B \oplus A_{init} = B_{init}$ なら Yes 、そうでなければ No である。

公式解説は、 $a$ のビットが独立でないということを上手く利用している。以下のパターンが循環すると考える。当初ビットが循環することを考えて解法を組み立てていたが、 $a$ のビットが独立でないので三通りしかないことに落としこめなかった。

• $0$ が循環する
• $A,A,0$ が循環する
• $A \oplus B \oplus C = 0$ なる $A,B,C$ が循環する

実装する と結構長い。

コードはこちら

頂点の一つは原点に固定する。

他の二点を選び、外積 $X_2 Y_3 - X_3 Y_2 = S$ とすればよい。だが $S$ が素数だと素因数分解が厳しそうである。そこで $X_2 = 10^9..1$ と決め打ちする。 $Y_3 = \lceil S / X_2 \rceil$ に固定し、 $X_3 Y_2 = X_2 Y_3 - S = R \geq 0$ となるような $X_3$ を決め打ちする。

$R = 0$ なら $X_3 = 0, Y_2 = 0$ が答えの一つである。そうでなければ $1 \leq X_3 \leq R$ の範囲で $Y_2 = \lceil R / X_3 \rceil \land Y_2 \leq 10^9$ なる整数 $Y_2$ があるかどうか探索してそうであればそれが答えの一つである。

公式解説を見たら、 $Y_2 = 1$ のときに必ず題意を満たす答えが見つかることが示されている。

公式解説はループ検出ではなくダブリングだが、他の方の解説をみるとやはりループである。どこを間違えたのだろう。

コードはこちら

長考

解くのに24分掛かった。文字列の長さが違えば文字列は異なるので、文字列長は基本的に1にして、1でだめなら2にして、2の後は必ず1にすればいい。このgreedyで解ける。

• 1文字の文字列の後に1文字の文字列を置けないのは、前が1文字の文字列で、同じ文字が続いたときだけである。
• そうでなければ1文字1文字列に分割する
• 前が1文字の文字列で、同じ文字が続いたら2文字からなる文字列を作る。つまり aaa を a,aa にする。
• 2文字の文字列の次は、1文字からなる文字列を作る。 aaaaaa は a,aa,a,aa にする。

基本的にはこれで上手くいくのだが、 aaaaa と同じ文字が5文字続く(一般的には $3N+2$ 文字続く)まま $S$ が終わるときの扱いを考える。 a,aa,a,a を a,aaa,a と区切り直せばよく、余った一文字を2文字の文字列と合併して3文字にすると考える。要するに最後の分割文字列をなかったことにして無視すればよい。

コードはこちら

どうして解けないのかが分からない。

コードはこちら

2 WAsまで来たがそれ以上わからず、解説を読んでも2 WAsが取れず、 こちら をほぼ丸写ししたら解説ACした。Equivalentな条件がほぼあっているがどこか抜けている。

コードはこちら

丁寧に場合分け

$S$ がすべて同じ文字からなるなら、答えは $\lfloor SK/2 \rfloor$ である。乗算と除算の優先順位に気を付ける。

そうでないなら $S$ を二周した文字列 $S+S$ をランレングス圧縮して、2文字以上同じ文字が続く状況 $[L,R] = [L,L+len-1]$ を抜き出す。上記を例外として除けば $S$ には異なる文字があり、一周目の最後の文字か二周目の最初の異なる文字で止まる。

ランの長さから以下の答えを求める。 $S$ の最初と最後の文字が異なれば二周目は無いので、すべてのランを書き換えて $K \lfloor len/2 \rfloor$ である。 $S$ の最初と最後の文字が同じなら以下の和である。

• $L=0$ のランがあるなら $K \lfloor len/2 \rfloor$
• $R >= |S|$ つまり一周目と二周目をまたぐランがあるなら $(K-1) \lfloor len/2 \rfloor + K \lfloor (|S|+1-L)/2 \rfloor $
• それ以外は $K \lfloor len/2 \rfloor$

コードはこちら

二部グラフの彩色問題と同じである。つまり頂点集合 $V_i$ と $V_{i+1}$ を結ぶ二部グラフを構築する。 $k$ を最大にすればいいのだから、最初に塗る頂点を $1..N$ を決め打ちして、頂点をBFSしてできるだけ多くの色を塗る。

色を塗れないのは、既に色が塗ってあって条件を満たさない=頂点集合の番号の差が1以外のときである。このときは探索を打ち切ってよい。

公式解説は、グラフの直径を用いてきれいに導出している。よく考えたら、上記も同じことをしている。

コードはこちら

どこかで見た気がする

< $a_{i} < a_{i+1} < a{i+2} ...$ と連続するとき、 $a_{i}=0, a_{i+1}=1, a{i+2}=2$ と割り当てるのが最適である。逆に > $... > a_{i} > a_{i+1} > a{i+2}$ と連続するとき、 $a_{i}=2, a_{i+1}=1, a{i+2}=0$ と割り当てるのが最適である。

初期値は $a=0$ である。 $i=1..(N-1)$ について1つ以上連続する < があれば $a$ に $0..$ を割り当て、その後 $i=(N-1)..1$ について1つ以上連続する > があれば $a$ に $0..$ を割り当てる。ここで割り当てるとは、 $a$ の値が大きくなるなら更新しそうでないならそのままにする、という操作を行う。

コードはこちら

基本方針はすぐ立ったが、その後の9 WAsを解決するのに3日掛かった。

基本方針を示す。まず $L,R$ を座標圧縮して、座標圧縮前後の値の対応を取れるようにしておく。

座標圧縮した区間 $[L,R]$ を辞書順に昇順に並べる。ある区間に該当する人が何人いるか遅延セグメント木に載せて数える。

• 区間 $[L,R]$ の正解者が $k$ 人いることを、遅延セグメント木の apply の整数加算で増減する
• 区間 $[L,R]$ の正解者最大で $k$ 人いることを、遅延セグメント木の prod の整数maxで得る

ソート済の区間 $S_{i=1..N}$ について、クイズの集合を $A = [1,i]$ と $B = [i+1,N]$ に分割する。 $A$ のうれしさは、 $i$ となるような遅延セグメント木の要素数である。この区間は空で無ければ連続した一まとまりの区間なので、左右から二分探索することで求まる。 atcoder::lazy_segtree を使っているときは max_right, min_left で求める。 $A$ のうれしさが $i$ となる区間が $[l,r]$ ならうれしさは、 $max(0, r+1-l)$ を座標圧縮前に戻した値である。同様に $B$ のうれしさが $N-i$ となるような区間長を求める。 $A,B$ が空集合にならないように気を付ける。

$S$ を逐次更新することで、 $A,B$ の要素を逐次更新する。初期状態は $A$ は全部0, $B$ は $S$ の全区間を載せた値とする。 $i$ について $A$ の区間 $S_i$ に1を足し、 $B$ の区間 $S_i$ から1を引く。

ここまで実装すると 9 WAs する。もう一工夫要る。

答えの最小値を考える。同一区間 $[L,R]$ を取るクイズを区別せず1個だけあるとする。このように区間の多重度を考慮しない区間集合を $U$ とする。上記と同様の処理を考え、初期状態は $A$ は全部0, $B$ は $U$ の全区間を載せた値とする。

区間 $j$ があり、区間 $U_j = [L,R]$ を取る。区間 $j$ について $A$ に区間 $U_j$ を足し、 $B$ から $U_j$ を引く。この状態で $A,B$ のうれしさを求める。求めたら $A,B$ の区間を逆に足して元に戻す。このとき同一区間をまとめて差し引きしないと2 WAsするので、同一区間については一回しか操作しない。

このようにして求めたうれしさの最大値が答えである。

公式解説は、 $[L,-R]$ の昇順に並べた集合を上手く使って、集合の共通区間を上手く求めている。方針が上手いと実装も軽くなる。しかし上記の 一工夫がないと やはり9 WAsする。

コードはこちら

端に押し付ける

$A,B$ の差が偶数なら互いに1卓ずつ、2人で計2卓ずつ動けばいい。答えは $abs(A-B)/2$ である。

$A,B$ の差が奇数なら差を奇数にする必要がある。1卓とN卓からは移動しないので、このとき2人で計1卓ずつ動ける。Aが1またはN卓に移動する、Bが1またはN卓に移動する、の4通りから最短の移動を選べばよい。移動したら移動先の1卓またはN卓に一回だけ貼りついて、そこから互いの卓を詰める。よって答えは $min(A-1,N-A,B-1,N-B)+1+abs(A-B-1)/2$ である。

コードはこちら

二分探索だとは分かったが、それ以上詰め切れず諦めた。

$A_i$ が採用されるには、 $A_i$ が $P$ 番目ぎりぎりで採用され、より順位の高い問題(勝ち確定)と $P$ 番目に届かない問題(負け確定)に投票されればいい、というのは分かる。しかしそれをどう二分探索すればいいのかが分からなかった。

コードはこちら

01BFSっぽい。

白黒同じ色をたどって移動できるマスの組をめる。始点 $(Y,X) = (1..H, 1..W)$ を決め打ちして、到達可能なマスをBFSで求まる。

始点 $(Y,X) = (1..H, 1..W)$ を左から右、上から下に走査する。 $(1,1)$ から $(Y,X)$ までに色が変わる回数 $dp(Y,X)$ は、

• $(1,1)$ が白なら0回、黒なら1回
• $(1,1)-(Y,X) \setminus (Y,X)$ から $(Y,X)$ に同じ色でたどれるなら0回
• $(Y-1,X)-(Y,X)$ から1操作でマス目をよい状態にしてたどれるなら1回
• $(Y,X-1)-(Y,X)$ から1操作でマス目をよい状態にしてたどれるなら1回

の最小値である。これをDPで求める。色が変わる回数を $C = dp(H,W)$ として、白黒、黒白の反転が合計 $C$ 回 あるので、操作回数はその半分 $\lfloor C / 2 \rfloor$ が答えである。

公式解説はこれをもっと洗練させて、白から黒への変化回数( $(1,1)$ が黒なら1回追加)というDPにしている。

コードはこちら

基本方針を間違え、結局諦めた。

間違った方針から示す。1を $N$ にしようとして、2,3,5 以外の素因数を持たない数に寄せようとした。いくつか解説を読むと、 $N$ を1にする方が簡単であり、探索するパスは 2,3,5 のいずれかを素因数として持つ数である。

計算量解析が正しければ、よくあるメモ化再帰で解ける。つまり今持っている $N$ を、近くの2,3,5の倍数に寄せて、2,3,5で割るといつかは1にたどり着く。注意深く実装すれば無限再帰にはならないのだが、この実装が大変である。答えが1ずれたり、無限再帰になったりする。

コードはこちら

正N角形。

$X \leq 90$ なら軌道が正N角形になる。辺同士の内角は $180-X$ 度であり、これが0になるのは少なくとも $N=360/GCD(360,X)$ 回進んだ時、つまり正N角形が一周した時である。

$X > 90$ でも辺同士が交わるだけで考え方は同様で、向きが元に戻るのは少なくとも $N=360/GCD(360,X)$ 回進んだ時であることに変わりはない。辺に対応するベクトルの和が0になると言い換えてもいい。

コードはこちら

$DP[C][D][2]$ なのは分かったが、 $[2]$ で管理するのは右上が黒いかどうかではなく、一番上の行に黒いマスが1つだけか否かだった。これが分からなくて諦めた。

コードはこちら

合同かと思ったら違った、

小数を整数部 $B_i$, 整数部以外 $B_f$ を書いて、 $(B_i + B_f)(B^{'}_i + B^{'}_f)$ をいい感じにするのかと思ったのだが全く見当外れだった。

入力を $10^9$ して整数とみなす。このように加工した $A_i \times A_j$ の下9桁が0なら、元の入力の $A_i \times A_j$ は整数である。これは加工した $A_i \times A_j$ について、2の素因数が9個以上かつ、5の素因数が9個以上と同じことである。

よって加工した $A$ について、 $A_i$ の2の素因数が $T_i$ 個、 5の素因数が $F_i$ 個であると数える。テーブル $M[j][k]$ は、2の素因数が $j$ 個、 5の素因数が $k$ 個 となる $A$ の要素が $M[j][k]$ 個であることを保持する。このテーブルに二次元累積和を取る。

$i = 1..N$ について、 $A_i$ 自身を除いて、2の素因数が $A_{9 - T_i}$ 個以上かつ、5の素因数が $A_{9 - F_i}$ 個以上になるような $A$ の要素数を数える。これは先の二次元累積和から分かる(累積和でなくその場で数えてもTLEしない)。この和が答えである。

コードはこちら

41分は時間掛け過ぎである。

atcoder $< S$ なら答えは0である。 $S$ が a を含むなら先頭に持ってくれば操作回数はどうあれ atcoder $< S$ にでき、 $S$ が a しか含まないならどうやっても atcoder $< S$ にできないので答えは-1である。

先頭から $i=0..(min(6, |S|)-1)$ 文字が $atcoder$ の先頭 $i$ 文字と一致したら、 $atcoder$ の $i$ 文字目より大きな $S$ にある最左( $j$ 文字目)の文字があれば取り換える。この操作回数は $j-i$ 回である。すべての $i$ における最小の $j-i$ の最小値が答えである。

公式解説は1,2文字目しかみていない。

コードはこちら

公式解説を読んでも理解できない。

なのでこちらの 記事 を読んで理解した。私が想定した 0 を寄せるのではなく 1 を寄せるのが正解で、余った 1 を対消滅させる方法が上手く思いつかなかった。

コードはこちら

解説を見るまで全く分からなかった。

コードはこちら

数時間掛かった。

左上ほど値が増える直交座標で考える。単位長 $N$ について、左上方向に連続する整数座標を $N$ 個並べる斜線を作る。つまり始点 $(SX,SY)$ として、 $(SX,SY),(SX+1,SY+1),...,(SX+N-1,SY+N-1)$ である。この斜線は、視点A,Cから $N$ 個見え、視点Bからは1個見え、視点Dからは $N$ 個見える。

この斜線を二次元グリッド $N \times N$ 個並べることを考える。視点Bからは高々 $N^2$ 個見える。視点A,Cについて視界が重なるように並べ $N^2$ 個見えるようにし、視点Dは視界が重ならないよう $N^3$ 個見えるように並べれば題意を満たす。

視点A,Cは始点座標が同じ斜線を複数グリッド上に並べればよい。このとき視点Dがかぶらないよう、X座標の間隔を2のべき乗にする。パターン番号を横 $i = 1..N$ 、縦 $j = 1..N$ として、始点座標を $(SX + N 2^i, SY+Nj)$ とする。このとき座標が制約を満たすように、 $mod 10^9$ する。 $mod$ が重なる可能性があるが、実際には重ならないので問題ない。

$A,B,C,D$ から見えるピンの数を $|A|,|B|,|C|,|D|$ とし、比率 $R=|D|/max(|A|,|B|,|C|)$ を確認する。一般的に $N$ が大きいほど $R$ が大きいが単調増加とは限らず、 $N = 20$ では $R$ が小さくなる。 $N$ に素数を選ぶとよさそうである。

公式解説はもっと簡潔に上記を述べている。

コードはこちら

実装を間違えたらACできてしまった。

答えは 0 , $N$ 個の 1 , $N$ 個の 0 を並べたものである。

• $S+S$ の $1..N$ 文字目に 0 がなければ、 $S+S=1..1,0..0,1..1,0..0$ と 1,0 を $N$ 個連続で並べたものなので題意を満たす
• $S$ の $1 \leq i \leq 2N$ 文字目が 0 で、それより前つまり $j < i$ 文字目は 1 とする。このとき $[i+1,2N+i-1]$ 文字目には 1 を $N$ 個含み、 $[2N+i,4N]$ 文字目には 0 を $N$ 個含む。

コードはこちら

実は $S$ を見る必要がない。

$|A_i - A_{i+1}|$ の最小値が、 $A$ を分解して作れる $B$ の数 $k$ の最大値である。0-based indexingで $B_i$ の要素 $j$ を $B_{i,j}$ と書く。

$B_1, ... ,B_k$ について辞書順である、つまり $\forall j B_{i,j} < B_{i+1,j}$ と定める。この数列は題意を満たす。なぜなら $B_i < B_{i+1}$ の各要素に1ずつ合計 $k$ 増やして $B_{i+1}$ を作れば、 $B_{i,j} < B_{i+1,j}$ になるからである。もっとたくさん増やすのは構わない。不等号が逆の場合も同様である。

具体的には、 $B_{i,j} = \lfloor A_i / k \rfloor + ind(j < (j MOD k))$ とすればこのような数列を作れる。ここで $ind(p)$ は述語 $p$ が真なら1、そうでなければ0を返す。これを答えとして出力すればよい。

正の数ではなく非負整数というのを扱い損ねてペナルティを出してしまった。

コードはこちら

最初が肝心

$S$ の先頭の文字をいつかは削除する必要があるので、削除できるかどうか考える。

• $S$ が末尾の文字が、 $S$ の先頭の文字 $k$ と異なるなら、 $S$ を1回で丸ごと削除できる。
• $S$ を末尾から見ていく。 $k$ と異なる箇所が連続している、つまり $k,...,(c,d),...,k$ なら、先頭から $c$ までと、 $d$ から末尾までを削除する。計2回である。 $c$ と $d$ は同じ文字でも構わない。
• 上記を満たさない、つまり $k$ と異なる文字が連続しなければ、削除できない $k$ が残る。

コードはこちら

基本方針は立ったがそこから先に進まなかった。

$W$ の和 $S$ が奇数なら答えは0である。以下 $S$ は偶数とする。

緩和問題として、取る順序を問わずに一人が取ったみかんの重さの和が $S$ のとき、そうなる組み合わせの総数を求める。これはあるみかんを取るか取らないかという動的計画法で求まる。具体的には、みかん $1..N$ 、これまで取ったみかんの重量 $0..S$ について、取ったみかんの組み合わせ数 $0..N$ を数える。組み合わせは膨大になるのでintではなくmodintにする(そうしないとWAする)。

ここからは公式解説を読まないとわからなかった。高橋くんが取ったみかんの集合が $P$ 、青木くんが取ったの集合 $Q = 1..N \setminus P$ があるとき、 $P$ の順列と $Q$ の順列を固定すれば、解を満たす。最終的に両方が取ったみかんの重さが等しいことは分かるが、そのような取り方が常に可能なことがわからなかった、というよりこのことが公式解説では省略されている。こちらに 解説 がある。

ともかく上記を正しいとみなすなら、緩和問題を拡張する。 $i = 0..N$ について、 $|P| = i$ を満たす組み合わせが $C_i$ 通りあるなら、 $C_i \times i! (n-i)!$ の合計を求める。

$P,Q$ からあり得る順列の組み合わせを求める方法がどうしても分からなかった。

コードはこちら

ABC, ACB, BAC, BCA, CAB, CBA を全部試せばよいのは分かるが、どう試すのかが分からなかった。前から取るとか後ろから取るとか色々試したが解けなかった。

公式解説はホールの定理に基づいて3分割する、とある。意外と実装が大変である。

コードはこちら

手を動かすと解ける。

$N$ が3の倍数のときは、下記の通り3個並べて一段下げるを繰り返す。

###......
...###...
......###
###......
...###...
......###
###......
...###...
......###

$N-1$ が3の倍数のときは、 # の場所として上記から ? を除いて * を増やす。確かに連結成分は $N$ 個である。

###.......
...###....
......?##*
###.......
...###....
......##?*
###.......
...###....
......#?#*
......***.

$N-2$ が3の倍数のときは、 # の場所として上記から ? を除いて * を増やす。確かに連結成分は $N$ 個である。

###........
...###.....
.......?##*
###........
...###.....
......##.?*
###........
...###.....
......?.##*
......###..
......**.*.

公式解説1が簡潔で、公式解説2は大きさ1の成分を基に上記とは異なる微調整をしている。

コードはこちら

いかにもマルチテストケースらしく、入力例以外が全滅したかと思ったら再々提出がACした。

数 $x$ の桁数を $W$ とする。

$W(L) = W(R)$ なら、 $a,b$ をどう選んでも同じ桁数の異なる文字列表記なので、答えは $R - L + 1$ である。

一般的に、桁数の少ない数を残すと損する。なぜなら桁数が一つ多ければ数字の候補は10倍になる、つまり $x$ に対して、 $10x + 0..9$ があるのだから、 $x$ を残すとそれ以上多い種類の数を集合 $A$ に残せなくなる。

このことから、 $W(L) + 1 < W(R)$ なら $W(L) + 1 = W(R)$ となるよう $L$ を読み替えて構わない。つまり $L = max(L, 10^{W(R)-2})$ と読み替える。

$R$ の最上位桁が1よりも大きい時、 $R$ の最上位桁以外は $[0..10^{W(R)-1})$ を網羅する。そのため $W(R)-1$ 桁の数を残すと損する。よって答えは $R - 10^{W(R)-1} + 1$ である。

$R$ の最上位桁が1ときは、 $R$ の最上位桁以外の数を $SL = R - 10^{W(R)}$ 、 $R$ の最下位桁以外の数を $SR = \lfloor R / 10 \rfloor$ と置く。 $W(R)-1$ 桁の数 $[L,10^{W(R)-1})$ の内、 $[0,SL]$ にも $[0,SR]$ にも重ならない数は $A$ に含めてもよい。よって答えは $R - max(L, 10^{W(R)-2}, SR + 1, SL + 1) + 1$ である。

コードはこちら

解答長が $N$ 以下なので、決め打ちできるのだろう。

自明な到達点として、 $1, 2N, 2, 2N-1, ... , N, N+1$ がある。こうなるようにバブルソートすると $O(N^2)$ 掛かるので答えにはならない( $1..2N$ を入力されたとき)。そこでこれに近いジグザグを作ること考える。

奇数番目が山になる、つまり $A_{2i-1} < A_{2i} > A_{2i+1}$ になるように局所的にソートする。便宜上 $A_{2N+1} = -1$ とする。

• 元々 $A_{2i-1} < A_{2i} > A_{2i+1}$ なら何もしない
• $A_{2i-1} < A_{2i} < A_{2i+1}$ なら $A_{2i} > A_{2i+1}$ になるように交換する
• $A_{2i-1} > A_{2i} > A_{2i+1}$ なら $A_{2i-1} < A_{2i}$ になるように交換する
• それ以外つまり $A_{2i-1} > A_{2i} < A_{2i+1}$ ときは、 $max(A_{2i-1}, A_{2i+1})$ と $A_{2i}$ を交換する。こうすることで $i$ が小さいほど振れ幅を大きくする

公式解説1としていることは同じだが、公式解説は証明を与えている。

コードはこちら

文字の置き方をDPするのだと予想はしたが、その先が全く分からなかった。公式解説にある通り、ある連続部分文字列である文字が過半数なら、半分に切ってもどちらかでは過半数を占めている。これが分からなかった。

DPの初期化が大変である。

コードはこちら

実験すると分かる。 $n=N, k=K$ のときの答えを $f(n,k)$ おく。

最初に、 $N,K$ で場合分けする。 $N = 2$ なら答えは $3 - K$ である。 $N$ が奇数なら $N-1$ に対する答えに $shuffle(1,N-1)$ , $shuffle(2,N)$ したものが答えである。先に $N$ の奇数の場合を求めて、そのあとに $N$ が偶数の場合を求める。

$N$ を奇数とする。 $K = 1$ なら答えは2である。そうでなければ、 $p = f(N-1, K-1)$ と求める。 $p$ は $shuffle(2,N)$ の $K$ 番目の位置に、 $shuffle(1,N-1)$ の何番目の要素が来るかを示す。 $p = N - 2$ なら $N$ が来るので $f(N,K) = N$ である。 $p < N - 2$ なら $shuffle(1,N-1)$ で $p$ 番目に来る要素が答え $f(N,K) = f(N-1, p+1)$ である。 $N-1$ は偶数なので下記から求める。

$N$ を偶数とする。先頭から2個ずつ要素を区切り、 $i = 1..(N/2)$ として、隣り合う要素 $(2i-1,2i)$ について考える。実験すると分かるが、 $shuffle(1,N)$ において、 $(2i-1,2i)$ はそのままか、入れ替えたもの $(2i,2i-1)$ になるかどちらかで、要素はそれ以外の場所に移動しない。この仮定が正しいとして、入れ替え回数の偶奇は二項係数 $N/2 \choose i$ の偶奇と同じである。

二項係数 $a \choose b$ の偶奇は $a \verb|&| b = b$ なら奇数、そうでなければ偶数である。証明は省略するが、ネットで探すとみつかる。よって答えは以下の通りである。

• $N/2 \verb|&| i = i$ なら、 $f(N,2i) = 2i-1$ 、 $f(N,2i-1) = 2i$
• $N/2 \verb|&| i \ne i$ なら、 $f(N,2i) = 2i$ 、 $f(N,2i-1) = 2i-1$

先ほどの仮定を帰納的に証明する。理詰めで考察すると入れ子構造のあみだくじと分かり、実験すると $(2i-1,2i)$ 番目の要素しか入れ替わらないと分かるので、両方突き合わせるとパスカルの三角形になる。

• $N = 2$ なら問題文通り手を動かして $(2,1)$ を得る
• $N = 4$ なら問題文通り手を動かして $(2,1,4,3)$ を得る。このとき値ではなく添え字の組で、 $(1,2)$ を1回、 $(2,3)$ を2回、 $(3,4)$ を1回入れ替える。
• $N = 6$ なら $(1,2)$ を1回、 $(3,4)$ を2回、 $(5,6)$ を1回入れ替える。なんとなく二項係数の予感がする。
• $N$ が偶数の時、 $i=1..(N/2)$ について $(2i,2i-1)$ を入れ替え、 $i=2..(1+N/2)$ について $(2i,2i-1)$ を入れ替える回数は、二項係数のそのものである。偶数回入れ替えるのは入れ替えないのと同じ(0回入れ替えるのと同じ)なので、二項係数の偶奇だけ求めればいい。

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

当初の着眼点が悪く時間が掛かってしまった。 $N$ が偶数なら左半分と右半分に対称性がある(端からの距離が等しい添え字の値を足すと $N+1$ になる)とか、 $N = 2^i$ なら左半分は $2^{i-1}$ と同じだとか、確かにそうなのだが解法にはつながらない。実験コードを素早く書けることは重要である。

void visit_dfs(Num l, Num r, Vec& v) {
    if ((l + 1) == r) {
        std::swap(v.at(l), v.at(r));
        return;
    }

    visit_dfs(l, r-1, v);
    visit_dfs(l+1, r, v);
    return;
}

void solve(std::istream& is, std::ostream& os) {
    Num n {0};
    is >> n;

    Vec ns(n);
    std::iota(ns.begin(), ns.end(), 1LL);
    visit_dfs(0, n-1, ns);
    print_oneline(ns, os);

    Vec inv(n);
    for(Num i{0}; i<n; ++i) {
        inv.at(ns.at(i)-1) = i+1;
    }
    print_oneline(inv, os);
}

コードはこちら

解説を読むまで全く分からなかった。

コードはこちら

初手を考える。Aliceとしては、 $S$ の最初の A の前に B がなければ、 $N$ より大きな $x$ を選べば $mex(X) = mex(0) = A$ でAliceが勝つ。 $S$ の最初の A の前に 'B' が一文字だけあれば、 $x = 0$ を選び、 $mex(X) = mex(1) = A$ でAliceが勝つ。それ以外はどうやっても $mex(X) = mex(0) = B$ でありAliceは勝てない。

これを拡張し、 $i$ 番目のAliceの手番が来る直前に、Alice, Bob 共に $H = \lfloor (i-1) / 2 \rfloor$ 手を打ったとする。後で分かるように、Bobは最大 $H$ 個の A を取り除いているので、この時点で A が残っていなければAliceは勝てない。言い換えれば、 $S$ に少なくとも $H + 1$ 個の A を含んでいる必要がある。この状況で、先頭から $H + 1$ 番目の A までに B が $H + 1$ 個以内ならそれの位置を $x$ に指定してAliceが勝て、そうでなければ勝てない。

Bobはこれと対照である。 $i$ 番目のBobの手番が来る直前に、Aliceは $H = \lceil i / 2 \rceil$ 手を、Bobは $H-1$ 手を打ったとする。Aliceは最大 $H$ 個の B を取り除いているので、この時点で B が残っていなければBobは勝てない。言い換えれば、 $S$ に少なくとも $H + 1$ 個の B を含んでいる必要がある。この状況で、先頭から $H + 1$ 番目の B までに A が $H$ 個以内ならそれの位置を $x$ に指定してBobが勝て、そうでなければ勝てない。

$i$ の偶奇に注意し上記を使い分けて出力する。AliceとBobで境界が1個ずれているので注意する(これを間違えるとWAする)。

公式解説はこれを起点にもっと証明を簡潔にしている。

コードはこちら

丸一日以上考えたが、わからなかった。

始めはスタックだろうと思い、次は木構造だと思ったが、結局正解はスタックだった。スタックに積みながら、左から右に連続する要素につなげていくDPなので、実は両方だったといえる。公式解説のもう一つの解法が こちら 。どちらのコードも、公式解説をほぼ丸写しである。

なお入力 $A$ 全体が生成可能である必要はなく、一部が生成可能なら答えは0より大きい。

コードはこちら

左右対称にしようとして解けなかった。公式解説にある通り、左側は1ずつ増やせばよい。

コードはこちら

最初の方針は26分で立ったが、結局数時間掛かった。

前処理として $A$ は $modK$ を取った値とする。

緩和問題として、 $AmodK$ のすべての要素はそれぞれ異なるとする。 $A$ を昇順に並べる。 $A_i < A_{i+1}$ なので、これらの距離は $K - (A_{i+1} - A_i)$ になる。 $(A_N, A_1)$ 間の距離も考慮して、差が最も広いところを除いて他の組み合わせ $(A_i, A_{i+1})$ を採用すればいい。

$A$ に重複があるとする。ある数 $v$ が $A$ に含まれる回数(多重度)を $C[v]$ として、 $C[]$ の最大値を $M$ とする。 $C[v] = M$ となる $v$ の集合を $S$ とする。このような $S$ について昇順に並べて、上記と同様に $(S_i, S_{i+1})$ の差が最も広いところを除いて他の組み合わせを採用すればいい($S$ の各要素はそれぞれ異なるので)。このような $i$ を求め、 $p = S_{i+1}$ とする。

$A$ に重複がある多重集合として、上記の $p$ を初期値として、以下の操作を $N-1$ 回繰り返す。 $modK$ 周回を考慮して、 $A$ に含まれる $p$ より大きい数のうち最小の数を $q$ とすると、 $d = K - (q - p) mod K$ が問題文の $\sum$ の成分である。次に $A$ から $p$ を一つ除き、 $p$ を $q$ で置き換える。このようにして作った $p$ の逆順が問題文の数列であるが、答えは和だけ求めればいいので、 $d$ の和を出力する。

公式解説と結論は同じである。公式解説は証明しているが、上記は証明を端折っている。

コードはこちら

正確な時間をはかりそこねたが、自力ACまで3時間を切ったと思う。ヒントは解くまで見ていない。

$A$ が同じ値 $a$ を共有する集合 $a= A_{a1}, A_{a2} ...$ について、 $a$ をキーとして添え字の昇順の集合 $P_a = [a1, a2, ...]$ と、 $P_a$ を一回左シフトした集合 $Q_a = [a2, ..., a1]$ を求める(集合の要素が1個以下なら $P_a$ と同じにする)。

初期値として $S$ は $N$ 個の 0 、 $T$ は $N$ 個の 1 を考える。最初に $S,T$ に $N$ 個の要素 $S_1, T_1$ を追加し、 $A_1$ に値を持ってくる。 $a = A_1$ として $P_{a,j} = A_1$ を満たすある $j$ があって、位置 $Q_{a,j}$ から持ってくればよい。これは $S_1$ の $Q_{a,1}$ と等しい要素を 1 に、それ以外を 0 にすると実現できる。 $T_1$ はすべて 0 にする。以後、 $[1..N] \setminus Q_{a,1}$ について同じ操作を行う。このようにすれば、 $P_{a,j}$ をサイクルにすることができる。

上記を一般化して、 $i = 1..N$ 回目の操作を規定する。初期値として、追加する添え字の集合を $R = [1..N]$ で初期化する。

$S$ に $N+1-i$ 個の要素 $S_i$ を追加し、 $T$ に $N+1-i$ 個の 0 を追加して、 $A_i$ に値を持ってくる。 $a = A_i$ として $P_{a,j} = A_i$ を満たすある $j$ があって、位置 $Q_{a,j}$ から持ってくればよい。これは $R$ の $Q_{a,1}$ と等しい要素を 1 に、それ以外を 0 にすると実現できる。より正確には、 $R$ を昇順に並べた要素について、 $j$ 番目の要素が $Q_{a,1}$ なら $S_i$ の $j$ 番目を 1 にし、それ以外の $S_i$ の要素を 0 にする。この後、 $R$ から $Q_{a,1}$ を取り除く。

$|S| = N + \sum_{i=1}^{N} i = N + (N+1)N/2$ なので、 $S$ の長さは制約を満たす。

公式解説と全く同じ解き方だと思う。