青diff(★6)までを解く練習です。解答時間は分未満切り捨て、誤答ペナルティは含みません。

コードはこちら 。★4: 途中で諦めた。

二分探索

であることはすぐわかったが、何をしていいか鉄則本A77を読み返すまで全く分からなかった。右端を切りすぎないようにする。

コードはこちら 。★3: 5分。

全探索

気を取り直して今度は全探索である。 $N$ が奇数なら何も出力しない。以下 $N$ が偶数とする。

std::string の辞書順で ( < ) なので、 $N/2$ 個の ( に $N/2$ 個の ) をつなげた文字列 $S$ を初期解とする。 $S$ を std::next_permutation で全探索する。 $S$ のうち正しいカッコ列は、先頭からの ) の個数が ( の個数以下のものである。これは $S$ を先頭から走査すれば分かる。

コードはこちら 。★4: 19分。

木の直径

$N$ 頂点で $N-1$ 辺ですべての頂点間が到達可能なら木である。よって頂点間の距離の最大値が答えで、これは木の直径である。求め方は こちら にあるので、その通り実装する。木の直径を初めて実装したので、解答に20分掛かった。

スコアは木の直径に1足したもの(ループなので)である。

コードはこちら 。★2: 5分。

重複を除く

$i$ 行目かつ $j$ 列目 の値は、 $i$ 行の合計 + $j$ 列の合計 - $A_{i,j}$ である。

コードはこちら 。★6: 15分。

先頭の文字は $1..(N-K+1)$ 文字目から選択する。このとき a..z のうち、辞書順で最も小さい文字の、最も左側(位置 $p_1 \in {1,(N-K+1)})$ が小さいもの)を選ぶ。

二番目の文字は $(p_{1}+1)..(N-K+2)$ 文字目から選択する。このとき a..z のうち、辞書順で最も小さい文字の、最も左側(位置 $p_2 \in {1,(N-K+2)})$ が小さいもの)を選ぶ。以下同様である。

$i..(N-K+i)$ 文字目に a が含まれているかどうかは、 $1..N$ について a の出現回数の累積和を取れば分かる。 b..z についても同様である。よって部分文字列にある文字が含まれているかどうかは $O(1)$ で分かり、その位置は std::string::find で分かる。 std::string::find そのものは $O(N)$ であるが、 $p_i$ は1回走査するごとに文字列の終端に向かっていくので走査回数の和は $O(N)$ である。

コードはこちら 。★3: 5分。

$A_i$ を昇順にソートして、それぞれの $b$ について $b \leq A_i$ なる最小の $i$ を std::lower_bound で求める。 $min(abs(A_i - b), abs(b - A_{i-1}))$ が答えである。ただし $i &gt; N$ なら $abs(A_i - b)$ は無く、 $i = 1$ なら $abs(b - A_{i-1})$ は無い。

コードはこちら 。★4: 6分。

DP

幾度となく見たDPである。 $DP[i][j]$ は、 $S$ の $i=1..N$ 文字目までみたときに、 atcoder の $j$ 文字目までを取る組み合わせの数である。

• $DP[][] = 0, DP[0][0] = 1$ で初期化する
• $DP[i+1][j] += DP[i][j]$ で一文字進める
• $s_i = j$ なら $DP[i][j]$ に $DP[i-1][j]$ を足す

コードはこちら。★6: 33分。

頂点を三つ選ぶと計算量は $O(N^3)$ だが、一つを固定して円周方向に調べれば計算量は $O(N^2log(N))$ になる。

くの字の真ん中 $P_j$ を $P_{j=1..N}$ に固定して、 $P_{i=1..N}, i \ne j$ の角度を求める。これは $P_j$ を原点として $P_i$ を平行移動してから長さ1にする。このときX軸方向の単位ベクトル $I=(1,0)$ に対して $\angle P_i P_j I = cos(P_i, U) = X_i - X_j$ である。角度は $Y_i - Y_j \geq 0$ なら $180cos(P_i, U) / \pi$ 、 $Y_i - Y_j &lt; 0$ なら $360-180cos(P_i, U) / \pi$ である。

こうして求めた $N-1$ 個の角度を昇順に並べ、並べたものに360を足して $angles[2(N-1)]$ を作る。 $angles[2(N-1)]$ の先頭から $i=1..(N-1)$ までの要素について、 $(i+1)..(i+N-2)$ 番目の要素の中から $angles[i] + 180$ の前後の要素を2個選ぶ。これは std::lower_bound のイテレータ範囲を注意深く設定すると求められる。

