現形式(120分 5,6問)のARCを解いてみます。

コードはこちら

ビット総当たり

おそらくARC 103まではABCと同時開催で問題が同じ、ARC 104以降はARCとABCが別開催で問題が異なるようである。なのでおそらくこのA問題はやさしめに問題を設定したのだろう。

求める答えは $(A+B)/2$, $(A-B)/2$ である。

コードはこちら

括弧が一致

よくある問題に、左右の () が一致するというのがある。ここでは部分文字列の A-T, C-G が一致すればよい。

• 先頭から順に、 先頭から $i$ 文字目までのAの出現回数-Tの出現回数を数える。同様にCの出現回数-Gの出現回数を数える。便宜上、空文字列 $i=0$ については0回とする。
• 先頭から順に、 $0..i$ 文字目について、Aの出現回数-Tの出現回数=ATと、Cの出現回数-Gの出現回数=CGについて識別子を作る。 $AT + 10000CG$ とすればよい。
• それれぞれの識別子について、 $n$ 回出現するならその中の2通り $L,R$ を取ると、部分文字列 $(L,R]$ ではAの出現回数=Tの出現回数かつCの出現回数=Gの出現回数である。このような組み合わせは $n(n-1)/2$ 通りである。

これをすべての識別子について足すと答えが求まる。この解き方は計算量が $O(Nlog(N))$ なので公式解説のbonusだった。

コードはこちら

ビット総当たり

クッキーの選び方は $2^4$ 通りしかないので、ビット全探索すると答えが求まる。公式解説はソートして取りうる組み合わせをハードコーディングしている。

コードはこちら

問題文通りシミュレーションする。a_i の集合と、値が a_i になる要素数を別に管理すると、C++なら 1221 ms で間に合う。想定解法はとてもエレガントである。

コードはこちら

問題名がそのまま答えだった。

$N = 1$ なら後手必勝 Second である。以下 $N > 1$ とする。すべての袋からコインを取り出した直後の、皿 $i$ にあるコインを $B_i : i=1..N$ とする。

まず $N$ が偶数とする。Nimの必勝法、すべての皿のコイン $B_i$ のXORが0のときを勝ちということを思い出す。これを満たすには後手の最善手は、できるだけ $B_i$ の値がペアになるようにすることである。鏡打ちとも言う。これは $a_i$ の値がペアである、つまりある $a = a_i$ について、そのようなコインの枚数となる袋が常に偶数個(0袋を含む)ことと等価である。これがすべての $a_i$ について成り立てばいい。

$N$ が奇数なら先手後手が入れ替わるので、勝敗が逆になる。以上をまとめると以下になる。

• ($\forall a \in a_{i=1..N}$ について、コインの枚数が $a$ となるような袋が偶数個) XOR ($N$ が偶数なら) Second
• そうでなければ First

コードはこちら

総当たり

$log(1e+18) / log(3) = 37.7$, $log(1e+18) / log(5) = 25.7$ なので、 $(A,B)$ を二重ループしても計算量は少ない。 $B$ を決め打ちして、 $N-5^B$ を3で割れるだけ割って、割り切れたら3で割った回数が $A$ である。

コードはこちら

不変量

連結成分において、頂点の数値の和は不変である。よってグラフを連結成分分解して、すべての連結成分において $a$ の和と $b$ の和が等しければ Yes 、等しくない連結成分があれば No である。

連結成分において $a$ の和と $b$ の和が等しければ、ある頂点を決め打ちして $a_i$ を $b_i$ にし、その隣の頂点を $a_j$ を $b_j$ にし、ということを繰り返せば有限回で $a$ を $b$ にできる。非ループの頂点があればそこから値を決めて、その後ループに頂点について一つずつ決めればよい。

コードはこちら

エッジケースは大事。

$N=1, M=0$ なら区間 $[1,2]$ を出力する。これを忘れて1 WAした。

$M < 0$ は解なしである。昇順に並べた時、高橋君は選べないが青木君は選べる区間を構築することはできない。上手く証明を与えられないが、とにかく構築できない。と思っていたのだが、公式解説を読むまで、高橋君が最適解を出すことを忘れていた。

$M \geq 0$ ときに、十分大きな区間 $[L,R]$ を作り、 $[L_1,R_1], ... , [L_d,R_d]$ , $L < L_1 < R_1 ... < L_d < R_d < R$ とする。高橋君は $d$ 区間選べるが、青木君は1区間しか選べないので、差 $d-1=M$ を作れる。 $M < N-2$ なら $d+1$ 区間の重なりをこのように構築し、その後重ならない区間を並べる。 $M > N-2$ なら解なしである。

コードはこちら

再帰的

$\sum_{a=1}^{A}{aX} = XA(A+1)/2$ である。 $B,C$ についても同様なので、求める答えは $ABC(A+1)(B+1)(C+1)/8$ である。

コードはこちら

対称性

$K=0$ なら $a=1..N$, $b=N..1$ なので左辺も右辺も $N$ 通り、計 $N^2$ 通りである。

$K < 0$ なら $K$ の符号を反転させて移項すると、 $a+b$ と $c+d$ の役割を入れ替えることができる。よって $a+b = c+d+K, K > 0$ について考える。右辺の和は $2..(2N+K)$ なので、 $i=c,d$ として $a,b$ が取りうる値は $max(1,i-N)..min(N,i-N)$ 、 $c,d$ が取りうる値は $max(1,i-K-N)..min(N,i-K-N)$ である。これらの組み合わせを $i=(2+K)..(2N)$ について足すと答えになる。

コードはこちら

問題文の意味を理解するのに20分掛かった。分かってしまえばそこからは早い。

問題文の操作を言い換えると、要素数 $N$ のベクトルを入れ替え可能なのは、ベクトルの和についてすべての要素が $K$ 以下のときである。行列を入れ替えても回転というかトーラス上に回すだけなので、ベクトルの和についての条件は変わらない。

よってすべての行の組み合わせについて、入れ替え可能な組を求める。 $A$ 行と $B$ 行を入れ替え可能で、 $B$ 行と $C$ 行を入れ替え可能なら、連続する操作を用いて $A$ 行と $C$ を入れ替え可能である。直接二行を入れ替え可能なことはベクトルの要素を計算すると分かり、連続する操作で入れ替え可能であることはunion-find木を構成すると分かる。

Union-find木は連結成分として、入れ替え可能な行の集合 $[S_1, S_2, ..., S_m]$ を表現している。行の入れ替え方法は $|S_1|! \times |S_2|! \times ... \times |S_m|!$ 通りである。列についても行と独立に操作できるので、同様に求める。行の入れ替え方法と列の入れ替え方法の積が答えである。

コードはこちら

総当たり

$P \leq 10^{12}$ なので $P$ の約数を列挙して $S$ を総当たりすればよい。

公式解説を読むと、 $i=1.. \sqrt{P}$ と $S-i$ を決め打ちして総当たりしている。この方が実装は簡潔である。コードは こちら

コードはこちら

スタック

fox を取り除くと前後の文字がくっついて fox になりうる、というのはまさにスタックがうってつけである。 $s$ を一文字ずつスタックに積んでいき、末尾が fox なら可能な限り取り除く、というのを繰り返す。データ構造に std::stack を使う必要はなく、普通に std::string::pop_back() を使えばいい。

コードはこちら

問題の意図を完全に取り違えて解けなかった。

1辺2頂点から成るグラフを考える。一方を辺のラベルで塗り、他方をそれ以外の色で塗る。ここでそれ以外なら何でもいい、ということを理解できず、解なしの状況を作り出してしまった。DFSまでは分かったのだが余計な処理を入れてしまった。

公式解説にある通り、連結成分についてそれぞれ木構造を考えれば、上記の延長になる。根に塗る色を決め打ちして、後はDFSで彩色すれば、辺以外の色は多数あるので詰むことは無い。

連続する A 、 A から B 、連続する B 、 B から A の個数でDPしたら半分WAした。諦めた公式解説をみたら、まるっきり異なる解法だった。

コードはこちら

回り道

$2x < y$ なら、同じビルの1階分を移動するのに階段を使うより廊下を一往復する方が短時間である。同じビルの1階分移動するのに掛かる時間は $step = min(2x,y)$ である。廊下を最低1度は使うのと、廊下で上の階には行けないので、総移動時間は以下の通り。

• $a \leq b$ なら $x + step(b-a)$
• $a > b$ なら $x + step(a-b-1)$

コードはこちら

入力例から逆算

入力例2から、 $N-\sqrt{2N}$ あたりが答えだと察しが付く。ので後付けで説明を考えると、丸太 $N+1$ で $1..i$ までを賄うことができるかどうか考える。 $\sum_1^i=(i+1)i/2 \leq N+1$ を満たす最大の $i$ は、 $\sqrt{2(N+1)}$ 付近を探せば見つかる。

つまり $1..i$ までは丸太 $N+1$ 1本で賄える。残りは賄えない。なぜなら残りの丸太 $j,k > N - \sqrt{2(N+1)}$ について、 $j,k$ を $j+k \leq n$ 一本で賄うとして、

• $j+k > N$ であればそのような丸太は買えない。 $N+1$ の丸太はもう買ってしまった。
• $j+k \leq N$ なら結局は $j+k$ の丸太を用意しなければならない。 $j+k$ の丸太を買ってそのまま使うなら分割できず、そうなければ $j+k,l$ に分割できる他の丸太 $j+k+l$ を用意しなければならない。この堂々巡りが続く。

結局分割可能な丸太は $N+1$ 一本しかなく、それを長さ1からできるだけ細かく分割した時が答えである。

コードはこちら

メモ化再帰

トーナメントの部分木について、 幅は $K$ 通り、文字列はの始点は $N$ 通りなので、 $KN$ 通りについて考えればよい。よって $KN$ 通りについてメモ化再帰すれば解ける。

トーナメントを決勝からトップダウンに考える。0-based indexingで、決勝を0とした深さ $d$ の部分木について左端が $i$ としたとき、この部分木の直接の部分木は幅 $W = 2^{k - d - 1}$ なので、左の部分木が $[i, W)$ 、右の部分木が $[i + W, i + 2W)$ である。このとき $W ,i$ は $modN$ で計算する。このような部分木の勝者はメモ化できる。

コードはこちら

Nは定数

$N = 30$ のときだけ求めればよい。30以下の数の素因数すべてで割り切れる数 +1 が答えなので、30以下の素数について $2^4 \times 3^3 \times 5^2 \times 7 \times ... \times 29 + 1 = 2329089562801$ である。途中結果を64ビット整数で求める必要がある。

公式解説は最小公倍数を実行時に求めている。実装したコードは こちら

コードはこちら

場合分け

丁寧に場合分けをすれば解ける。

まず $T$ が一文字か二文字の場合を網羅する。その後 $T$ が三文字以上の場合を考える。

Sの先頭、先頭の次、先頭の次の次、つまり 110110... , 10110... , 0110... のどれに $T$ が一致するか総当たりする。どれにも一致しなければ答えは0である。一致するならオフセットつまり $S$ の $i \geq 1$ 文字目から始まると分かる。

Sを先頭からのオフセットを考慮し、 $T$ が $L=i-1+N$ 文字目で終わると考える。 $S$ における $T$ の開始位置は後ろの余白がどれだけあるかなので、 $L$ が3で割り切れるなら $10^{10}-L/3+1$ 通り、そうでなければ $10^{10}-L/3$ 通りある。

コードはこちら

貪欲法で解ける。以下0-based indexingで考える。

$0$ が位置 $i$ にある、つまり $Pi = 0$ なら、バブルソートで実際に $P_i$ から $P_0$ に移動する。このとき $(P_{i-1},P_i) .. (P_0,P_1)$ を入れ替えるのでこの順に操作を記録する。これらの手を後で使うことはできない。

