ABC 350点問題に対策するため、ARCを解いてみます。

コードはこちら

$S[i], T[i], 1 \leq i \leq N$ について、 $d = T[i] - S[i]$ を求める。 $d$ が奇数なら $S,T$ とハミング距離が等しい $U$ を作ることはできないので -1 を出力する。 $d$ が負なら $S,T$ を入れ替えて $d$ の符号を入れ替える。

$U$ の作り方として、最初は $0$ で埋めて、 $S[i]=0, T[i]=1$ な $i$ について $U[i]$ を $d/2$ 個だけ $1$ にする。こうすれば、 $S,U$ のハミング距離も $T,U$ のハミング距離も $d/2$ になる。このような $i$ は文字列の末尾から $N..1$ 番目を探して該当する箇所から順に選べば、辞書順で最小になる。

コードはこちら

$\vec{i,P_i}$ という有向グラフは必ずループがあるので、ループ単位でまとめる。

要素が1のループつまり $\vec{i,i}$ は、 $A_i$ にどのような値を設定しても答えに影響しないので無視する。以下ループ長2以上のループ $L$ を、 $min(L)$ の昇順 $L_1, L_2, ... , L_K$ に並べる。特に $min(L_1) = 1$ である。

$L_1$ の要素数を $C_1 = |L_1|$ として、 $L_1 = (A_{1,1}, A_{1,2}, ..., A_{1,C_1})$ について考える。 $A_{L_1}$ の要素がすべて同じでなく降順なら、 $A_1$ を含むループ $L_1$ に基づく辞書順が $A < AP$ を決め、 $L_1$ 以外の要素は順位を決めないので任意とする。

このような降順の組み合わせは、先頭 $p$ が $M$ 通り, 先頭より小さい数が $p-1$ 通り、それ以外は任意となる順列組み合わせなので、 $M(M-1)/2 \sum_{j=0}^{C_1-2} M^{j}$ 通りである。 $L_1$ 以外の数は任意なのでこれに $M^{N - L_1}$ 通りを掛ける。

一般に $L_i : i=1..K$ について、 $min(L_i)$ より左は $A = AP$ で $A_{L_i}$ が $A < AP$ を決める状況を考える。 $L_i$ の順列組み合わせは、 $M(M-1)/2 \times \sum_{j=0}^{C_i-2} M^{j}$ 通りである。 $A_{L_{1..(i-1)}}$ をそれぞれ同じ数にそろえる方法が $M$ 通りずつ、計 $M^{i-1}$ 通りある。

$A_{L_{(i-1)..N}}$ は任意なので $R_i = \sum_{j=1}^{i} C_j$ として $M^{N - R}$ 通りある。併せて $M(M-1)/2 \times M^{N - R_i + i-1} \sum_{j=0}^{C_i-2} M^{j}$ = $M(M-1)/2 \times M^{N - R_i + i-1} (M^{C_i-1} - 1)/(M-1) = M^{N - R_i + i} (M^{C_i-1} - 1) / 2$ 通りである。

$i=1..K$ についての合計が答えである。

公式解説2は同じことをもっと簡潔に述べて、公式解説1は 閉じた式 である。

$1/2 \sum_{i=1}^{K} M^{N - R_i + i} (M^{C_i-1} - 1)$ = $1/2 (M^{N-C_1+1}(M^{C_1-1} - 1) + M^{N-C_1-C_2+2}(M^{C_2-1} - 1) + ... + M^{N-C_1-...-C_K+1}(M^{C_K-1} - 1))$ = $1/2 (M^{N} - M^{N-C_1+1} + M^{N-C_1+1} - M^{N-C_1-C_2+1} + ... - M^{N-C_1-...-C_K+K})$ = $(M^{N} - M^{K}) / 2$ から導ける。

コードはこちら

最も冗長な並び方は、これまで並んだ列から一つ椅子を空けて、一人または二人組が座る、という方法である。一人組はどこでも座れるが、二人組が座れるかどうかは列の後に空いた椅子が2つ以上並んでいるかどうかで決まる。列の長さ $len$ は $max(L, len + 1 + a_i)$ で更新し、空いた椅子は $L-len$ である。

公式解説も考え方は上記と同じだが、最後の組だけ考えている。

コードはこちら

今回も青diffはダメかと思ったらACした。

出発点はどうあれ、2人の旅人は以下の経路をたどる。そうでない場合は、出発点を後にずらし、終着点(出発点と同じ)も同じだけ後にずらすので、経過時間という観点からは変わらない。

• 2人は地点 $a_A$ にある休憩所で出会う。
• 2人は地点 $a_A$ を互いに別方向に出発し、地点 $a_B$ にある休憩所で出会う。 $A = B$ かもしれないし、そうではないかもしれない。
• 2人は地点 $a_B$ を互いに別方向に出発し、地点 $a_C$ にある休憩所で出会う。 $A = C$ かもしれないし $B = C$ かもしれないし、そうではないかもしれない。

地点 $B$ の候補は、 $A$ から西の端を折り返して距離 $L$ に達した付近である。つまり西の端から $L - a_A$ 前後の最大二か所である。移動距離の長い方が短い方を待ち、長い方の経過時間を求める。距離 $2L$ を休憩所で2分割して、分割後の差が最も小さくなるような休憩所を選ぶ、と言える。

地点 $C$ の候補は、 $B$ から西の端を折り返して距離 $L$ に達した付近である。つまり西の端から $L - a_B$ 前後の最大二か所である。二人の動きは対称つまりAntsと同じである。移動距離の長い方が短い方を待ち、長い方の経過時間を求める。

$a_A = a_1 .. a_N$ を決め打ちすると、 $B$ は2か所、 $C$ は 4か所なので、これらを総当たりすると最大経過時間が分かる。次に合流する地点の候補は std::lower_bound で見つかるので、計算量は $O(Nlog(N))$ である。

入力例2に相当する特別な場合として、 $a_i + a_j = L$ となる休憩所がある場合、 $A = C = a_i, B = a_j$ が成立し、2人は同時にこれらの地点に到着するので答えは $2L$ である。これがヒントになっている。

基本的に公式解説と同じ解き方である。

コードはこちら

4重ループ

$S_1=S_2$ , $S_5=S_6$ , $S_7=S_9$ , ${S_3,S_4,S_8}$ はそれぞれ 9,10,10,1000 通りなので全探索してからソートすればよい。

コードはこちら

遅延セグメント木だと思って一時間半溶かした。

遅延セグメント木ではない。行と列は独立した操作なので、行の操作だけ考える。実際に手を動かすと、偶数番目の手順と、奇数番目の手順が異なることが分かる。

0-based indexing で、奇数番目に $p$ 、その直後の偶数番目に $q$ のとき、元々 $0..(h-1)$ と並んでいたら以下のようになる。

• 奇数番目 : $p..0, (h-1)..(p+1)$
• 偶数番目
  • $q = p$ なら明らかに $0..(h-1)$
  • $q < p$ なら $q..p, (p+1)..(h-1), 0..(q-1)$
  • $q > p$ なら $q..(h-1), 0..p, (p+1)..(q-1)$

となるので、偶数番目は $(h + q - p)$ 回だけ左に回転するのと同じである。

よって奇数番目から偶数番目までの回転回数 $\sum_{i=1.. \lfloor Q/2 \rfloor} (a_{2i} - a_{2i-1})$ を足して回転した後、 $Q$ が奇数なら上記の操作をすると、元々の $0..(h-1)$ 行がどの行になるかが分かる。列も同様である。これから答えが求まる。

コードはこちら

数学

数字の組 ${C,D}, 0 \leq C < D$ と ${E,F}, 0 \leq E < F$ がある。 $CE + DF$ と $CF + DE$ のどちらが大きいだろうか。 $CE + DF - CF - DE = (D - C)(F - E) > 0$ より、 $CE + DF > CF + DE$ である。直観的には、大きい物同士の積と小さい物同士の積の和より、大きいものと小さい物を混ぜた方が小さくなるが、実際にその通りである。

なのでそれぞれの桁について $A$ に小さい数字、 $B$ に大きな数字を寄せ集めればよさそうである。 $A,B$ の $10^i$ 桁目の数字を $A_i,B_i$ としたとき、 $A \times B$ は以下の通りである。

$(A_{N-1}10^{N-1} + A_{N-2}10^{N-2} + A_{N-3}10^{N-3} + ...)(B_{N-1}10^{N-1} + B_{N-2}10^{N-2} + B_{N-3}10^{N-3} + ...)$

以下のように同じ桁を掛けた部分は $A,B$ の数字を入れ替えても変わらないので無視して、

$A_{N-1}B_{N-1}10^{2(N-1)} + A_{N-2}B_{N-2}10^{2(N-2)} + A_{N-3}B_{N-3}10^{2(N-3)} + ...$

以下のように違う桁だけ注目して、

$(A_{N-1}B_{N-2}+A_{N-2}B_{N-1})10^{2N-3} + (A_{N-1}B_{N-3}+A_{N-3}B_{N-1})10^{2N-4}+$ $((A_{N-1}B_{N-4}+A_{N-4}B_{N-1})+(A_{N-2}B_{N-3}+A_{N-3}B_{N-2}))10^{2N-5} + ...$

上の桁から $10^{2N-3}, 10^{2N-4}, ...$ の順に係数が小さくなるように、 $A,B$ の各桁を決めればよい。これは最初に述べた通り、 $A$ に小さい数字、 $B$ に大きな数字を寄せ集めればよい。

コードはこちら

有限オートマトン

$S$ と $T$ を構成する各文字の出現回数が異なるときは、一致させることはできない。 $S,T$ をそれぞれソートしたものが等しいかどうか調べれば分かる。

$S$ の末尾から連続する部分文字列 $U = S[L,N]$ を取って $T$ を作ることを考える。以下の条件を満たせばよい。

• 先頭を $T[1]$ にする。つまり $S[1,L-1]$ に少なくとも一つの $T[1]$ を含む
• $S[1,L-1]$ の各文字を $S_L$ 以降に挟み込める。つまり $T$ の連続しない部分列を $T$ の末尾から取ったときに、 $S[L,N]$ に一致する。

前半は累積和で求まる。後半は有限オートマトンで求まる(尺取り法ともいう)。 $T$ を末尾から一文字ずつ $S$ の末尾と比較する。より具体的には以下の通りである。

1. $T$ の文字を指すカーソル $C_t = N$ で初期化する
2. $S$ の文字を指すカーソル $C_s = N$ で初期化する
3. $T[C_t] = S[C_s]$ なら $C_s$ を一減らす。つまり $S$ の一致部分を一個増やす
4. 3の結果に関わらず $C_t$ を一減らす。つまり $T$ の次の文字を見る。
5. 3,4を $C_t = N..1$ まで繰り返す