それぞれの $j$ の、それぞれの $i$ から求めた角度が解の候補であり、最大の値が答えである。角度 $a$ が180を超えたら $360-a$ に読み替える。

コードはこちら 。★2: 6分。

累積和

クラス1について、学籍番号 $i=1..N$ について累積和 $cumcum[0]$ を求める。属していないクラスについては0点とする。答えは $cumsum[0][R] - cumsum[0][L-1]$ である。クラス2も同様。

コードはこちら 。★6: 全部は解けなかったがsubtask2(4点)まで解けた。

Subtask2まで解くなら、 $2^N \leq 2^{20}$ 通りを全探索すればよい。

全部解くのはDPでよかった。制約をよく見れば、仕事と期限の二次元DPすればよいと分かる(報酬では多すぎる)。

コードはこちら 。★4: 22分。

Union-find木

マスがつながっているかどうかは、union-find木の連結成分かどうかで分かる。

• クエリ1についてマス $(r_i,c_i)$ を塗り、 $(r_i \pm 1,c_i \pm 1)$ が塗られていたら連結する
• クエリ2についてマス $(r_a,c_a)$ と $(r_b,c_b)$ が両方塗られていてかつ連結なら Yes 、そうでなければ No である

解の方針はすぐにたったが、なぜか実装を誤って時間が掛かった。

コードはこちら 。★5: 5分。

ダイクストラ法である。頂点 $1$ と頂点 $N$ それぞれから、頂点 $1..N$ への最短距離を求める。頂点 $1$ から頂点 $k$ を経由して頂点 $N$ に行く最短距離は、頂点 $1$ から頂点 $k$ への最短距離と、頂点 $k$ から頂点 $N$ への最短距離の和である。

コードはこちら 。★3: 4分。

貪欲法?

$|A_i - B_i| + |A_{i+1} - B_{i+1}| \leq |A_i - B_{i+1}| + |A_{i+1} - B_i|$ なので、 $A_i$ から $B_i$ に通うのが最適である。

コードはこちら 。★6: 諦めた

解法はおおむねあっていたが、メモ化するものを間違えた。

メモ化する対象は階乗 $n!$ と階乗の逆元 $1/n!$ である。 $n \choose k$ をメモ化しても実行時間は短くならない。

ボール間を距離 $k$ 離せるときにボール間の隙間( $k-1$ 個以上離した場所)は最大 $w = \lfloor (N-1)/k \rfloor$ 箇所である。この数は調和級数なので、ループ回数は $O(N^2)$ ではなく $O(Nlog(N))$ になる。

隙間の数は $i=0..w$ 個ある。隙間が $i$ 個のとき、ボール間をきっちり距離 $k$ 離す、つまり間にボールをきっちり $K-1$ 個ずつ詰めた場合、残りのボールは $r = N-i \times w - 1$ 個ある。残りのボールをどの隙間に置くか考える。 $r$ 個のボールを $i$ 箇所の隙間に積める組み合わせは、 $r$ 個ボールと $i+1$ の仕切りを並べる方法の数なので ${r+i+1} \choose {i+1}$ 通りである。これをすべて求めればよい。

あらかじめ $0..N$ の階乗およびその逆元を求めておくとTLEしない。公式解説も表現は異なるが、本質的には同じことを述べている。

コードはこちら 。★3: 15分。

総当たり

$A &gt; B &gt; C$ に並び替えて置く。合計9999枚と解っているので、

• A は $a = 0..9999$ 枚を総当たりする。ただし $aA \leq N$ の範囲だけ調べる。
• B は $a = 0..(9999-a)$ 枚を総当たりする。ただし $aA + bB \leq N$ の範囲だけ調べる。
• C は $N - aA - bB$ から一意に求まる。ただし合計枚数が9999枚以下で、合計金額がきっちり $N$ になることが条件である。

DPにしようかどうか悩んでしまった。制約条件を上手く使う。

コードはこちら 。★3: 14分。

素直に求める。

$L$ は半分、 $E$ は $T$ で割った余りとする。観覧車の始点からの角度は $rad = E/T$ なので、像を基準に観覧車の相対位置は $(tx,ty,tz) = (-X, sin(rad) \times L-Y, (1-cos(rad)) \times L)$ にある。求める角度は $arctan(tz / \sqrt{tx^2 + ty^2})$ である。

Degreeとradianの変換に悩んでしまった。

コードはこちら。★6: 自力では解けなかった。