$0$ を固定したので、 $left = 1..(N-2)$ , $right \quad s.t. \quad P_{right} = left$ について同様にバブルソートを実行し、操作不能なら -1 を返す。そうでなければ、操作順を記録する。操作可能かどうかは、 $(P_i,P_{i+1})$ が1なら未操作、0なら操作済というセグメント木を作って管理する。 $sum([left, right)) = right - left$ なら操作可能、そうでなければ操作不能である。

公式解説を読んだら、 $[P_{left}, P_{right})$ を区間ごとに確定することで $O(N)$ で解いている。

コードはこちら

求める答えを $r$ とする。 $10^N = Ma + b : 0 \leq b < M$, $a = Mb + r, 0 \leq b < M$ から、 $10^N = M^2 ab + Mr + b$ を得る。よって $r = \lfloor (10^N mod M^2) / M \rfloor$ が答えである。

$10^N mod M^2$ はABC 167-Dと同様に周期的に求めることができる。つまり1を出発点に、 $10 mod M^2, 10^2 mod M^2, ...$ を順に求めてパス $P$ を作り、サイクルとサイクルに入るまでを分ける。サイクルに入るまで(サイクルを含まない) $L$ ホップ、サイクルの周期を $C$ とすれば、 $10^N mod M^2$ は以下の通り求まる。添え字は1-based indexingとする。

• $N \leq L$ なら $P[N]$
• $N > L$ なら $P[L + (N - L) mod C]$

公式解説にあるように、 $mod M^2$ だけあれば、サイクル検出は要らない。数十行が不要だった。

コードはこちら

ある色が一つのカードにしかなければ優先的に使う。この貪欲法で解けるは思わなかった。

$C[color]$ を色 $color$ が塗ってあるカード番号の集合、 $D[card]$ をカード $card$ に塗っている色の集合で初期化する。ある色が塗っているカードが一種類、つまり $|C[color]| = 1$ となる $color$ をキューに入れる。

キューから色を取り出し、その色が塗ってあるカード $card$ を消費する。つまりカード $card$ の裏面の色 $t$ について、 $C[t]$ から $card$ を除き、 $|C[t]| = 1$ ならキューに入れる。併せて $D[card]$ を空し、答えの色の種類数を1増やす。 $carad = t$ でも重複を数えなければ特に配慮する必要はない。

これを繰り返すと残ったカードは短調減少なので、いつかキューは空になる。ここで $C[color]$ が2以上の色はカード間の依存関係が循環参照なので、何らかの方法で塗れる。よって $C[color]$ が非0の色の数を答えに足す。これが求める答えである。

公式解説は、連結成分が木かどうか判定することの意味を解いている。エレガントな解説である。期せずして上記のアルゴリズムは木かどうかの判定と同じだった。

コードはこちら

どうして正解できないのか分からない。

初期状態で解なら 0 、他人の荷物を持っていて重すぎるとき $a_i \leq a_{p_i}$ は -1 である。

それ以外は、本来の持ち主の方が体重が軽い時に、本来の持ち主に交換と交換する。 $(a_i , a_{p_i=x}), (a_j , a_{p_j=i})$ を $(a_i , a_{p_j=i}), (a_j , a_{p_i=x})$ に交換するとき、 $a_i > a_{p_i=x}, a_j > a_{p_j=i}$ なので、 $a_j \geq a_i$ なら $a_j \geq a_i > a_{p_i=x}$ である。

つまり体重が軽い順に、本来の持ち主に交換と交換する。ほとんど正解まで思いついたのにACできなかった。

コードはこちら

式変形

$A = B + C$ より $L \leq B+C \leq R$ を満たすような $A,B,C$ を求めればよい。条件より $2L \leq B+C \leq 2R$ なので、 $A$ の取る値は、

• $R < 2L$ なら該当する $A$ は無し
• そうでなければ $2L \leq A \leq R (\leq 2R)$

である。後者のとき $(B,C)$ が取る当たりの組み合わせは $1..(R-2L+1)$ 通りなので、 $W=R-2L+1$ と置いて $W(W+1)/2$ 通りである。

コードはこちら

丁寧に数える。まず始点 $B$ が一通りあり、以下を追加する。

$B = 0$ なら以下の和である。

• 負の無限大に向かって動く $\lfloor C/2 \rfloor$ 通り
• 負の無限大に向かって動いてから、一回だけ符号を反転して正の数になる $\lfloor (C-1)/2 \rfloor$ 通り

$B > 0$ なら以下の和である。

• 符号を反転して $-B$ になる1通りと、負の無限大に向かって動く $\lfloor (C-1)/2 \rfloor$ 通りと、負の無限大に向かって動いてからもう一回だけ符号を反転して正の数になる $\lfloor (C-2)/2 \rfloor$ 通り
• $0$ に向かって動く $P=min(B, \lfloor C/2 \rfloor)$ 通りと、動いてから一回だけ符号を反転して負の数になる $P$ 通りの、計 $2P$ 通り。ただし以下のいずれかに該当するときは、符号を反転できないので1通り減らす。
  • $B \leq \lfloor C/2 \rfloor$ のとき($0$ にたどり着くので)
  • $C$ が奇数(符号を反転する残り金額は無い)

$B < 0$ なら以下の和である。

• 負の無限大に向かって動く $\lfloor C/2 \rfloor$ 通り
• 負の無限大に向かって動いてから、一回だけ符号を反転して正の数になる $\lfloor (C-1)/2 \rfloor$ 通り
• 符号を反転して $-B$ になる1通りと、 $0$ に向かって動く $P=min(B, \lfloor (C-1)/2 \rfloor)$ 通りと、動いてから一回だけ符号を反転して負の数になる $P$ 通りの、計 $2P+1$ 通り。ただし以下のいずれかに該当するときは、符号を反転できないので1通り減らす。
  • $B \leq \lfloor (C-1)/2 \rfloor$ のとき($0$ にたどり着くので)
  • $C-1$ が奇数つまり $C$ が偶数(符号を反転する残り金額は無い)

公式解説は $C$ の偶奇で分けている。

コードはこちら

解説を読んでもなかなか分からなかった。

部分木が頂点数が $N$ なら、部分木の手番は $3N$ である。よって $N$ が偶数なら自分の手番で部分木から戻り、 $N$ が奇数なら相手の手番で部分木から戻る。奇数手番なら、有利なものから交互に取ればよい。と大まかな方針は立ったがそれ以上のことが分からなかった。

見落とした点として、頂点数が偶数で損する部分木は後回しにすることである。頂点数が偶数で得する部分木は先に訪ればよいが、常に先に訪れると勘違いした。そのため正解にたどり着けなかった。

後は先手と後手のややこしさを、解説の実装から読み解く。符号を 入れ替える 方が理解しやすい。

コードはこちら

丁寧に場合分けする

• $K=1$ なら1通り
• 3つの数が同じ x 順列は1通り。 $i^3 \leq K$ となる $i$ の数を求める。
• 2つの数が同じだが、3つの数が同じではない x 順列は3通り。 $i^2 < K$ かつ $k/i^2 \ne i$ となる $i$ の数を求める。
• 3つの数が異なる x 順列は6通り。 $a < b < c$ かつ $k/ab > b$ となる組み合わせを網羅する。

コードはこちら

ライブラリ

$A^B \quad mod \quad 10$ には周期性がある。例えば $A=1$ なら $A^{1..} = 1,1,...$, $A=2$ なら $A^{1..} = 2,4,8,16,2(32),...$, である。最初に $A=0..9$ について一周するまでに出る値を求めて置く。鳩の巣原理から、11乗まで調べれば十分である(実際はもっと短い)。

一般に $(A^B)^C \ne A^{(B^C)}$ なので注意である。 $A$ の周期 $p$ が求まるので、 $B^C \quad mod \quad p$ を求めれば、先の周期から答えが分かる。これは atcoder::modint::set_mod(cycle_A) して B.pow(c).val() すればいい。ライブラリを使わずに求める方法を忘れてしまった。

公式解説は周期を正確に求めている。

コードはこちら

二時間掛かった。

中断を何度か挟んでACできた。方針は見えていたが細部の詰めが上手くいかなかった。

最初に $S$ をランレングス圧縮する。併せて文字 $A..Z = 0..25$ が、 $S$ の先頭から何回出現したか累積和を取る。

圧縮後の文字列を末尾から(添え字の大きい方から)順に処理する。長さ1のランは無視する。長さ2以上のラン $[L,R]$ があるとき、そのランを延ばして操作を繰り返せるかどうか判断する。

前の操作で $[l,r]$ を置き換えたとする。最初の操作については、前の操作を $[N+1,N+1]$ とみなす。

$c = S[R]$ が前の操作の文字 $p$ と異なるなら(初回の操作は必ず異なるとする)、 $S$ の末尾までつまり $[R+1,N]$ を $c$ に置き換えることができる。なぜなら $[R+1,N]$ において、 $c$ が連続する箇所は他の文字列で置き換わっているからだ。 $[R+1,l-1]$ のうち $c$ が単独で出現するときは操作できないが、 $c$ が連続で出現することはない(そのように操作順を決めたので)。 $[R+1,l-1]$ に含まれる $c$ を $M$ 個として、操作回数は $N - R - M$ 回操作できる。

$c = S[R]$ が前の操作の文字 $p$ と同じなら、前の操作の左端まで $[R+1,l-1]$ を $c$ に置き換えることができる。上記と同様に、操作回数は $l - 1 - R - M$ 回操作できる。

これらの操作回数の和が答えである。境界条件がややこしい。

他の方の 解法 が理解しやすいので、この方針を基に求める。

$S$ を末尾から先頭に順に走査する。0-based indexingで $i=(N-1)..0$ とし、便宜上 $S$ の末尾にはどの英小文字とも一致しない .* を追加済とする。

• $S[i] = S[i+1] \land S[i+1] \ne S[i+2]$ のとき、それ以後の文字を $S[i]$ で置き換える。何文字置き換え可能かは以下で求める。
  • これまで見た $S[j] = S[j+1]$ が成立する最後の位置 $j$ を $prevP$ , $prevC = S[prevP]$ とする。初期値は $prevP = |S|$ とする。
  • $S[i..prevP)$ にある、非連続な $S[j]$ な出現回数を $C$ とする。これは a..z について、出現位置に対する累積和をあらかじめ求めればわかる。
  • $S[i] = prevC$ なら、連続する次の $S[i]$ まで操作できるので $prevP - (i+2) - C$ を解に足す
  • $S[i] \ne prevC$ なら、 $S$ の末尾まで操作できるので $|S| - (i+2) - C$ を解に足す
• $S[i] = S[i+1]$ なら、 $prevP = i, prevC = S[i]$ とする

コードはこちら

二日掛かった。

$A$ の最小値を $1..K$ に決め打ちすると答えが求まる。エッジケースが厄介なので先に考える。

$N = 1, M = 1$ なら一マスしかないので、そのマスの埋め方が全てで答えは $K$ 通りである。以下の説明で、0の累乗は0とする。

$N = 1, M > 1$ なら $A_{1} = i = 1..K$ に決め打ちする。このとき各マスの値は $i$ 以上である。よって $i$ 以上の組み合わせは $(K-i+1)^M$ 通り、 $i+1$ 以上の組み合わせは $(K-i)^M$ 通りなので、 $i$ を少なくとも一つ含む組み合わせは $(K-i+1)^M - (K-i)^M$ 通りである。これをすべての $i$ について足したものが答えである。解説にある通り、よく考えたらこれは $K^N$ である。

$N > 1, M = 1$ なら $B_{1} = i = 1..K$ に決め打ちする。このとき各マスの値は $i$ 以下である。よって $i$ 以下の組み合わせは $i^N$ 通り、 $i$ 未満の組み合わせは $(i-1)^N$ 通りなので、 $i$ を少なくとも一つ含む組み合わせは $i^N - (i-1)^N$ 通りである。これをすべての $i$ について足したものが答えである。

