AtCoder Regular Contest lessons learned 5

ARC 198で緑になったのでARCはratedではなくなりました。いつか戻ってきたときのための、振り返りです。

棚卸し

次回の ARC Div. 2に備えて過去問を分類する。

数学

移項して0になる式を作ると答えを求めやすくなる。

• 104-A : 連立方程式の解を求める
• 105-B : やっていることは、ユークリッドの互除法そのものである
• 107-A : $\sum_i f(i)$ において、 $f(i)$ の成分で添え字 $i$ によらない値は定数なので、 $\sum_i$ の外に出す
• 107-B : 引き算を移項すれば足し算になり、値が正という制約を探索しやすくなる
• 110-A : 最小公倍数を std::lcm で求める
• 111-A : 分子を $mod M^2$ で考える。 $M \leq 10000$ が暗示している。
• 115-C : 素因数の数を考える。約数または素因数が何個あるかで整数を分類するのは頻出である。
• 116-A : 整数 $i$ の約数の数は、 $i$ を素因数 $i = \prod {P_j^{Q_j}}$ の積で表現して、 $\prod (Q_j+1)$ である。よって $i$ が2または4の倍数かどうかで分類できる。167-Bも同様。
• 122-B : 値 $x$ と値の集合 $S$ との絶対誤差の和を最小化するには、 $x$ として $S$ の中央値を選ぶ
• 124-C : 数の集合 $S_1..S_N$ の最大公約数は、 $S_1..S_N$ それぞれの約数以下である。ほとんど同語反復だが、 $N$ が少ないときに $S_1$ の約数を全探索すると、 $S$ の最大公約数かどうかわかる。
• 125-B : 公式解説通り、 $x^2 - y = z^2$ から $p = x + z, q = x - z$ と置ける。幾何平均は算術平均以下であることを使う。
• 129-B : 公式解説通りに式を変形するとわかる
• 139-Bは平方分割することで、計算量を $O(\sqrt{N})$ にできる。実は全探索しか解がない。150-Bも同様。
• 154-Aは $A < B$ かつ $C < D$ なら $AD < BC$ である。差を取って因数分解すればわかる。
• 158-Bは 2つの数を固定すれば残り1つの数を変えて最大最小化することに帰着する
• 160-Bは $1..sqrt{N}$ を全探索すると決めれば、 $x \leq y \leq z$ の等号の位置と順列を考える
• 173-Bは 同一直線にたくさん点があれば残った点の数が上限になる。そうでないときに $\lfloor N/3 \rfloor$ になることを上手く証明する。
• 176-Bは 2進数の除算を筆算で求める
• 197-Bは 二つの数を入れ替えたらどうなる、と考えると最大の数を削るのがよいと分かる

丁寧に場合分けする

• 110-B : $T$ の長さが1,2,3以上で分ける
• 112-B : $B$ の0、正、負、Bが小さいので0にたどり着く場合、Cの偶奇で分ける
• 142-C : ほとんどの場合は、 $min(D_{1,i} + D_{2,i})$ だが、頂点1,2が隣接しているときが例外である
• 145-A : 基本は2文字目から AB 重ね書きして BAA..AAB か、右から2文字目から重ね書きして ABB..BBA にできる。文字列長が2,3の時に気を付ける。
• 178-B : 桁数が同じかどうか、繰り上がりが起きるかどうかで丁寧に場合分けする
• 188-B : $N = 2$ , $N$ が偶数かつ $K = N /2$ , $N$ が偶数, $N$ が奇数、に分ける
• 192-B : $N = 3$ を特別扱いする
• 193-A : 区間が重なっている時を考慮する
• 198-B : 状態遷移をすべて網羅する

上手く言い換える

グラフとネットワークフロー(まだコンテスト中に解いたことがない)は、言い換えがすべてである。包除原理も積極的に使う。

111-Bは解説通り言い換える。グラフの連結問題ということは直感的にわかるが、グラフが木かどうか判定するという意味付けを思いつく必要がある。

114-BはABCでもよくある、単射がサイクルを構成するなら強連結成分をなす、という問題である。なもりグラフもよく出る。