区間DP

鉄則本C18と同じである。初見では全く解けずに悔し涙を流した問題である。解法を知っているとはいえ、今なら30分で解ける。

コストは取り除く数の組に依存するが、組が同じならどういう順番で取り除いたかには影響しない。よって最終的には取り除く区間は全域になるが、全域になるまで連続した部分をどう組み合わせるかをDPで網羅すればよい。これをボトムアップに考える。 $A_i$ から連続する整数を除くことを考える。

• 最初は位置が2連続する整数 $[A_i, A_{i+1}] \quad for \quad 1 \leq i \leq n$ を除く
• 次に連続する4整数を除く。これは $[A_i, A_{i+1}], [A_{i+2}, A_{i+3}]$ か $[A_i, A_{i+3}], [A_{i+1}, A_{i+2}]$ のどちらかなので最小値を採用する。 $[A_i, A_{i+3}]$ はその場で計算し、残りは位置が2連続する整数を除くコストとして既に分かっている。
• 位置が $2w \geq 6$ 連続する整数を除く。これは以下の通り網羅できるので最小値を採用する。
  • 両端をつまむ $[A_i, A_{i+2w-1}], [A_{i+2}, A_{i+2w-2}]$ 。前者はその場で計算し、後者は既に求まっている。
  • 区間を分割する $1 \leq j \leq w$ なる各 $j$ について、 $[A_i, A_{i+2j-1}], [A_{2j}, A_{i+2w-1}]$ 。どちらも既に求まっている。

これまで調べた区間の幅を $2w$, 区間の左端の位置を $i$ として $DP[w][i]$ を更新すればよく、区間を分割する方法が $O(N)$ なので計算量は $O(N^3)$ である。答えは $DP[w][1]$ である。

コードはこちら 。★3: 8分。

有効桁数53-bit浮動小数の罠

と思われるので64-bit整数の範囲で計算する。 $log_{2}a &lt; b \times log_{2}c \Leftrightarrow 2^{log_{2}a} &lt; 2^{log_{2}c \times b} \Leftrightarrow a &lt; c^b$ に変換し、 $c^b$ を整数演算で( std::pow を使わずに)計算する。

$x^{y \times z}$ は ${x^y}^z$ である。うっかり $x^{y+z}$ にしてしまった。

コードはこちら。★5: 4分。

強連結成分分解するとサイクルが分かる。各サイクルの大きさを $K$ としたとき、 $K(K-1)$ が互いに行き来できる頂点の組み合わせ数である。これをすべてのサイクルについて足す。

コードはこちら 。★2: 1分。

$A,B,C$ の最大公約数 $g$ が、立方体の大きさである。 $A$ を $g$ にするには、 $A/g-1$ 回切ればいい。 $B,C$ も同様である。

コードはこちら 。★2: 5分。

$A,B$ の絶対値の差の和 $d$ を取る。 $d &gt; k$ なら No である。 $d \leq k$ が奇数なら No 、偶数なら Yes である。

コードはこちら 。★2: 43分。

鳩の巣原理

木の頂点を赤と黒で互い違いに塗る。どの頂点から塗ってもよい。赤と黒で塗った頂点は隣り合わない。赤い頂点と黒い頂点のどちらか一方は $N/2$ 個以上あるはずなので、それらを列挙する。

木は二部グラフにできることを知っていると冷静になれる。

コードはこちら 。★2: 1分。

$S_i$ が既に存在するかどうかを std::set<std::string> で管理する。

コードはこちら 。★4: 8分。

二次元いもす法 そのままである。

コードはこちら 。★5: 43分。

始めて遅延評価セグメント木を使った。ノードを整数、演算をmaxにすればよい。

コードはこちら 。★5: 27分。

$K=1$ なら答えは $N-1$ である。

エラトステネスの篩の変形である。既知の素数 $2 \leq p \leq \sqrt{N}$ で割れるだけ割ってみると、 $\sqrt{N}$ 以下の素因数で何種類割れたか分かる。あとは $\sqrt{N} &lt; i \leq N$ について、残った商が1より大きければ素数のはずなので素因数の数を1足す。

コードはこちら★6: 諦めた

Grundy数を求める問題である。解説をしっかり読まないと理解できない。可能手の依存グラフの最短距離と求めたのではだめだった。

コードはこちら 。★3: 11分。

$N=10$ なので、すべての順列を調べる。順列について、仲が悪い選手の並びが無いものについて、最小タイムを求める。

