旧型式(C,D問題がABCと共通)のARCを解いてみます。

コードはこちら

典型90-031の解説を読んで解いたので、実質解説ACである。とはいえ、どうGrundy数を適用するかは考えなければならない。

ある豆腐のX軸について、ハバネロの位置の最小値が $xmin$ なら最大 $xmin$ 回豆腐を刻んで食べることができる。同様にハバネロの位置の最大値が $xmax$ なら最大 $X_i - 1 - xmax$ 回豆腐を刻んで食べることができる。同様のことがY軸とZ軸について言える。

何回刻むかについて互いに最善を尽くした場合、残りが偶数回ならGrundy数は0 (0回つまりどう刻んでもハバネロを食べざるを得ない場合を含むので)、残りが奇数回ならGrundy数は1である。公式解説によるとNimである。

よってある豆腐についてのGrundy数は $G_i = (min(x_i) \oplus (X_i - 1 - max(x_i)) \oplus min(y_i) \oplus (Y_i - 1 - max(y_i)) \oplus min(z_i) \oplus (Z_i - 1 - max(z_i))$ である。ゲーム全体のGrundy数は $(G_1 \oplus ... \oplus G_N)$ である。

ゲーム全体のGrundy数が0なら後手必勝 LOSE 、そうでなければ先手必勝 WIN である。

コードはこちら

典型90-031の解説を読んで解いたので、実質解説ACである。Grundy数で素直に解ける。最下行から最上行、同じ行内は右から左に順にGrundy数を求めればよい。

コードはこちら

$N$ を下の桁から順に $D$ に無い桁で繰り上げる、というのを繰り返したら1 WAした。桁を変えたらそれより小さい桁を全部 $mex(D)$ にする、最上位桁を繰り上げた時だけ最上位桁を一つ増やす、という処理を追加したらACした。

二分探索でも 解ける 。 $S = {1..10} \setminus D$ とすれば、支払う金額の候補は $|S|$ 進数の数値表現で $0..(|S|-1)$ を $S$ を読み替えたものに等しい。このような数を1桁から $N$ の桁数+1までの間で二分探索する。1桁の数は $|S|$ 個、2桁以下の数は $|S| + |S|^2$ 個、という累積和を求めておくと、ちょうど $w$ 桁の数を求めやすい。

ここまでしなくても $N$ は小さかった。

コードはこちら

余事象を考える。

縦 $v$ 通り、横 $h$ 通りに移動する方法は、縦同士横同士を区別しない順列組み合わせの数なので ${v+h} \choose v$ 通りである。前提知識として、 ${{n+i} \choose {i}} = (n+i)/i \times {n \choose i}$ を漸化式で作ることがある。ARCでは頻出なのでさっと出せるようにしたい。

右下を立ち入り禁止にされなかった通り方から、右下を立ち入り禁止にされた通り方を引いたものが答えである。右下を立ち入り禁止にされなかった場合は、 ${W+H-2} \choose {H-1}$ 通りである。右下を立ち入り禁止にされた場合は以下の通りである。ここでは 0-based indexing とする。

• 左上 $(0,0)$ から立入禁止領域の左上 $P_{A-1} = (H-A,B-1)$ まで $C_{A-1} = {{B-1 + H-A-1} \choose {H-A-1}}$ 通り、ここから右下 $(H-1,W-1)$ まで ${W-B + A-1} \choose {A-1}$ 通りなので、両者の積が $P_{A-1}$ を通る経路の数である。
• $P_{A-2} = (H-A+1,B-1)$ について、 $P_{A-1}$ を通る経路を除くので $C_{A-2} = {{B-1 + H-A-2} \choose {H-A-2}} - C_{A-2}$ 通り、ここから右下 $(H-1,W-1)$ まで ${W-B + A-2} \choose {A-2}$ 通りなので、両者の積が $P_{A-2}$ を通る経路の数である。
• 以下 $P_{(A-1)..0}$ まで同様に求まる。

公式解説は余事象でなく、立ち入り禁止領域の横を通る方法を直接求めている。考え方は上記と同じである。

コードはこちら

1ノルムが中央値はよく忘れるが、2ノルムが平均値は忘れない。

コードはこちら

すべての文字 a-z を独立と考え、いずれかの文字が過半数になるか調べる。どの文字も過半数でなければ解なしである。

文字 $A$ の位置を $P = (P_1, P_2, ... P_K)$ とする。 $|P| < 2$ なら題意を満たさない。文字列の最左の位置 $L = P_1$, 文字 $A$ の出現回数 $C = 1$ として尺取り法する。

連続する部分文字列の長さは $W = P_i - L + 1$ である。文字 $A$ 以外の出現回数は $R = W - C$ である。 $i = 2..|P|$ について以下の通り更新する。

• $C$ を1増やし、 $W,R$ を求める。
• $C < R$ なら他文字が過半数なので、 $P_i$ より左を考慮すると損する。 $P_i$ を左端にする方が過半数をとれる可能性が常に高い。よって $L = P_i, C=1$ にする。
• $C = R$ なら $A$ と他文字が同数なので、更新後の $C, L$ で続ける
• $C > R$ なら $(L, P_i)$ が答えである。

公式解説は3文字以下の文字列だけ考える余事象だった。

コードはこちら

まず部分点を獲る。 $DP[i][j]$ を、子供 $i=0..N$ まで見た時に、これまでアメを $j=0..C$ 配ったときの総和とする。外ループを子供 $i$ のはしゃぎ度 $x_i \in [A_i,B_i]$ として内ループを足す。内ループはアメを $k$ 個配ったときに $DP[i+1][j+k]$ に $DP[i][j] \times x_i^k$ を足す。

満点解法を獲るには、累積和を使って一次元削減する。 $DP[i+1][j+k] = \sum_{l=0}^{k} DP[i][j+l] \times x_i^{k-l}$ である。左辺は $k$ を一増やすごとに、 $x_i$ 倍して $DP[i][j+k]$ を足す累積和として更新する。

コードはこちら

$DP[i][C][S]$ を、カード $i=1..N$ まで見た時に、選んだカードが $C=0..N$ 枚で、選んだカードに書かれた数の合計が $S$ とする。これは $DP[i+1][C+1][S+x_i] = DP[i][C][S]$ で更新する。

$DP[N][C][S]$ のうち、 $S = AC$ となる要素の和が答えである。

コードはこちら

答えが存在すると仮定する。$b$ 進数の $i \geq 0$ 桁目を $D_i$ とする。 $\sum b^i D_i = n$ , $\sum D_i = s$ である。 $i = 0$ のときに注目して両者の差を取ると、ある整数 $C$ が存在して $(b-1)C = n - s$ である。

よって $n < s$ なら解なし、 $n = s$ なら $n + 1$ が答え、そうでなければ $n - s$ の約数に1足したもので解を満たすものがあればその最小値が答え、そうでなければ解なしである。エッジケースの扱いが大変である。

コードはこちら

ダブリングする。

Consistent Hashing で次ノードダブリングで探す処理の、周回が無い版である。0-based indexingとして、 $X_{i=0..(N-1)}$ から $2^d$ 日後に行ける最左(添え字が最小)のホテルを $R[i][d]$ とする。 $R[i][0]$ は二分探索で求める。 $R[i+1][d+1] = R[R[i][d]][d]$ である。左右対称なので、右(添え字が大きくなる)のホテルへの移動だけ計算すればよい。

ダブリング表 $R$ を使って、ホテル $a$ から $b$ に行く方法を考える。 $a < b$ とし、そうでなければ $a,b$ を入れ替える。 $p = a$ として、経過日数を累積する。

• $b \leq R[p][0]$ なら1日で行けるので、1日足して終わる
• 二分探索で、 $b \ne (N-1) \land b = R[p][d]$ なら、ちょうど $2^d$ 日で行けるので、 $2^d$ 日足して終わる
• そうでなければ $b < R[p][d]$ を満たす最小の $d$ があるので、 $2^d$ 日足して $p = R[p][d]$ として繰り返す

$(b+1) = N$ のときの扱いが厄介だったが、他の方の実装を見てもっと簡単に 書けた 。

コードはこちら

全探索して間に合う。

コードはこちら

C++の力でごり押す。

各点 $(y,x)$ の周辺 5x5 領域について調べる。始点が $(y-2..y,x-2..x)$ の9通り、始点を左上とする領域が9か所なので、点の81倍の箇所を調べる。

コードはこちら

二分探索

得票は減らないので、現時点の得票数 $t,a$ を基に考える。新たな得票比 $T,A$ がきたとき、定数倍 $S$ を決め打ちして $t \leq ST \land a \leq SA$ を満たす最小の $S$ を二分探索で求める。これを $i$ ごとに繰り返す。

コードはこちら

グーを後何回出せるかの余剰を $P$ 、答えを $D$ とする。

相手がグーを出すと分かっているとき、 $P > 0$ ならパーを出して勝つ( $P$ を1減らし $D$ を1増やす)、 $P \leq 0$ ならグーを出してあいこにする( $P$ を1増やす)。

相手がパーを出すと分かっているとき、 $P > 0$ ならパーを出してあいこにする( $P$ を1減らす)、 $P \leq 0$ ならグーを出して負ける( $P$ を1増やす)。

公式解説はもっとエレガントである。

コードはこちら

頂点の値の最大最小値を狭めていく。

あらかじめ値 $p$ を書き込んだ頂点 $v$ の最大最小値を $[p,p]$ で初期化する。一斉に初期化してから探索しないとTLEする。

あらかじめ値を書き込んだ頂点 $v$ から順にDFSで探索する。最大最小値がそれぞれ $[l,r]$ なら、隣の頂点は $[l-1,r+1]$ で偶数と奇数のどちらか一方しか取りえない。

探索が後戻りせず(親にもどらなければいい)、最大最小値が狭まる限り探索を続ける。このとき値が空集合(最小値が最大値より大きい)はまたは値の偶奇が一致しないなら解なしなので、探索を打ち切って解なしと答える。

すべての頂点を探索したら、すべての頂点について書き込み可能な値がある。あらかじめ値を書き込んだ頂点を起点に値を書き込む。ある頂点に書き込んだ値 $p \pm 1$ の値のうち、隣の頂点に書き込める値を選んで書き込む(どちらでもいいときは小さい方の値でよい)。

コードはこちら

左から右に食べていく。 $a_1 + a_2 \leq x$ を達成するとき、 $a_2$ から先に食べると $a_2 + a_3$ も減ってお得である。よって $d = max(0, a_1 + a_2 - x)$ として、

• 先に $a_2$ を $r = min(a_2, d)$ 食べる
• 後で $a_1$ を $max(0, d - r)$ 食べる

これを右端まで繰り返す。同様に、右端から左端に向かって食べたときの答えを求める。両方の向きの少ない方が答えである。

コードはこちら

$S$ の先頭の文字を $C$ とする。 $1..|S|$ 文字目までに $C$ が出現する位置を $C_1=1, C_2, ..., C_k : k \geq 1$ とする。

• $i < k$ について、 $C_{i} - C_{i-1} - 1$ 文字取り除くことができる。具体的には、 $C$ のすぐ右隣りの文字が $C$ でなければ取り除いて詰める。
• $i = k$ について、 $C_k = |S|$ なら $S$ の最後の文字 $C$ 以外と1文字を除く $C_{k} - C_{k-1} - 1$ 文字取り除くことができる。 $C_k \ne |S|$ なら $S$ の最後の文字以外 $C_{k} - C_{k-1}$ 文字取り除くことができる。

これら取り除ける文字数の和が奇数なら先手の勝ち、偶数なら後手の勝ちである。後述の通り実はこの考察は間違っていて、偶然正解できてしまった。

公式解説は $|S|$ と $S$ の先頭末尾の文字が一致するかどうかで求めている。しまった、それは一度思いついたのだが、証明を思いつかず方針を変えてしまった。

私の解法に当てはめると、確かにあっている。最終的に残る文字列長さは $2C-1$ つまり奇数、 $S$ の末尾が $C$ 以外なら1追加して偶数である。よって $|S|$ が偶数なら $S$ の末尾が $C$ なら先手必勝、そうでなければ後手必勝、 $|S|$ が奇数ならその逆である。ではなぜ私の解法があってしまったかというと、 $C$ の前後の文字が一致する $C x C x$ なら 2,3文字目の $x C$ を除けないのでこれでよく、一致しない $C x C y$ なら3,2文字目の $C x$ の順に除いた残りについて考えるので偶奇は入れ替わらない。

コードはこちら

$C1, C2$ を中心、 $R1, R2$ を半径する二つの円の間を結び、円の外の最短距離は、 $max(0, |C1-C2| - (R1 + R2))$ である。点 $P$ と $C$ を中心、 $R$ を半径する円の間を結び、円の外を結ぶ最短距離は、 $max(0, |C-P| - R)$ である。これを基にダイクストラ法で解ける。 $S$ から $T$ の直交する経路を忘れない。

公式解説にある通り、始終点を半径0にすると場合分けが減る。

コードはこちら

なぜかDFSすると正解できない。

道路、鉄道をそれぞれunion-find木で連結成分を求める。各都市について、union-fine木の代表元の組 $(leader(Load),leader(Railway))$ に属する都市の数が答えである。

コードはこちら

人数が $G = A..B$ のグループを $Z=0 \lor C..D$ 個作り、それぞれのグループに人を含む方法が何通りあるか求めれば答えである。 $DP[i]$ を、 $i$ 人の行先が決まった時点で何通りの方法があるかと定義する。 $DP[0] = 1$ で $DP[N]$ が答えである。

$G = A..B$ のグループを外ループ、グループを $Z=0 or C..D$ 個作るのを内ループとする。

• $NEXT = DP$ とする。これは人数が $G$ のグループを作らないことに相当する。
• グループを $Z = C..D$ 個作ることにする。 $DP[i=0..N]$ について、 $i + GZ > N$ なら何もしない。 $i + GZ \geq N$ なら、人数が $G$ のグループを $Z$ 個作るときの人の割り当てを $T$ 通りとして、 $NEXT[i+GZ]$ に $T \times DP[i]$ を足す。
• $NEXT$ と $DP$ にして外ループを繰り返す。

$T$ の値を求める。 $N - i$ 人から $GZ$ 人を選ぶ方法は ${N-i} \choose {GZ}$ 通り、 $GZ$ 人を $Z$ 個のグループに分ける方法は $(GZ)! / (G!)^{Z}Z!$ 通り、両方掛けると ${N-i}! / ((N-i-GZ)! {G!}^{Z}Z!)$ 通りである。階乗を何度も計算しないようにあらかじめ求めておく。

コードはこちら

6,5,6,5,... を繰り返せばよい。よって以下のように求める。基本的に $2 \lfloor x/11 \rfloor$ 回で、 $x mod 11 > 0$ なら1回追加、 $x mod 11 > 6$ ならさらに1回追加する。

コードはこちら

数が重複するカードを選んで2枚捨てるのを繰り返す。重複するカードが奇数枚なら、重複しないカードを巻き添えで1枚捨てる。よってカードが $M$ 種類あるなら、答えは $M - (N - M) mod 2$ である。

コードはこちら

S の方が貴重なので、 S と c を組み合わせる。 c を $P = min(M, N/2)$ 個 S と組み合わせる。組み合わせた数 $Q = min(N, P/2)$ だけ c が減り、残り $R = (M - 2Q)$ の c を4個使って Scc を作る。答えは $Q + \lfloor R / 4 \rfloor$ である。

コードはこちら

上から整地する。

石の山が$a_i$ について、 $p = max(a_i)$ を満たす $p$ の集合を $U$ とする。 $j \in U$ のうち番号の大きい物から順番にラウンドロビンで $a_j$ を除くと、 $s$ の末尾に $min(S)$ 回を $|U|$ 回追加する。この繰り返しは、元々の $a$ で二番目に高い山との差、つまり $p - 2nd(a_i)$ 回繰り返す。最後は全部の山が同じ高さになるので、 $s$ の末尾に 1 を $N$ 回繰り返すのを山の高さだけ繰り返す。

正確に記述すると以下の通りになる。最初の $a_i$ において、高さ $H_j$ の山の場所の集合を $U_j$ とする。 $(H_j,U_j)$ を $H$ の降順に並べる。この組が $K$ 個あるとき、 $j=1..(K-1)$ 回以下を繰り返す。最も高い山の数を $W=0$ 、最も高い山のうち最小の添え字を $L=N$ で初期化する。答えを $C_{1..N}$ とする。

• $W$ に $|H_j|$ を足す
• $L$ を $min(L, U_j)$ で更新する
• $C_L$ に $W(H_j - H_{j+1})$ を加える。

最後に、 $C_1$ に $N(min(a_i))$ を加える。

コードはこちら

時刻 $t$ で行ける最長距離 $t(t-1)/2$ が $X$ 以上になったら、その時刻 $t$ が答えである。逆にそのような $t$ では、 $t(t-1)/2 \geq X$ なる $X$ はすべて到達可能である。これは $t$ についての帰納法で示せる(はず)。

コードはこちら

Shapley–Shubik Power Index の pivotal player を思い出すと部分点解法が獲れる。カード集合 $S$ があり、 $\sum_{i \in S} a_i < K$, $\sum_{i \in S \cup j} a_i \leq K$ なら、カード $j$ は必要である。

Shapley–Shubik Power Indexは全順列を求めるがそれだとTLEする。動的計画法で、 $DP[i]$ を $i$ 番目までみたときに、部分集合で作れるすべての和の集合、より厳密には $S \subseteq {a_1..a_{i}}$ で取りうる $\sum_{i \in S} a_i$ の集合とする。 $i$ 番目までで $K$ 未満の和、 $i+1$ 番目までで $K$ 以上の和という状態遷移を観測したら、 $a_i$ は必要なのでカード $i$ が要ると記録する。

これだけだと解けないが、 $a$ の始点を $1..N$ 回回転してそれぞれ求めると必要なカードをすべて記録できる。正当性を雑に説明すると、カード $i$ をPivotal player とするとき、並びが $l < i < r$ なカードを回転することで $l,r < i$ にも $i < l,r$ にもできる。ここで $a_l, a_r$ の和だけが重要で $l,r$ は順不同なので、Shapley–Shubik Power Indexは全順列に相当するものを作れる。

コードはこちら

a-z が $S$ にそれぞれ何回出るか数える(出現しないなら0回)。 a-z それぞれについて、 $S$ についての最初値回だけ、 繰り返し出力する。

コードはこちら

$X$ 軸と平行な直線と $Y$ 軸に平行な直線は独立に数えられる。

$X$ 軸に平行な直線が $m$ 本ある。 $x_1, x_2, ... , x_n$ をすべて $x_1$ で引く。 $\sum_{j=i+1}^{n} \sum_{i=1}^{n-1} (x_j - x_i)$ を効率よく数えればいい。 $i=1$ のとき $S_1 = \sum{i=2} (N - i + 1) x_i$ である。漸化式を逆に計算して、 $S_{i+1} = S_i - (N - i + 1) x_i$ で更新する。

$X$ について $\sum S$ が求まるので、 $Y$ について同様に求めて掛けると答えである。

コードはこちら

よくある緑diffだと思って身構えてしまったが、よく考えると分かる。

$S$ と $T$ それぞれの部分文字列が同じかどうかだけが問題で、最小手順は問われないので、全部 A に置き換えて構わない。よって文字列先頭からの A の長さについて累積和を取る。元の文字が A なら A 1個、 B なら A 2個分と数える。 $S,T$ それぞれについて $i$ 文字目までの累積和を $CS_i$, $CT_i$ とする。

各クエリについて、 A の長さを3で割った余りが同じなら YES 、違ったら NO である。これは $(CS_{b} - CS_{a-1}) \equiv (CS_{d} - CS_{c-1}) mod 3$ である。

コードはこちら

Greedyであってる。

$a_1$ までの累積和を1以上、 $a_2$ までの累積和を-1以下、 $a_i$ までの累積和を $(-1)^(i-1)$ と決め打ちする。 $1..N$ について累積和がこの性質を持っていれば $a_i$ は変えず、そうでなければ累積和を1または-1になるように $a_i$ を変える。

$a_i$ までの累積和を $(-1)^i$ と決め打ちした場合も調べ、両方の最小値が答えである。

コードはこちら

2時間以上考えて解法が分からないので、ゲーム木を書いて法則性を見つけて提出したら通った。 $X \leq Y$ として、 $Y < 2$ または $X = Y$ または $X + 1 = Y$ が答えである。まとめると $|X-Y| < 2$ なら後手必勝、そうでなければ先手必勝である。

後付けで証明を考える。常に $X \geq Y$ と解釈して一般性を失わない(そうでなければ $X,Y$ を入れ替える)。 $X - Y \geq 2$ なら $i = \lceil (X - Y) / 2 \rceil$ とすれば、 $Y - X < 2$ にできる。逆に $X - Y = 0$ なら $X - Y = 3$ になり、 $X - Y = 1$ なら $X - Y = 2$ になる。つまり $|X-Y| < 2$ かどうかは相互に入れ替え可能である。

$X < 2$ の場合は先手は何もできないので後手の勝ちである。そうでなければ石の数は単調減少なので、いつか $X=1$ になる。初手で $X - Y \geq 2$ なら先手 Alice の勝ち、そうでなければ後手 Brown の勝ちである。公式解説は同じことを簡潔に述べている。

片方の数から $2i$ 引いて他方に $i$ 足すと差が $3i$ 変わる。これを基に不変量を探したが上手くいかなかった。

コードはこちら

いもす法。

スイッチを押したとき $t$ で +1 、 $t+T$ で -1 する変化点を登録する。変化点を時間の昇順に並べていもす法する。お湯が出始めるのは、変化点の累積が0から非0になったときで、お湯が止まるのは、変化点の累積が非0から0になったときである。よって両区間の幅を足していく。

コードはこちら

$0 \leq w_i \leq 3$ より、 $0 \leq \sum w \leq 3N$ である。よって $w0 > 3N$ なら、物と一つ増やすときの重量増を $3N+1$ とみなすことで、物と一つ増やすときと複数増やすときを区別できる。

$w0 \leq 3N$ というかおおざっぱに $w0 \leq 400$ ならいつものナップザックDPする。 $w0 > 400$ なら、物を一つ増やした時の重量増を $L = 400 + w_i - w_0 $ とみなしてナップザックDPする。 $L$ から真の重量は、 $w_0 \lfloor L/400 \rfloor + L mod 400$ で求まる。

コードはこちら

丁寧に場合分けする。縦横を入れ替えて数えると、コードを短くできる。

• 幅つまり横方向の長さが $W$ なら、三等分して答えは0である
• 縦に2回割ると、 $\lfloor W/3 \rfloor, 1 + \lfloor W/3 \rfloor$ に割れるので、答えの最大値は高さつまり縦方向の長さ $H$ である。
• 縦に割る位置を全探索し $i = 1..(W-1)$ と $W-i = (W-1)..1$ にする。横に割るのはできるだけ均等にする、つまり $j = \lfloor H/2 \rfloor, H - j$ に割る。このときの答えは $iH, (W-i)j, (W-i)(H-j)$ の最大値から最小値を引いたものである。

コードはこちら

尺取り法で解く。

$P = a_{1..N}$ , $B = a_{(N+1)..3N}$ として、 $Q$ を $B$ の下位 $N$ 個、 $R = B \setminus Q$ で初期化する。

$i = (N+1)..2N$ について尺取り法で更新する。 $P$ と $Q$ の総和を更新し、総和の差である答えも更新する。

• $min(P) < a_i$ なら $P$ から $min(P)$ を除き $a_i$ を加える
• $a_i \in Q$ なら、 $Q$ から $a_i$ を除き、 $min(R)$ を $Q$ に移動する。そうでなければ $R$ から $a_i$ を除く。

公式解説は優先度キューを用いている。

コードはこちら

最大フロー最小カット問題だと思って解けず、局所点連結度という用語を知ったものの求め方が分からず、諦めて解説を見たら最大フロー最小カット問題だった。着眼点はよかったが、具体的な解法に落とし込むには経験が足りない。

コードはこちら

DPで解ける。正攻法ではなくやりすぎらしい。

コードはこちら

体力が最も高い魔物を $A$ 減らして、とすると正解できないしTLEしそうである。なので二分探索で求める。

少なくとも $X$ 回で倒すと決めた時、体力 $h_i$ のモンスターを倒すのに必要な魔法の回数を考える。最低 $BX$ のダメージを与えるので、必要な追加ダメージは $E_i = \lceil (h_i - BX) / (A - B) \rceil$ である。 $\sum E_i \leq X$ となる最小の $X$ が答えである。

上記の解法も、TLEしそうなことも、公式解説通りである。

コードはこちら

Policy based data structure で multisetを使うと解ける。

部分列が $[a_1, a_R]$ の平均が $K$ であることを、 $(\sum_{i=1}^{R} a_i) - RK \geq 0$ と読み替える。これは累積和で求める。この累積和を基に、 部分列が $[a_L,a_R]$ で平均が $K$ であることを、 $(\sum_{i=1}^R a_i) - RK \geq (\sum_{i=1}^{L-1} a_i) - (L-1)K$ と読み替える。便宜上、 $l=0$ のときの右辺を0とする。

部分列でこの不等式を満たす要素の数、つまり $L=1..N$ の累積和において $(\sum_{i=1}^{L-1} a_i) - (L-1)K$ を超える要素の数を求めればよい。これはPolicy based data structure で multisetを使うと、 order_of_key で求まる。あとは累積和の要素を一つずつ除いて繰り返す。

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using Element = Num;
using ordered_set = tree<
  Element,
  null_type, std::less_equal<Element>,
  rb_tree_tag,
  tree_order_statistics_node_update>;

公式解説は座標圧縮とFenwick Treeを使っている。それと累積和から累積和を引いていることを用いている(そもそも累積和とはそういうものだった)。

コードはこちら

$|N - M| > 1$ なら、犬同士または猿同士が並んでしまうので答えは0である。そうでなければ並べ方は $N!M!$ ある。ただし $N = M$ なら、先頭を犬と猿どちらか選べるので2倍する。

コードはこちら

二頂点の少なくともいずれか一方が矩形の境界になければ、その頂点を結ぶ曲線を他の曲線は迂回できる。つまり二頂点の両方が矩形の境界にある曲線同士が交わるかどうか調べる。それ以外の曲線は無視する。

頂点番号を、矩形の境界に沿って定義する。入力を入れ替えて縦方向を $Y$ 、横方向を $X$ とし、座標系は $Y$ が増える方向を下、 $X$ が増える方向を右にする。頂点の座標を $(X,Y)$ と表現するとき、 $(0,0)-(c,0)-(c,r)-(0,r)$ と時計回りに移動したときの移動距離 $p$ を、頂点 $(X,Y)$ の位置とする。

この操作により、曲線 $i$ を $(P_i, Q_i)$ と結ぶものと決める。 $(P_i, Q_i), (Q_i,P_i)$ を $P$ の昇順にソートし、曲線を順に見てこれまで見た曲線と交わるかどうか調べる。 $P_i < Q_i$ なら $Q_i$ をスタックに積む。 $P_i > Q_i$ ならスタックの最上位が $P_i$ なら取り出し、そうでなければ他の曲線と交わったので答えは NO である。

すべての操作を終えることができたら答えは YES である。

コードはこちら

久しぶりに std::list<Num> を使った。奇数回目の挿入は後ろに、偶数回目の挿入は前に行う。 $N$ が奇数なら逆順、偶数なら正順に要素を出力する。

コードはこちら

余事象を考える。

重複する数 $c$ が、0-based indexingの位置で $(L,R)$ に出現すると調べる。位置 $L$ より左からきて(なくてもよい) $L,R$ のどちらか一方を経由して位置 $R$ より右側に向かう(なくてもよい)長さ $k$ の数列は、 $c$ の区別がつかないのでそれらを数え上げる。このような組み合わせは $W = L + N - R$ として、

• ${{W} \choose {k-1}} : 0 \leq k-1 \leq W$
• $0 : otherwise$

通りである。これを全組み合わせ ${N+1} \choose k$ から引くと答えである。

コードはこちら

逆から考える。

お気に入りボタンが $a_{2..M}$ それぞれの切り替えにどう効くかではなく、 $a_{2..M}$ それぞれの切り替えがお気に入りボタンのお得度にどう効くかを考える。

切り替え前後 $a_{i},a_{i+1}$ を $p,q$ とする。 $modM$ で考えて $W = q - p < 2$ ならお気に入りボタンを使っても、順送りよりボタンを押す回数は少なくならない。そうでなければ $modM$ で考えて $[q - W + 1, p]$ の範囲は、お気に入りボタンを使うと順送りよりボタンを押す回数が $1..W$ 回減る。ボタンを押す回数が何回減るかをお得度 $D$ 、早送り先のお得度を $W$ と呼ぶ。

これを $i=1..2N$ に対して累積する。いもす法的に考える。ある範囲を $[L_j,R_j)$ 、その範囲での早送り先のお得度 $W_j$ 、 $i$ における範囲の数を $C_i$ 、ある $i$ におけるお得度 $D_i$ を以下の通り更新する。

• $L_j$ で範囲 $C_i$ が一つ増える
• $R_j$ で範囲 $C_i$ が一つ減る
• 範囲を出るまでつまり $i < R_j$ なら、お得度 $D_i$ は $C_i$ 増える
• 範囲を出たつまり $i = R_j$ でお得度 $D_i$ は $W_j$ 減る

累積先は $i=1..2N$ を $modM$ で考えることに注意する。答えは $\sum (a_{i+1} - a_i) - max(D)$ である。

公式解説もいもす法だが、直接答えを求める必要はなく、ボタンを押す回数が少なくなる操作の最多得票となる早送り先を探してから、後で答えを求めている。

コードはこちら

累積和をとれば分かる。

コードはこちら

2つの定期便を使う、というのを、中継地を探す、と読み替える。

ある島 $i = 2..(N-1)$ について、 $1,N$ の両方に定期便が出ていれば POSSIBLE 、そういう島がなければ IMPOSSIBLE である。

コードはこちら

雑に考察したらACしてしまった。

$2..50$ を素因数に持たない $K$ を選ぶことができるので、 $N=50$ に固定して構わない。 $a$ を広義単調減少にしても一般性を失わないのでそう決める。

周期 $N$ の操作で $a$ をそれぞれ1減らせるので、元々の $a$ は少なくとも $B = N - 1 + \lfloor K/N \rfloor$ 以上にする。後は $a$ を一つずつ操作するとき $R = K mod N$ 回ちょうどで操作が終わるようにする。これは $R$ 個の $a$ について、 $C = B + N - R$ にすると、 $N$ 減らした後 $R-1$ 回経っても $N$ に浮かび上がってこない。残りの $N-R$ 個については $C - N$ にする。

制約が $50 \times 10^{16}$ なのになぜか $10^{16}$ 桁と勘違いして任意精度整数を使ってしまった。

コードはこちら

あちこちいじくったらACしてしまった。

最初に問題を読み替えて、 $a_i -N$ を操作して数列の最大値が0未満になるまでとする。 $N$ が小さいので、 $N^3$ 回のシミュレーションで細部を詰めてもTLEしない。

細部の詰めまでをまとめて実行することを考える。 $a_i$ を昇順に並べる。 $a_{N-1}$ と $a_{N}$ の差を埋めるには、 $a_{1..(N-1)}$ を1増やすのと $a_{N}$ を $N$ 減らすのを同時に行う。よって $max(a_{N}, \lfloor (a_{N} - a_{N-1}) / (N+1) \rfloor)$ 回の操作を行って差を埋める。

この操作を $i=(N-1)..1$ について順に実行する。念のため操作後の $a_i$ を昇順に並べる。 $a_{i}$ と $a_{N}$ の差を埋めるには、減らす数列の幅を $W = N-i$ として、 $a_{1..i}$ を1増やすのと $a_{(i+1)..N}$ を $N+1-W$ 減らすのを同時に行う。 $max(\lfloor a_{N} / (N+1-W) \rfloor, \lfloor (a_{N} - a_{i}) / (N+1) \rfloor)$ 回の操作を行って差を埋める。

このとき数列を引きすぎないように気を付ける。 $a_N \leq N$ になったらこの操作を止めて微調整すると答えが求まる。

公式解説を読むと、 $N$ より大きな $a$ を引く順序は簡単に考えてよかったようであるが、理解していない。

コードはこちら

4の倍数、4の倍数ではないが2の倍数、奇数、がそれぞれ何個あるか数える。これらを $A,B,C$ と置く。

• 4の倍数ではないが2の倍数という数が無いとする(つまり $B = 0$ ) 。このとき、奇数と4の倍数を交互に置ける、つまり $A \leq (C+1)$ なら Yes である。
• そうでなければ奇数と4の倍数を交互に置ける、つまり $A \leq C$ なら Yes 、それ以外は No である。4の倍数ではないが2の倍数は連続して並べるしかないので、 $B > 0$ なら何個あるかは影響しない。

コードはこちら

S字型にぐねぐね曲がる。つまり左上から左端まで行く、一段下がる、右端まで行く、一段下がる、左端まで行く、を繰り返し、 $i$ を $a_i$ 個連続で置く。

コードはこちら

ある長さの辺 $L$ である棒が $K$ 本あることを $(L_i,K_i)$ と置く。 $L \geq 2$ な棒について、 $L$ の降順に並べる。下記で上から順に最初に当てはまるものが答えである。

1. 棒がなければ答えは0である
2. 最も長い棒 $(L_1,K_1)$ について、4本あれば正方形を作れる。答えは $L_1^2$ である。
3. 棒の長さが1種類しかなければ答えは0である
4. 最も長い棒2本と、2番目に長い棒で長方形を作れる。答えは $L_1 L_2$ である。

コードはこちら

難しい動的計画法かと思ったらそうではなかった。

縦棒だけに注目し、列 $1..N$ を動的計画法で塗る。

• 1列目は縦棒なら3通り、横棒x2なら6通り
• 2列目以降は、前が縦棒なら2通り、前が横棒で今も横棒なら3通り、前が横棒で今は縦棒なら1通り
• 縦棒なら列を1増やし、横棒なら列を2増やして次の列を見る

コードはこちら

$a$ を $a-1,a,a+1$ にしかできないので、それらの数をすべて候補に挙げる。 $x$ を固定したとき、 $x-1,x,x+1$ それぞれの値を取る $a$ の数の和が、操作後の $x$ の個数である。よってすべての候補について $x$ と置いて調べればよい。

コードはこちら

ランレングスだと思ったら違った。値が定位置の場所をランレングスして、ラン長 $L$ に対して $max(1, L-1)$ を足すとWAする。

正解はアドホックに入れ替えである。 $p_{1..(N-1)}$ について、定位置なら右隣と入れ替える。つまり $p_i = i$ なら $p_i,p_{i+1}$ を交換する。 $p_N = N$ なら $p_(N-1),p_{N}$ を交換する。

公式解説の通りだが、 $p_i = i$ のときに $p_{i+1}$ と交換すれば、 $p_i$ は $i$ 以外の数値を引き取って条件成立、 $p_{i+1}$ は $i (\ne i+1)$ を引き取って条件成立、なので常に得する。

コードはこちら

二次元DP

砂糖が溶け切るかどうかはともかく、 $100A, 100B, C, D$ を足して作れる砂糖水の組み合わせをすべて網羅する。これは $DP[water][sugar]$ というDPにすればよい。

$DP[0][0]$ を除く砂糖水について濃度を求めて、最大値を返す。有理数で計算しても間に合う。

コードはこちら

$M$ 問正解する確率は $1/2^M$ であり、最初に成功するまでの回数の期待値は $2^M$ 回である。それに提出1回当たりの時間 $1900M + 100(N-M)$ を掛ける。

コードはこちら

スコアの定義を間違えた。

最適化対象は2人の持っているカードに書かれた数の差の絶対値である。Xさんが持っているカードを最大化、Yさんが持っているカードを最小化、ではない。そうと解ればmin-max treeをメモ化再帰しながらたどればよい。

公式解説がエレガントすぎるが、この発想が無いと今どきのARCは獲れない。

コードはこちら

多数派のボールを $K$ 種取って、それ以外のボールを書き換える。具体的には、値 $x$ を持つボールが $y$ 個あるとき、 $y$ から成る集合 $S$ を作る。 $S$ を降順に並べて、先頭 $min(|S|,K)$ 個の要素を足して $N$ から引いたものが答えである。

コードはこちら

元々全部同じ数字なら(特に全部0なら)、すべきことは何もない。

前処理として、全部0以上か全部0以下にそろえる。これは絶対値が最大の数を他の数に足すとできる。全部0以上なら左から右に順に累積和を取る。全部0以下なら右から左に順に累積和を取る。

コードはこちら

$x$ が $k > 0$ 個あるとする。 $x > k$ なら全部除くしかないので $k$ 個除き、そうでないなら $x$ 個にするために $k - x$ 個除く。

コードはこちら

X,Y座標を独立に考えてよい。よって以下の通り考える。 $S$ の末尾に T を追加しても答えが変わらないので、処理を簡単にするために追加する。

• 今載っている軸をX軸、最後の方向転換から距離 $D$ を0にする
• F なら、最後の方向転換から距離を1増やす
• T なら、これまで今載っている軸のうち、最後の方向転換で居たことのある点 $i \in [-8000..8000]$ からの相対値 $i \pm D$ に居たことにする。この後 $D=0$ にして、載っている軸を交換する(X軸ならY軸、Y軸ならX軸)
• ただし、最初の方向転換までは、相対値は $i + D$ である。 $i - D$ も使うと2 WAsする

コードはこちら

数列をできるだけ増やしたく無ければ $A_{i+1} = 2A_i$ にすればいい。後は初期値 $X$ を2倍にするのを、 $Y$ を超えるまで繰り返す。

コードはこちら

如何にもARCらしい問題である。

自明な場合を解く。 $N = |S|$ とする。 $N=1$ なら答えは1である。 $N=2$ なら $S$ の両文字が同じとき答えは2、異なれば答えは1である。

$S$ をランレングス圧縮し $L$ とする。 $|L| < 3$ なら $L$ の最大要素が答えである。 $|L| = 1$ ならすべての文字が同じなので必要なら $S$ 全体を反転する、 $|L| = 2$ なら多数派の文字を反転してから、必要なら $S$ 全体を反転する。

$|L| \geq 3$ なら、ラン長の累積和を左右から取ったものについて、 $|S| / 2$ 以上の最小値が答えである。左端から数えた場合、 $C_i = \sum_{i=1} L_i$ について、 $C_i \leq |S| / 2$ を満たす最大の $C_i$ を選ぶ。同様に右端から数えて $D_j$ を選ぶと、 $|S| - max(C_i, D_j)$ が答えである。

答えが $D_j$ のときの操作を述べる。左側から区間 $A = (1, |S| - D_j)$ を反転すると、反転した区間 $A$ の右端と反転しない区間 $B$ の左端は値が同じである(ランが異なれば値が異なるようにランレングスを定義したので)。これを繰り返すといつかは、 $B$ はすべて $A$ の右端の値にそろう。

同じことを $B$ にを基に $A$ を右側から適用する。 $C_i \leq D_j$ より $|S| - C_i \geq |S| - D_j$ よりこのような操作は可能であり、上記と同様に繰り返すといつかは、 $A$ はすべて $B$ の左端の値にそろう。これで $S$ はすべて同じ値になったので、必要なら反転するとすべて 0 になる。

公式解説は上記を別の表現で書いている。

コードはこちら

時間と時刻の差に気を付ける。

時刻 $t_i$ に点 $(x_i, y_i)$ に存在できる条件は、前回いた点からの距離 $d$ , 前回いた点からの経過時間 $p$ が、 $d \leq p$ かつ $d,p$ の偶奇がそろっていることである。偶奇がそろっているなら無駄に往復することで時間を2の倍数つぶせる。

コードはこちら

ほとんど分かっているのに正解できなかった。

パターンを $2K$ 単位で繰り返すので、座標は $mod2K$ で考えてよい。盤面を $(4K,4K)$ と考える。 $(X^{'}, X^{'}) = (Xmod2K, Ymod2K)$ とおいて、 $(X^{'}, X^{'}), (X^{'}+2K, X^{'}), (X^{'}, X^{'}+2K), (X^{'}+2K, X^{'}+2K)$ に増やして数える。のだが、なぜか $(X^{'}+2K, X^{'}), (X^{'}, X^{'}+2K)$ を置き忘れて解けなかった。

ここまで分かれば、左下を $(0..2K,0..2K)$ の総当たりで数える。これは二次元累積和で求まる。二次元累積和のコードは間違ってなかった。

公式解説にある通り、黒なら(白なら) $(X+K,Y)$ とみなしてよかった。

コードはこちら

$i=1,2$ それぞれについて $A_{i,1..N}$ の累積和を取る。

下方向に行く場所は $c = 1..N$ しかないので全探索する。列 $c$ で下に行くなら、 $A_{1,1..c} + A_{2,c..N}$ であり、累積和を使って $O(N)$ で解ける。

なぜか公式解説は $O(N^2)$ である。

コードはこちら

Potentialized DSUを適用するだけである。

コードはこちら

丁寧に場合分けする。

$N > M$ なら $N,M$ を入れ替える。

• $N = 1$ なら、 $M = 1$ のとき答えは1、 $M = 2$ のとき答えは0、 $M > 2$ のとき答えは $M - 2$ である、
• $N = 2$ なら答えは0である
• $N > 2$ なら答えは $(N-2)(M-2)$ である

コードはこちら

いかにも調和級数。

$b = (K+1)..(N-1)$ としたときに、 $a = 1..N$ を長さ $b$ の周期 $c = \lfloor N/b \rfloor$ 回繰り返し、残りが $r = N - cb$ と分割できる。周期の部分に余り $K$ 以上の $a$ は $b - K$ 個あり、残りの周期の部分に余り $K$ 以上の $a$ は $min(0, 1 + r - K)$ 個ある。併せて $c(b - K) + min(0, 1 + r - K)$ 個ある。これを $b$ について合計する。

$K = 0$ のときは $(a,b)$ = $(N,1)$ があるのでさらに1足す。

コードはこちら

検算したら通った。

$A=N,B=1$ は $1..N$ 、 $A=1,B=N$ は $N..1$ それ以外の $A,B \geq N$ は解なしである。

周期 $A$ で内部が昇順のブロックを $\lceil N / A \rceil$ 個作る。ブロック内では昇順、ブロック間では降順にする。具体的には $[(N-A+1)..N], [(N-2A+1)..N-A], ...$ と作る。こうすると $A$ の条件を満たす。

残りは $B$ で、最初のブロック以外を一部降順にすると、 $B$ を $k=0..(A-1)$ まで増やせる。ブロック内の最初の $K$ 個を大きな数から降順、残った数を昇順にする。このような $B$ があれば答え、なければ解なしである。

どうしても1 WAが取れず、出力結果を検算してLISがあってなければ -1 を返したら通った。

コードはこちら

二部グラフのMax flowを求める。始点 $0$ 、終点 $2N+1$ 、赤い点 $1..N$ 、青い点 $(N+1)..2N$ とする。始点から赤い点、青い点から終点を結び、赤い点か青い点は題意を満たすときだけ結ぶ。

全ての辺の容量を1として、始点から終点のmax flowが答えである。公式解説の別解である。

コードはこちら

順方向の移動を無視する。

便宜上、座標0の始点を $A_0$ , 座標0の終点を $A_{N+1}$ とする。観光スポットをすべて訪れたときの総移動距離を $T$ とする。

順方向の移動は、経由地を通過しても総距離は縮まらない。具体的には、 $A_{i-1} \leq A_{i} \leq A_{i+1}$ のとき、観光スポット $A_i$ を通過しても総移動距離は変わらない。そうでなければ $|A_{i-1} - A_{i}| + |A_{i} - A_{i+1}|$ が $|A_{i-1} - A_{i+1}|$ に変わるので、その差を $T$ から引いたものが答えである。

なお $A_{i-1} \leq A_{i} \leq A_{i+1}$ の判定で、 $A_{i-1} > A_{i+1}$ なら両端を入れ替えて判定しても、判定結果も距離も変わらない。

公式解説にある通り、順方向かどうかを明示的に判定しなくても、順方向なら距離の差は0である。

コードはこちら

全体の大きさ高さ100x幅100に固定して、以下のパターンを繰り返す。右端と下端がつながるので、 . の連結成分は右のように穴を開けない限り増えない。

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

$A \geq B$ とし、 $A < B$ なら $A$ と $B$ , . と # を入れ替える。

上記左のパターンを $A$ 個作る。このようなパターンは $(100/4)^2 = 625$ 個作れるので題意を満たす。その後で、 $B-1$ 個の穴をあけて右側にする。これも $min(625, A) > B-1$ 個作れるので題意を満たす。

上下2分割して格子状に点を打つ方が楽だった。

コードはこちら

解空間は $128^3$ だろうと祈ってBFSすると解ける。

というのはあんまりなので $O(1)$ 解法を 示す 。

一般性を失わずに、 $a \leq b \leq c$ とする。まず $a,b$ に $c - b$ 回1を足す。次に $a$ を増やす。 $c - a - (c - b)$ が奇数なら $b,c$ に1回1を足し、 $(c + 1 - a - (c - b)) / 2$ 回2をAに足す。そうでなければ $(c - a - (c - b)) / 2$ 回2をAに足す。

なんとこの問題は不変量だった。不変量をそうと見抜くのはなかなか難しい。

コードはこちら

境界値の扱いが難しい。

参加者のスコア $(a,b)$ が $ab < AB$ になるような $(a,b)$ を数え上げる。反比例曲線 $y = 1/$ に $ab = AB-1$ を描いて下側に点を打っていく。これは $a=i, \lfloor (AB-1)/i \rfloor$ を $i = 1..(\lfloor \sqrt{(AB-1)} \rfloor)$ に打って $x=y$ で反転して二倍すればよい。

よって $R = \lfloor \sqrt{(AB-1)} \rfloor$ として、概算では解は $C = 2R$ である。ここから調整する。

• $x=y$ に点が乗っているときは、折り返した分1個余計に数えているので、 $C$ を1引く。 $R = \lfloor (AB-1)/R \rfloor$ のときが該当する。
• $A \ne B$ のときは、他の参加者で1回目の順位が $A$ または他の参加者で2回目の順位が $B$ の人がいるので、 $C$ を1引く。
• $A = B$ のときは、他の参加者で1回目の順位が $A$ または他の参加者で2回目の順位が $B$ の人はいない。なぜなら $(A,B)$ は反比例曲線の外側だからである。

公式解説も同様の解き方である。

コードはこちら

差に注目したら解けなかった。正解は $min(B_i) for A_i > B_i$ である。

最適戦略として、先手はできるだけできるだけ大きい数字を残し、後手はできるだけ小さい数字を残すのは分かった。上界と下界を与えるという考え方が分からなかった。

公式解説に補足すると、 $\sum A = \sum B$ から、 $A_1 > B_1$ なら $A_i < B_i$ を満たす $i$ を少なくとも一つ見つけることができる。

コードはこちら

中央値の場所は2か所しかない。

$X$ を昇順に並べて先頭を1番目を数えるとき、 $N/2$ 番目以下の数値を抜けば元々 $1+(N/2)$ 番目だった数字が中央値になる。 $1+(N/2)$ 番目以下の数値を抜けば元々 $N/2$ 番目だった数字が中央値になる。後は $X_{1..N}$ が何番目に大きいかから、中央値を求める。

コードはこちら

想定解法とまるっきり異なるが解けてしまった。

$a$ を降順にソートし、添え字を順位で振りなおす。 $a_i$ について、 $a_{i+1..N}$ から、 $a_i / 2$ 前後の数 $b_1, b_2$ を候補として最大2つ取り出す。

• $0 \leq b \leq a_i$ を満たさなければ、候補からはずす
• 候補が無いなら何もせず、候補が1個ならその $b$ を使う
• 候補が2個なら、 ${a_i \choose b} = a_i!/(a_i - b)!b!$ より、 $min(a_i-b,b)$ が大きい方の $b$ を選ぶ

$a_i$ に対応する $b$ を選んだら、 $d = log(a_i!/(a_i - b)!b!) = log(a_i!) - log((a_i - b)!) - log(b!)$ を求める。階乗の対数を近似する式は こちら の記事を参考した。タプル $(d,a_i,b)$ を候補に載せる。

これを $i=1..N$ についてすべて求める。 $a_i$ の多重集合 $S$ に $a_{1..N}$ を入れて置き、 $S$ を $S \setminus a_i$ で更新する。上記のタプルのうち、 $(d,a,b)$ が最大の要素について $(a,b)$ が答えである。

コードはこちら

2に限らず一般解がある問題を解いた気がする。ピザC 2枚とピザA,B 1枚ずつは調達という点で等価なので、どちらか安い方を買えばいい。よって端数だけに意味がある。この問題に限っては、以下の総当たりで解ける。

• ピザA,Bをそれぞれ買う : $AX + BY$
• ピザCだけ買う : $2max(X,Y)C$
• ピザAをピザCだけで調達し、足りないピザBを買う : $2XC + max(0,Y-X)B$
• ピザBをピザCだけで調達し、足りないピザAを買う : $2YC + max(0,X-Y)A$

確かに定数時間で解けるが、実は全探索でよかった。全探索しないと解けないのが ABC 374-E である。

コードはこちら

円環をつなげて平たくする。

原点をまたがず、時計回りと反時計回りの一方通行のパターンを数える。これらは答えの候補を与える。

その後 $x+C$ 座標を複製して、原点をまたぐパターンを作る。鮨 $i$ は座標 $x_i$ にあってカロリー $c_i$ であるとする。原点 $0$ から鮨 $i=1..2N$ まで食べた時の $v-x$ の累積和 $C_i$ を取り、セグメント木に載せる。

左端を $L=2..N$ 番目とし、右端を $R=L..(L=N-1)$ として、セグメント木で区間max $M=max(L,R)$ を取ると、左端を固定したときの $R$ が分かる。後は原点の移動距離を $M - C_{L-1} + x_L - x_{L-1} - c + x_i$ と補正する。この最小値が答えである。

コードはこちら

C++の力でごり押す。

std::string_view::substr を使うと、全探索しても 1268 ms で間に合う。想定解法は長さ $K$ 以下の文字列を全列挙することだった。

コードはこちら

交換の交換を繰り返せば、それぞれの要素を望んだ位置に置ける。なぜならバブルソートと同じだからだ。

よって交換可能な要素をunion-find木でまとめる。それぞれの連結成分について、定位置に置ける要素 (要素 $i$ を位置 $i$ に移動できる) を数える。

コードはこちら

累積和の典型問題である。

人が東を向いているとき 1 、西を向いているとき 0 として、人 $i$ までの累積和 $C_i$ を取る。リーダー $i$ を向かせるために向きを変える人数は、人 $1..(i-1)$ は $i - 1 - C_i$ 、人 $(i+1)..N$ は $C_N - C_i$ なのでこの和である。 $i=1..N$ における最小値が答えである。

コードはこちら

数日考えて分からず、ようやくACした。

左右から取っていったときに必ずみる数は何か、という方針はACできなかった。

$A$ を位置と併せて $(A_i,i)$ を昇順に並べた数列 $(V_i,P_i)$ を作る。 $i=1..N$ について $V_i$ が最小値と決め打ちして、 $V_{j=i..N}$ を最大 $Q$ 回の操作で取り除けるかどうか調べる。

• 使えない要素の位置の集合 $U$ に $P_{1..(i-1)}$ を加える
• $V_j=i$ を取り除けるのは、 $P_j$ の前後が $Q$ 以上離れているときである。 $U$ の $P_j$ 未満の最大要素を $L$ (なければ $0$ )、 $U$ の $P_j$ より大きい最小要素を $R$ (なければ $N+1$ )とする。このとき $R - L - 1 \geq Q$ と言える。
• $V_j$ を取り除けないなら何もせず $j$ を1増やす
• $V_j$ を取り除けなるなら、取り除いた数の集合 $S$ に $V_j$ を追加する。 $V_j$ を除いたことを Fenwick Tree $T$ に記録する( $T[P_i]$ に1足す)。 $j$ を1増やす
• $|S| = Q$ なら $max(S) - min(S)$ を答えの候補とする。これ以上 $S$ を増やす必要はない。
• $V_j$ を取り除ける条件を、 $R - L - 1 - T[L+1,R-1] \geq Q$ と読み替えて上記を繰り返す。

コードはこちら

実は配列の中身は関係ない。これが分からなくてWAの山を築いた。

操作が終わったとき、すべての要素が 1 になっている。連続 $K$ 個を選んで最小値を取るということは、 1 を連続する区間の最大 $K-1$ 個増やすことと等しい。

$i=1..N$ を起点に、 $[i-K,i-1]$ または $[i,i+K]$ に要素を増やす。何回増やすかは、 $\lceil (i-1) / (K-1) \rceil + \lceil (N-i) / (K-1) \rceil$ で求まる。この最小値が答えである。逆操作を考えれば、元々 1 だった要素がコピーされるよう操作順序を定義できる。

$i=1..N$ を全探索しなくても、答えは $\lceil (N-1) / (K-1) \rceil$ だった。幅 $K-1$ のブロックを並べてずらすイメージである。

コードはこちら

全く答えが分からなかったので、他の方の説明を見た。

実験すると、 $n < 1000$ なら最上位桁が $1..9$ で下の桁が全部9、それ以外は上の桁が $10..99$ または $100..999$ の一部、下の桁が全部9と解る。しかしその規則性が分からなかった。

$W > 3$ 桁の数について、 $n = B 10^{W-3} + (10^{W-3} - 1) : 100 \leq B < 1000$ について総当たりする。 $n$ の桁和が同じで $n$ より大きな最小の数 $n + (10^{i} - 1) - 1 : W-3 \leq i \leq W-1$ だけ調べればよい。

コードはこちら

三分探索する。

$b \in [-\infty .. \infty]$ を探索すると、 $b < A$ なる $A$ の数 $L$ は広義単調減少、 $b > A$ なる $A$ の数 $R$ は広義単調増加する。よって

• $L > R$ を満たす $b$ ならを増やすと悲しさは減り
• $L = R$ を満たす $b$ なら悲しさは変わらず
• $L < R$ を満たす $b$ ならを増やすと悲しさは増える

ので三分探索できる。三分探索を浮動小数で行うと丸め誤差が含まれるので、最小値の候補 $\pm 1000$ を探索すると正解が出る。整数を三分探索するのは、微分を二分探索するのと 同じ である。

正解はなんと中央値だった。 $A_i$ から $i$ をあらかじめ引いておき、 $N$ が偶数のときに中央値は小数点以下切り捨てでよい( $N/2$ 番目の要素と $N/2 + 1$ 番目の要素のどちらを $b$ にしても悲しさは同じなので)。

コードはこちら

貪欲法も時に青diffになる。

四分割は二分割の二分割なので、大きな二分割点を決め打ちして、小さな二分割点を決めればよさそうである。実際そうすることができ、部分列の要素の和を $sum$ とすると、先頭から $\lfloor sum/2 \rfloor$ と $\lceil sum/2 \rceil$ のどちらかで分割する。こうすれば分割してできた二つの部分列の和について、両者の差をもっとも小さくできる。この二か所以外で分割しても両者の差が広がるだけなので考えない。

あとは大きな二分割点を全探索すればよい。二分探索なら $O(N \times log(N))$ で求まる。尺取り法を用いてもよい。

$K$ の一部のビットが立った数の集合 $S$ があったとき、 $i \in S$ について $A_i$ の上位2位を選べばいい、と予想はしたがそれ以上分からなかった。

コードはこちら

原点 $x=0$ にろうそくがあるなら即座に回収して $N,K$ をそれぞれ1減らす。この時点で $N=0$ なら答えは 0 である。

負の座標にろうそくが $L$ 本あるとする。正の座標にはろうそくが $R = N-L$ 本ある。これは $X$ を std::upper_bound(xs,0) - xs.begin() で求まる。以下のパターンを網羅して、最小値が答えである。

• $L \geq K$ なら、負の座標のろうそくだけ回収する。これは $-X[L+1-K]$ である。
• $R \geq K$ なら、正の座標のろうそくだけ回収する。これは $X[L+K]$ である。
• 負の座標のろうそくを $i = 1..min(L,K)$ 本回収して、残りは正の座標のろうそくを回収する。これは $-2 \times X[L+1-i] + X[L+N-i]$ である。
• 正の座標のろうそくを $i = 1..min(R,K)$ 本回収して、残りは負の座標のろうそくを回収する。これは $2 \times X[L+i] - X[L+1-(N-i)]$ である。

公式解説は上記で2倍するのを避けて、回収する連続 $N$ 本のろうそくを求めることで簡単にしている。実装は こちら 。

• 回収する左端のろうそくを $L=X_i$ , 右端のろうそくを $R=X_{i+K-1}$ とする。ただし $i=1..(N-K+1)$ 。
• $L$ が負で $R$ が正、つまり $LR < 0$ なら、原点に近い方を往復、そうでない方は片道なので最短距離は $R - L + min(|L|, |R|)$
• そうでなければ一方通行なので最短距離は $min(|L|, |R|)$

コードはこちら

$r = A mod K$ とする。題意を満たすには、 $B mod K = (K - r) mod K$ , $C mod K = r = (K - r) mod K$ である必要がある。 $C$ に注目すると、

• $A,B,C$ とも $K$ の倍数。この組み合わせは ${\lfloor N/K \rfloor}^3$
• $K$ が偶数かつ $A,B,C$ とも $K$ で割った余りが $K/2$ 。この組み合わせは ${\lfloor (N+K/2)/K \rfloor}^3$

が答えである。

コードはこちら

桁DP

あらゆる数は2進数表記 $\sum_{i} 2^i$ で表現可能である。制約から2進数20桁以内で表現できると分かるので、頂点を関連付ける。

頂点番号を逆に読んで0-based indexingとし、終点を頂点0、始点を頂点19とする。

$L$ を2進数 $W$ 桁で表現可能として、 $2^{W-1}$ 以下の数を $\sum_{i=0..(W-2)} 2^i$ で表現する。これは頂点 $i+1$ から 頂点 $i$ に向かって、長さ $(0,2^i)$ という多重辺を張れば実現できる。それ以外の番号が連続する頂点は、頂点 $i+1$ から 頂点 $i$ に向かって長さ0の頂点を張る。

$2^{W-1} \leq a < L$ の数を $\sum{i=0..(W-1)} 2^i + C$ で表現する。これは $L$ の2進数表現を上の桁からみて、 $i$ 桁目に1のビットを2個以上見たら、そのビットを立てられないと解釈する。 $L$ の $i$ 桁以上の部分を $C$ として、始点と頂点 $i+1$ を長さ $C$ で結ぶ。

このようなグラフを構成する、前者の辺は高々40本、後者の辺は高々20本なので題意を満たす。

コードはこちら

除外条件が厄介。

グラフを構築できない状況として、サイズ1の連結成分を作れない、サイズ $n$ の連結成分を作れる、サイズ $i=1..(n-1)$ の連結成分が作れるのにサイズ $n-i$ の連結成分が作れない、というものがある。これらを列挙するのが大変である。

上記の条件を満たすとして、逐次的にグラフを構築する。まず頂点1をサイズ1の連結成分とする。最後につくった連結成分の大きさを $U$ 、連結成分サイズが $j$ の根となる頂点を $R_j$ する。特に最後に作った連結成分の根を $R$ とする。サイズ $i$ の連結成分は以下のように作る。

• サイズ $i$ 頂点を作らない、つまり $s[i] = 0$ なら何もしない。以下 $s[i] = 1$ とする。
• 新たな頂点 $V = R + 1$ を確保する。頂点が足りないつまり $V > N$ ならグラフを作れない。
• 辺 $(V,R)$ を張る。
• $i = U$ ならこの辺を切断すると、サイズ $U$ の連結成分を作れる。そうでなければ $D = i - U$ 個の頂点 $V+1..V+D$ と $(V,V+1..V+D)$ を足りていれば追加する。追加した頂点と隣接する辺を切断すると、サイズ $i = U + D$ の連結成分になる。
• 最後に作った連結成分の大きさを $i$ 、根を $R = V + D$ とする

頂点が足りていれば題意の形式で出力する。