AGC lessons learned1

AtCoder Grand Contest lessons learned

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

AGC 002-A

コードはこちら

丁寧に場合分けする

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

AGC 002-B

コードはこちら

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

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

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

AGC 002-C

コードはこちら

逆から考える。

短いロープから順に結合して、最後に $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)$ から左右に結合すればよかった。

AGC 003-A

コードはこちら

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

AGC 003-B

コードはこちら

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である。視点が違った。実装は こちら 。

AGC 003-C

コードはこちら

最初に $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だけでよい。

AGC 004-A

コードはこちら

最小の断面

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

AGC 005-A

コードはこちら

括弧

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

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

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

AGC 006-A

コードはこちら

総当たり

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

AGC 006-B

コードはこちら

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

$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)$ である

AGC 007-A

コードはこちら

やはり総当たり

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

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

AGC 007-B

コードはこちら

$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$ だった。難しく考え過ぎである。

AGC 008-A

コードはこちら

対称性が無い

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

AGC 009-A

コードはこちら

非対称

ボタン $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$ である。

AGC 009-B

コードはこちら

トーナメントの決勝を根、初戦を葉として、根から葉までの深さを距離と定義する。題意を満たすつまりトーナメント木全体の深さを最小にするには、深い部分木を浅い頂点につなげればよい。これは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)$ で、その返り値が問題の答えである。

AGC 010-A

コードはこちら

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

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

AGC 011-A

コードはこちら

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$ と同様である。

AGC 011-B

コードはこちら

Union-find木でマージ

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

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

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

AGC 012-A

コードはこちら

上に寄せる

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

AGC 013-A

コードはこちら

三方比較

本当は整数を <=> で比較したい。間違って > で比較して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(横這い)にする

AGC 014-A

コードはこちら

やってみる

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

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

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

AGC 014-B

コードはこちら

オイラーツアー

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

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

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

AGC 015-A

コードはこちら

場合分けが大変

$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)$ 通り

AGC 015-B

コードはこちら

端まで行く

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

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

は2回乗る。

AGC 016-A

コードはこちら

決め打ち

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

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

AGC 016-B

コードはこちら

徹底して理詰め。

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な猫という表現で、上記と同じことを述べている。

AGC 017-A

コードはこちら

パリティ

偶数な $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のべき乗である。

AGC 017-B

コードはこちら

足し引きについて対称なので、最初に正規化する。つまり $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)$ である。

AGC 018-A

コードはこちら

最大公約数

$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)$ を直接使っている。

AGC 018-B

コードはこちら

まさか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)$ だった。

AGC 019-A

コードはこちら

単価で並べる

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

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

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

AGC 019-B

コードはこちら

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

AGC 020-A

コードはこちら

不変量

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

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

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

AGC 021-A

コードはこちら

入力例を見直す

入力例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が並ぶというのが、意外と実装が大変である。

AGC 020-B

コードはこちら

最後が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)$ ならそれが答え、そうでなければ解なしである。

AGC 022-A

コードはこちら

辞書順なら並べ替え

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

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

AGC 022-B

偶数を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)$ にする。

AGC 023-A

コードはこちら

累積和

$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 で求めて足すと答えが求まる。

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

AGC 023-B

コードはこちら

$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$ 倍したものが答えである。

AGC 024-A

コードはこちら

手を動かす

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

AGC 024-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} &lt; Q_{i}$ なら $L_i = L_{i-1} + 1$
• $Q_{i-1} &gt; Q_{i}$ なら $L_i = 1$

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

AGC 024-C

コードはこちら

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

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

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

AGC 025-A

コードはこちら

総当たり

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

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

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

AGC 025-B

コードはこちら

やはり総当たり

この問題は $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を持ち出したが使い道が無く、単に解答時間の無駄だった。

AGC 026-A

コードはこちら

ランレングス

同じ色のスライムが $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}$ のときにこれらに魔法を唱えるためである(色が連続したまま列が終わると魔法を唱えるのを忘れてしまうので、色違いで終わる)。

AGC 027-A

コードはこちら

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)$ である。

AGC 028-A

コードはこちら

条件がややこしい

解があるなら $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する。

AGC 029-A

コードはこちら

やってみる