factorial(10)
## [1] 3628800

コードはこちら 。★2: 8分。

定義により $H,W=1$ なら不適切にならない。それ以外は先頭を1行目、1列目と数えて、偶数行と偶数列とを点灯せず、奇数行かつ奇数列のみ点灯する場合が答えである。

コードはこちら 。★4: 30分。

デバッグに苦しんだ。 std::multiset::size() は要素の数、 std::map::size() はキーの数なので混同しない。それと std::map::operator[] はデフォルトコンストラクタで作った値(0)が格納されたキーを作ってしまう。つまり

if ((size < k) || ((size == k) && (xs[d] != 0))) {}

はキー d が増えてしまうので、

if ((size < k) || ((size == k) && (xs.find(d) != xs.end()))) {}

と書かなければならない。

解き方は尺取り法である。右側を伸ばすと部分列に含まれる要素の種類は広義単調増加(同じか増える)である。よって $K$ 種類を超えたところまで右側を伸ばす。右側が伸びきったら左側を伸ばすと部分列に含まれる要素の種類は広義単調減少(同じか減る)ので、 $K$ 種類以下になるまで伸ばす。

集合は std::map で、キーの種類は集合の要素の種類、キーの値は要素の数である。要素の数が0になったらキーごと削除する。

コードはこちら 。★7 解説AC

Auxiliary Tree の例題と知った上で解いた。

Auxiliary Tree の実装は こちら を参考にした。

最初にセグメント木で、任意の2頂点間のLCAを求める。次にクエリにある頂点からAuxiliary Treeを構成し、それぞれの頂点から親(根を除く)までの辺の長さの和が答えである。

コードはこちら 。★5: 29分。

Convex hull ではない、等高線である。

マンハッタン距離の等高線 $x+y$, $x-y$ を定義し、それぞれの頂点を等高線上の座標に変換する。等高線間の距離の最大値が答えである。

コードはこちら 。★5: 43分。

DPなのだがそのままではTLEする。 $DP[i][r]$ を料理 $i$ まで作ったときにスパイスの残りが $r$ のときの料理の価値の合計とする。 $DP[0][W]=1, DP[0][]=-Inf$ とする。

料理 $i+1$ にスパイスを $L \leq j \leq R$ 使うとして料理の価値の合計は $DP[i+1][r-j]=max(DP[i+1][r-j], DP[i][r]+V_i)$ である。これを $0 \leq r \leq W$ , $L \leq j \leq R$ ごとに計算するとTLEするので工夫する。

• $from[r] = DP[i][r]+V_i$ を計算しておく
• $to = (W-L)..0$ について、 $DP[i+1][to]$ が取りうる値の集合は $from[to+L,to+R]$ が重なる区間である。よって重なっている区間の集合 $S$ を std::multiset で管理する。
• $to$ を一個減らすごとに、集合 $S$ に $from[to+L]$ を増やす。 $DP[i+1][r-j]=max(DP[i+1][r-j], max(S))$ である。 $S$ の要素数が $R-L+1$ 以上なら、最後に集合に入れた要素を除く。

コードはこちら 。★3: 7分。

$LCM(A,B) = GCD(A,B) \times A \times B$ である。よって $GCD(A,B) \times A \times B &gt; 10^{18} \Leftrightarrow GCD(A,B) &gt; (10^{18}/AB)$ を判定する。この式が成り立つなら Large を出力し、そうでなければ求めた $LCM(A,B)$ を出力する。

コードはこちら 。★5: 12分。

頂点間の距離ではなく、辺を何回数えるかを求める。頂点 $a,b$ を結ぶ辺 $AB$ があるとして、辺 $AB$ を数える回数は辺 $AB$ を通らずに行ける頂点の組、つまり頂点 $a$ より端と頂点 $b$ より端の頂点の数の積である。よって辺の両端以降に何個頂点があるか数える。

木の根を頂点1と決め打ちして、DFSによって部分木の頂点数(部分木の根を含む)を求める。木なので頂点 $a$ は頂点 $b$ よりも根から遠いと定められる(そうでなければ $a,b$ を入れ替える)。根から遠いかどうかは、部分木の大きさが小さい方が根から遠い。 頂点 $a$ を根とする部分木の頂点数が $K(a)$ なら、aより端とbより端の頂点の数の積は $K(a) \times (N-k(a))$ である。この和が答えである。

コードはこちら 。★4: 12分。

$K$ を9で割り切れなければ0通りである。