$N > 1, M > 1$ なら、ある $i \in [1,K]$ を決め打ちして $\forall j : A_j \leq i$ , $\exists j : A_j = i$ とする。このとき $A$ の組み合わせは $i^N - (i-1)^N$ 通り、 $B$ の組み合わせは $(K-i+1)^M$ である。 $N = 1$ または $M = 1$ と異なり、 $B > i$ の場合があっても構わない。これをすべての $i$ について足したものが答えである。

公式解説も上記とは異なる表現で同じ式を導いている。

コードはこちら

総当たり

いい感じに素因数を集めようとして失敗し、結局総当たりにした。50以下の素数は15個しかないので、素数の選び方は32768通りである。選んだ素数を選んで掛けて、 $X_i$ との最大公約数がすべて1より大きいものについて、その最小値を取ればよい。

公式解説も上記の通りなので、素因数を上手く集める方法がなさそうだ。

コードはこちら

全単射

$T$ が $f$ について全単射、つまり $f(T)$ の全ての要素は $T$ に属し、 $f$ の逆関数 $f^{-1}$ が存在することを要請する。このような $T$ は、 $i$ から $f(i)$ への依存関係を有向グラフにしたときにサイクルを構成することと同じである(鳩の巣原理より、 $f$ を高々 $N$ 回適用すれば、サイクルなら $i$ に戻る)。

よってこの有向グラフを強連結成分分解して $M$ 要素になったとき、強連結成分の空ではない組み合わせの数 $2^M - 1$ が答えである。

コードはこちら

単調減少

二人の解答の1の数が(あるいは0の数が)偶数個異なれば、正解数を等しくできる可能性がある。 0 または 1 が一致する問題はその正解がどうあれ正解数が一致する。違っているものの半分は正解を取り敢えず 0 に決め打ちし、正解数が違ったら一つずつ 0 を 1 に変えれば、正解数が多い方は1減って正解数が少ない方は1増えるので、いつかは正解数が一致する。逆に二人の解答の1の数が(あるいは0の数が)奇数個異なるときは一致させることができない。

よって解答の1の数が $0..M$ 個であるような生徒の人数 $P_i$ を数え、 解答の1の数が $i$ 個のときかつ $i+1,i+3,...$ 個になるような組み合わせの数を数えればよい。つまり $\sum_{i=0}^M \sum_{j=i+1}^M P_i P_j$ ただし $(i-j) \quad mod \quad 2=1$ である。

公式解説では、 1 と解答した問題数が奇数の生徒の人数と偶数の生徒の人数の積とある。しまった、そうまとめられたのか。

コードはこちら

解に一意性がない。

$A$ を1ずつ増やしても $B$ を1ずつ増やしてもどちらも解の条件を満たす。よって解に一意性がない。これに気が付かなくて1時間掛かった。

$r$ 行目を足すと $\sum_{i=1}^N{C_{r,i}} = \sum_{i=1}^N{(A_r+B_{i})}$ である。 $B$ は各行に共通なのでキャンセルすることができて、行の和を引くことで $A_{r}$ と $A_{1}$ の差分を得られる。

$N(A_{r} - A_{1}) = \sum_{i=1}^N{(A_r+B_{i})} - \sum_{i=1}^N{(A_1+B_{i})} = \sum_{i=1}^N ({C_{r,i}} - {C_{1,i}})$ から $DA_r = (A_{r} - A_{1})$ を求める。

同様に列の差分を取って、 $N(B_{c} - B_{1}) = \sum_{i=1}^N{(B_c+A_{i})} - \sum_{i=1}^N{(B_1+A_{i})} = \sum_{i=1}^N ({C_{i,c}} - {C_{i,1}})$ から $DB_c = (A_{c} - A_{1})$ を求める。

よって $A_1,B_1$ を決め打ちしたときに、 $A_{2..N},B_{2..N}$ を求めることができる。このような $A,B$ が存在する条件は以下の通りである。

• 各行について、列方向の差分が等しい。つまり $\forall r, \forall c=1..N : C_{r,c} - C_{r,1} = C_{1,c} - C_{1,1}$ である。
• 各列について、行方向の差分が等しい。つまり $\forall c, \forall r=1..N : C_{r,c} - C_{1,c} = C_{r,1} - C_{1,1}$ である。
• $A_i,B_i$ に下駄を履かせることで $C$ を非負にできる。つまり $C$ を非負にするためには $A$ に $AD=max(0, A_1 - A_i)$, $B$ に $BD=max(0, B_1 - B_j)$ だけ下駄を履かせる必要があり、 $C_{1,1} \ge AD+BD$ でなければならない。

上記を満たさなければ答えは No である。すべて満たすなら答えは Yes で、 $A_{1..N}=DA_{1..N} + AD$, $B_{1..N}=DB_{1..N} + BD + (C_{1,1} - AD -BD) = DB_{1..N} + C_{1,1} - AD$ が答えの一つである。

公式解説はもっと簡潔である。解に一意性がないので、 $A$ の最小値を0に固定している。これは気が付かなかった。実装は こちら

コードはこちら

シミュレーション

約数を列挙すればいいと思ったが、 $i=4$ のときに3になるのでシミュレーションするしかなかった。 $i=1..N$ について

• 使ってはいけない数を集合で持ち
• $1..$ について使っていい数、つまり使ってはいけない数に表れない最小の数 $j$ を求め
• $2i,3i,...$ に使ってはいけない数 $j$ を設定する。この回数は調和級数を思い出せば、 $O(N^2)$ にならないと分かる。

公式解説ははるかにエレガントである。約数に着目したのは間違いで、正解は素因数の数だった。

コードはこちら

時間制限が厳しい。

C++で1249ms掛かった。しかも解法が間違っているのにACした。

約数を求めて数えればいいのだが、そのまま数えると $N$ が巨大な素数のときTLEする。まず $N$ を2で割れるだけ割って、素因数2の数 $P \geq 0$ を求める。この後 $N$ は必ず奇数になっている。 $10^{18/6} = 1000$ なので、少し多めに上限 1009 までの数について約数を求めることにする。その前に $N^{1/6}$ より大きい約数を探す。

• $N^{1/6}$ が整数なら、奇数な約数として少なくとも $1,N^{1/6},N^{2/6},N^{3/6},N^{4/6},N^{5/6},N$ がある。 $N^{1/6}$ は平方数かもしれない。
• (中略)
• $N^{1/2}$ が整数なら、奇数な約数として少なくとも $1,N^{1/2},N$ がある。

次に $min(N^{1/2}, 1009)$ 以下の約数を探す。これは $1..1009$ で割り切れるかどうか総当たりすればよい。この後両者をマージして重複を排除すると、奇数の約数の数 $Q$ が分かる。

奇数の約数の数は上記の通りである。偶数の約数の数は奇数の約数に $2^{1..M}$ を掛けるので $PQ$ である。特に $M=0$ なら偶数の約数は無い。

公式解説はとても簡潔である。偶数の約数の方が奇数の約数より多いかどうかだけ答えればよいので、約数を数える必要はない。

• Nが $2^2$ で割り切れるなら偶数の約数の方が奇数の約数より多い。奇数の約数の2,4倍の他に $2^i$ があるので。
• Nが $2$ で割り切れ $2^2$ で割り切れないなら偶数の約数と奇数の約数は同じ数である。奇数の約数に1があるので。

実装すると こちら 。上記の実装がいつか役に立つといいのだが。

コードはこちら

順不同なので $A$ の降順にしてから考える。

降順なら $A_1$ が必ず最大値になり、 $[A_{1},A_{2}]$ なら $A_2$ が最小値, $[A_{1},...,A_{n}]$ なら $A_n$ が最小値になる。

一般的な $i$ について、 $A_j : j < i$ を含まず、 $A_i$ を必ず含み、 $A_j : j > i$ を含むかどうかは任意の部分列について、

• 最大値は $A_i$
• 最小値が $A_i$ になるような部分列は $[A_i,A_i]$ の一通り
• 最小値が $A_j$ になるような部分列は $[A_i,...,A_j]$ の $...$ から何を抜くかなので $2^{j-i-1}$ 通り

である。最初に $i = 1$ として、 $S = \sum_{i=2..N} 2^{i-2} A_i$ を求めておく。ここから $i+1$ のときの値を求めることができる。

• $A_i : i = 1..N$ について、 $[A_i,A_i]$ の一通りに対応して、答えに ${A_{i}}^2$ を足す
• $A_i : i = 1..(N-1)$ について、答えに $A_i \times S$ を足す。 $S$ から $A_{i+1}$ を引き、その後 $S$ を2で割ることで、 $S$ を更新する。

コードはこちら

素因数分解かと思ったら約数列挙だった。

ある数 $x$ を1以外の約数の積 $x = x_1 \times x_2 \times x_3$ と表現できるとする。積を累積して、 $x_1, x_{1}x_{2}, x_{1}x_{2}x_{3}$ は $N \geq 3$ なら $A$ の要素にできる。この $A$ の並びは $(x_1, x_2, x_3)$ の並びと一対一に対応する。よって $(x_1, x_2, x_3)$ を並べて積が $x$ になるパスの内、パス長が $N$ 以内のものが何通りあるか求めることと等しい。

$i=1..M$ についてまとめてパス長を求める。 $i$ のパスは $i$ の1と $i$ 以外の約数の集合 $S$ について動的計画法で求まる。

• $DP[i][c]$ を、掛けて $i$ になるパス長 $c$ になる組み合わせが何通りかを定義する
• $DP[1][1] = 1$ とする
• 以下を $i=2..M$ について順に求める。約数の数はそれほど多くないのでTLEしない。
  • $DP[i][1] = 1$ とする
  • $i$ は $f \in S$ で割り切れるので、 $DP[i][c+1] = DP[f][c]$ とする。これは $DP[f][c]$ 通りのパスに、 $i/f$ を掛けると、 $DP[i][c+1]$ 通りのパスになること意味する。

こうして求めたパスに $1$ を挟みこむ。パス長を $c$ とする。

• $c > N$ なら無視する
• そうでなければ $N - c$ 個の1を $A$ に挟み込むことができる。この組み合わせは $N \choose c$ 個である。これを $DP[][c]$ に掛ける。
• これらの和が求める答えである。

この方法は公式解説3と同じである。公式解説1の方法をなんとなく思い浮かべたが解法に至らなかった。

素因数を掛ける場所に注目する、とあるが、これは素数 $p,q$ について $x = p^a \times q^b$ のとき、 $p$ を掛ける場所は $N-1+a \choose a$ 通りある、という意味である。これをすべての $x$ のすべての素因数について数えればいい。実装は こちら 。素因数を掛ける順列に注目すると、 $2 \times 3 = 6$ と $3 \times 2 = 6$ の区別がつかない。

コードはこちら

桁DP

$A$ の $2^i$ 成分に注目する。 $\oplus A = 0$ なので、 $2^i$ 成分は必ず偶数個である。 $DP[i=0..][j=0..M]$ を、ビット $i=0..$ まで見た時に、和が $j$ になるのが何通りかと定義する。具体的には以下のようにする。

• $DP[-1][]=0, DP[-1][0] = 1$ つまり和が0になるのは1通り
• $d = 2k \times 2^i$ のとき、 $DP[i][from+d] = DP[i-1][from+d] + DP[i][from] \times {N \choose d}$ つまり $DP[i][from]$ の組み合わせから、 $N$ 中 $2k$ ビット立てる方法である。これを $0 \leq from+d \leq M$ を満たす全ての $from, k$ について更新する。