白石の左に黒石が並んでいれば、並んでいる黒石の左端にその白石を置ける。並んでいないつまり左が白石なら何もできない。よって、既知の黒石の場所をカーソルとして覚えて置き、白石を左に寄せていく。 $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$ を操作回数に加算する

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

AGC 029-B

コードはこちら

実はgreedyで解ける。

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

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

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

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

AGC 030-A

コードはこちら

一つ多い

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

AGC 031-A

コードはこちら

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

AGC 031-B

コードはこちら

制約からDPだと思った。

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

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

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

AGC 032-A

コードはこちら

後ろから再帰

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

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

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

AGC 032-B

コードはこちら

手を動かす

とても時間が掛かったが、手を動かすと状況が見えてくる。例えば $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$ を除いて偶数個の場合を拡張している。

AGC 033-A

コードはこちら

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

AGC 033-B

コードはこちら

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

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

AGC 034-A

コードはこちら

どこで追い越すか

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

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

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

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

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

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

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

AGC 034-B

コードはこちら

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

AGC 035-A

コードはこちら

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$ が循環する

実装する と結構長い。

AGC 036-A

コードはこちら

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

他の二点を選び、外積 $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$ のときに必ず題意を満たす答えが見つかることが示されている。

AGC 037-A

コードはこちら

長考

解くのに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文字にすると考える。要するに最後の分割文字列をなかったことにして無視すればよい。

AGC 038-A

コードはこちら

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

AGC 039-A

コードはこちら

丁寧に場合分け

$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 &gt;= |S|$ つまり一周目と二周目をまたぐランがあるなら $(K-1) \lfloor len/2 \rfloor + K \lfloor (|S|+1-L)/2 \rfloor $
• それ以外は $K \lfloor len/2 \rfloor$

AGC 039-B

コードはこちら

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

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

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

AGC 040-A

コードはこちら

どこかで見た気がする

< $a_{i} &lt; a_{i+1} &lt; a{i+2} ...$ と連続するとき、 $a_{i}=0, a_{i+1}=1, a{i+2}=2$ と割り当てるのが最適である。逆に > $... &gt; a_{i} &gt; a_{i+1} &gt; 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$ の値が大きくなるなら更新しそうでないならそのままにする、という操作を行う。

AGC 041-A

コードはこちら

端に押し付ける

$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$ である。

AGC 041-B

コードはこちら

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

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

AGC 043-A

コードはこちら

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にしている。

AGC 046-A

コードはこちら

正N角形。

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

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

AGC 046-B

コードはこちら

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

AGC 047-A

コードはこちら

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

小数を整数部 $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しない)。この和が答えである。

AGC 048-A

コードはこちら

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

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

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

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

AGC 049-A

コードはこちら

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

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

AGC 051-A

コードはこちら

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

AGC 052-A

コードはこちら

実装を間違えたら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 &lt; i$ 文字目は 1 とする。このとき $[i+1,2N+i-1]$ 文字目には 1 を $N$ 個含み、 $[2N+i,4N]$ 文字目には 0 を $N$ 個含む。

AGC 053-A

コードはこちら

実は $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} &lt; B_{i+1,j}$ と定める。この数列は題意を満たす。なぜなら $B_i &lt; B_{i+1}$ の各要素に1ずつ合計 $k$ 増やして $B_{i+1}$ を作れば、 $B_{i,j} &lt; B_{i+1,j}$ になるからである。もっとたくさん増やすのは構わない。不等号が逆の場合も同様である。

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

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

AGC 054-A

コードはこちら

最初が肝心

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

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

AGC 055-A

コードはこちら

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

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

AGC 056-A

コードはこちら

手を動かすと解ける。

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

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

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

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

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

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

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

AGC 057-A

コードはこちら

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

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

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

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

このことから、 $W(L) + 1 &lt; 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$ である。

AGC 058-A

コードはこちら

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

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

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

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

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

AGC 060-A

コードはこちら

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

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

AGC 062-A

コードはこちら

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

AGC 063-A

コードはこちら

初手を考える。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する)。

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

AGC 064-A

コードはこちら

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

AGC 068-B

コードはこちら

正確な時間をはかりそこねたが、自力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$ の長さは制約を満たす。

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