動的計画法で残りが $i$ となるのが $DP[i=K..0]$ 通りとする。 $DP[K]=1,DP[]=0$ とし、 $DP[i-j] =DP[i-j]+DP[i] \quad for \quad j=1..9$ で更新する。答えは $DP[0]$ である。

コードはこちら 。★4: 30分。

01-BFSで解く。位置 $(y,x)$ と方向(4方向)について、始点からの距離を $dist[y][x][dir]$ とする。方向が同じなら距離はそのまま、方向転換するときは距離を1増やす。

BFSは次に探索する位置と方向をキューで管理する。キューから取り出した時距離が最短より長ければ何もせず捨てる。そうしないとTLEする。キューが空になったとき、 $dist[y][x][]$ の最小値が答えである。

コードはこちら 。★3: 7分。

カーソルを持つ。クエリ2はカーソルを1減らす。クエリ1,3はカーソルを足した位置で扱う。

コードはこちら 。★6: 62分。

効率的に全探索する。

最初に二頂点間の距離の二乗を測る。 $O(N^2)$ なのですぐ終わる。次に可能なグループ $2^N$ 通りについて、グループ内の頂点の最長距離を測る。

可能なグループ分けをDFSで求めて、グループ内の頂点の最長距離が求まったら、その最小値を更新する。効率よくDFSしないとTLEする。以下0-based indexingで要点を挙げる。

• グループ群を std::vector<std::bitset<16>> groups(k) で実装する
• 頂点0をグループ0に固定する
• 頂点iをグループ $0..min(i,k-1)$ のどれかに含める。それ以外のグループに属すると数え上げが重複してTLEする。
• どのグループに割り当てるかが未決定な頂点の数より、空のグループが多ければ打ち切る
• あるグループの最長距離が、既知の最小値以上なら打ち切る。既知の最小値より長ければ、にするとTLEする。

公式解説はbitDPで、上記とは少し異なる気がする(現在のグループ数を更新している訳ではないので)。

コードはこちら。★3: 4分。

$A$ を46で割った余り + $B$ を46で割った余り + $C$ を46で割った余り = 46 の倍数である。なので $A,B,C$ を46で割った余りが $0..45$ になるような数が何個あるか数える。 $A,B$ を46で割った余りを総当たりすれば $C$ を46で割った余りは一意に決まるので、そうなる数の個数を掛ける。

コードはこちら ★3: 13分。

部分点を優先度キューに入れて、値が最も大きな物から $K$ 個取り出す。部分点を優先度キューから取り出したら、対応する問題の満点と部分点の差を優先度キューに入れる。すでに部分点を優先度キューに入れたことがある問題は、優先度キューに入れない。

コードはこちら 。★6: 39分。

最小全域木(MST: Minimum Spanning Tree)を作る問題と等価である。入力を0-based indexingに読み直して、アイテム $i$ は $[L_i-1,R_i)$ を覆うとみなす。このとき $L_i-1$ と $R_i$ を双方向(無向)に重み $C_i$ の辺で結ぶと、 $L_i-1$ が決まれば $R_i$ が決まる(またはその逆)と読める。決めるとはどういうことかは、公式解説に載っている(よく理解しないままACできてしまった)。

アイテムをコストの昇順に並べ替えて、頂点番号 $0..N$ , 頂点数 $N+1$ , 辺の数 $N$ のMSTを作る。これはunion-find木などを使って構築できる。MSTが作れなければ答えは -1 である。作れたらMSTの辺の重みの和が答えである。

コードはこちら ★3: 2分。

配るDPで実装する。

コードはこちら ★3: 4分。

あるサイコロの目の和は、必ず同じ回数足す。つまりサイコロが二個のとき、

$\sum_{i=1..6} \sum_{j=1..6} (A_{i,1} A_{j,2}) = \sum_{i=1..6} A_{i,1} \times \sum_{j=1..6} A_{j,2}$ である。サイコロが3個以上あってもこの繰り返しになる。

コードはこちら ★6: 22分。

高橋数は1ずつ増えて連鎖する。つまり

• 研究者1が書いた論文の共著者は高橋数1
• 研究者1が書いた論文の、共著者が書いた論文の共著者は高橋数2
• 研究者1が書いた論文の、共著者が書いた論文の、共著者が書いた論文の共著者は高橋数3

を繰り返すと求まる。同じ論文と同じ著者を二度数えないようにする。実質的に、研究者1から研究者Nへの最短距離を求めることに等しい。