答えは $DP[\infty][M]$ である。 $M \leq 5000 < 2^{13}$ なので下位から12ビットみればよい。

コードはこちら

制約が緩い

$A,B \leq 1000$ で $|E| \leq 10^9$ なので、 $E$ を絶対値1から順に取れば制約を満たしそうである。とりあえず $A,B$ は1から1ずつ増える正の数として $\sum_{i=1}^n = n(n+1)/2$ を計算して、差 $d=abs(sum(A) - sum(B))$ を $sum(A)$ と $sum(B)$ の少ない方の一番大きな数( $A$ または $B$ )に足す。

あとは $1..A$ と $-(1..B)$ を絶対値1から順に出力する。ただし上記に基づいて、 $A$ を $A+d$ にするか $B$ を $-(B+d)$ にする。

コードはこちら

整地

同じ高さのビルは同じ挙動をするので、ビルの高さを降順にして一意にする。このとき最後に0階建てを入れておくと処理が楽である。

並び替えた後のビルの高さ $B_1,..,B_{M+1}=0$ について、 高さの差 $D_1=B_1-B_2,D_2=B_2-B_3,...,D_M=B_M$ について、それぞれの階数の差について、階を減らすかどうかは独立である。その組み合わせは、 $D_1+1,D_2+1,...,D_M+1$ 通りである。それぞれ1増やすのは減らさない場合である。この積が答えである。

公式解説は昇順であること(最初に0階建てを入れる)、同じ高さのビルは同一視できるが図に書いてあることを除けば、上記と同じである。

コードはこちら

$S$ の各文字を数値 $B=0, W=1, R=2$ に対応させる。 $mod 3$ で以下が成り立つ。1階層を操作するごとに、余りと3引く余りが入れ替わる。

• $B + B = B$
• $B + W = 3 - R$
• $B + R = 3 - W$
• $W + W = W$
• $W + R = 3 - B$
• $R + R = 3 - R$

$S[i=0..(N-1)]$ が上記の可算に寄与する回数は $(N-1) \choose i$ とわかる。よって $r = \sum_{i=0}^{n-1} (S_i {(N-1) \choose i})$ を求める。 $N$ が奇数なら $r$ 、 $N$ が偶数なら $(3-r) mod 3$ に対応する文字が答えである。

ここまではわかったが、mod 3の取り方が分からなくて諦めた。公式解説に方法が載っている。

コードはこちら

やってみる

$\lfloor 0..(100+t-1) \rfloor$ のうち $0..(100+t-1)$ に出現しない数を実際に調べる。このような数が $R_0,...R_{M-1}$ の $M$ 個あれば、 答えは $\lfloor N/M \rfloor \times (100+t) + R_{N \quad mod \quad M}$ である。

コードはこちら

ブレゼンハムのアルゴリズムっぽい貪欲法を思いついたが詰め切れなかった。残差が小さい物から増やせばよかったのであり、 $A$ の降順ではなかった。

二分探索によるコードはこちら 。貪欲法より却って理解が大変である。

貪欲法っぽく実装しても 正解 する。

• $B$ の初期解を作る。 $B_i N = A_i M$ なら残差0なので $B_i = A_i M /N$ にして以後何もしない。 $b = \lfloor A_i M / N \rfloor$ とおいて、 $b$ と $b+1$ のうち、 $|b N - A_i M|$ が小さい方を $B_i$ の初期値にする。この時点の $S = \sum B$ を求める。
• 残差 $|B_i N - A_i M|$ の降順に $i$ をソートする。以下を2ループ回す。
  • $S < M$ なら $B_i N < A_i M$ な $i$ を先頭から $M - S$ 個について、それぞれ $B_i$ に1加えて $S$ を1加える
  • $S > M$ なら $B_i N > A_i M$ な $i$ を先頭から $S - M$ 個について、それぞれ $B_i$ から1減らして $S$ を1減らす

コードはこちら

偶奇に分ける。

$A$ の一つを奇数 $M$ 、他を偶数の集合 $S$ にする。 $M$ と $S$ とは共通の素因数を持ち、 $S$ の要素同士は素因数 $2$ を持ち、 $A$ 全体は共通の素因数を持たない( $2$ を持ったり持たなかったりするから)ようにしたい。

$M = 3 \times 5 \times 7 \times 11 = 1155$ として、 $S$ を偶数かつ $3,5,7,11$ の少なくとも一つで割り切れる数の集合とする。 $A \leq 10000$ でこのような $S$ を2499個以上集めることができる。よって $M$ を必ず選び、他に $S$ から $N-1$ 個任意に選んで出力する。

コードはこちら

制約が小さい

$b$ が64通りしかないのだから、全部試せばよい。 $b=0,c=0$ なら $a=N$ なので、答えは $N$ 以下である。 $b$ を1増やすごとに、 $a$ を半分にし、 $c$ を1桁ずつ増やせばいい(ビットマスクを2倍して1足す)。

コードはこちら

一瞬のひらめき

初見で一時間以上かけて解けず、そのまま数日寝かせて、ある日突然ひらめき、数分で解けた。

この操作は 0 と 1 の数を変えないので、 $S$ と $T$ で 0 の数が異なれば一致させることはできない。この種の洞察はARCでは多々出てくる。以後 $S$ と $T$ で 0 の数は等しいものとする。

$S$ と $T$ で 0 の位置を一致させるには、 $S$ の左から $i$ 番目の 0 を $T$ の $i$ 番目の 0 と同じ位置にする。この操作回数は、両者の場所が異なれば1回、そうでなければ0回である。つまり位置が不一致な 0 の数が答えである。

コードはこちら

10分で解けてしまった。

交代和 $\sum_{i=l}^{r} A_i - A_{i+1} + A_{i+2} ...$ が0なら計画を達成できる。隣り合うビルの高さを増やしても減らしてもその差は変わらないので、交代和は不変量である。よって交代和が0になる区間の数が答えである。

$A_0=0$ から $A_i$ までのの交代和 $C_i$ を求めておけば、 $C_i$ の値が等しい組を $l,r$ と置くことで交代和が0の区間を作れる。これは値が $C_i$ となる $i$ の集合が $S$ 個あるというテーブルを作れば、その $C_i$ について $S(S-1)/S$ 組である。

コードはこちら

累積最大値と二重累積和

$a$ の累積を以下の通り取る。空集合の累積として、先頭は0としておく。

• 累積最大値 $cummax(0..N)=(0,a_1,max(a_1, a_2),max(a_1, a_2,a_3),...)$
• 累積和 $(0,a_1,a_1+a_2,a_1+a_2+a_3,...)$ は二重累積和を取るのに使える
• 二重累積和 $cumsum(0..N)=(0,a_1,2a_1+a_2,3a_1+2a_2+a_3,...)$

$a=(A_1,..,A_k)$ について、 $f_k(a)=cummax(k) \times k + cumsum(k)$ である。これは以下から分かる。

• $A_1$ を $A_1+cummax(k)$ にする
• $A_2$ を 計算する時点で $a$ の最大値は $A_1+cummax(k)$ なので、 $A_2$ を $A_2+A_1+cummax(k)$ にする
• $A_3$ を 計算する時点で $a$ の最大値は $A_2+cummax(k)$ なので、 $A_3$ を $A_3+A_2+A_1+cummax(k)$ にする
• 一連の操作が $A_k$ まで終わったあと $a$ を合計すると、 $cummax(k)$ は $k$ 回、 $A_i$ は $i$ 回足すことになる。

公式解説は累積最大値と二重累積和を逐次的に求めている。

コードはこちら

等高線

$(1,1)$ からのマンハッタン距離 $d$ が等しいマスの集合を $S_d$ とする。すべての $0 \leq d \leq (H + W - 2)$ について、 $S_d$ にあるマスの色が等しければ題意を満たす。よってそれぞれの $d$ について調べ、取りうる組み合わせの積を求める。

• 塗られているマスが無いなら2通り
• 赤く塗られているマスが無く、青く塗られているマスが1つ以上あれば、全部青く塗って1通り
• 青く塗られているマスが無く、赤く塗られているマスが1つ以上あれば、全部赤く塗って1通り
• 上記以外は赤青が混在するので0通り

コードはこちら

手を動かす。

入力例4を実際に手を動かして求める。以下のように、左端から順に、最も近い候補を移動させると7手で求まる。

 8   5   4  <7   4   5
10<  7   4  <3   4   5 (+3)
10   5<  6   3   4  <5 (+1)
10   5   6   7<  2  <3 (+2)
10   5   6   7   4<  1 (+1)

この操作を一般化すると、以下が成り立つ。左に1移動すると値が1増えることを利用する。

1. まだ定位置にないつまり $A_i \ne B_i$ を満たす最小の $i$ を求める
2. $B_i = A_j + j - i$ なる最小の $j$ を求める。なければ手詰まりなので -1 を出力して終わる。
3. $A_j$ を $B_i$ に移動する
4. $A_{i}..A_{j-1}$ から1引いて、 $A_{i}..A_{j}$ にシフトする

これを明示的に行うとTLEするので、高速化を試みる。位置が1シフトするのと値が1減るのを足すと0になるのが鍵である。

1. 連想配列に $P$ 、 $P[A_i + i]$ の値を $i$ の集合として登録する
2. 遅延セグメント木 $T$ に、 $A_i$ の現在地を $T[A_i] = i$ して登録する
3. $i = 1..N$ について以下を順に調べる

• 連想配列に $B_i + i$ が載っていなければ手詰まり
• 載っているならば移動元として最小値 $p = min(P[A_i + i])$ を得る。
• 移動元の現在地 $q = T[p]$ を得る
• 移動する距離は $q - i$ である。これを答えに足す
• 遅延セグメント木の区間 $[1,p)$ に1足して、移動元をシフトする。
• $P[A_i + i]$ から $p$ を削除する

途中で手詰まりにならなければ、移動距離の和が答えである。

公式解説は転倒数を使っている。

コードはこちら

二時間掛かった

方針はすぐ立つが、エッジケースの作り込みが大変である。

家の座標 $X,Y$ と、ある $X,Y$ 座標にある家の識別子 $1..N$ を求める