$S$ を末尾から $M$ 文字取った部分文字列が、 $T$ を末尾から取った連続しない部分文字列と一致するなら、実際に $i=1..M$ 文字取ってみる。 $S[1..(N-M)]$ に $T[1]$ が含まれるならそのような取り方は可能である。このような $i$ について、 $N-i$ の最小値があるならそれが答えであり、そうでなければ -1 にする。

公式解説は二分探索で解いており、貪欲法とも書いてあるが、その貪欲法が上記の解答である。 $S$ と $T$ を構成する各文字の出現回数が同じなら解があることを公式解説では導いているが、私の解法ではそのことを仮定しない。

コードはこちら

5時間36分掛かった。

$S$ を反転したものと $R$ とする。 $K < N$ のとき、 $S$ の先頭 $K$ 文字を $S2$ とし、 $S2$ を反転したものと $R2$ とする。

$N = K$ なら $SR = RS$ なら Yes 、そうでなければ No である。

$N < K$ なら、 $SS^{'}$ について考えると $S^{'}$ の末尾 $N$ 文字は $R$ である。 $S^{'}S$ について考えると $S$ の末尾 $N$ 文字は $S$ である。このように $S$ の先頭から $SRSR...$ と、 $S$ の末尾に向かって $...SRS$ と埋めることができる。

周期 $C = \lfloor K / N \rfloor$ を考え、 $C$ の偶奇で場合分けする。 $r$ を、 $K$ を $N$ で割った余りとする。

$C$ が偶数のとき、 $SS^{'}$ は $C / 2$ 個の $SRS...$ 、長さ $r$ の文字列 $T$ 、 $C / 2$ 個の $..SRS$ からなる。同様に $S^{'}S$ は $1 + C / 2$ 個の $SRS...$ 、 $T$ 、 $C / 2 - 1$ 個の $..SRS$ からなる。 $T$ は $N,K,S$ から一意に決まるので、 $SS^{'}$ と $S^{'}S$ が回文かどうかは $T$ 周辺を調べると分かる。

$T = S[(N-r+1)..N]$ にする。 $TR$ が回文であることが $SS^{'}$ を回文にする必要条件である。 $RT$ が回文であることが $S^{'}S$ を回文にする必要条件である。両方の条件を満たせば Yes 、そうでなけば No である。

$C$ が奇数のとき、 $SS^{'}$ は $(C + 1) / 2$ 個の $SRS...$ 、長さ $r$ の文字列 $T$ 、 $(C + 1) / 2$ 個の $..SRS$ からなる。 $S^{'}S$ は $(C + 3) / 2$ 個の $SRS...$ 、長さ $r$ の文字列 $T$ 、 $(C - 1) / 2$ 個の $..SRS$ からなる。

$T = S[(N-r+1)..N]$ にする。 $RST$ が回文であることが $S^{'}S$ を回文にする必要条件である。 $T$ が回文であることが $S^{'}S$ を回文にする必要条件である。両方の条件を満たせば Yes 、そうでなけば No である。

$N < K$ なら、 $N$ と $K$ を入れ替え、 $S2,R2$ を $S,R$ に読み替えると同様の結果になる。

公式解説は、中央ではなく両端から決めることで $K < 2N$ の場合に帰着して簡潔に解を求めている。

コードはこちら

こちらは5時間ではなく30分で解けた。

絶対値を展開して数直線を書くと、 $f_{S}(x) = 0$ となるのは $a+b,a-b$ の二点で、両点から絶対値が1離れると $f$ が1増えることが分かる。つまり数直線において $f(x)$ の値は、0を最小値とするW字形になる。

初期値 $A,B$ とクエリ1の $a,b$ から $a+b,a-b$ を集合 $U$ に追加する。クエリ2において、区間 $[a,b]$ に $U$ の要素があれば答えは0、そうでなければ $c \in U \land (- \infty, a]$, $d \in U \land [b, \infty)$ について $min(a-c,d-b)$ が答えである(該当する $c,d$ が存在しない場合は無視するが、少なくとも一方は存在する)。これは std::set::lower_bound で求まる。

公式解説は上記と全く同じである。

コードはこちら

例外処理

典型例はすぐ分かるが、例外を網羅するのが難しい。

まず不変量として、表になっているコインの偶奇がある。なぜならコインを2枚裏返すと、表になっているコインの数は $-2,0,2$ 枚しか変化しないからだ。なので最初に表になっているコインが奇数個なら、コインをすべて裏向きにすることはできない。

コインが3枚かつ2枚が表のとき、 110 と 011 が無限ループするのでコインをすべて裏向きにすることはできない。

コインが4枚で 0110 のとき、 0011 , 1010 , 0000 の3回掛かる。これが分からなくて問題を解くのに1時間掛かった。全探索すればわかる。

上記以外ならコインをすべて裏向きにすることができ、基本的には表になっているコインの数の半分回である。ただし1回余分に掛かる場合があり、それは表になっているコインが2枚かつ並んでいるとき、つまり 11..., ...11..., ...11 のときである。なぜなら隣接するコインを同時に裏返すことはできないので、一度裏になっている端のコインと 1 を裏返し、表になった端のコインと残りの 1 を裏返すからである。

const std::string zeros{"0000"};

Num visit_dfs(const std::string& current, std::set<std::string>& seen, Num cnt) {
    if (current == zeros) {
        return cnt;
    }

    const size_t size = current.size();
    Num ans = 100000000;
    for(size_t l{0}; l<size; ++l) {
        for(size_t r{l+2}; r<size; ++r) {
            auto t = current;
            t.at(l) = (t.at(l) == '0') ? '1' : '0';
            t.at(r) = (t.at(r) == '0') ? '1' : '0';
            if (!seen.contains(t)) {
                seen.insert(t);
                ans = std::min(ans, visit_dfs(t, seen, cnt + 1));
                seen.erase(t);
            }
        }
    }

    return ans;
}

コードはこちら

組み合わせが大変。

MEXは、数値の集合に穴があれば一つずつ増やせる。つまり元の集合に $0,2,5,6$ が 無ければ、一操作ごとにこれらを一つずつ増やせる。 $i$ 回目に穴を埋めずに多重集合を増やすか、穴を埋めて $i+1$ 回目に多重集合を増やすか、両方の可能性について組み合わせを数える。

$i=1..K$ 番目の穴が $H_i$ のときを考える。 $H_1 = 0$ なら必ず0が埋まり、組み合わせは1通りである。それ以外の場合は以下の通りである。

• $i$ 回目およびそれ以降の操作で $H_i$ を埋めない。このとき多重集合は $[0..H_i)$ から $R = K - i - 1$ 回復元抽出する組み合わせなので、 $R+H_i-1 \choose H_i$ 通りである。これは $H_i$ 個の要素を $R - 1$ 個の仕切りで区切る方法である。
• $i$ 回目の操作で $H_i$ を埋める。このとき $i+1$ 回目の操作は $[0..H_{i+1})$ から $R = K - (i+1) - 1$ 回復元抽出する組み合わせである。

これを $i=1..K$ について足せばいいのだが、組み合わせの数を素で求めるとTLEするので、漸進的に求める。公式解説には階乗の前計算とあるが、慣れていないと大変である。

• ${n-1 \choose k} = {n \choose k} \times (n-k) / n$
• ${n+1 \choose k} = {n \choose k} \times (n+1) / (n+1-k)$

コードはこちら

ロジックアナライザ

Xを低電圧、Yを高電圧と考えると、XからY、YからXは電圧の遷移に見える。よってXからYへの遷移回数と、YからXの遷移回数の差は、高々1以下でなければならない。つまり $abs(b-c)>1$ なら No である。

問題文をよく読むと、入力は0以上である。つまり遷移が全くないことがある。遷移が無いなら低電圧と高電圧の両方を取ることはできない。よって $B=0 \land C=0 \land (A>0) \land (D>0)$ なら No である。

それ以外は Yes である。遷移しないつまり電圧が同じ(XX,YY)ことは、文字列の好きな場所に挟み込むことができる。

コードはこちら

優先度付けに苦しんだ。

YX...XY と両側を Y に囲まれた X が連続 $C$ 個並んでいるとする。このとき $i \leq C$ 個の X を Y に置き換えると Y が連続する箇所は何個増えるか考える。 $i \leq C$ なら $C$ 個、 $i = C$ なら $C+2$ 個増える。つまり短い $C$ を埋めきる方が、長い $C$ を埋めきるより、 Y が連続する箇所が増えてお得ということである。

両端つまり X...XY と片側が開いていて X が連続 $C$ 個並んでいるとする。 Y が連続する箇所は $i \leq C$ なら $i$ 個増えるので、埋めきったときのお得はない。つまり $K$ 箇所の X を Y に置き換えるなら、 両側を Y に囲まれた X を連続長が短い順に埋めて、最後に両端を埋めるのが最適である。

X の数 $D$ より $K$ が大きいときは、 $S$ をすべて Y にした後に $K - D$ 個の Y を X に置き換える。このときの操作は上記とは逆で、元々の $S$ について先に両端から Y を X に置き換え、その後に両側を X に囲まれた Y を連続長が長い順に埋めるのが最適である。

上記の優先度は、 X , Y のランレングスに優先度をつけて、 $prio,len,left$ として昇順に並び替えればいい。優先度 $prio$ (数字が低いほど高優先度)は以下の通りつける。ここで手こずってしまった。

• 両端の場合、 X なら $- \infty$ , Y なら $\infty$
• 両端以外の場合、 X なら $-len$ , Y なら $len$

コードはこちら

不変量

ARCは不変量が頻出で、いい不変量を見つけるとあっさり解けて、そうでないと解けないか実装が大変になるようである。今回は不変量を自力で思いつかなかったので公式解説を読んだ。こんなに短い コード になる。

不変量を使わない冗長な解法なら思いついた。数の差だけが重要なので増分を $[0,2,4]$ としても答えは変わらない。これを $[-2,0,2]$ としたのが公式解説と、そこから導ける不変量である。以下は増分を $[0,2,4]$ だと思って解く。テストケースを並び替えて、 $x_1 \leq x_2 \leq x_3$ としても一般性を失わない。

• 数の差、 $x_1-x_2$ および $x_2-x_3$ がともに偶数でなければ $x$ を等しくできない。 -1 を出力する。
• $x_1 = x_2 = x_3$ なら答えは0
• 上記でなく、 $x_2 = x_3$ またはなら $x_1$ に4を足して $x_2,x_3$ と等しくする。2回足すと6差が縮まり $x_1 = x_2$ にできる。なので $x_2 - x_1$ が6の倍数でなければ $x$ を等しくできない。6の倍数なら3で割った回数が答えである。
• $x_1 = x_2$ のときも同様である
• $(x_2 - x_1) < (x_3 - x_2)$ なら $x_1$ に4を、 $x_2$ に2を繰り返し足すことで $x_1 = x_2$ にできる。この回数は $(x_2 - x_1)/2$ である。あとは上記と同様に、 $x_3$ とそろえる。
• $(x_2 - x_1) \geq (x_3 - x_2)$ なら $x_2$ に4を、 $x_3$ に2を繰り返し足すことで $x_2 = x_3$ にできる。この回数は $(x_3 - x_2)/2$ である。あとは上記と同様、 $x_1$ とそろえる。

不変量を使わないと場合分けがとても大変である。

コードはこちら

ほぼ思いついたが6 WAsが取れなかった。

正の値、負の値の集合から、絶対値が大きい順に3つ、絶対値が小さい順に3つ、計24通り取って総当たりすれば解けると思った。のだが、どうしても6 WAsが取れずに諦めた。公式解説を読み、符号を無視して $1/x$ が大きい順に3つ、絶対値が小さい順に3つ取れば正解した。

コードはこちら

ワーシャルフロイド法

幅 $N$ の $A$ を繰り返したところで、頂点番号を $N$ で割った余りが等しければある頂点から他の頂点に到達可能かどうか、到達可能なら最小距離は変わらない。よって $A$ について頂点間の最小距離をワーシャルフロイド法で求める。

ただし頂点自身へは到達不能(距離は0ではなく $\infty$ )にする。そうしないと頂点番号がちょうど $N$ 離れている、 $\lfloor s/N \rfloor \ne \lfloor t/N \rfloor$ かつ $s \quad mod \quad N = t \quad mod \quad N$ のとき答えがおかしくなる(距離が0ではないのに0を返す)。

ここまでくれば、 $s=t$ なら答えは0、そうでなければ $s \quad mod \quad N$ から $t \quad mod \quad N$ までの最小距離が答えである。

コードはこちら

ほぼ解法は見えているのに数時間掛かってしまった。

$A = B$ なら答えは1である。以下 $A > B$ とする。

問題文中の $a,b$ を $a-gcd(a,b), b-gcd(a,b)$ に置き換えるのは、 $a/gcd(a,b)-1, b/gcd(a,b)-1$ に置き換えることにしても操作回数は変わらない。こうすると $a,b$ は互いに素と考えてよいので考察が簡単になる。

操作をそのまま実装するとTLEするので高速化を考える。 $d = a - b$ と置いて、 $d$ の1以外の約数の集合 $S$ を求める。 $f \in S$ について、 $a MOD f = b MOD f = r$ なら、 $a - r, b - r$ は公約数 $r$ を持つと言える。要するに操作で $a,b$ から1ずつ引くのではなく、まとめて $r$ 引くことができる。引きすぎないように最小の $r$ を求める。

このような $r$ が求まらない場合を考える。 $(a - b) > b$ つまり $a$ が $b$ の倍以上なら、 $b$ を $b - 1$ 引いて $a = 1$ にする。そうでなければ $b$ から1引く。これが分からなくて時間が掛かった。

これを繰り返し、 $b$ から引いた数を操作回数にすると答えが求まる。公式解説もこの通りだが、 $(a - b) > b$ の場合が書いてないように見える(もしかしたら明示的に書かなくても達成できるのかもしれない)。

コードはこちら

1時間と4分

解の方針は立ったが、Fenwick Treeのaddとsumを間違えて時間を溶かした。

$A$ に重複が無いというのは重要な制約である。これに気づくのが遅れた。 $A_1$ を $A_2..A_n$ と入れ替えることかどうか考える。 $i=1$ 、取りうる組み合わせ $M = N(N+1)/2$ で初期化する。

• $A_i > A_j : i < j$ な $j$ が $C_{low}$ 個であることをFenwick Treeで数える。 $C_{low} < K$ なら、 $A_j$ の $K$ 番目に小さい要素を見つけて $A$ の $[i,j]$ 間を逆順にする
• $A_i < A_j : i < j$ な $j$ が $C_{hi}$ 個であることをFenwick Treeで数える。 $M - C_{hi} < K$ なら、 $A_j$ の $K$ 番目に小さい要素を見つけて $A$ の $[i,j]$ 間を逆順にする
• それ以外なら $A_i$ を入れ替えないので、 $i$ を1足す。併せて、 $K$ に $C_{low}$ を足し(少なくともこの順位なので)、 $M$ から $C_{low} + C_{hi}$ を引く(順位の上限が下がるので)

この反復が停止したときが答えである。公式解説は $O(N^2)$ とあるが、Fenwick Treeを使うと $O(Nlog(N))$ の 3msec である。

コードはこちら

2日掛かった。夜解いてTLEしたので翌朝解いた。これだけ時間を掛けるとコンテスト中には間に合わない。

$x \leq y \leq z$ として一般性を失わない。上手く場合分けしたあと、計算量を減らして順列を数える。 $M = \lfloor \sqrt{N} \rfloor$ とする。

• $x = y = z$ は $x = 1..M$ で成り立つ。順列はそれぞれ1通り。
• $x = y < z$ は $z = (x+1).. \lfloor N/x \rfloor$ で成り立つ。順列はそれぞれ3通り。
• $x < y = z$ は $y = (x+1).. M$ で成り立つ。順列はそれぞれ3通り。
• $x < y < z$ を上手く数える。順列はそれぞれ6通り。

$x < y < z$ を $x,y$ の二重ループで数えるとTLEするので、計算量を減らす。結論から言うと、以下の $cumsum$ について、 $\sum_{i=1..M} cumsum(M) - cumsum(i)$ である。

• $cumsum(0) = 0$
• $cumsum(i+1) = cumsum(i) + N / i - i$

ここで累積和に足す $N / i - i$ は、 $i$ に掛けたら $N$ 以下になる $i$ より大きな数の個数である。

公式解説2と同じ解法だが、累積和は要らなかった。

コードはこちら

考えるより手を動かす。

同じ数字が何個並んだら、という規則性を見いだそうとしてWAした。 $A$ を昇順にソートし、前半 $\lceil n/2 \rceil$ 個の先頭からの隙間に、 後半 $n - \lceil n/2 \rceil$ 個を先頭から挟み込んでM字になるかどうか確かめる。

解法2を正答することができず27分掛かってしまった。解法2を実装すると こうなる が、 $N=1$ を特別扱いしないとWAする。

コードはこちら

変数の使いまわしに注意

入力した値 $N$ を最後まで変えない。ビット列を取り出すときに $N$ の値を右シフトして変えるとバグる。

$f(X)=3$ なので全パターン網羅すればいい。 $N$ が何ビット立っているかで、答えのどの3ビットを立てるか決める。最上位ビットは常に立っていることにする。

• $N<7$ なら解なし(-1)
• $f(N) \leq 3$ なら、上位ビットから順にから3ビット集めて立てる
• $f(N) = 1$ なら最上位ビットしか立っていないので、最上位ビットの一つ下の桁から3ビット連続で立てる
• $f(N) = 2$ なら、最上位ビットではない立っているビットの位置で分かれる
  • $N \quad mod \quad 3 > 0$ つまり下位2ビットがいずれも0でなければ、立っているビットより下位ビットに2ビット立てることはできないので、 $f(N) = 1$ と同じにする。
  • そうでなければ最上位ビット以外で立っているビットの、一つ下の桁から2ビット連続で立てる。最上位ビットも立てる。

あとは立てたビット位置3つから答えを求める( ビット $i$ を立てたなら $2^i$ を足す)。公式解説は3通りあり、上記は解法2である。解法1だと実装がもっと短く このよう になる。

コードはこちら

D問題なのに25分で解けた。

完全グラフの変数は $N(N-1) / 2$ である。よって $N(N-1)/2 < D$ つまり $N(N-1) < 2D$ なら解なしである。これは入力例2が重要なヒントになっている。

それ以外の場合は解がある。まず完全グラフつまり $N(N-1) = 2D$ で $G$ の密度が $N(N-1) /2N = (N-1)/2$ で の場合を考える。このとき $G$ から頂点を1つ除くと、除いた頂点の密度は0、それ以外の頂点は完全グラフで密度は $(N-2)/2$ になる。つまり頂点を除くと密度の低い完全グラフができるので、完全グラフは解の条件を満たす。

完全グラフ以外の場合、最初に正 $N$ 角形を考える。 $D = 1$ ならこれが答えである。なぜなら頂点を一つ除くと、除いた頂点の密度は0、それ以外の頂点からなるグラフはパスグラフで、密度は $(N-2)/(N-1) < 1 = D$ になり、以後操作するごとに頂点と密度は減るからである。

$D > 1$ の状況を考える。正 $N$ 角形において、距離 $d = 1..D$ の頂点同士を結ぶ。このようなグラフ $G$ から頂点を一つ除くと、除いた頂点の密度は0、それ以外の頂点からなるグラフの密度は $D(N-2)/(N-1) < D$ になり、以後操作するごとに頂点と密度は減るからである。

以上から解が求まった。公式解説と答えは同じだが、公式解説の証明はハミルトン閉路を用いている。

コードはこちら

線を描く

往路の順位と往復の順位を描くと、線が交わったり交わらなかったりする。交わらないというのは誰にも抜かれなかったことを意味するので、区間賞になりうる。つまり自分より遅く出発して、自分より早く着いた選手以外の数が答えである。

図を描いて、誰にも抜かれなかった(抜いたかもしれないし抜かなかったかもしれない)ときは垂直な縦線、抜かれたときは垂直線を左上から右下に横切る斜線を描くと分かりやすい。鉄道ダイヤグラムの急行と普通の関係である。公式解説通りに $O(N)$ 実装すると こちら

コードはこちら

不変量

解説を見ないと解の方針が立たなかった。1から順番に数を左から定位置を決めていく、末尾にあるときは二つ左に引っ張り出す、を繰り返せば解ける。不変量が重要で、解があるなら $A_{N-1},A_{N}$ だけが転倒しているという状況はありえないことを見つける必要がある。

実装方法は std::rotate が一番簡単である。定位置 $i$ に置くべき数が今どこにあるかは、表で管理しなくても std::find で都度見つけてよい( std::rotate が律速なので)。

ここまで考えなくても上記の通り実装して、 $A_{N-1},A_{N}$ だけが転倒したら No を出力すればよい。

コードはこちら

二分割だけ考える

単に分割する場所を総当たりすればよかった。難しく考えすぎてデバッグに苦しみ、30分以上掛けてしまった。狭義単調増加は std::string::operator< である。

コードはこちら

穴をボールに寄せる。

$A_1, A_2$ を1増減することと $A_{3..N}$ を1増減することは相対的には同じであり、 $A_1, A_2$ を増減する方が増減回数は同じか少ないのだから、常に $A_1, A_2$ を増減させればいい。

$A_1, A_2$ を増減させたときの値の候補は $A_{3..N}$ のいずれかが最適であり、それ以外の値にする意味は無い。よって $[A_1,A_2]$ を $[A_{3..N-M+1},A_{3+M-1..N}]$ にしたときの増減回数を総当たりで計算して最小値を求めれば、 $O(N)$ で答えが求まる。

• $A_1$ を $A_i$ にしたときの増減回数は $min(0,A_1-A_i)$ である。 $A_i \leq A_1$ なら $A_i$ を減らして $A_1 \leq A_i \leq A_2$ の範囲を拡大する。 $A_i > A_1$ なら既に $A_1 \leq A_i \leq A_2$ の範囲に居るので $A_1$ を増減する必要はない。
• $A_2$ を $A_{i+M-1}$ にしたときの増減回数は $min(0,A_{i+M-1}-A_2)$ である。理由は同様。
• よって $i=3..N$ を固定したとき、総増減回数は $min(0,A_1-A_i)+min(0,A_{i+M-1}-A_2)$

$A_1 > A_2$ でも上手くいく。

コードはこちら

3進数

$N=K$ なら明らかに Yes 、 $N < K$ なら明らかに No である。

冗長でない3進数、つまり各桁が0,1,2のいずれかである3進数で $N$ を表記して、すべての桁を足した和 $S$ を求める。 $S < K$ ならこの3進数が $N$ 未満になってしまうので答えは No である。

3進数を冗長にする、つまり各桁が3以上になることを認める。このとき冗長にすると、 $3^p \rightarrow 3 \times 3^{p-1}$ なので桁は一つ減って三つ増え差し引き二つ増える。つまり $S - K$ が偶数なら Yes 、奇数なら No である。

コードはこちら

ループ検出

ループを一周して、今いる頂点と異なる色に移動するのを繰り返すことができればよい。これはある出発点から、頂点と異なる色に移動するのを繰り返し、出発点の頂点と一周直前(出発点の隣)の頂点が同じ色ならよい(出発点の頂点の色は反転しているので)。

問題は、上記の条件を満たすループ検出を効率よく実装しないとTLEすることである。以下のようにDFSするとTLEしない。

• 出発点は頂点 $1..N$ をすべて試す。辺の数が少ないので問題ない。
• 最初の移動では、今いる頂点と同じ色に移動する。そうでないなら次の候補となる頂点を探す。
• 二番目以降の移動は、今いる頂点と異なる色に移動する。そうでないなら次の候補となる頂点を探す。
• 直前の頂点には戻らない(同じ色なので戻ることができない)。訪れたことの無い頂点を再帰的にたどる。
• ループを検出する、つまり一度訪れた点をもう一度訪れた場合、それが出発点なら上記の条件を満たす(DFSはtrueを返す)。そうでなければDFSはfalseを返す。
• DFSがtrueを返したらそれ以降の探索を打ち切って Yes を出力する。trueを返すケースがなければ No を出力する。

公式解説通り、union-find木を使うと簡単に 実装 できる。

コードはこちら

DPではなかった。

DPだと思ったがそうではなかった。Aliceにとっての最適反応は、裏返すとBobが最大損するカードを裏返すことであり、Bobにとっての最適反応は裏返されると最大損するカードを真っ先に取ることである(今取らなくても後で再度裏返しになって取れるようになるかもしれないが、今取っても損はしない)。

つまり現時点で 表の数字-裏の数字 が最大のカードをAliceはひっくり返し、Bobは取るのが最適反応である。

{表の数字-裏の数字, 表の数字, 裏の数字} を優先度キューに載せることで管理できる。

• Aliceは優先度キューの先頭、つまり表の数字-裏の数字が最大のカードを取って、裏返して優先度キューに載せる。 {裏の数字-表の数字, 裏の数字, 表の数字} を載せればよい。
• Bobは優先度キューの先頭のカードを取り除き、表の数字を得点として得る。

公式解説には $O(N)$ 解法があり、実装はとても簡潔である。この種の導出をする能力が私には足りない。

コードはこちら

13分掛かる。

灰色とは思えない難易度である。 $A_n$ の数が任意であることに注意する。このとき $A_i=N$ なる数があったら No 、そうでなければ Yes と予想できる。

$A_i=N$ となる数なしに $A$ の最小公倍数を $N$ にはできない状況を考える。 $N$ が素数なら約数は ${1,N}$ 、 $N$ の素因数が一つだけなら約数は ${p^{0..k}}$ 、前者は後者に含まれるので素因数が一つだけなら答えは No である。

そうでなければ $A$ の最小公倍数が $N$ になるようないい感じの $A$ を作れそうである。例えば素因数 $p_1,p_2,...$ が $c1,c2,...$ 個あるなら、 $A_1=p^{c1},A_2=p^{c1},...$ とする。これらの和はNより小さくなる( $A_1 \geq 2,A_2 \geq 3$ )からである。 $A$ の和が $N$ に足りない分をすべて $A=1$にすれば、最大公約数が $N$ であるまま $A$ の和を $N$ にできる。このとき答えは Yes である。

コードはこちら

3日間かかった。なんとなく方針は立ったが、エッジケースを詰めるのに時間が掛かった。

$K = 1$ なら入力がそのまま出力になる。以下 $K > 1$ とする。

$P$ の要素が $K$ 個連続で数が昇順なら( $P$ の各要素は一意なので)、その部分をソートすることで、入力がそのまま出力になる。よく考えたら $K = 1$ もこれに該当する。以下該当しない場合を考える。

ソートをちょうど1回するので、ソートすると $P$ の辞書式順序が下がってしまう場合でもソートせざるを得ない。小さな数をソートして手前に持ってくると損するので、仮の答えとして、ソートを最も遅らせる、つまり $(P_{N-K+1}, ... , P_N)$ をソートしたものを解の候補 $P^{'}$ とする。そうでない解を探索する。

ある $i$ に対して、 $(P_{i}, ... , P_{i+K-1})$ をソートするとき、 $M_i = min(P_{i}, ... , P_{i+K-1})$ として、 $P_i = M_i$ なら少なくとも $P_{i}$ についてはソートしても損しない。そうでなければソートすると $P$ の辞書式順序が下がってしまう。よってソートするなら、 $P_i = M_i$ を満たす $i$ があればそうしたい。

このような $i$ の集合 $S$ を求め、連続する $i$ をランレングス圧縮する。つまり $S = (A_1,C_1), ... (A_L,C_L)$ は、連続する $(A_1,...,A_1+C_1-1)$ が $S$ に属すると表現する。結論から言うと、 $max(A) = A_L$ として、 $(P_{A_L}, ... , P_{A_L+K-1})$ をソートした $P$ と $P^{'}$ の大きい方が答えである。

理由を考える。 $(P_{A_L}, ... , P_{A_L+K-1})$ をソートした $P^0$ と $(P_{A_L+1}, ... , P_{A_L+K})$ をソートした $P^{1}$ を比較する。 $P_{A_L}$ については $P^0$ と $P^1$ で等しい。 $P_{A_L+1}$ については、後者については $P$ の $P_{A_L+K}$ をソートすると前に持ってきてしまう、つまり $max(P_{A_L+1}, ... , P_{A_L+K-1}) > P_{A_L+K}$ なら $P^0 > P^1$ になる。 $P^0 = P^1$ はありえるが $P^0 < P^1$ にはならない。同様なことが $A_L + 1..(C_L-1)$ について言えるので、 $A_L$ を先頭にソートするのが最適解と言える。

公式解説は、論理的に探索区間を限定している。

コードはこちら

重実装すぎて解けなかった。

$Y$ で C な場所は $X$ でも C でなければならない(操作で C は作れないので)。 C で区切られた区間(終端に C が暗黙にあるとみなす)において、操作3で A を右に移動できる。ここまでは分かったが、 C から A, B をどう作るかが分からなくなった。

公式解説にある通り、 A はできるだけ左に、 B はできるだけ右に寄せて、 $X$ の A を $Y$ の A に移動できるか調べればいい。こう書くと簡単に見えるが実装が結構重い。順番に処理を書く。

1. $Y$ の C で区切ったランを作る。入力の $X,Y$ に C を追加しておくと、終端処理が楽になる。
2. $X,Y$ を先頭から走査して、 $i$ 文字目つまり $Y[i]$ が C 以外なら、 $X,Y$ の連続部分文字列の末尾に追加する
3. $Y[i]$ が C なら、 $X[i]$ が C 以外なら答えは No である。そうでなけば以下の処理を行う

• $X$ の連続部分文字列に出現する A,B,C の個数を $X_a, X_b, X_c$ とする
• $Y$ の連続部分文字列に出現する A,B の個数を $Y_a, Y_b$ とする
• $X$ の C を A に転換して、 $Y$ と同じ個数にする。 A　が足りないつまり $X_a < Y_a$ のままなら答えは No である。
• $X$ の C を B に転換する
• $X,Y$ の B の個数が一致しなければ答えは No である。
• $X,Y$ の先頭から $i$ 番目の B をそれぞれ、 $PX_i, PY_i$ とする。 $PX_i < PY_i$ となる $i$ があったら答えは No である。
• 上記以外なら答えは Yes である

コードはこちら

ある数 $A_i$ を、 $a b, c, lcm(a,b), lcm(a,c), lcm(b,c), lcm(a,b,c)$ のいずれに倍数するか考える。その上で $A_i$ をある数の倍数にしたとき、他の数の倍数も兼ねられるかどうかで場合分けする。

$N = 1$ なら $A_1$ を $lcm(a,b,c)$ の倍数にするしかない。答えは $\lceil A_i / lcm(a,b,c) \rceil lcm(a,b,c) - A_i$ である。以下略記法として、 $x$ を $m$ の倍数にするために必要な数を $r(x,m) = \lceil x / m \rceil m - x$ と表記する。

$N = 2$ なら $A_1, A_2$ ともに $lcm(a,b,c)$ の倍数にするして、 $max(r(A_1,lcm(a,b,c)), r(A_2,lcm(a,b,c)))$ が答えの上限である。他の候補として、 $A_1$ を $lcm(a,b)$ の倍数、 $A_2$ を $c$ の倍数にすることが考えられる。 $lcm(a,c)$ と $b$ , $lcm(b,c)$ と $a$ と置き換えてもよく、これらを総当たりする。求め方は後回しにして説明を続ける。

$N \geq 3$ ならさらに、ある数を $a$ の倍数、別の数を $b$ の倍数、さらに別の数を $c$ の倍数にできる。 $r(A_{1..N}, a)$ を求めて昇順に並び替え、ある $r$ の値になる $A_i$ の添え字 $i$ が分かるようにする( $r$ と $i$ の組 std::pair<Num,Num> をソートすればよい)。

基本的に $r(x,a), r(x,b), r(x,c)$ の小さい順から取ればいいが、同じ $A_i$ からは一度しか取れないという制限がある。よって $r(x,a), r(x,b), r(x,c)$ の下位3個同士を組み合わせて、 $A$ から重複なく3つ選べるならその組について $r$ を足せば、必要な操作回数になる。先に戻ると、 $N \geq 2$ なら $r(x,lcm(a,b)), r(c)$ などについて下位2個同士を組み合わせればよい。

このようなすべての組み合わせについて、最小の操作回数が答えである。この方法は公式解説の解法2と同じである。

コードはこちら

最小二乗法

美味しさの大きいトースト $2M-N$ 枚はそのままにする。残りのトーストを $2(N-M)$ 枚について、美味しさと小さいトースト $1..2(N-M)$ から順に美味しさの大きなトースト $2(N-M)..1$ ものと一緒に皿に載せる。

公式解説は、0をパディングすることで証明している。実装は こちら

コードはこちら

任意精度整数で通る。

除算切り捨てをmodintでする上手い方法が無いので、任意精度整数( boost::multiprecision::cpp_int )で解いた。最後に 998244353LL で割ってから long long int にする(int にしてから割ると間違える)。

$A$ を素因数分解し、素数 $P_i$ が $C_i$ 個あるとする。 $A^B$ を素因数分解したら、素数 $P_i$ が $B \times C_i$ 個ある。素数 $P_i$ に着目したとき、 $A^B$ の約数として素数 $P_i$ は $B \times C_i (B \times C_i + 1) / 2$ 個含み、 $P_i$ 以外の素数の組み合わせは $Q_i = \prod_{i \ne j} (C_j + 1)$ 個ある。

よって $P_i$ だけ考えると、 $A^B$ は $A$ で $\lfloor B \times C_i (B \times C_i + 1) Q_i / 2 C_i \rfloor$ 回つまり $\lfloor B (B \times C_i + 1) Q_i / 2 \rfloor$ 回割り切れる。ここで除算で余りが出ないことを保証できないので、modintではなく正確な値を求める。

全ての $P_i$ についての最小値が答えである。公式解法は、2で割る前の分子が奇数になる状況を導出している。

コードはこちら

転倒数になるのは連続する短調減少の中だけである。なぜなら短調減少が止まったら、その次の単調増加を十分高い値に増やすことで、それ以前の数より大きくできるからだ。公式解説は具体的な値を使っていて、考え方は同じである。

連続する短調減少が長さ $L$ なら、その転倒数は $L(L+1)/2$ である。これをそれぞれの連続する短調減少について数えて足すと答えになる。

コードはこちら

$A_i$ を対消滅できるならしておく(偶数個なら無かったことにし、奇数個なら1個にする)、普通のNimは $\oplus A$ が0以外なら先手必勝、までは分かった。なので $\oplus A$ が0で後手必勝のとき、ある $k$ で先手必勝にすればよい。

• $A_i$ が空なら 0
• $\oplus A \ne 0$ なら -1

しかし肝心なGrundy数を上手く定義できなかった。Grundy数の定義を公式解説通りに行うとACする。

コードはこちら

湧き出しを考える。

$1 \leq P_i < i$ から、 $i$ と $P_i$ は頂点1を根とする木構造の関係にある。このようなグラフを構築し、根からの距離 $0 \leq d < N$ を求める。

頂点1つまり根からもっと遠い頂点から無限に湧き出した値が、他の頂点に波及する。そこで $d$ が等しい頂点の値を足して $S_d$ を求める。 $S_d : d = N-1..0$ を順番に走査して、最初に正の値を見つけたら + 、最初に負の値を見つけたら - 、正負どちらも見つからなければ 0 を出力する。

考え方としては、最も $d$ が大きい頂点群の湧き出しが正または負なら、無限回では $P_1$ が正または負の無限大に向かう。0だったら次に $d$ が大きい頂点群の湧き出しを考える、というのを繰り返す。

コードはこちら

境界値がややこしい。

$f(x)$ について、右端 $R=x$ として区間 $[L,R]$ を考えた時に、 $\sum_{i=L}^{R} A_i \leq S$ なる $L$ を定められるとする。

• $L = 1$ なら、左端から $A_R$ まで足した和が $S$ 以下である。このとき、 $f([i,R])=1 : i=1..R$ である。 $f(x)$ の累積和を $g(x) = \sum_i f(i)$ として、 $g(x) = x : x=1..R$ である。
• $L > 1$ なら $f([i,R])=1 : i=L..R$ である。この部分について $g(R)=R-L+1$ である。さらに $i < L$ について、最後の一区間を加える対象が $1..(L-1)$ の $L-1$ 通りで、加えられる $f()$ の総和が $g(L-1)$ なので、 $R + g(L-1)$ である。

答えは $g()$ の総和である。 $L$ の求め方がややこしい。

コードはこちら

$i=1..N$ 文字目について、 $S,T$ で $i$ 文字目が異なる場所を記録する。より具体的には、 $S[i] = B \land T[i] = A$ な場所( Bを A にしたい場所)と、 $S[j] = A \land T[j] = B$ な場所( A を B にしたい場所)をそれぞれ記録する。

ここから尺取り法で求める。B を A にしたい場所( $i$ )と、 A を B にしたい場所( $j$ )のもっとも小さい添え字を初期値とする。併せて最も左の $i=left$ と最も右の $j=right$ をあらかじめ求めておく。

• $i$ が尽きたら、最左の $i=left$ について、 $k < left$ なる $k$ について $S_k$ を A から A に置き換える。そのような $k$ が十分たくさんなければ置き換えられないので -1 を出力する。そうでなければ残りの $j$ をすべて A から B に置き換える。
• $j$ が尽きたら、最右の $j=right$ について、 $right < k$ なる $k$ について $S_k$ を B から B に置き換える。そのような $k$ が十分たくさんなければ置き換えられないので -1 を出力する。そうでなければ残りの $i$ をすべて B から A に置き換える。
• $i < j$ なら、 $S_i$ を A で、 $S_j$ を B で置き換える操作をまとめて行い、次の $i,j$ に移る。
• $i > j$ なら、 $S_i$ を A に置き換え、 $i < k$ なる $k$ があれば B を B に置き換え、次の $i$ に移る。そのような $k$ がなければ置き換えられないので -1 を出力する。

$i$ を更新したら $left = min(left, i)$ に、 $j$ を更新したら $right = max(right, i)$ に更新する。

コードはこちら

遅延セグメント木

左右の幅は広く取りすぎても問題ない。つまり $(A_i,A_j,A_k)$ が等差数列なら、左側は $[1,i]$ 、右側は $[k,N]$ から任意の値を組み合わせられる。如何にもセグメント木で更新するとよさそうである。セグメント木には、 $i$ が取りうる最小の $k$ を記録する。

$(A_i,A_j,A_k)$ の値は 1..10 から総当たりする。すべての $i$ について、 $i$ が決まれば $A_i$ は一意に決まり、 $A_j$ を決め打ちすると $A_k$ の値が一意に決まるので、 $A_k$ となる最も小さい $j,k$ が求まる。これはあらかじめ 1..10 の出現位置を求めて置けば二分探索で求まる。 $[1,i]$ の最小値を $[k,N]$ との最小値で更新する。区間更新なので遅延セグメント木を使う。

公式解説2の方法に似ている。

コードはこちら

仮にルークを対角線上に置く。この配置はルーク同士が攻撃しあわないことを満たす。 $N \leq A$ ならポーンをすべて対角線上に置くことができる。 $N < A$ なら置くことができないので即座に No を出力する。

次にポーンを置くことを考える。横方向(列方向には) $N - A \geq 0$ 個置ける。ここで縦方向(行)を入れ替えることを考える。ルークが一個も無ければ横方向(列方向には) $N$ 個、行方向には一行目に一行飛ばしで $\lfloor (N+1)/2 \rfloor$ 行、計 $N \lfloor (N+1)/2 \rfloor$ 個置ける。

行を入れ替えて、可能な限り偶数行にポーンが無いようにすることを考える。このときポーンが無い行は $H=max(\lfloor (N+1)/2 \rfloor, N-A)$ 行作ることができる。よって $(N-A)H < B$ なら No を、そうでなければ Yes を出力する。

コードはこちら

入力例から察した。

解法が分からないので、入力例3を全探索した。以下の18通りの $P$ が挙がる。

2 6 7 1 3 4 8 5
2 6 7 1 3 5 8 4
2 6 7 1 4 3 8 5
2 6 7 1 4 5 8 3
2 6 7 1 5 3 8 4
2 6 7 1 5 4 8 3
2 6 7 3 1 4 8 5
2 6 7 3 1 5 8 4
2 6 7 3 4 1 8 5
2 6 7 3 4 5 8 1
2 6 7 3 5 1 8 4
2 6 7 3 5 4 8 1
2 6 7 4 1 3 8 5
2 6 7 4 1 5 8 3
2 6 7 4 3 1 8 5
2 6 7 4 3 5 8 1
2 6 7 4 5 1 8 3
2 6 7 4 5 3 8 1

何となく規則性が予想できる。 666, 888 のそれぞれ先頭2数が固定である。

$B_i < P_{B_i}$ のとき操作可能であることから、初期状態 $B_i = i$ において $B_i = i > A_i$ だと困る。同様に $B_i > A_i$ だと困るので、 $P_i \leq A_i$ であって欲しい。このような $P_i$ が何通りあるか求める。

• $i=1..N$ について、 $i = A_j$ となるような $A_j$ の集合 $G_i$ を求める
• $max(G_i) \ne i$ なら解なし(0通り)である。このとき $B_i = i > A_i$ になるからである。
• $max(G_i) = i$ なら
  • $|G_i| = 1$ なら特に対処しない
  • $|G_i| = S > 1$ なら、 $G_i$ の末尾以外をシフトして $P$ に設定する。 $G_i= [G_{i,1}, ..., G_{i,S}]$ として $P_{G_{i,j}} = G_{i,j+1} : j < S$ に固定する。

$|G_i| = S > 1$ なら、問題文にある操作を繰り返すと $G_i$ の先頭 $S-1$ 要素が $max(G_i)$ になる。

解ありのときに、固定していない番号に何通り選べるか求める。

• 初期値 $C_0=1$ とする
• $i$ について $P_i$ の選び方を $C_i$ 通りとする。ここで
  • $P_i$ が固定されていれば1通り
  • $P_i$ が固定されていなければ $C_i = i - seen(i) - cnt(i)$
  • $seen(i)$ は $P_1..i$ のうち、すでに固定された要素数。セグメント木に載せて $P_i$ を1増やす。
  • $cnt(i)$ は $P_1..i$ のうち、固定されていない要素数。 $P_i$ を固定していなければ1増やす。
• こうして求めた $\prod_{i=0}^N C_i$ が答えである。

上記はサイクル分解であり、公式解説もそのような方針である。公式解説は題意を上手くグラフの性質に言い換えている。

コードはこちら

Greedyで解ける。

チョコレートの長方形片の縦横の長さを $(PY, PX)$ とおく。一般性を失わずに $PY \leq PX$ と考えて構わない。最初は $(H,W)$ とする( $H > W$ なら $H$ と $W$ を入れ替える、以下同様)。

$A$ を降順にソートして、 $(L,L) : L = 2^{A}$ が長方形片に収まるかどうか調べる。収まれば収めた残りから新たな長方形片を作る。このとき長方形片を $(PY, PX)$ の降順にソートして(優先度キューを使う)、 $(L, L)$ が収まる長方形片を選ぶようにする。そのとき存在する最大の長方形片で構わない。 $L$ は2のべき乗に限るので、 $L$ を収められるなら $L/2$ も必ず収まる。

これを繰り返して、すべての $A$ を長方形片に収めることができたら Yes , そうでなければ No である。

$(PY,PX)$ に $(L,L)$ を収めた残りは以下のいずれかである。

• $(0,0) \quad if \quad PY = L \land PX = L$
• $(L,PX-L) \quad if \quad PY = L \land PX > L$
• $(PY-L,L), (PY,PX-L) \quad otherwise$

公式解説は、 $L$ が2のべき乗に限ることに注目してもっとエレガントに解いている。

コードはこちら

条件を満たさない文字列とは、 $s$ のある種の文字 $c$ を複数の場所から選べる文字列である。条件を満たすには、 $c$ を十分引き離して複数の場所から選べないようにする。 $c$ の位置を $W=N-K$ より多く離せばいい。

よって文字の選び方は以下の通りである。

• $s$ の 1文字目は $L$ 通り
• $s$ の 2文字目は $L-1$ 通り
• $s$ の 3文字目は $max(L-min(2,W))$ 通り
• より一般的には、 $s$ の $i$ 文字目は $max(L-min(i-1,W))$ 通り

これを掛けたものが答えである。 $L$ が足りないつまり選べる文字が尽きたときは、乗算結果が途中で0になるので答えは0である。

コードはこちら

添え字を一個間違えて諦めた。

不正解は こちら で、最後のループが一個足りない(2から始めているが正しくは1である)。ここさえ直せば正解できたが、解法に自信が無いと気が付かない。

公式解説にある通り、投票者1を挿入するのを全部試せばいい。別解として上記の通り、変化点を数えてもよい。

コードはこちら

桁DP

$K$ について、 Neq Numberが $K$ 個以下になるような $X$ を二分探索で求める。

最上位桁が非0 (leading zeroを除去した)な数 $Y$ を決め打ちする。 $DP[i][j]$ を

• 0..9 の任意の数を選ぶと $Y$ を超える可能性があるなら $i = 1$ , そうでなければ $i = 0$
• 今注目している桁が $j = 0..9$

とする。 $Y$ が $W$ 桁として、 $Y$ の各桁を上の桁から順に $D_{1..N}$ とする

まず最上位桁に設定できる数字 $P_1 \in [1..9]$ の取りうる組み合わせは、

• $P_1 < D_1$ なら、 $dp[0][P_1] = 1$ 。つまり下位桁を任意に 0..9 を組み合わせても $Y$ を超えない。
• $P_1 = D_1$ なら、 $dp[1][P_1] = 1$ 。つまり下位桁上手く選ばないと $Y$ を超えてしまう。
• 上記以外は0

である。次に最上位桁以外の上から $i$ 桁目に設定できる数字 $P_i \in 0..9$ の取りうる組み合わせ $next$ は、

• $P_i < D_i$ なら、 $next[0][P_i] = dp[0][P_{i-1}] + dp[1][P_{i-1}]$ 。つまり $Y$ を超えそうだったものも、今後は超えなくなる。
• $P_i = D_i$ なら、 $next[0][P_i] = dp[0][P_{i-1}], next[1][P_i] = dp[1][P_{i-1}]$ 。つまり $Y$ を超えないものは超えないままだし、超えそうなものは超えそうなままである。
• $P_i > D_i$ なら、 $next[0][P_i] = dp[0][P_{i-1}]$ 。つまり $Y$ を超えないものは超えないままだし、超えそうなものは選べない。

である。この条件下で、 $P_i \neq P_{i-1}$ な 0..9 の組み合わせ100通りを網羅して $dp$ を $next$ で更新する。

最上位桁を非0としたので、 $Y$ についての Neq Numberは、 $Y$ そのものについての上記の値と、 $Y$ より桁が小さく9が並ぶ数、つまり $(10^0 - 1), ..., (10^{W-1} - 1)$ についての上記の値の和である。このとき $Y$ の全桁が9の場合を二度数えないようにする(これで1 WAした)。

ここまで来たので、 $[1,10^{17}]$ について二分探索して、Neq Numberが $K$ 個以下になる最小の $Y$ を答える。

公式解説は、次の桁が9通りか0通りかどちらかしかないことを使ってDPを簡略化している。

コードはこちら

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

直線 $L$ にたくさん点が乗っていて、残りが $\lfloor N / 3 \rfloor$ 未満ならその点と $L$ の点を結ぶ。言われてみれば分かるが自力では分からなかった。

$(X,Y)$ と $(X+DX, Y+DY)$ を通る直線の一意な表現は、 $Y$ 軸の切片と傾きの有理数表現 $(SX, SY, DX, DY)$ にすると得られる。

• $X$ が変わらないつまり垂直、 $Y$ 軸に平行なら $(SX=X, SY=0, DX=0, DY=1)$
• $Y$ が変わらないつまり水平、 $X$ 軸に平行なら $(SX=0, SY=Y, DX=1, DY=0)$
• それ以外は $(SX=DX, SY=Y \times DX - X \times DY, DX=DX, DY=DY)$ 。ただし以下の変換を行った後である。
  • 傾き $(DX,DY)$ は $gcd(DX,DY)$ で割って、 $X$ が負なら $(DX,DY)$ の符号を反転する
  • $Y$ 軸の切片は $Y - X \times DY / DX$ なので、分母を掛けて整数にし、分母を $SX$ にする。

コードはこちら

茶diffに一時間半

$A$ を変えないのは $C = 0$ ではなく $C = 1$ である。この間違いに気が付かず1時間以上溶かした。

左右から要らない要素を削って残った連続列を $C$ 倍すればいい。 $l$ を決め打ちした解法は以下の通りである。 $A$ の総和を $S$ とする。 $A$ は答えの一つなので、それ以外の値を下記の通り探索して最大値を更新する。

• $C = 1$ なら、 $S$ が答えである
• $C > 1$ なら、 $l$ が固定なら $max [l,r] for r \in (l+1)..N$ となる $r$ を求めて、 $A_l..A_r$ を $C-1$ 倍したものを $S$ に加える。すべての $l$ についての最大値が答えである。
• $C < 1$ なら、 $l$ が固定なら $min [l,r] for r \in (l+1)..N$ となる $r$ を求めて、 $A_l..A_r$ を $C-1$ 倍したものを $S$ に加える。すべての $l$ についての最大値が答えである。

累積和をセグメント木に載せることで、区間の最大最小値が分かる。 $cumsum[l,r] = cumsum[1,r] - cumsum[1,l-1]$ なので、 $l$ を固定したときに $cumsum[1,r]$ を最大にする $r$ は $cumsum[l,r]$ も最大にする。最小値も然り。

コードはこちら

上記の緑とは打って変わって31分で解けた。

私の場合、ARCは解答時間のばらつきが大きい。解の方針は立ったが、場合分けを整理するのに時間が掛かってしまった。

買うレビューは星4,5しか意味が無い。星1,2,3を買っても平均評価を星3未満から星3以上に上げることはできないからだ。

$R = A_1 + A_2 + A_3 + A_4 + A_5$ , $S = 1 \times A_1 + 2 \times A_2 + 3 \times A_3 + 4 \times A_4 + 5 \times A_5$ とする。星4のレビューを $B_4$ 件買い、星5のレビューを $B_5$ 件買って、 $(S + 4 \times B_4 + 5 \times B_5) / (R + B_4 + B_5) \geq 3$ を達成したい。

これを式変形すると、 $(S + 4 \times B_4 + 5 \times B_5) \geq 3(R + B_4 + B_5) \geq 3$ から $B_4 + 2 \times B_5 \geq 3R - S$ を得る。整数不等式制約問題だが、2変数しかないので場合分けで解ける。判断基準は、星5は星4二つ分の価値があるか否かである。最低限買う必要がある価値を $V = 3R - S$ と置く。

• $V < 0$ ならそもそも星を買う必要はないので答えは0である
• $B_4 > B_5$ なら星4を買う意味はなく、星5だけ買えばいい。答えは $\lceil V/ 2 \rceil B_5$ である。
• $2 \times B_4 > B_5 \geq B_4$ なら星5で2価値を買い、1価値が端数なら星4を買う。答えは $\lfloor V / 2 \rfloor B_5 + (V mod2) B_4$ である。
• 上記以外、 $B_5 \geq 2 \times B_4$ なら星5を買う意味はなく、星4だけ買えばいい。答えは $V B_4$ である。

コードはこちら

実験したら21分で解けてしまった。A,B問題より速い。

解析解に見当がつかないので候補を列挙したら、 1, 80, 90-99, 100-109, 9800, 9900-10099, 998000, 999000-1000999, ... が見つかる。よって解 1 以外については、 $i=1..$ について $W_i = 10^i$ , $B_i = 100^i$ として、 $B_i-2W_i, [B_i-W_i,B_i+W_i)$ が解と予想できる。この通り実装したらACした。

公式解説には論証があるが、実験結果をそのまま実装するとACできることが前提だった。

コードはこちら

全く解ける気がしない。

最終形態を想定すれば解けることが分からなかった。出力例をみると、立っているビットは高々2つなので、2の階乗を2個足したものと気づけば解けたかもしれない。

最終結果は全員左側を取るか、全員右側を取るかどちらかしかない。どちらか決め打ちしてシミュレーションする。 $L,R$ のどちらが番号が増えるか問題文をよく読む。0-based indexing として、ここでは右手が $(p + 1) Mod N$ 、左手が $p Mod N$ である。

• 決め打ちした左右のスプーンをすでに取られていたら、0通りである
• ? のとき、決め打ちした左右のスプーンの反対側をすでに取られていたら LR を問わないので2通り、そうでなければ1通りである。
• LR は問題文通りに取って1通りである。その結果、後の人はスプーンが取れないかもしれない。

コードはこちら

入れ替え操作で、 $S$ に含まれる ( と ) の数を変えることはできない。よって置き換え操作が要る。 ( が $L$ 個、 ) が $R$ 個あるとき、 $L > R$ なら $(L - R) / 2$ 個の ) を ( に置き換える。このとき最左の ) から順に ( に置き換える。なぜなら ( が左にあるほど正しい括弧列を作りやすいからだ。同様に $L < R$ なら $(R - L) / 2$ 個の ( を右からから順に ) に置き換える。

後は ( と ) の不整合があれば置き換える。置き換え一回のコストは $min(A, 2B)$ である。 $S$ を左から順にみていき、正しくない ) の位置と、 ) との対応が取れていない ( の位置を記録する。その後、最左の正しくない ) の位置と、最右にある ) との対応を順に取っていく。

コードはこちら

諦めた。以下0-based indexingで説明し、 $(A,B)$ から1引いておく。

$(0,0)..(N-1,N-1)$ の斜め線をずらしながら $M$ 本引けばいいと分かったのだが、どういう訳か行列を上手く入れ替えて $(A,B)$ を拾わなければならないと思って解けなかった。

公式解説を読んだら、別に入れ替える必要なかった。 $(A,B)$ が重なるような $(0,N-1)..(N-1,01)$ の斜め線が重なるようなずれ方が求まる。 $ofs=(A+B)modN$ だけ左にずらせばいい。 $ofs$ が $M$ 個なければ、足りない分は空いているところを使う。

コードはこちら

$K+1 = M$ のときは、 $2^K$ で割る。よって $n \leq k$ なら割り切れるので0、そうでなければ $2^N mod 10$ である。

$K+1 < M$ のときは、2のべき乗以外で割るので、その方法を考える。

$2^N = 2^{N-M} (2^M - 2^K) + 2^{N-(M-K)}$ より、 $2^N$ を $M-K$ 桁減らして $2^{N-(M-K)}$ にできる。これを $2^N$ が2進数で $M$ 桁未満になるまで繰り返す。この繰り返しは、 $n < m$ なら $C=0$ 回、そうでなければ $C = \lceil (n - (m - 1)) / (M-K) \rceil$ 回である。答えは $2^{N - C(M-K)} mod 10$ である。

コードはこちら

久しぶりのARC 灰diffである。

大は小を兼ねる。つまり500円硬貨は100円硬貨を兼ね、100円硬貨は50円硬貨を、50円硬貨は10円硬貨を、10円硬貨は5円硬貨を、5円硬貨は1円硬貨を兼ねる。よって大きな金額から順に使い、足りなくなったら小さな金額で払うようにすればよい。こうすれば大きな金額でお釣りが必要な場面が、小さな金額でお釣りが要らない場面より後に来ることは無くなる。

後は買い物の順番について順列組み合わせを全部試せばよい。と思ったら、順列は関係ないことが公式解説で分かった。

コードはこちら

ものすごく久しぶりのARC B問題 灰diffである。入力例の妥当性を確かめずに10分以内に提出してACした。

1-based indexingで、最右にある1が $i$ 番目にあるとする。操作 $A$ を $i$ 回、操作 $B$ を $i-1$ 回実行すると、初期状態から $i$ 番目だけを1、それ以外を0にできる。

この要領で、最右にある1から順に0から1に変えればよい。操作回数は高々 $N^2$ 回なので、 $10^6$ 回には十分間に合う。公式解説と同じ解き方である。

コードはこちら

緑diffが解けた。

左上から右下への経路と、左下から右上への経路は、少なくとも1マスを共有する。なぜならマスを共有しない経路は構築不可能だからだ。

そこで四隅からの他のマスへの距離を01-BFSで求める。ここで距離とは、始点とは色が違うマスの数である。始点は制約から距離0とし、終点のマスの色は 数えない 。その手前までの距離を記録する(うっかり実装を間違えたのだが実は正解だった)。

こうすると、それぞれのマスから四隅への距離の和 + 1が、あるマスを共有したときに紫色に変えなければならないマスの最小数である。+ 1したのは共有するマスは必ず紫にしなければならないからだ。あとは四隅を含めてすべてのマスについてこれらの値を求め、最小値が答えである。

公式解説を見たら、2経路で共有するマス云々を考える必要はない、なぜなら赤から紫に変えるのと青から紫に変えるのは独立な事象なので、と分かった。これをとっさに思いつくことができない。

コードはこちら

題意を読み解くのがかなり大変である。

$A$ を昇順に並べる。 $A_1 = 1$ なら解なしなので -1 を出力する。ここから $A$ に沿って実際に手を動かしてみる。

$2 \in A$ のとき、連続列 $[1,2]$ を崩すには間に 3 を挟んで $[1,3,2]$ にすればよい。 $2 \notin A$ のとき、連続列 $[1,2]$ を崩す必要なく、解は辞書順なので先頭から $[1,2]$ を並べる。

$3 \in A$ のとき、連続列 $[1,2,3]$ または $[1,3,2]$ を崩すには間に 4 を挟めばよい。辞書順で最小なので 4 を3番目に置けばよい。 $3 \notin A$ のとき、連続列を崩す必要ない。

ということは $B = [1..N]$ を先頭からみていき、 $i \in A$ なら $B_i$ と $B_{i+1}$ を入れ替える。ただし $i = N$ なら入れ替え不能なので -1 を出力する。こうしてできた $B$ が答えなので出力する。

公式解説の一番下にある方法と同じである。よく見たら、 $N \in A$ のときも即座に解なしとしてよかった。

コードはこちら

ARC 水diffには珍しく(?)、鋭い発想もエッジケースの考慮も必要なくて丁寧な数え上げで解ける。

$A_{1} = A_{2}$ と $A_{1} < A_{2}$ で場合分けする($A_{1} > A_{2}$ なら互いに入れ替える)。 $A_{2} < A_{3}$ なら桁が足りず、 $A_{2} + 1 < A_{3}$ なら桁あふれで解なしである。

$a = A_{1} = A_{2} = A_{3}$ の場合を考える。例えば $a = 3$ なら、 $100+100..999, 101+ 100..998, ..., 899+100$ である。これを一般化すると、 $d = 10^a - 2 \times 10^{a-1}$ として $\sum_{i=1}^{d} i = d(d + 1) / 2$ である。

$a = A_{1} = A_{2}, A_{3} = a + 1$ の場合を考える。 $a$ 桁の数と $a$ 桁の数を足しても $a$ または $a+1$ 桁にしかならないので、 $A_{1},A_{2}$ の組み合わせの総数 $(10^a - 10^{a-1})^2$ から上記の値を引けばいよい。

$A_{1} < A_{2} = A_{3}$ の場合を考える。例えば $A_{1} = 1, A_{6} = 5$ なら、 $1+100000..999998, ... , 9+100000..999990$ である。これを一般化すると、 $lower = 10^{A_{2}} - 10^{A_{2}-1} - 10^{A_{1}} + 1, upper = 10^{A_{2}} - 10^{A_{2}-1} - 10^{A_{1}-1}$ として、 $\sum_{i=lower}^{upper} i = (lower+upper)(upper-lower+1)/2$ である。

$A_{1} < A_{2} = A_{3} - 1$ の場合を考える。 $A_{1}$ 桁の数と $A_{2}$ 桁の数を足しても $A_{2}$ または $A_{2}+1$ 桁にしかならないので、 $A_{1},A_{2}$ の組み合わせの総数 $(10^{A_{1}} - 10^{A_{1}-1})(10^{A_{2}} - 10^{A_{2}-1})$ から上記の値を引けばいよい。

補集合の考え方も含めて、公式解説1とだいたい同じである。上記を $A_{1} \leq A_{2}$ とまとめてよかった。

コードはこちら

38分と3ペナである。

累積和の先頭が0というのが壁になる。まず昇順に並べてみる。このとき累積和は

• 先頭が0
• その後 $X$ に負の値があるなら累積和が負になる
• その後累積和は正になるかもしれない

である。 $K > 0$ のとき、累積和が正になるなら適当な $K$ を選んで条件を満たすことができる。よって $X$ の昇順が答えである。

$K < 0$ のときは累積和の最小値を求めればいい。昇順の累積和の最小値だと思ったらWAした。降順の累積和の最小値を求めればよく(累積和が負にならなさそうなものから選ぶので)、これは $S = \sum X$ である。よって $K \leq S$ なら $X$ の降順が答えである。

どちらでもなければ解なしなので No を出力する。

コードはこちら

解法はすぐ思いついたが、詰めに時間が掛かった。 $M$ が小さいので $2^M$ のビット全探索だろうと思った。実際その通りである。

以下 $1..M$ の整数を、0-based indexingで考えて $0..(M-1)$ とする。 $X$ の読み方を逆にする。つまり $B$ の間に $X_B$ が存在するのではなく、 $A$ に $B$ を置いたら $B$ を置けなくなり、 $X_B$ を置いたら $B$ を置けると考える。ある $B$ について $B = X_i$ となる $X_i$ の添え字 $i$ の集合を $S_B$ と置く。この添え字も0-based indexingにする。

$DP[i=0..N][s=0..(2^M-1)]$ は、 $A$ を長さ $i$ まで決めたときに、 $j=0..(M-1)$ を置けるかどうかの状態 $s$ になる $A$ の並べ方が何通りあるか、という定義する。 $s$ のビット $j$ が0なら $j$ を置くことができ、ビット $j$ が1なら $j$ を置くことができない。便宜上 $DP[0][0] = 1$ として $A_1$ は何でも置けるようにある。

DPの状態遷移を定める。 $DP[i][s]$ のビット $j$ が1なら $A_{i+1}$ に $j$ を置くことはできない。 $DP[i+i][s]$ のビット $j$ が0なら $A_{i+1}$ に $j$ を置ける。遷移先の状態 $u$ は、状態 $s$ のビット $j$ を1にして(置けないので)、 $\forall k \in S_j$ のビット $k$ を0にした(置けるようになるので)ものである。こうして $DP[i+1][u]$ に $DP[i][s]$ を足す。

$X_i$ はまた置けるようになる数字を示しているという考え方も含めて、公式解説とだいたい同じである。

コードはこちら

解法は早めに思いついたが、昇順の $A_1, ... , A_N$ に挿入する際に、先頭の前と末尾の後に挿入するときのバグがなかなか取れなかった。

$2..1000$ を二分探索する回数は以下の通り8977回なので、2倍して $N$ 足しても25000回制限は超えない。よって $A_{1..(2N-1)}$ の位置を二分探索する。

sum(purrr::map_dbl(2:1000, ~ ceiling(log2(.x))))
# 8977

$A_{1..N}$ の順番を確定させる。 $A_{P_1} \leq A_{P_2} \leq ... \leq A_{P_N}$ となるような $P_{1..N}$ を求める。これは以下の繰り返しで求まる。 $P$ の保持に std::vector を用いたとしても、 $\sum_{i=2}^{N} i = 500499$ なので、 std::vector に添え字で insert/erase して要素数に比例する計算時間が掛かってもTLEしない(96 ms)。

• $A_1 < A_2$ かどうか比較する。
• $i > 2$ について、 $A_{P_j} \leq A_i \leq A_{P_{j+1}}$ を満たすような $j$ を二分探索で求める。 $A_i \leq A_{P_{1}}$ または $A_{P_{N}} < A_i$ の場合も考慮する。この実装に時間が掛かってしまった。

$i > N$ について、 ある時点の $A$ を昇順に並べた時に、最小要素 $b=A_{P_1}$ と最大要素 $c=A_{P_{|A|}}$ を足して $A_{P_i} = b+c$ にする。これは $R$ がどんな値であっても題意の制約を満たす。

• $-R \leq b \leq 0 \leq c \leq R$ なら $-R \leq b+c \leq R$ である
• $0 \leq b \leq c \leq R$ なら $\sum_{i=1}^N A_i \leq R$ より、 $0 \leq b+c \leq R$ である
• $-R \leq b \leq c \leq 0$ なら同様に $-R \leq b+c \leq 0$ である

つまり $i > N$ 番目の要素 $A_{P_i} = A_{P_1} + A_{P_{|A|}}$ を作り、 $A_{P_1}, A_{P_{|A|}}$ を除いてから、上記の要領で $A_{P_i}$ を挿入する。これらをクエリとして入出力すると答えになる。

想定解法はマージソートだった。 std::vector に添え字で insert/erase すると要素数に比例する計算時間が掛かることを承知で、C++の力でごり押した感がある。

コードはこちら

B問題以降が難しすぎて、これがratedなら1完でもレーティングが上がった可能性がある。

ABA が A 、 BAB が B 、ということは、文字列に A と B の入れ替わりが2つ連続すればまとめて削除できる。よって連続する文字の入れ替わりが $L$ 回あったとして $\lfloor L/2 \rfloor$ 回削除できるので、 $1 + \lfloor L/2 \rfloor$ 通りの文字列を作れる。異なる連続部分は独立なので、それらの積(連続部分がなければ1)が答えである。

公式解説も方針は同じだが、使っているテクニックは驚きである。

コードはこちら

全く見当がつかなかった。

$i=1..N$ を定位置に置くのが最適解だと思ったが、上手く証明が思いつかなかった。公式解説1は $i=1..N$ の順に定位置に 置き 、公式解説2は $i=N..1$ の順に定位置に 置く 。

コードはこちら

丁寧に場合分けすればいいが、途中で実装が分からなくなって47分掛かった。

• $P = (1,...,N)$ なら答えは0
• $P = (1,...)$ または $P = (...,N)$ なら端以外をソートして答えは1
• $P = (N,...,1)$ なら、 $P[1,N-1]$ をソートして左端の $N$ を押し出す、 $P[2,N]$ をソートして右端の $1$ を押し出して $N$ を右端に収める、 $P[1,N-1]$ をソートして答えは3
• 上記以外で $P = (N,...)$ または $P = (...,1)$ なら、 $P[1,N-1]$ をソートして左端の $N$ を押し出す、 $P[2,N]$ をソートして右端の $1$ を押し出して $N$ を右端に収めると答えは2

上記以外は、ある添え字 $i$ があり、左右をソート済に分割できるかどうか調べる。左側 $P(1..i-1)$ に $1..i-1$ が1個ずつあり、右側 $P(i+1..N)$ に $i+1..N$ が1個ずつあるなら、分割可能と言える。これはFenwick treeで求まる。分割可能な $i$ があれば答えは1、そうでなければ $1,N$ の順に定位置にそろえて答えは2である。

公式解説によれば、分割可能かどうかは累積min,maxで求まる。分割可能でなく、 $P = (N,...,1)$ なら答えは2、と簡潔にまとまる。

コードはこちら

TLE解しか思いつかなかった。

自明な場合は分かるが、そうでないときに $S |X|$ から $T$ を総当たりで求める方法しか思いつかなかった。

$X$ に含まれる $0$ の数を $X_0$, $X$ に含まれる $1$ の数を $X_1$, $Y$ に含まれる $0$ の数を $Y_0$, $Y$ に含まれる $1$ の数を $Y_1$ とする。

• $X_0 = Y_0 \land X_1 = Y_1$ なら $S=T$ とすれば解の条件を満たすので Yes
• そうではなく、 $X_0 \neq Y_0 \land X_1 = Y_1$ ならどんな $T$ を選んでも $S$ の繰り返しを一致させることができないので No
• そうではなく、 $(X_0 - Y_0)(X_1 - Y_1) > 0$ なら、 $S$ (空ではない)と $T$ をどう選んでも、 $X$ または $Y$ について $S$ または $T$ の繰り返しが余分なので No

上記以外では $|T| = |S|(X_0 - Y_0) / (X_1 - Y_1)$ である。 $|T|$ が整数でなければ No である(公式解説にある通り上記3を $|T| < 0$ なら No と言い換えてもいい)。ここから先が分からなかった。

コードはこちら

何時間考えても分からず諦めた。

解き方は公式解説にある通りである。DPで解こうとして結局解けなかった。出力例3が2の60乗と分かったのを大事にすべきだった。

制約から解き方を察する。クエリ $Q_i = (P_i, V_i)$ について、過去のクエリ $Q_{j=1..(i-1)} = (P_j, V_j)$ と帳尻を合わせる。

• すべてのクエリについて、左右どちらにもできると初期化する
• $V_i \leq V_j$ なら、クエリ $Q_i$ はどうしてもよい
• $P_i = P_j$ なら、クエリ $Q_i$ を左右どちらにしても $Q_j$ と衝突が避けられないので、答えは0である
• $P_i < P_j$ なら、クエリ $Q_i$ を左、 $Q_j$ を右に固定する。逆に言うと、 $Q_i$ を右に置けない、 $Q_j$ を左に置けないと設定する。これらは上書きして構わない(制約が厳しくなる方にしか行かないので)。
• $P_i > P_j$ なら、 $Q_i$ を左に置けない、 $Q_j$ を右に置けないと設定する

全クエリを処理して、取りうる組み合わせ(左右どちらでもなら2、左右どちらか一方なら1、左右どちらも不可なら0)の積が答えである。

コードはこちら

A問題より易しい。ペナルティの山を築きつつ52分で解いた。問題選びがとても重要である。

制約から $A / 2^K \leq 0$ になるので、0は必ず作り出せることが分かる。それ以外の数を作り出す方法を考える。

$A$ 自身は $A / 2^0$ から作り出すことができ、 $0..2^{K-1}$ は $\lfloor A/2^{1} \rfloor$ から作り出すことができる。よって $2^{K-1} \leq N$ なら、 $0..(2^{K}-1)$ のすべての数を作り出すことができる。出力する長さは $N$ でなければならないので、 $1..(2^{K}-1)$ をラウンドロビンで出力するなりして長さを調整する。

$2^{K-1} < N$ の時を考える。 $A$ を $0..(2^{0..K})$ で割るということは、 $A$ の下位桁(LSB側)が無くなって上位桁(MSB)が残るということである。よって $A \geq 2^{K-1}$ として、 $A - 2^{K-1}$ の上位桁を 0,1,00,01,10,11,000,001,010,011,1000,... という順番で残す。バイナリツリーをBFSして根から各頂点までのパスを列挙する、という雰囲気である。具体的には、キューを使って $A$ を最大 $N$ 個生成すればよい。

• キューの初期メンバは組 $(2^{K-1}, K-2)$ とする。これは $2^{K-1}$ のビット $K-2$ (LSBを0と数える)を操作するという意味である。併せて、 $A = { 2^{K-1} }$ とする。
• キューから $(V,P)$ を取り出したら、 $A$ に $V + 2^{P}$ を追加する。要するにビットを立てた値を $A$ の新たなメンバとする。その後 $(V,P-1)$ と $(V + 2^{P}, P-1)$ をキューに入れる。
• これを $|A| = N$ になるまで繰り返す。 $2^{K-1} < N$ なのでこの操作はいつか止まる。

上記は公式解説2の上のbitから構成する方法である。ビット反転してもよかった。

コードはこちら

桁DPかと思ったら入力例通りだった。

$N$ が偶数のとき、先頭の桁が $N/2$ のgoodな整数列と先頭の桁が $1+N/2$ のgoodな整数列は同数である。よって先頭の桁が $N/2$ で、それ以降が最も辞書順で大きい整数列を出す。これは $1..N$ が $K$ 個ずつ(ただし $N/2$ は $K-1$ 個)の整数列を降順にソートすると得られる。

$N$ が奇数のとき、 $H = (N+1)/2$ と置く。 $H$ が $K$ 個、 $H-1 > 0$ なら $H-1 > 0$ が $1$ 個、それ以降が最も辞書順で大きい整数列を出す。

コードはこちら

やはり600点問題は厳しく、翌日2時間38分掛けて解いた。

硬貨 $1..N$ を隣同士 $2i-1,2i$ で比較する。

• 異種なら一方が本物、一方が偽物なので、後で判定するよう $i$ を $D$ に保存しておく。
• 同種なら両方とも本物もしくは両方とも偽物なので、union-find木でマージして代表元を $L$ に保存しておく。このときunion-find木における $size(x)$ を、 $x$ が属する集合の大きさとする。

$|D| = M$ なら、 $D$ の要素でない硬貨はすべて本物であり、それらと比較すれば答えが出る。

$|D| < M$ なら、 $L$ を要素数の昇順に並べて、両端 $L_l, L_r$ から比較する。 $l = 1,2,...$, $r = |L|,|L|-1,...$ として 候補 $L_l, L_r$ を比較する。比較結果を基に、候補の代表元を $S$ 、偽物の硬貨の集合の代表元を $U$ として更新する。

• $l = r$ なら、その要素を後で比較することにして、 $S$ に $L_l$ を追加して比較を終了する。
• $Z = M - |D| - |U| < size(x)$ なら、 $x$ を代表元とする集合はすべて本物の硬貨である。よって $size(L_1) > Z \land size(L_r) > Z$ なら、両方とも本物なので、クエリを投げることなく $L_1$ と $L_r$ をマージして $S$ に追加する。
• そうでなければクエリを投げる
  1. 同種なら $L_1$ と $L_r$ をマージして $S$ に追加する。
  2. 異種かつ $size(L_l) > Z$ なら、 $L_r$ を代表元とする集合はすべて本物の硬貨でなので、 $U$ に追加する
  3. 異種かつ $size(L_r) > Z$ なら、 $L_l$ を代表元とする集合はすべて本物の硬貨でなので、 $U$ に追加する
  4. 上記以外なら本物か偽物かはまだ分からないので、 $L_l, L_r$ を $S$ に追加する。

一通り $L$ についてみたら、 $S$ で $L$ を置き換える。これを $L$ が一要素になるか、 $M - |D| - |U| = 0$ になるまで繰り返す。 $M$ が $N$ よりとても少ないので、いつかは本物の集合が大きくなって、偽物の集合と上記ii,iiiで比較可能になる。

こうすると偽物の硬貨は $D$ か $U$ に含まれる。 $i \in D$ について $L_1,2i$ を比較し、同種なら $2i-1$ が偽物、異種なら $2i$ が偽物である。これで $M$ 個すべての偽物を特定できる。

上記の解き方は公式解説2-1に似ている。公式解説1の通り解くと こう なる。この発想が無いと解答時間が2時間に収まらない。