公式解説では著者間を直接結ぶのではなく論文を経由することで辺の数を抑えているが、上記と本質的には同じである。超頂点を導入しなくても論文が超頂点代わりになっていると言える。

コードはこちら ★2: 数十分。

乗算が重い。数字を選ぶ方法は $N \choose 5$ 通りあるが、これを全列挙するとTLEする。 $N \choose 4$ 通り列挙して残りは総当たりするとTLEしない。

コードはこちら ★6: 諦めた

あるスイッチ群と $S$ のxorを取ると全部のパネルが0になることは分かったが、組み合わせを列挙する方法が分からなかった。XORで行列の掃き出し法を使うのが想定解法である。

コードはこちら ★4: 13分。

鳩の巣原理である。電卓の状態は 100000 個しかないのだから、100000回より多くボタンを押せば必ず同じ状態を二度通る。これを初期状態 $0..99999$ から同じ状態を二度通るまでの状態遷移を作成する(クエリではないので初期状態は $N$ だけ考えればよい)。

これが分かれば、初期状態 $N$ からループまでと、ループのどこで止まるかを求める。

コードはこちら ★5: 27分。

LIS: Longest Increasing Subsequence を左右から求める。LISの求め方は鉄則本A24のコードを用いる(ただし0-based indexingにしてある)。求める部分列は、左端から右肩上がりの $L_i$ 個、右端から左肩上がりの $R_i$ , 頂点なので $max(L_i+R_i+1)$ である。

コードはこちら ★2: 4分。

std::deque で実装する。

コードはこちら ★6: 31分。

最後のボールを塗るためには自己ループしかありえない。よって自己ループがないときは塗れないボールがある。

アイテムについて、 $A_i$ から $i$ , $B_i$ から $i$ (ただし $A_i \ne B_i$ のときに限る)への有向グラフを張る。塗れるボールをキューで管理し、最初に自己ループするボールつまり $A_i = i$ または $B_i = i$ を満たすボール $i$ をキューに加える。

キューからボールを取り出し、有向グラフの行先があり、行先のボールはまだキューに一度も積んだことがなければキューに積む。これをキューが空になるまで繰り返す。併せてキューからボールを取り出した順番を記録する。

キューからボールを取り出した順番の逆順が答えの一つである。ただしキューに入れたことの無いボールは塗れないので、取り出した順番が $N$ より短ければ -1 である。自己ループがなければ一度も塗れない。

コードはこちら ★3: 23分。

いもす法だが、中間結果を求められる。落ち着いて0-based indexingする。

不便さが変わるのは $L_{i-1},L_{i}$ と $R_{i},R_{i+1}$ だけで他は変わらない。よってこの二か所(ただし両端を除く)の不便さだけを更新する。

コードはこちら ★5: 20分。

$a_{i=1..N}$ が $0..101$ になる期待値 $E_i[0..101]$ を求めれば、 $E_i[0..k-1] &gt; k, L_i \leq k \leq R_i$ が転倒数の期待値である。ここでは $N$ が小さいので累積和を使わなくてもいい。

コードはこちら ★2: 11分。

0には0を出力する。8進数を文字列、9進数を int64_t で管理すると扱いやすい。下の桁が文字列の最初と最後のどちらなのか気を付ける。

コードはこちら ★5: 72分。

$X_i$, $Y_i$ は0-based indexingとして1引いておく。

$T_i=1$ に対して、 $A_{X_{i}},A_{X_{i+1}}, ... ,A_{Y_{i}}$ までがつながっていれば、これらから求めた値と $V_i$ から $A_{Y_{i}}$ を求めることができる。なのでつながっているとはどういうことか、値をどう求めるかが課題である。

$T_i=0$ で以下の操作をすればいい。

• $X_i$ と $Y_i=X_i+1$ をunion-find木で連結する
• セグメント木の $[X_i,X_{i+1})$ に $V_i \times (-1)^{X_i-1}$ を設定する。交代和という。

$T_i=1$ に対して、 セグメント木の $prod(X_i,Y_i)$ に対する値 $diff$ を使って、 $V_i$ から $A_{Y_{i}}$ を求めることができる。なぜなら $X_i &lt; Y_i$ なら $prod(X_i,Y_i) = (X_i+X_{i+1})(-1)^{X_i} + (X_{i+1}+X_{i+2})(-1)^{X_i+1} + ... + (Y_{i-1}+Y_{i})(-1)^{Y_i-1} = X_i(-1)^{X_i} + Y_{i}(-1)^{Y_i-1}$ だからである。同様に $X_i &gt; Y_i$ なら $prod(Y_i,X_i) = Y_i(-1)^{Y_i} + X_{i}(-1)^{X_i-1}$ である。 $X_i = Y_i$ なら $X_i = v = Y_i$ である。