実際に1番目の距離を求める。 $max(X)-min(X) < max(Y)-min(Y)$ つまり $Y$ 方向に長いとする(そうでなければ $X,Y$ を反転して同様に考える。

• $max(Y)$ もしくは $min(Y)$ の少なくとも一方について、座標が一致する家が複数あるなら、1番目の距離と2番目の距離は同じである。
• そうでなければ $max(Y)$ もしくは $min(Y)$ となる家はそれぞれ一つしかないのだから、それぞれを取り除いて2通りについて、1番目の距離を求める。

$max(X)-min(X) = max(Y)-min(Y)$ なら、

• $max(X)$, $min(X)$, $max(Y)$, $min(Y)$ の少なくとも一方について、座標が一致する家が複数あるなら、1番目の距離と2番目の距離は同じである。
• そうでなければ $max(X)$, $min(X)$, $max(Y)$, $min(Y)$ となる家はそれぞれ一つしかないのだから、それぞれを取り除いて4通りについて、1番目の距離を求める。

2番目の距離を明に求めようとするとデバッグが大変なので、1軒除いて一番長い距離を求める方が簡単である。ここで時間を使ってしまった。X字と/字について考える、などと場合分けすると上手くいかない。

想定解法は、 $max(X),min(X)$ と $max(Y),min(Y)$ を総当たりである。これは思いつかなかった。実装したものが こちら である。

• $X,Y$ の辞書順の昇順で並び替えて、 最初のX, 二番目に小さいX, 二番目に大きいX, 最大のXとなるような家を挙げる。辞書順なので、Xが等しければYの昇順になる。つまりすべてXが同じなら、最初のY, 二番目に小さいY, 二番目に大きいY, 最大のYとなる。
• $Y,Y$ も同様。
• 上記から最大8軒、 $X,Y$ で挙げた家に重複があるときと $N=3$ のときは少ないので最小3件挙がる。重複を排除して、それぞれの家の距離を総当たりで求め、二番目に大きい距離を出力する。少なくとも3軒あるので、二番目に大きい距離は必ずあり、ダミーの0を追加する必要はない。

コードはこちら

一時間半掛かった

色がR,G,Bの犬がそれぞれ偶数匹いるなら答えは0である。以後は奇数匹が2色、偶数匹が1色とする。一般性を失わず、 R,Gが奇数匹、Bが偶数匹、匹数 $|R| < |G|$ とする。犬の集合を std::set<std::pair<Num,Num>> 、 $a$ と $i$ の組で管理して $a$ でソートする。

まずR,Gの端数1匹同士を組み合わせることを考えるこれは $R$ のすべての $a$ について、もっとも近い $G$ と組み合わせればいい。 std::set::lower_bound で分かる。 差が0なら即座に答えは0であると分かる。そうでなければ最小値を求める。Bが0匹ならこれで答えが求まる。

次にBと組み合わせることを考える。R-Gより、R-B, G-Bの方が差が小さいことがあるので、貪欲法では上手くいかず総当たりする必要がある(これが分からなくて時間を溶かした)。RまたGを決め打ちして、最も近いBとの差を求める。R-Bの最小値にG-Bの最小値を足せばよいが、このとき同じBを取りあいにならないように注意する(そのために集合に $i$ を入れた)。同様にG-Bの最小値にR-Bの最小値を足せばよい。

これらの最小値が答えである。

コードはこちら

フィボナッチ数列

$N=1$ なら $A_1$ , $N=2$ なら $2A_1$ である。以下 $N > 2$ とする。

$A_i$ と $A_{i+1}$ の間に演算子 $OP_{i}$ に + と - を入れる組み合わせについて漸化式を作る。先頭から順にみて、 $OP_{i}$ に + を置ける組み合わせの数を $P_i$ とし、 - を置ける組み合わせの数を $N_i$ とする。

• 先頭 $A_1$ の前には暗黙の $OP_0$ + がある。つまり $P_0=1$ , $N_0=0$ である。
• - の前は + しか置けない。なので $N_i=P{i-1}$ , $P_i=P{i-1}+N_{i-1}$ である。
• これはフィボナッチ数列であり、 $fib(0)=0, fib(1)=1, fib(i+2)=fib(i+1)+fib(i)$ として、 $P_i=fib(i+1)$ , $N_i=fib(i)$ である。
• 良い式の総数は $fib(N+1)$ である。

$OP_i$ が + である含む良い式の数を考える。これは $i$ を出発点として $fib(N+1-i)$ 通りあるので、 $P_i \times fib(N+1-i)$ つまり $Q_i=fib(i+1)fib(N+1-i)$ 通りである。 $OP_i$ が - である含む良い式の数は、 $fib(N+1)-Q_i$ である。よって求める答えは $\sum_{i=1}^{N} A_i(2fib(i+1)fib(N+1-i) - fib(N+1))$ である。

公式解説はフィボナッチ数列であることを明言していないが、DPを使った解き方は同じ。

コードはこちら

茶diffで三分探索

三分探索をすれば求まる。

コードはこちら

制約からビットごとの桁DPかフィボナッチ数列しかないと思い、桁DPは上手くいかないのでフィボナッチ数列にした。公式解説はフィボナッチ数列を使った解法が厳密に書いてあるが、私は黄金分割で雑に実装してACした。

黄金比を $r = (1 + \sqrt{5}) / 2) = 0.618$ とする。 $N$ を再帰的に黄金比で分割し、誤差をいい感じに扱うとACする。このような実装にしたが、公式解説とは違って厳密ではない。

• 初期値は、 $x = N(1-r), y=Nr$ にする。 $10^{18}r$ の丸め誤差を考慮して、前後30くらい振って、制約を満たす解を選ぶ。この処理を実装し間違え、一つ見つけたら操作が多すぎる解を返してしまっていた。
• $x < y$ として $(x,y)$ を $(x,y-x)$ に分割する。そうすると操作4を適用できる。 $x > y$ なら $x,y$ を入れ替えて、操作3を適用する。ここを証明無しで使った(確かに上手くいくが、操作回数の上限を満たすかどうか明らかではない)。
• $(x,y-x)$ が解無しなら、 $(x,y-x-1)$ を探し、上手くいったら操作4,2を適用する。 $x > y$ なら $x,y$ を入れ替えて、操作3,1を適用する
• $x < y-x$ つまり $2x < y$ なら、操作2を適用する。 $x > y$ なら操作1を適用する。

コードはこちら

場合分けを減らす。

$A < C$ として一般性を失わない(そうでなければ $A$ と $C$ を入れ替えれば左右反転する)。あとは $B$ の大小で二通りに場合分けできる。

1. $A < B$ かつ $A + 2(B - A) \leq C$ なら、 $C$ を $A - B$ を延長した先まで増やす
2. そうでなければ $B$ を $A-C$ の中間点まで増やす。中間点が整数でなければ切り上げる。

公式解説は次元削減をして、等差数列を作るための特徴量を変更する回数を求めている。この方が証明しやすい。

コードはこちら

尺取り法

単に尺取り法すればいいのだが、解くのに54分掛かった。二部グラフの最大フロー問題として解こうと思ったのだが、辺が $O(N^2)$ なので解けない。

• $A,B,C$ をそれぞれ昇順に並び替える
• $ia=1,ib=1,ic=1$ について、 $A_{ia} < B_{ib} < C_{ic}$ なら組み合わせを1増やす。そのあと $ia,ib,ic$ を1ずつ増やして再度試す。
• $A_{ia} < B_{ib}$ になるまで $ib$ を増やす
• $B_{ib} < C_{ic}$ になるまで $ic$ を増やす
• 上記を $ia,ib,ic < N$ の間繰り返す

コードはこちら

制約が小さい。

$N=1000$ なので $N^2$ 解法が通りそうである。よって $i=1..K$ について、位置 $1..N$ にカード $i$ を置くことができるかどうか印をつけてよい。実際には位置 $1..N$ に置くことができるカードが何種類あるか数えればよく、どのカードなのか覚える必要はない。

制約を満たすということは、位置 $k_i$ にカード $i$ を必ず置くことを意味する。なので $i$ が書かれたカードが少なくとも1つ存在する必要がある、という条件は自動的に満たす。

位置 $1..N$ について、あるカードを必ず置くなら1通り、そうでなければ置けるカードの種類通りであり、この積が答えである。

コードはこちら

連想配列を比較する

$x=XOR(A_1,B_i)$ のとき、 $A_1=XOR(x,B_i)$ である。これを利用して $B_{1..N}=XOR(x,A_{1..N})$ かどうか調べれば、 $A_1$ について $x$ がよい数かどうか分かる。これを $i=1..N$ について調べる。

$XOR(x,A_{1..N})$ と $B_{1..N}$ について、それぞれの数の出現回数を std::map に収めて == で比較する。そうしないとTLEする。

コードはこちら

あと1 WAだった。

公式解説にある通り、 $GCD(A,B) \leq A,B$ なので、最初の要素の約数と決め打ちしてよかった。すべての要素の約数 $f$ を列挙して、 $f$ が $A_{1..N}$ または $B_{1..N}$ の約数になるのが $N$ 通りなら最大公約数の候補にする、という方法を実装したら1 WAだけ残った。

コードはこちら

反復横跳び

$M$ の要素が $N$ になければ解なし -1 である。そうでなくて $N$ の要素がすべて同じならシフト不要なので $M$ 回である。

それ以外なら $N$ の中に $a_{i} \ne a_{i+1}$ なる $0 \leq i \leq N-1$ がある。このとき $min(i,N-i)$ 回シフトすれば、 $a_0$ と異なる値にすることができる。なので以下のように操作する。

1. $a_0=T_0,T_1,..$ を可能な限り $b$ に追加する
2. $a_0 \ne T_j$ になったらシフトして $b$ に追加する
3. $T$ に同じ要素が続くならシフトせず追加し、異なる要素が現れたら1回シフトして追加する

答えはシフト回数 + $M$ である。 $M$ を足し忘れないように。

コードはこちら

2時間超え。

反比例曲線 $y = 1/x$ と、対角線との間にある格子点が答え、というのはなんとなく分かる。実際その通りなのだが、考察してみる。

$i=0,1,2,3,..$ について、 $i^2=0,1,4,9,..$ であり、 $i^2$ と $(i+1)^2$ の差は $W_i=2i+1$ である。ある $x,y$ について、区間 $[x^2-y,x^2], 0 < y \leq N$ に収まる平方数が $k$ 個以上になる $W_i$ が何個あるか ( $C_i$ とする)数える。 $k=1$ のとき $C_1$ は $1 \le W_i \leq N$ を満たす $W_i$ の数である。同様に $1 \leq k \leq sqrt(N)$ について $C_k$ は $k \le W_i \le \lfloor N/k \rfloor$ を満たす $W_i$ の数である。

つまり求める答えは、 $N$ が平方数のときに注意して、 $\lfloor sqrt(N) \rfloor + \sum_{k=1.. \lceil sqrt(N) \rceil - 1} \lfloor (N/k - k)/2 \rfloor$ である。

公式解説と式は同じだが、公式解説はもっとすっきり式を導出している。

コードはこちら

理詰めでは分からず、実験して分かった。

区分化とは $A_0 = 0$ として、 $A_{i-1}$ と $A_{i}$ の間(両端を挟まない)にある数を $A_{i}$ 直後から降順に並べること指す。 $A_{i-1}=4$ 、 $A_{i}=7$ なら、 765 と並べる。

$A$ による区分化をすると大量にWAする。実験コードを書くと、 10 3 3 7 9 の答えは 3 1 7 2 10 9 8 6 5 4 である。しかし単なる区分化は 3 2 1 7 6 5 4 10 9 8 を出力する。 10 3 4 7 9 に対して正解は 4 1 7 2 10 9 8 6 5 3 だが区分化は 4 3 2 1 7 6 5 10 9 8 を出力する。

実験による考察から、 $i = 1..N-1$ について以下を繰り返す。答えを $V$ とする。

• $V$ に $A_i$ を追加する。
• $A_{i-1}..A_{i}$ の数を集合 $S$ を入れる。 $A_{i-1},A_{i}$ を含まない。
• キューが空でなければ $A_{i}$ の直後に、 $S$ で最小の数 $M$ を挟む。つまり $V$ に $M$ を追加して、挟んだ数を $S$ から除く。

最後に $A_n$ を $S$ に加えて、 $S$ の要素を降順に $V$ に付け加える。こうしてできた $V$ が解である。

コードはこちら

貴重品から使う

以下の順に優先的に割り当てる。

1. 長さ3の棒x2 + 長さ4の棒x1
2. 長さ3の棒x2 + 長さ2の棒x2
3. 長さ4の棒x2 + 長さ2の棒x1
4. 長さ4の棒x1 + 長さ2の棒x3
5. 長さ2の棒x5

コードはこちら

最大フローだと思ったら全然違った。

正解はセグメント木だった。 $(a,b)$ を辞書順つまり $a$ の昇順で、 $a$ が等しい辺は $b$ の昇順にソートする。ソートしたものを順に追加できるかどうか考える。

辺 $(a_i,b_i)$ を追加するとき、すでに追加した辺は $y=0$ の頂点のX座標について $a_i$ 以下である(ソートしたので)。よって $y=1$ の頂点のX座標について $b_i$ 未満の辺は交わらない。このような辺の集合 $E_i$ があり、辺 $e \in E_i$ について辺 $e$ と交わらない辺の集合(自身を含む)に $(a_i,b_i)$ を追加することを考える。辺 $e$ と交わらない辺の集合が $C_e$ 個あるなら1辺足せばよく、辺 $(a_i,b_i)$ と交わらない辺の数の最大値は $max(C_e) + 1$ である。