120-Cは公式解説にある通り、 $A_i^{'} = A_i + i$ と読み替えると転倒数に帰着できる。 $A_i$ を左に $j$ 移動すると値が $j$ 増えて位置が $j$ 減り、右に $j$ 移動すると $j$ 減るが位置も $j$ 増えるので、この読み替えが成立する。

126-Bは最長増加部分列(LIS)と等価である。LISの実装方法は複数あるが、セグメント木があるならセグメント木に載せるのがわかりやすい。133-Bも同じである。

合計 $N$ 個のボールを $K$ 個の箱に入れる方法は、箱と箱の間に仕切りを設ける方法を数える。箱にボールを0個以上入れるなら、 $N$ 個のボール、 $K-1$ 個の仕切りなので、 $(N + K - 1) \choose N$ 通りである。134-Cは1と書かれたボールを1個ずつ箱に配り(1通り)、1以外と書かれたボールを配り(この組み合わせを求める)、同数の1と1と書かれたボールを配り(1通り)、1と書かれたボールを過半数になるように配る(この組み合わせを求める)。

• 123-A : 移項して次元削減し、3変数を1変数にする
• 126-A : 長さ3の棒は偶数個ずつ使うので、長さ6の棒とみなす
• 128-A : 何もしないことは一日に2回交換すると考えると、連続する日を消去できる
• 143-A : 三つのうち二つの数を1引くことは、残り一つの数に1足すといえる
• 151-B : 辞書式順序の等号をunion-findでまとめていく
• 159-A : 基本的にワーシャルフロイド法だが、 $modN$ が同じときでも距離0にしないで測る
• 160-A : 左から $i$ 番目が $A_i$ より大きい、小さい、同じなので右を見る、というのは桁DPである
• 166-A : A を左に寄せると解釈する
• 172-B : 包除原理、つまり問題文に合わない文字列を数える
• 179-B : $B$ を置いたら $B$ は置けない、 $X_B$ を置いたら $B$ をまた置けるようになる

深読みし過ぎない

自明な解がそのまま答えで、深読みして時間を使いすぎないことがある。あるいは操作対象はそれほど多くないことを見抜く。

• 109-B : 長さ $n$ 以下の丸太をわざわざ分割する必要はなので、分割するなら長さ $n+1$ 丸太に限る
• 110-C : 1を左端に寄せて、寄せるための手番を消費する、というのは必須である。 $P_i=1$ を寄せた後 $i$ に対して同様に続ける。
• 111-C : 単に体重が軽い人から順に、本来荷物を持つべき人と交換すればよい
• 113-C : 文字列の末尾から先頭に向かってgreedyでよい。連続しない文字は操作で常に上書きできる。
• 115-B : $A$ の最小値を0に決め打ちして構わない。他の $A$ は差分であり、 $B$ は $\sum A$ から一意に求まる。
• 118-B : だいたい平均にして、残差が小さい物から1ずつ増やして補正する
• 120-B : 等高線、つまり始点からの距離が同じマスの集合をそろえる
• 121-A : 一番端と二番端の座標にある家を総当たりする。座標の組は高々8通りしかない。
• 121-B : 色違いは高々2組しかいない(1組目は奇数匹の集合から作るとわかるが、2組目を見落としがち)。公式解説ある通り、 RB, GB を別に計算しても最適性は失われない。
• 127-B : 2で始まる数値は三進数で小さい順に並べる。0,1で始まる数値は、0,1,2を置換すれば数合わせできる。
• 129-A : 桁DPに見えるが、実は $N$ の立っているビットを落とすだけである
• 137-A : 素数の間隔はそれほど広くない。 $10^{18}$ 以下なら連続する整数が1500個あればどれかは素数である。
• 146-B : 2進数の最上位桁を $i$ に決め打ちして、 $i$ 桁にそろえられるかどうかつまり全要素を $2^{i-1}$ 以上にできるか調べる。
• 163-A : 実は2分割でいい。先頭文字で分類するまでもなく、総当たりで間に合う。
• 169-A : 湧き出し、つまり入力がない頂点の値が無限回の値を決める
• 172-C : 投票者1を開票するタイミングを総当たりして解ける。公式解説2の通り、変化点だけ数える。
• 174-C : 期待値からの差だけに意味がある。買うのが星4のみ、星5のみ、星4一つと残りは星5、を全部試す。
• 175-A : 最終結果は2通りしかないので決め打ちする
• 176-A : $M \leq 10$ なので、高々10個しかない $(A,B)$ から斜めに線を引く
• 177-C : 2経路に必ず交点があるのは明らかだが、交点の場所を求める必要はない
• 182-A : 過去の操作と総当たりしても $O(N^2)$ で間に合う
• 184-A : $M+1$ 個が同種なら本物なので、 $M+1$ 個ずつ分割する
• 192-A : $A$ がどうあれ ARCR で埋め尽くせばよい
• 194-C : 単調減少であることを仮定して探索を打ち切ってはならない。そもそも探索を打ち切ったところで計算量は減らない。
• 195-A : 2個見つければよいので、前から後ろから貪欲で求める

変数を固定する

ある値 $k$ を固定して、その値を取りうる範囲 $k \in [1,K]$ について一通り求める。あるいは二分探索する。

• 113-D は $max(A) = 1..K$ を固定すると求まる。

不変量

ABC 水diffでは不変量はほぼ出題されないが、ARCでは不変量が頻出である。不変量を素早く見抜けるかどうかでARCの勝敗が決まる。総和が不変量なら、平均値付近が終端状態になる。

106-Bは全頂点の値の総和が不変量である。 $\pm 1$ し、と問題文にあったらまず不変量を探す。

107-Cは、swap操作は行番号、列番号を読み替えるだけで、入力の行列そのものは不変とみなせる。よって読み替え可能な行の集合、列の集合を求める問題と言い換えられる。132-A は黒マスは左上の上三角に寄せて、行番号、列番号を読み替える。

119-Cは、隣り合うビルについて増減を共にするなら、隣り合うビルについて高さの差が不変量である。より一般的には交代和( $\sum_i (-1)^i A_i$ が不変量である。後述する、条件を満たす区間の数と組み合わせると答えが求まる。

128-Bは、ボールの数を3で割った余りが不変量である。2個足して1引くので差が3縮まる、というのは頻出である。

135-Cは、任意の $i,j$ について、 $A_i \oplus A_j$ が不変量である。2回操作すると元に戻る $A_1 \oplus (A_1 \oplus A_2) \oplus A_3 = A_2 \oplus A_3$ ので、操作は0または1回だけ考えればよい。

136-Bは、転倒数の偶奇が不変量である。これに加えて、同値については位置を入れ替えたとみなすと転倒数の偶奇を入れ替えられる。同様に、164-Aは、桁和の偶奇が不変量である。

158-Aは、総和は変わっても差が不変量と思い、 $[-2,0,2]$ を足す操作と読み替える。こう変換すると $x_1 + x_2 + x_3$ が不変量である。 $x_1 + x_2 + x_3$ が不変量であることを見抜けなくても、 $x_1 = x_2, x_3 - (x2 - x1)$ と2数をそろえてから3数をそろえる方法で解ける。

162-Bは、転倒数の偶奇が不変量である。それがわからなくても、左から埋めるgreedyで $[N,N-1]$ が最後にきたら詰み、 $i$ に移動したくて $i$ が右端なら1つ左に引っ張り出す、という方針で解ける。

185-Bは、 $\sum A$ が不変量である。なおかつ、全要素が平均値付近にそろっている(任意の要素の差が高々1)状況が、これ以上状態が変化しない終端状態である。答えを求めるには終端状態だけに興味があり、終端状態以外は一切考慮しない。

188-Bは、間隔が不変量である。奇数番目の間隔、偶数番目の間隔それぞれについて、構成要素は変わらないのでそれぞれソートする。

構築問題

どうやったら上手くいくのかわからない。慣れるしかなさそうである。

142-Bは、小さい物半分、大きい物半分に分けて組み合わせる。公式解説通り、奇数列に小、偶数列に大を並べる。この種の二分割は、構築問題では頻出である。ABC 388-E も、小さい物半分、大きい物半分に分けると二部グラフを貪欲マッチングできる。

147-Bは、添え字が偶数の集合と、添え字が奇数の集合に分離する。149-Cは上半分を奇数、下半分を偶数に分離して、境界線を3の倍数にする。元々分離されているのが189-Bである。

178-Aは、題意を読み解くのが大変である。辞書式順序が最小のものだけ考えればいいので、 $1..A_i$ が連続できないなら、 $A_i$ の前に何か挟む。

ゲーム

一往復しかできないゲームがある。 $N$ を何かで割った余りで、手詰まりかどうかわかることがある。145-Bと185-Aが該当する。

164-Cは、カードの数値ではなく表裏の差つまり利得を最大最小化する。公式解説は取りたいカードの偶奇に帰着しているが、理解が難しい。

条件を満たす区間の数

抽象的に言うと、ある条件 $C$ を満たす区間 $[L,R)$ の数は、 $C$ を満たす $L,R,...$ の個数 $N$ の組み合わせ $N(N-1)/2$ 個である。

具体例を挙げると、 $M$ で割った余りが0の区間は、 $modM$ が等しい $[L,R)$ を選べばよい。ARCでは $modM$ よりよい識別子を思いつく必要があり、104-Bは A-T , C-G の個数の差、119-Cは交代和、188-Aは文字列の反転状況である。

倍化

周回問題を解く典型として、入力 $A_0..A_{N-1}$ を二度繰り返して $B_0..B_{2N-1} : B_i = A_{i Mod N}$ にする、というのがある。

109-C は参加者を倍にして $N$ にすると、単なるトーナメントになる。

常にもしくはだいたい解がある

問題文には、解がなければそのことを示せとあるが、実は常に解を構築可能という状況がある。108-Cは常に解がある。最初の選択肢は決め打ちし、選択肢は $x$ 以外の $N-1$ 通りなので選択肢が無くて詰むことはない。

132-Bは解がある入力しか与えられないことに注意する。そうと分かれば可能手を列挙する。

148-Cは単に子の数だけ反転すると考える。ただし $S$ に親子の関係にある頂点があれば2引く(2回ボタンを押すのは押さないのと同じなので)。

問題文には、解がなければそのことを示せとあるが、だいたいの場合は解を構築可能という状況がある。そうでない状況を上手く見抜く。

• 133-Cは、行の和と列の和に矛盾がなければ常に達成できる。マスの値を具体的に決めなくても、最大値からいくつ引くかだけ考えればいい。
• 161-Dは密度を達成できる、つまり完全グラフ以下の密度なら、完全グラフから辺を間引いて実現できる
• 181-Aは、コスト3以下を常に達成できる。 $(N,..,1)$ のコストが高そうと気づく。
• 190-Aは、コスト3以下を常に達成できる。よってコスト1,2を達成可能な状況だけ判断する。

実験する

厳密に証明するのは大変だが、実験すると法則が見える問題がある。

131-C は小さい $N < 9$ 、小さい $A_i < 8$ でランダムな入力を与えて実験すると答えが見える。ゲーム木をDFSして、勝者(先手番/後手番)と決まり手を表示する。15分あればコードを書けるので、理詰めで解けそうもなく他に解ける問題も無いなら、実験が残された解法である。

156-A は $N = 4$ の扱いが大変である。理詰めで解けないなら全探索する方が早い。

174-D は候補を全探索すると解の法則が見えてくる。

153-B は実際に手順を書くと、2回操作すると向きが同じで原点が動く=回転することだとわかる。偶数回の操作はまとめることができて、奇数回なら最後の1回だけ実際に操作する。

171-B は問題文を読んでもよくわからないが、入力例3を全列挙するとサイクル分解が見えてくる。

191-B は入出力例を2進数表記すると、 $X$ で立っているビットはすべて $N$ でも立っているとわかる。 $1..N^2$ を実験するとより明確になる。

教科書をよく理解する

106-Cは、映画をたくさん見るには終演時刻の昇順にソートしてgreedyという典型アルゴリズムがある。これは最適解を出すので偽解法は勝てないということを最初に理解する。

117-Cの解説にある $n \choose r Mod 3$ の計算方法がいる。これを知らないと解けない。

129-Cは多角数定理を用いる。この問題の制約下ではgreedyな方法で $N = \sum_i C_i(C_i-1)/2$ に分解できる。

典型を思い出す

• 143-Bは包除原理を用いる。題意を満たす組み合わせを数えるのは大変だが、題意に反する組み合わせは数えられる。
• 150-Aは普通に累積和で求まる。ワイルドカードを都合よく読み替えればよい。
• 156-Bは $N$ 個の選択肢から復元抽出で $K$ 個取り出すときの多重集合の組み合わせを求める。 $1..N$ の間 $N-1$ 箇所に $K$ 枚の仕切りを入れる組み合わせである。
• 164-BはBFS,DFSだとTLEすることがあるので、union-find木を使う
• 168-Bは、Grundy数をまず定義する。そこから $k$ の最大値を導出するのが難しい。
• 170-Bは、 $L$ が取りうる $R$ の最大値を遅延セグメント木で持つ
• 173-Aは、桁DP $DP[over][digit]$ で解ける。ちょうど $K$ 番目は、 $K$ 個以下あるかどうか二分探索するのも典型である。
• 180-Aのように、偶数番目の文字だけ反転させると見通しがよくなる
• 186-Bはトポロジカルソートの順列を数える
• 194-Aのように、どうしていいかわからない問題はDPの漸化式を考える。その次は不変量。
• 197-Cは、転倒数のようにセグメント木で数を数える方法を使う

後日見直したい問題

180-B、181-B、その他