元のコードが条件分岐だらけで読みづらいので、 このよう にまとめる。

$-1^{X_i}$ または $-1^{X_i-1}$ の部分を $X_i$ の符号として整理する。

• $flip = 1 \quad if \quad (X_i &gt; Y_i) \quad else \quad 0$
• $sign(X_i) = 1 \quad if \quad (X_i + flip) \quad is \quad even \quad else \quad -1$
• $sign(Y_i) = 1 \quad if \quad (Y_i + flip) \quad is \quad even \quad else \quad -1$

符号から以下を求める。

• $X_i = Y_i$ なら $Y_i = V_i$
• $X_i \ne Y_i$ なら $Y_{i} = (prod(X_i,Y_i) - sign(X_i)V_i) / sign(Y_i)$

コードはこちら ★3: 6分。

距離が2個より離れれば何でも選べる。 $N=1$ なら $K$, $N=2$ なら $K(K-1)$ , $N &gt; 2$ なら $K(K-1){(K-2)}^{(N-2)}$ である。

コードはこちら ★4: 35分。

X座標とY座標は独立に考えてよい。一次元座標にある点 $A..{1..N}$ からのマンハッタン距離の和を最小化する点は $median(A..{1..N})$ である。重心 $mean(A..{1..N})$ ではない。おそらく中央値だとは思ったが、実際に調べるまで分からなかった。 $N$ が偶数の場合は、中央値の左右どちらの要素を選んでもよいので、中央値として0-based indexingで $A_{\lfloor x/2 \rfloor}$ を調べる。

コードはこちら ★5: 解けなかった

木DPである。公式解説 に詳しく載っている。

コードはこちら ★6: 35分。

左から先頭 $1..N$ 文字目が a になるようにそろえていくが、いったんそろえたものが崩れてもいいと考える。 $ord(x)$ を文字 x の文字コードとする。1文字目が x のときそろえる回数は $ord(x)-ord(a)$ 、つまり a なら0回、 b なら1回、 c なら2回である。同様に左から先頭 $1..i$ 文字目が a で $i+1$ 文字目が x のときそろえる回数は $2^{i-1} \times (ord(x)-ord(a))$ である。これを $1..N$ 文字目について合計したものが答えである。

おそらく不変量があると思ったが不変量を導出できなかったので、アドホックに解いた。この問題の不変量は公式解説に載っている。

コードはこちら ★3: 6分。

$N$ を素因数分解し、 $K$ 個の素因数から成ることが分かる。ボールを1個叩くと個数が2倍になるので、 $\lceil log2(K) \rceil$ 回叩けばよい。 $N$ が素数なら $K=1$ であり0回になる。$log2(K)$ は std::bit_width で求まる。

コードはこちら ★3: 7分。

$N$ ピースの大きさの合計が10の倍数でなければ No である。そうでなければ、合計の1/10を $S$ とする。

二周分の累積和を取り、尺取り法で $S$ になるような区間を求める。 時計回りの先頭を $right$ とし(累積和の左端でもある)、末尾(累積和の右端としては一つ前)を $left$ とする。二周あるので尺取り法の始点 $left &lt; N$ , 幅 $right-left \leq N$ の範囲で調べる。

コードはこちら ★2: 6分。

その通り実装する。

コードはこちら ★3: 7分。

左上から順に揃えて行けばよい。

コードはこちら ★6: 諦めた。

包除原理らしいのは分かったが、一般解が分からなかった。 $N$ 要素からなる集合について符号は $-1^{N}$ とわかれば解ける。あとは $A_{1..N}$ の全組み合わせを網羅すればいい。

コードはこちら ★5: 8分。

あるグループの最低身長 $minH$ と最低体重 $minW$ を決め打ちする。そうすればそれぞれを決め打ちして $5000^2$ 回のループを回せば解ける。

最初にある身長 $1..5000$ をキーとして、それぞれの人の体重 $1..5000$ をベクタとして持つ。ここから最低身長 $minH$ を尺取り法で変えつつ、 身長 $[minH,minH+K]$ の人の体重のヒストグラムを作る。

最低身長 $minH$ を決め打ちしたら、最低体重 $[minW,minW+K]$ をやはり尺取り法で変えると、グループに属する人数が分かる。この最大値が答えである。