これは区間maxセグメント木を更新することで得られる。注意点として、 $a_i$ を共有するつまり $b_i$ が異なる辺が複数ある場合、互いの影響を受けるとWAする。 $(a_i,b_1,b_2,..,b_k)$ について、セグメント木の要素 $b_1,b_2,..,b_k$ をそれぞれ $D_1,D_2,...,D_k$ に更新するつもりと保存しておいて、 $a_i$ を変える前にセグメント木を更新する。

公式解説を読んで、LISのセグメント木実装そのものだと分かった。確かに最近学んだ。

コードはこちら

嘘解法で4 WAsを出して直そうと足掻いたら時間が溶けた。方針を出し直してACした。

嘘解法は、解 $g$ を決め打ちして、 $A$ を $g$ の倍数にするまでの増分を求め、このような $g$ を二分探索するものである。おそらく $g$ と増分に短調性がない。

自明な解として、 $N \times max(A) \leq \sum A + K$ なら、 $K$ を全部足して整地した値 $\lfloor (\sum A + K) / N \rfloor$ が答えである。 $GCD(A) \leq min(A)$ なので、整地が最適である。

この方針を全部捨てて、調和級数で解く。 $A$ を昇順にソートする。 $A$ の最大公約数を $h$ として、 $A$ を $h$ で割っておく。この前処理の後の $A$ について、 $g = 2..max(A)$ が解の候補になるかどうか総当たりする。 $g = 1$ は常に解の候補なので調べるまでもない。

具体的には $g$ を固定して尺取り法する。

• 左区間 $L = 0$ , 右区間の閾値 $T = g$ とする
• $T$ より大きいという条件を満たす、最小の $A$ の要素の位置 $R$ を求める。 $[A_L..A_R)$ を $T$ にするので、最大公約数を $g$ にしたとき後の $[A_L..A_R)$ の合計は $(R-L)T$ である。これを和 $S$ に加算する。
• $R = N$ なら終了する。そうでなければ $L = R$, $T = \lceil A_R / g \rceil$ にして探索を繰り返す。
• $S -{\sum A} \leq K$ なら、 $g$ は解の候補である。

この尺取り法は $N/g$ 回で終わるので、計算回数は調和級数 $O(Nlog(N))$ である。全体ではもしかしたら $O(Nlog(N)log(N))$ かもしれない。解の候補となる最大の $g$ について $gh$ が解である。

公式解説と同じ方針である。実は $h = 1$ として構わない。

コードはこちら

Leading 1sの長さを決め打ちして、その範囲に収まる数が $N$ 以下かどうか調べる。

桁数 $W$ , Leading 1s が $L$ 個の整数の範囲を考える。

• $W = L$ なら、すべての桁が1の整数が一種類ある
• そうでなければ、 $[1..100..0, 1..109..9]$ と $[1..120..0, 1..199..9]$ の二つの範囲がある。この範囲にある $N$ 以下の整数を数える。より正確には、以下のような範囲を定める。
  • 先頭が $L$ 個の 1 で残りが0となる整数を範囲の下限、先頭が $L$ 個の 1、次が0、残りが9となる整数を範囲の上限とする。
  • 先頭が $L$ 個の 1、次が2、残りが0となる整数を範囲の下限、先頭が $L$ 個の 1、残りがすべて9となる整数を範囲の上限とする。

コードはこちら

寝かせたら解けた。

問題を見た初日には解けず、数日経ったら答えが分かった。最上位桁は0,1,2の繰り返ししかない。最上位桁が2のときに、3進数 $L - 1$ 桁で $0..(N-1)$ まで作って結合すれば、 $t$ としてありうる文字列の中で辞書順最小の文字列を達成できる。

それ以外の桁について大きさを気にする必要はない、0,1の出現回数をそろえればよいので、最上位桁が1のとき、他の桁は最上位桁が2のときの場合の0,1,2を1,2,0に置き換える。最上位桁が0のとき、他の桁は最上位桁が2のときの場合の0,1,2を2,0,1に置き換える。

コードはこちら

連勝連敗

$A_i \leq A_{i+1} \leq A_{i+2} \leq ...$ が続いているなら、途切れるまで金を銀に交換しない方が得である。逆に $A_i \geq A_{i+1} \geq A_{i+2} \geq ...$ が続いているなら、途切れるまで銀を金に交換しない方が得である。つまり上昇から下落、下落から上昇に転じる変換点で交換すればよい。

• 初期値は上昇にする。そうすると $A_1 > A_2$ のときに $A_1$ を変化点にできる
• $A_N$ が下落で終わったときは $A_N$ を変化点にする
• 交換する回数は0または偶数で、奇数回交換すると金が得られないので、変換点が奇数なら最後の一つを削る

公式解説が上手く理解できないのですが、上記と実装は同じです(下落の頂点で金を銀に交換し、谷で銀を金に交換することはコードから分かる)。

コードはこちら

不変量に注目して総当たりする。

$R = G$ または $R = B$ または $G = B$ が成り立つときは、それらの数だけ操作すればボールを1種類にできる。

そうでないときを考える。ボールの数の総和が不変量である。つまり $S = R + G + B$ 個のボールが一種類だけあるとして、 $R,G,B$ 個にする逆操作が可能か調べる。

• $S$ 個の単色のボールがあったとして、これらを3色のボール $p, p, S - 2p$ 個に配分する
• ボールの数を調整する。 $low = p - 2q$ , $middle = S - 2p + q$, $high = p + q$個に調整する。これが成り立つ条件は、 $high - low$ を3で割り切れることである。
• $q = high - low$ である。これを題意を満たすかどうか調べる $p \leq 0$ , $q \leq 0$ および上記 $low, middle, high$ の等式が成立すれば、最小の操作回数は $p + q$ 回である。
• 実は $low \leq high \leq middle$ かもしれないが、それでも操作可能なので題意を満たす

$low, middle, high$ は $R,G,B$ の順列6通りなので、それぞれ決め打ちして試す。こうして求めた操作回数の最小値が答えである(操作不能なら -1)。

公式解説は、最後の単色のボールを決め打ちして、二色を一色にする手順を導出している。最後は0個になる二色ボールの個数について、個数の差を3で割った余りが不変量であることを利用している。

コードはこちら

解けなかった

解説を見るまで、解き方がさっぱりわからなかった。桁DPと思いきや、単に $N$ の立っているビットを落とすだけである。

コードはこちら

数時間掛かったが解けた。

問題を理解し間違えていて、区間の間の最小の隙間を求めるのだと思っていた。全然そうではなかった。

まずすべての区間に幅1以上の重なりがあるなら、答えは0である。これは $max(l) < min(r)$ なら重なりがあると分かる。そうでなければ、 $max(l) - min(r)$ が答えである。もっと簡潔に書くと $max(0, max(l) - min(r))$ である。答えはこの半分(小数点以下切り上げ)である。

公式解説は式変形を用いて鮮やかに導出している。

コードはこちら

数時間掛かっても解けなかった。多角数定理を知らないと解けない。

左側にいい感じに数列を延ばす方法が全く分からなかった。公式解説にある通り、数字を下の桁からみたときの $mod 7$ を一致させればいいのだが、他の方のコードを見て7で割り切れる場合を上手く扱わないと答えが合わないと分かった。

コードはこちら

絶対値を外そうとして悪戦苦闘し、結局解けなかった。ARCによくある、実は最適解を常に構築できる問題である。 $A,B < C,D$ なら、 $|A-C|+|B-D| = |A-D|+|B-C|$ であることに気が付く必要があった。

コードはこちら

ランレングス

文字をランレングス圧縮して、同じ文字が2個以上続いたら、連続する文字から2個除く方法 $len(len-1)/2$ 通りを全部足す。 $S$ の前後に $S$ に出現しない文字つまり英小文字以外たとえば空白文字 を加えておくと、 $S$ の最後の文字を特別扱いしなくて済む。

公式解説も表現は異なるが、ランレングスを数えることと同じである。

コードはこちら

解くのを忘れていた。

ABC 346-Eが解けなかったのだが、ARC 130-Bが似たような問題だと言う指摘があった。確かにその通りでARC 130-Bを解いていればABC 346-Eも解けたのだと思うと悔しい。わかってしまえば、よくあるクエリ逆再生である。

コードはこちら

桁繰り上がりを連鎖すればよく、一番小さい桁から点火すればよい。

$W_A$ を $A$ の桁数、 $W_B$ を $B$ の桁数とする。 $W_A \leq W_B$ と仮定する(そうでないなら $A,B$ を逆とみなす)。

• $B$ の桁だが $A$ の桁ではない、つまり $i > W_A$ 桁目に9をずらっと並べる。この範囲を $[L_9, R_9]$ とする。
• その次に $i = W_A..2$ 桁目に、足して9になる数を大きな桁から並べる。この範囲を $[L_A, R_A]$ とする。
• その次に $i > j = W_A..1$ 桁目に、足して10以上になる数を並べる。この範囲を $[L_C, R_C]$ とする。CはcarryのCである。

そうすれば、 $[L_C, R_C]$ 目は繰り上がり、 $[L_A, R_A]$ 桁目は繰り上がって0になり、 $[L_9, R_9]$ 桁目も繰り上がって0になり、できるだけたくさん0を作ることができる。それ以外の部分は、桁が繰り上がらなければ答えには影響せず、繰り上がっても9が0になれば得なので考慮しない。

最初に $A,B$ に 0..9 それぞれが出現する回数を数える。問題は、上記の割り当ての優先度である。

• $[L_A, R_A]$ を最初に割り当てる。最大 $W_A - 1$ 個集める。これを間違えると1 WAする。
• $[L_C, R_C]$ を最初に割り当てる。このとき $B$ にある 9 を使わない。最大 $W_A - (R_A + 1 - L_A)$ 個集める。これを間違えると1 WAする。
• $[L_C, R_C]$ が空で $B$ に 9 が無いなら、一切繰り上がりできないので、入力の $A,B$ が答えである
• $[L_C, R_C]$ が空なら、 $B$ から 9 を使い、区間長1の $[L_C, R_C]$ を作る
• $B$ の余った 9 を $[L_9, R_9]$ に割り当てる
• 残った数字はどう割り当ててもよい

公式解説を読むと $[L_C, R_C]$ を最初の桁から詰めてよかったらしい。

コードはこちら

入力例にないものを補う

入力例には $B$ が奇数の例がないので自分で作って確かめる。 $A$ はそのまま出力すればよく、その後 $B$ は半分にした値を出力する。半分にして小数点以下を切り捨てないように、

• Bが偶数なら $B/2$
• Bが奇数なら 0 を出力したあと $5B = 10B/2$

を出力する。Bが奇数のとき 0 を出力しないと、2倍したときに桁が繰り上がって $A$ が変わってしまうことがある。

公式解説を見ると、 $B,A$ の順に出力すればよかった。しまった、 $5B$ と $A$ の間に余分な0があっても答えが $10^{18}$ 未満なら何でもいいことに気が付かなかった。なので このよう に書ける。

コードはこちら

ビットボード

マスに1..5を入れられることではなく、入れられないことを管理する。なお以下では1..5を0..4に読み替える。

マスを std::bitset<5> で表現し、 $d=0..4$ を入れられないことを $grid[i][j][d] == true$ 、入れられることを $grid[i][j][d] == false$ とする。座標 $i,j$ に $d$ を入れるなら $grid[i][j][k \ne d] = true$, $grid[i][j][d] = false$ , $grid[i \pm 1][j][d] = true$, $grid[i][j \pm 1][d] = true$ である。センチネルとして、座標 $0,H,W$ を用意すると例外処理が楽になる。

マスに複数の候補があるなら、既に埋めたマスと矛盾しなければよい。よって外ループ $i=1..N$, 内ループ $j=1..N$ として、

• マスに候補が一つしかないならそれを使う
• マスに候補が複数あるなら最も番号の小さい番号を使う

を繰り返してマスを埋める。

コードはこちら

全く解法が分からなかった。実験するとわかる。

コードはこちら

行と列を適宜入れ替えると、左上に黒マスを寄せることができる。黒マスの数で行を降順にソートして、元々の行がどこに行ったかを対応付ければいい(列も同様)。

クエリに対しては、入れ替え先の行番号と列番号に読み替えて、左上か対角線上なら黒マス、それ以外なら白マスである。これは $(r,c)$ が $r-1+c-1 \leq n$ であるか否かで分かる。

コードはこちら

可能手が少ない

この操作でできることは、先頭を $1$ にすることと、末尾を $n$ にすることだけである。それ以外は操作しても昇順に並べ替えることはできない。しかし昇順にできることは保証されているので、先頭を $1$ にすることと、末尾を $n$ にすることをすればいい。

先頭を $1$ にするには、シフトか、反転してシフトか、どちらか少ない方をすればよい。その後末尾が $n$ でなければ $p_2=n$ になっているはずなので、シフトして反転する。それ以外の状況を考える必要はない。公式解説は少し異なるが、可能手が少ないことは確かである。

コードはこちら

一度解こうとして後回しにしたらしいが、後日見直したら自力ACした。以下 $n,d$ を $N,D$ と表記する。

$D$ が小さいのが如何にもヒントである。 $p$ を何にするかではなく、数 $i=1..N$ をどこに置くかをスライディングウィンドウで管理する。0-based indexingで計算したらデバッグに時間が掛かったので、以下1-based indexingとする。

数 $i$ を置ける場所は $max(1,i-d)..min(N,i+d)$ である。これを $2D+1$ ビットのビットマップで管理する。この配列は $2^{2D+1}$ 状態を持ち、ビット $k$ は、 $P_{i-d+k}$ に値を入れたことを意味する。

$DP[i][j]$ を、数 $i=1..N$ を置いた状態で、 $j = 0..(2^{2D+1}-1)$ のビットマップで表現する位置に何らか数を配置済であるときの、組み合わせの数とする。 $W = 2^{D+1} - 1$ として、初期値は $DP[0][] = 0, DP[0][W] = 1$ とする。これは $i < 1$ の数を密に配置したというダミーである。

$i$ について以下の通り処理する。

$DP[i-1][j]$ について、 $j$ のビット0が0なら、 $P_{i-d}$ をもはや埋めることはできないので無視する。そうでなければ $j$ を左に1回シフトした数を以後 $j$ として考える。これはスライディングウィンドウを1個ずらすことに相当する。

既述の通り、 数 $i$ を置ける場所は $k = max(1,i-d)..min(N,i+d)$ である。これらを一通り試す。

• $A_k$ が非負なら、置ける数は $A_k$ のみである。よって $A_k = i$ 以外なら無視する
• $j$ の $t = k - (i - D)$ ビット目が立っていたら、他の数が置かれているので無視する
• そうでなければ $i$ を置き、 $DP[i][j \oplus 2^{t}]$ に $DP[i-1][j]$ を加算する

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

コードはこちら

辞書順なので先頭が重要。

何個除くかは関係ない。先頭の要素を除いたら辞書順が下がるかどうかだけ興味がある。なので $A$ を先頭から見て行って、今の要素より次の要素の方が小さければ、今の要素を除くと辞書順が下がる。そのような最初の要素を見つけ、そのような要素が見つからない( $A$ が広義短調増加)なら最後の要素を削除する。

削除した要素 $x$ と同じ値は整数列からすべて除くのと、入力例2のように $x$ を除いたら $A$ が空になることがあるのに注意する。

コードはこちら

ARC 126-Bそのままかと思ったら、本当にそのままだった。

$Q$ の各要素から $P$ の各要素に有向辺を張る。辺の数は調和級数なので $Nlog(N)$ である。後はARC 126-Bと同じくセグメント木でLISを求める。

公式解説は lower_bound を使って最長部分増加列を求めている。

コードはこちら

当てずっぽうが通ってしまった。

$A$ の和も $B$ の和も、すべてのマスの和を $modK$ したものである。よって $A$ の和と $B$ の和が異なれば解なし( -1 である)。以下和が等しいときの解を求める。

すべてのマスが $K-1$ であると決め打ちする。このときすべてのマスの和は $HW(K-1)$ である

決め打ちが当たっていれば、行の和は $SR_i = W(K-1) mod K$ である。実際には行 $i$ の和 $modK$ は $A_i$ なので以下の $DR_i$ だけ調整する。

• $A_i \geq SR_i$ なら、行 $i$ から $DR_i = A_i - SR_i$ 引く
• $A_i < SR_i$ なら、行 $i$ から $DR_i = A_i + K - SR_i$ 引く

同様の列の和は $SC_i = H(K-1) mod K$ である。実際には列 $i$ の和 $modK$ は $B_i$ なので以下の $DC_i$ だけ調整する。

• $B_i \geq SC_i$ なら、行 $i$ から $DC_i = B_i - SC_i$ 引く
• $B_i < SC_i$ なら、行 $i$ から $DC_i = B_i + K - SC_i$ 引く

行と列の多く調整する方を採用し、答えは $HW(K-1) - max(\sum DR, \sum DC)$ である。行と列の少なく調整する方は結果的に上手くいくはずだが、このことを証明せずにACしてしまった。公式解説には調整方法が載っている。

コードはこちら

尺取り法

如何にも尺取り法である。貪欲法で解くために、シートを左端から順に並べる。このときシート $[L,L+1]$ をセンチネルとして追加しておくと右端の処理が楽になる。

シートで覆われていない部分を求める。これは既にシートで覆ったと分かっている座標 $right$ (初期値0)と、シート $[x,x+W]$ を比べて、 $right < x$ なら $[right,x]$ がシートで覆われていない隙間と分かる。このあと $right$ を $max(right,x+W)$ で更新する。すべてのシートで被ったら隙間を左端から順に並べる。

最後にシートで覆われていない部分をシートで被う。シートで覆ったと分かっている座標 $right$ (初期値0)と、シートで覆われていない隙間 $[l,r]$ を比べて、 $right$ を $max(right,l)$ で更新してから $m=max(0, \lceil (r - right)/W \rceil)$ 枚のシートで被う。この後 $right$ を $mW$ 増やす。

解説をよく読むと、隙間の次は少なくとも長さ $W$ のシートで覆われているので、それぞれの区間を独立に考えてよかった。上記の解は凝り過ぎである。実装を簡略化すると こちら になる。

コードはこちら

再び尺取り法

左端 $L=1$, 右 $R=N$ から尺取り法で縮めて、入れ替えられる文字列を入れ替えていけばよい。

最初に $S$ のそれぞれの文字について、 $a..z$ を $0..25$ と読み替え、それぞれの出現位置 $1..N$ を順序付き集合 std::vector<std::set<Num>> で持つ。

$S$ の $L$ 文字目が $c$ のとき、 $(l,R]$ 文字目に $c$ より小さな文字があれば入れ替える価値がある。 $d=0..(c-1)$ の順に、 $(l,R]$ 文字目に出現するかどう調べる。出現する最も小さい $d$ のうち、 $(l,R]$ で最も大きな(右にある)位置を $P$ とする。

• そのような $d$ があれば $S$ の $L$ 文字目と $P$ 文字目を入れ替える。 $L$ を1増やし、 $R$ を1減らす。
• そのような $d$ がなければ、 $L$ を1増やす。 $R$ は減らさない

$L \geq R$ になるまで $S$ を更新して得られる文字列が答えである。

コードはこちら

133-Cとは異なり、正攻法で解いた。

$a_i$ に制約が如何にも厳しく、 $K$ を制約にしないと解けなさそうである。それぞれのボールを独立に配置する方法を求めてその積が答えである。なぜならどのようにボールを配置するにせよ、以下のやり方で過半数を獲れるからである。

• それぞれの箱には、少なくとも1以外と書かれたボールの数だけ、1と書かれたボールを入れる
• 過半数を獲得するには、それぞれの箱に1と書かれたボールを1つずつ入れる
• それ以上ボール1を入れるかどうか任意(すでに過半数なので)

過半数を獲った後の余ったボールを $R = a_1 - K - \sum_{i=2}^N a_i$ 個とする。 $R < 0$ なら過半数を獲れないので答えは0通りである。そうでないとき、以下のようにボールを配り、それぞれのボールの配置の組み合わせの積が答えである。ここで $a_i$ 個のボール、 $K-1$ の仕切り、ボールも仕切りも区別できないときの組み合わせの数である。

• ボール $1$ の配置は について $R + K - 1 \choose k$ 通り
• ボール $i=2..N$ の配置は、 $a_i + K - 1 \choose k$ 通り

$K!$ は一度だけ求めておく。繰り返し求めると逆元を求めるのが重いのでTLEする。

コードはこちら

メモ化

$X < 4$ なら操作すると積が減ってしまう。そうでないなら操作する。あとはメモ化再帰で解ける(メモ化しないとTLEする)。

コードはこちら

ポテンシャルをいい感じに調整する。

$D_{i} = S_{i+1} - S_{i} = A_{i+3} - A_{i}$ は、 $D_{i}$ は $i$ を3個飛ばしつまり $i MOD 3$ で考えた時の、 $D_{i}$ のポテンシャル $P_{i}$ の差を表現している。 $P_{i+3} = P_{i} + D_{i}$ なので逐次的に求める。

$P_{0}$ を仮に0とし、 $min(P_{3i})$ の最小値(0以下)を引いてポテンシャルの最低値を0にする。 $min(A_{3i+1})$ , $min(A_{3i+2})$ も同様にする。

$A_{0} = S_{0} - P_{0} - P_{1} - P_{2}, A_{1} = P_{1}, A_{2} = P_{2}$ と置く。 同様に $A_{i} = S_{i} - P_{i-1} - P_{i-2} : i \geq 3$ と逐次的に求める。 $\forall i A_i \geq 0$ ならそれが答えの一つ、そうでなければ解なしである。

公式解説の導出はすっきりしている。

コードはこちら

結局どうしていいか分からなかった。

誤答は $A$ のビット $i$ について1になる $A$ の要素が0より多ければ1になる $A$ の要素を選び、0になるものが1より多ければ0を選び、そうでなければ両方選ぶ、というものである。この方法はanti_greedyケースが全滅する。

公式解説にある通り、任意の $i,j$ について、 $A_i \oplus A_j$ が不変量である。とにかく不変量問題はそうと見抜くのが難しい。

解説を読み解くと、2回操作すると元に戻る $A_1 \oplus (A_1 \oplus A_2) \oplus A_3 = A_2 \oplus A_3$ ので、操作は0または1回だけ考えればよいとわかる。

コードはこちら

フェンス。

C に対する操作は何もできないので、 C は A,B に対する一連の操作の区切り文字になる。よって連続する A,B をどうするか考える。

$a$ 個の A, $b$ 個の B からなる A または B だけからなる文字列があるとする。 AA,AB は何もしない。 BA は BBB を経て AB にする、 BB は BBBB を経て AA にする。よって $\lfloor B/2 \rfloor$ 個の B を A に置き換えることができる。置き換えられなかった高々1個の B を最後に持ってくれば辞書順で最小になる。

あとは上記の操作後の A または B だけからなる文字列と C を順に出力する。

コードはこちら

二日間考えて分からなかった。転倒数だと思ったが、その後どうしていいか分からず4 WAsで終わった。