ヒストグラムの更新は、最低身長 $minH$ を1増やしたら身長 $minH$ の人の体重を抜けばいい。なのでヒストグラムの更新回数は全体で $O(N)$ 回である。

二次元累積和を使うと あっさり 解ける。

コードはこちら ★3: 100分。

$1..R$ までの文字数から $1..(L-1)$ までの文字数を引けばよい。 $1..n$ の文字数は $n$ が $w = 1 + \lceil log10(n) \rceil$ 桁だとして $i$ 桁目について

• $i &lt; w$ なら $i \times (10^{i} + 10^{i-1} - 1) \times (10^{i} - 10^{i-1}) / 2$
• $i = w$ なら $i \times (n + 10^{i}) \times (n - 10^{i-1} + 1) / 2$

である。 $mod 10^{9}+7$ において、2で割る操作は最後に行わないとWAする。これで一時間半溶かした。ライブラリ化すると こちら のようになる。

除算の位置を間違えなければ atcoder/modint で普通に解ける。

コードはこちら ★6: 部分点 52分。満点は諦めた。

満点解法をまだ理解していない。

コードはこちら ★3: 8分。

包除原理を使う。同じ文字が並んでいる部分文字列、つまりそれぞれのランレングスを数える。文字列全体で取りうる組み合わせは $N(N-1)/2$ 、 長さ $L$ のランについては $L(L-1)/2$ なので引くと残りが答えである。

コードはこちら ★4: 27分。

全探索で解ける。上限を $a \leq 10^4, b \leq 10^6$ と決め打ちするとWAする。素直に $a^3 \leq k, b^2 \leq k/a$ でガードするとACする。

想定解法は約数を列挙する。確かにこの方が速い。演算に 気を付ける 必要があり、乗算を雑に使うとオーバーフローしてREする。

コードはこちら ★4: 34分。

$w_i$ の最大桁数 $width=1 + \lfloor log2(max(w_i)) \rfloor$ について、$A_i$ を二進数表記したときのすべての桁は独立に考えてよい。最大桁数を超える桁は全ビット0なので考えない。

条件1をクエリと称してこう読み替える。 $w_i$ の二進数表記したときの各ビット $i=0..60$ について

• ビット $i$ が0なら、 $A_x,A_y,A_z$ のビット $i$ をすべて0にしなければらならない
• ビット $i$ が1なら、 $A_x,A_y,A_z$ のビットの少なくとも一つを1にしなければならない

条件をすべて読み込んだらパターンを全探索する。ビット位置 $pos=0..width$ について以下を求める。

• ビットパターン $0..(2^{n}-1)$ を、 $A_0..A_{N-1}$ のビット $pos$ を0にするか1にするかに対応させて、条件を満たすか全探索する。
  • 0にするビットは、実際にそうなっているかどうか調べる
  • そうでなければ、すべてのクエリを満たすかどうか調べる

各ビット位置について取りうるビットパターンの数の積が答えである。

コードはこちら ★5: 諦めた

数えるのは片方向である。ワーシャルフロイド法と二分探索で解けることまでは分かったが、どうしてもWAが取り切れなかった。公式解説を読んで、どんな $X$ を選んでも $K$ 通りを超えるなら0通りだということが分からなかった(これが分からなくて $\infty$ にしてしまった)。ここまで分かれば、 $K$ 通りを超える $X$ の数から、 $K$ 通り以上になる $X$ 数を引いたものが答えである。ただし、

• $K$ 通りを超える $X_{K+1}$ が無限にあるなら0通り
• $K$ 通り以上のる $X_{K}$ が無限にあるなら無限大通り

コードはこちら ★6: 諦めた。

和が8889通りなのでDFSで見つかるだろうとは予想したが、どうDFSで探索すれば良いかが分からなかった。

実はカード $1..N$ を使う/使わないというカードの集合を作り、和が $\sum_{i} A_i$ になるになるカードの集合が2個みつかったら出力して即終了すればいい。なのでDFSはカード $1..N$ を使う/使わないを試すだけでいい。カードの集合をみて、次に加えるべきカードが同居できないなら除外するのが重そうだが、C++で4 msecしか掛からないので問題にならない。

一見すると計算量が $2^N$ だが、実は $\sum_{i} A_i \leq 8888$ の制約があるので2個みつかるのは意外と早い(正確な考察は公式解説にある)。これを鳩の巣原理と公式解説では呼んでおり、計算量を見抜くのが教訓である。