公式解説通り、転倒数の偶奇が不変量である。これに加えて、同値については位置を入れ替えたとみなすと転倒数の偶奇を入れ替えられる。

コードはこちら

茶diffが一時間

FizzBuzzである。 $GCD(L,R)=1$ なら答えは $R-L$ である。なのでそれより小さな答えなら探しに行く。

$GCD(L,R) > 1$ なので、 $L < i < R$ なる $i$ があって、 $i$ は $GCD(L,R)$ の整数倍でない数が存在する。 $R$ が $L$ の整数倍なら、 $GCD(L,R-1)=1$ であり答えは $R-L-1$ である。

そうでなければ $i$ は $GCD(L,R)$ の倍数ではなく $L$ の素因数 $l$ の整数倍でもなく $R$ の素因数 $r$ の整数倍でもない $i$ が存在する。ここで $l,r$ は互いに素である(そうでないなら $GCD(L,R)$ の定義に反する)。このとき $i=L,L+1,L+2,L+3,L+4$ を探すと $l$ の倍数でも $r$ の倍数でもない整数が5個連続することはない。これは $(l,r)=(2,3)$ を考えれば分かり、 $l$ または $r$ が大きければもっと隙間が空くからである。簡単言うと、差が2の奇数のどちらかは空いていると言える。同様のことが $i=R-4,R-3,R-2,R-1,R$ について言える。

なので $p=L..L+4$ と $q=R-4..R$ の組を全探索して $GCD(p,q)=1$ となる $q-p$ の最大値が答えである。これは上記の場合分けをすべて含む。

公式解説にある通り全探索でよかったのだが、 $L,R$ ではなく $R-L$ を全探索すればよかった。ここに気が付かずに時間が掛かった。鉄則本C18を解けなかったのを思い出す(端ではなく区間差を一つずつ増やすDP)。実装は こちら 。計算量の見積もりが難しい。ACできたので上記の説明は合っているはずだが、 $0..4$ は短すぎるかもしれない。

コードはこちら

折れ線グラフ

$A_{1..N}$ を反転したときに $A$ に含まれる1がいくつ増えるかを、累積和 $C_{1..N}$ として求める。これは $A_i = 0$ なら $+1$ 、これは $A_i = 1$ なら $-1$ として累積和を取る。

この累積和 $C=(C_1,..,C_N)$ の上限と下限を取ることでf、 $A$ の連続部分列 $R = [1, 1..N]$ を反転させたとき1の個数が何通りあるかが、上限と下限から分かる。つまり $max(max(C),0) - min(min(C),0) + 1$ 通りである。

区間の左端を $[i, A_{i..N}] : i=2..N$ と変えたい。そうするには $C$ から $C_i$ を取り除き、 $C$ 全体に $A_i = 1$ なら $+1$ 、 $A_i = 0$ なら $-1$ を足す。これは累積和の要素を除くことに等しい。明示的に $C$ に値を足すとTLEするので、いくつ足すか(下駄を履かせるか)をスカラー量 $ofs += 2A_i - 1$ で持つ。

各 $i$ について $max(ofs+max(C),0)$ , $min(ofs+min(C),0)$ を更新すれば、すべての連続部分列について、1の個数が何通りあるかが分かる。

実は一番最初の累積和だけでよかった、ということが公式解説に書いてある。

コードはこちら

証明できてないのにACできてしまった。

$A_{1..K}$ がすべて $A_{(K+1)..N}$ より大きければ、スコアを上げることはできないので -1 を返す。

そうでなければ $A_{i} : i \in [K+1,N]$ の値を、 $A_i$ より小さい $A_j : j < K$ と入れ替えればよい。そのような $i,j$ の組は見つかるはずである。よって $i = K+1..N$ の順に求めていく。

$A_i$ より小さい $A_j : j < K$ のうち最大の $j$ を求めるには、 $(A_i, -i)$ の組を昇順にソートすればよい。 $i < K$ なら既出の $i$ が入った集合 $S$ にいれ、 $i \leq K$ なら $S$ の最大要素が求めたい $j$ である。このような $(i,j)$ について、 $j-i$ の最小値が答えである。どうして答えなのかは公式解説を読むまで分からなかった( $i$ を $K$ に、 $j$ を $K-1$ にして $K$ と $K-1$ を入れ替えればよいのだが、そのことを思いつかなかった)。

コードはこちら

反転回数を数える。

先頭は必ず 0 なので、先頭が 1 なら No を返す。

操作Aを繰り返すと、 0101.. と、先頭が 0 で、 0 と 1 が交互に繰り返される。このような最長の列の長さが、操作Aの回数 $F$ である。 $F = N$ なら Yes を返す。

残り $A_i : i > F$ の数列について考える。上記の列で連続する 0 と連続する 1 の個数の和 $L$ (ランレングスでいうランの個数)に着目する。ただし末尾の連続する 0 は数えない。

• $L \leq F$ なら、操作Bの後に操作Aを行うことで、操作Bで末尾に追加した 0 を 1 にすることができる。不等号なのは、操作Aを連続すると二度反転して元に戻るから、多い分には構わないからだ。 Yes を出力する。
• 操作Bで末尾に追加した 0 にたいして、 $L > F$ になるような多すぎる反転はできない。 No を出力する。

公式解説をまだ理解できていません。

コードはこちら

括弧列だということはすぐ分かったが、二日掛かった。

緩和問題として、 $A$ には重複がないものとする。 $A$ の下位 $N/2$ 個に属する数の集合を $L$ 、上位 $N/2$ 個に属するの集合数を $U$ とする。

ここで括弧列を考える。 $A_{i} \in L$ なら $i$ 文字目を ( 、 $A_{i} \in U$ なら $i$ 文字目を ) とする。このとき $A_{1..N}$ が括弧列をなしているなら、すぬけ君は ) の数を取り、最小太郎君は ( を取らざるを得ない、という状況に追い込める。実はこのような状況は必ず作れて、答え $s = \sum U$ である。なぜなら ()()..() という () の繰り返しは常に構成可能で、 ( を左に寄せてもすぬけ君が有利になるだけだからである。

$k$ を求める。重複を考慮して1-based indexingで $A$ の下から $N/2$ 番目の数を $p$ とする。 $A_{1..N}$ について、

• $P_i = 1 if A_i < p$
• $P_i = 0 if A_i = p$
• $P_i = -1 if A_i > p$

とする。これを括弧列に対応させると、ある区間において、((累積和の最小値)が最大)になるような $k$ が答えである。セグメント木を使うと求まる。

• $C[i=1..2N] = \sum_{j=1}^i P_i$ とする
• $T[i=1..2N]$ を区間加算最小セグ木とし、初期値を $C$ とする
• ある $i$ についての値 は、 $V_i = T[i,i+N) - C[i-1]$ である

$V_k$ が最小となるような $k$ が答えである。

コードはこちら

繰上り

$i=1..N$ の途中結果を $A_i$ 、ビットマスク $m=A_i=2^{T_i}$ として、以下を繰り返すと解ける。最初は $A_0=0$ とする。

• $A_{i-1} < m$ なら、 $A_{i}$ の下位 $m$ ビットをすべて0に、 その一つ上のビットだけを1にして 10... とする。より正確には $A_{i}=m$ にする。
• $A_{i-1} \geq m$ かつ $A_{i-1} \land m = 0$ なら、 $A_{i}$ の下位から $m$ ビットをすべて0に、 その一つ上のビットを1に、他は $A_{i-1}$ と同じにして ???10... とする。より正確には $A_{i}= \lfloor A_{i-1}/2m \rfloor \times 2m + m$ にする。
• 上記以外なら $A_{i}$ の下位から $m$ ビットをすべて0に、 その一つ上のビットを1に、その一つ上のビットに1を足して (???+1)10... とする。より正確には $A_{i}= \lfloor (1+A_{i-1})/2m \rfloor \times 2m + m$ にする。

解説はもっと単純に場合分けしている。

コードはこちら

何日考えても分からず、青diffの厳しさを感じる。

$XN, X(N mod A) + Y \lfloor N/A \rfloor, X(N mod B) + Z \lfloor N/B \rfloor$ の最小値がまず思い浮かんだ。 $A,B$ を組み合わせて拡張GCDで $R= N mod GCD(A,B)$ を作り、 $N-R$ について同様に考えれば残りを網羅できるだろう、と思ったら入力例以外すべてWAになった。

正解は $X/1, Y/A, Z/B$ のお得度を使って平方分割だった。全く見当がつかなかった。

コードはこちら

一個ずつずらす。

$N \leq 2000$ より、 $T$ を $rot=1..N-1$ 回転したものについて答えを求めて、その最小値を求めればさそうである。

$T$ の $i$ 文字目を0-based indexingで扱う。左に $rot$ 回転して $T_{rot}$ を作った場合、回転前の $T$ の $i$ 文字目と $(i + rot) modN$ 文字目が対応する。よって $T$ の $(i + rot) modN$ 文字目を変更して両者一致させることを考える。すると今度は $(i + rot) modN$ 文字目と $(i + 2rot) modN$ 文字目が対応させる必要が出る。以下同様に繰り返して、いつかは $i$ 文字目に戻ってくる(鳩の巣原理より)。このループに出てくる文字の種類と、何文字出てくるかを数える。

例えば a が2文字、 b が1文字、 c が1文字なら、 a 以外を a にそろえるのが、最も文字の変更回数が少なくて済む。つまりループの長さから、最多出現回数以外の出現回数の合計だけ文字を変更すると、ループについて文字をそろえることができる。特にループ内の文字がすべて同じなら変更回数は0である。

これをすべてのループについて求めて合計して $M$ とする。 $M > K$ なら題意を満たさないので無視する。 $M \leq K$ なら題意を満たす文字列の置換方法が存在する。このとき $f(T_{rot})$ は $rot$ である。もしある $rot$ について $f(T_{rot}) < rot$ なら等号になるような $rot^{'}$ を別に見つけらから見落とすことは無い。このような $rot$ を見つけることができなければ、答えは $N$ である。

ループを構成するためには $rot$ は $N$ の約数でなければならない。公式解説はこの事実から出発している。他は公式解説と同じ解き方である。

コードはこちら

正規表現分割

AARCC という文字列があったとき、奇数回目の操作では ARC に、偶数回目の操作では AACC になる。奇数回目の操作では R の前後に $N$ 個の A と C があれば $N$ 回できる。偶数回目の操作をしたら、その後はどんな操作もできない。そのため偶数回目の操作を如何に先延ばしするか考える。

$S$ を正規表現で $A+RC+$ な文字列で分割する。正規表現を使わずに文字列をスキャンすると例外処理がややこしい。こうして連続文字列 $L_1, ..., L_M$に分割する。 $L_i$ が $a$ 個の A, $r$ 個の R, $c$ 個の C から成るとする。 $a = 0 \lor r \ne 1 \lor c = 0$ なら $A+RC+$ ではないので無視し、正規表現に当てはまる部分文字列が $M$ 個あるとする。

ある $L$ について、操作回数に $min(a,c) - 1$ 回の余裕がある。余裕回数の和が $E$ とする。 ARC を AC にするそれぞれ操作の前に、 ARC を R にする操作を差し込むことができる。よって最大で $M + min(M,E)$ 回の操作可能である。

Rubyなら String#scan を使って簡潔に 書ける 。以下に埋め込めるくらい短い。

t = 0
e = 0
gets
gets.scan(/A+RC+/).each do |s|
  t += 1
  e += [s.count("A"), s.count("C")].min - 1
end
puts [t*2, t+e].min

コードはこちら

ジグザグなのは分かったが、始点から $1,2,3...$ と始めたので答えが合わなかった。正しくは終点から $(N-1)..1$ または $(N-2)..1$ とする。