AtCoder の問題の考察・解法メモ(AGC 級)

問題から得た知見を忘れないように,考察・解法のポイントをまとめます.完全に自分用メモです.随時更新します.

AtCoder Grand Contest 050 (Good Bye rng_58 Day 1)

B - Three Coins

  • 第一印象:
    • $3$ ではなく $2$ の場合を考える.
    • 判定問題を解く.o にする添字列として可能なものの必要十分条件を調べる.自明な必要条件から考える.
  • $2$ の場合(連続する $2$ マスを反転させる場合):
    • 添字列において,偶数と奇数の数が等しいことが必要.
    • これで十分.偶数と奇数の数が等しい場合,偶数と奇数が切り変わる場所が $1$ つ以上ある.それらを最後に o にすることにすると,より小さいケースに帰着されるため.
  • $3$ の場合:
    • 添字列 $\bmod 3$ において,$0, 1, 2$ の数が等しいことが必要.だがこれで十分ではない.
    • 空の列から始めて,012120201 を挿入・削除することを繰り返して得られることが必要十分.
    • 小さい例を手で試すと,削除は不要そうと気づく(証明は editorial 参照).
    • あとは TDPC: I – イウィ 解説 と同様に解ける.

AtCoder Grand Contest 049

D - Convex Sequence

  • 全て 0-indexed で書く.$A = (A_0, \dots, A_{N-1})$ とする.
  • 「凸」の不等式から,$B_i := A_i - A_{i-1}$ $(0 \leq i < N)$(ただし $A_{-1} := 0$)と変数変換したくなる.すると,問題文の条件は以下と同値:
    • $B_0 + B_1 + \dots + B_i \geq 0\ $ $(0 \leq i < N)$($A$ の非負性由来)
    • $B_1 \leq B_2 \leq \dots \leq B_{N-1}$($A$ の凸性由来)
    • $\sum_{i=0}^{N-1} (N - i) B_i = M$
  • ここからさらに $C_i := B_i - B_{i-1}$ としたいが,$B_1 \geq 0$ とは限らない,つまり $A$ が単調増加とは限らないのがかなり厄介に見える.仮に $A$ が単調増加なら,$A$ の非負性由来の不等式のうち意味のあるものが $B_0 \geq 0$ のみとなり,大幅に簡単になる.
  • $A$ が単調増加な場合が解けたら,$A$ の最小値を達成する添字について場合分けすれば良さそう?
  • $A$ が単調増加な場合($B_1 \geq 0$)を考える.$C_0 := B_0,\ $ $C_1 := B_1,\ $ $C_i := B_{i} - B_{i-1}$ $(i \geq 2)$ とおくと,$B$ についての条件は以下と同値:
    • $C_i \geq 0\ $ $(0 \leq i < N)$
    • $NC_0 + \sum_{i=1}^{N-1} \frac{1}{2}i(i+1) C_{N-i} = M$
  • いつも通り FPS.$f := (1-z^N)^{-1},\ $ $g_i := (1 - z^{i(i+1)/2})^{-1}$ とおく.$B_1 \geq 0$ の場合のみ考えたときの問題の答えは,$[z^M] f g_1 \cdots g_{N-1}$.
  • $A$ の最小値を達成する添字(複数ある場合はそのうち最小のもの)$k$ を固定して考える.$A_{k-1} > A_k$ であることに気をつけると,問題の答えは以下:\[ \sum_{k=0}^{N-1} [z^{M - k(k+1)/2}] f \times g_1 \cdots g_{k} \times g_1 \dots g_{N-k-1}\] $k = 0$ が $B_1 \geq 0$ の場合に対応していると考えると,添字が合わせやすいかも.
  • 上の和は $k(k+1)/2 \leq M$ の範囲を考えればよいこと,$i(i+1)/2 > M$ となる $i$ に対しては $g_i = 1$ と見なしてよいこと,$g_i$ の乗除は $O(M)$ で計算できることから,これは $O(M\sqrt M)$ 時間で計算可能.

方針が分かってから細部を詰めるの(式変形や実装など)に無限時間かかってしまいました.「$A$ の最小値を達成する添字の区間を $[l, r)$ として〜」とやったのも良くなかったですし,無意識のうちに総和が $0,1,\dots,M$ であるものの個数を全て求めようとしていたのも良くなかったです.

AtCoder Grand Contest 046

C - Shift

  • 文字列 $S$ を「$0$ の間に挟まれた $1$ の個数を並べた数列」と見なすと良さそう.この数列を $a = [a_0, \dots, a_{N-1}]$ と書く.
  • 操作は「$0 \leq i < j < N$ を選び,$a_i \gets a_i + 1,$ $a_j \gets a_j - 1$ と更新する」ことに対応する.$K$ 回以下の操作で,$a$ を $[x_0,\dots,x_{N-1}]$ にできるための条件を考える.
  • 簡単な場合として,まず $K = \infty$ の場合を考える.必要条件として $x_0,x_1,\dots$ の順に上下限を考えると,次の不等式が得られる:
    • $\sum_{i = 0}^k x_i \geq \sum_{i = 0}^k a_i\ $ $(0 \leq k < N)$
    • $\sum_{i = 0}^{N-1} x_i = \sum_{i = 0}^{N-1} a_i$
  • $K = \infty$ の場合はこれが十分条件だと分かる($i=0,1,\dots$ の順に $a_i = x_i$ を満たすように操作ができる).
  • $K < \infty$ の場合を考える.各 $i$ について,$a_i$ を増加も減少もさせるのは損だと気づく.最小操作回数が $\sum_{i=0}^{N-1} (x_i - a_i)_+$ だと分かり,これで必要十分条件が得られた.
  • あとは数え上げ.素朴な DP だと $O(|S|^4)$ に見えて間に合わなそう(実は余裕で間に合う).
  • 部分和問題系なので FPS を考える.$f_i := \frac{1 - z^{a_i}}{1 - z} + \frac{z^{a_i}}{1 - zw}$ とおく.$g \gets 1$ と初期化したあと,$i = 0,1\dots,N-1$ の順で以下のように更新する:
    • $g \gets g f_i$ と更新し,$z$ について $(a_0+\dots + a_i)$ 次未満の項を捨てる.
  • 最終的に得られた $g$ に対し,$\sum_{k = 0}^K [z^{a_0 + \dots + a_{N-1}} w^{k}] g$ が答え.これは $O(|S|^3)$ で計算可能.

FPS を使うと,いわゆる「斜めの累積和」を使うべきだと機械的に分かる($f_i$ の第 $2$ 項の $1 - zw$ で割る部分)のが好きです.

AtCoder Grand Contest 043

C - Giant Graph

  • $10^{18} > N^3 $ に注目.$W$ の頂点 $(x_i, y_j, z_k)$ を,$i+j+k$ の降順に貪欲に独立集合に加えていけばよい.
  • $(x_i, y_j, z_k)$ と $(x_{i'}, y_{j'}, z_{k'})$ が隣接するならば $i=i',$ $j=j',$ $k=k'$ のうちちょうど $2$ つが成立することに注意する.「$i+k+j$ の降順」と書いたが,$i, j, k$ それぞれの降順に処理できる.
  • このままだと $O((N+M)^3)$ 時間で遅い.$W$ が $3$ つのグラフ $X, Y, Z$ の直積グラフであることを使えば.$X, Y, Z$ について独立に何かを計算した後,それらを組み合わせることで答えが出そう.
  • ここまでの考察をヒントに Grundy 数が使えそうと気づく.$W$ の頂点 $(x_i, y_j, z_k)$ にコマがある状態を,$X, Y, Z$ の頂点 $x_i, y_j, z_k$ に一つずつコマがある状態と同一視する.

「$X, Y, Z$ の最大独立集合が分かればよい?」→「情報足りなくてダメ」→「$X, Y, Z$ の Grundy 数が分かればいけそう?」までエスパーしたのに詰めきれませんでした.「$i, j, k$ それぞれの降順に処理できる」の部分がちゃんと分かっていなかったのが原因のようです.

AtCoder Grand Contest 040

C - Neither AB nor BA

  • 消せる / 消せない条件を $3 \times 3$ の表にしてみると,$1$ 行目と $2$ 行目(もしくは $1$ 列目と $2$ 列目)を入れ替えたくなる.
  • これは,偶数文字目(奇数文字目)の A と B を互いに置換することに対応する.つまり,AA と BB が消せないとしても答えは変わらない.
  • 典型: まず必要条件を考え,それで十分かどうかを確認する.
  • A, B の個数を $a, b$ とすると,明らかに $a, b \leq N/2$ は必要.
  • これで十分なことは $N$ についての帰納法で示せる:
    • $a = b = N/2$ のとき,AB or BA と連続する箇所がある.
    • $a = N/2$ のとき,AX or XA(X は B or C)と連続する箇所がある.
    • $a, b < N/2$ のとき,CX(X はなんでもよい)と連続する箇所がある.
  • あとは余事象を考えれば解ける.

十分性をちゃんと確認せず投げてしまいました(サンプルが強いので本番はそれでもいいかも?).

AtCoder Grand Contest 037

D - Sorting a Grid

  • 典型: 操作列を逆から見る.
  • $A_{ij} \to \lfloor (A_{ij}-1)/M \rfloor $ と置き換える.手順 1 の後,各列に $0, \dots, N-1$ が一つずつ現れるようにすればよいと分かる.
  • 二部マッチングや辺彩色が関係ありそうな感じがする.
  • 求めたいものは各列について $0,\dots,N-1$ の順列(=完全マッチング)であるため,行と数を頂点とする二部グラフを考えればよいと分かる.
  • 典型: 正則二部グラフには完全マッチングが存在する.
  • 完全マッチングを求めることを $M$ 回繰り返せばよい.

「二部マッチングや辺彩色を使いそう」「正則二部グラフには完全マッチングが存在することを使いそう」までたどり着いていたのに,二部グラフが作れなかったのは反省.思考停止で行と列を頂点とする二部グラフを考えてしまったのはかなり愚かでした.

AtCoder Grand Contest 036

C - GP 2

  • 典型: まず判定問題を解く.必要条件から考える.
  • 「$[x_1, \dots, x_N]$ が最終状態としてあり得るか?」を考える. 明らかに以下が必要:
    • $\sum_i x_i = 3M$
    • $x_i \leq 2M$
  • 「これで十分か?」を反例を作りながら確認する.$(N, M) = (4, 2)$ のとき $[3, 1, 1, 1]$ が反例.奇数はたくさん作れないと気づく.つまり以下も必要:
    • $x_1,\dots, x_N$ のうち奇数は $M$ 個以下
  • これで十分なことは,いつも通り $M$ についての帰納法で確認できる(条件を満たしつつ操作を一つ巻き戻せるか? を考える典型).
  • 部分和問題系なので FPS が使える.$x_1,\dots, x_N$ のうちの奇数の個数 $k$ を固定して考える.$f := z\frac{1-z^{2M-2}}{1 - z^2}$,$g := \frac{1 - z^{2M}}{1 - z^2}$ とおくと以下が答え: \[ \sum_{k=0}^M \binom{N}{k} [z^{3M}] f^k g^{N-k}. \]
  • $f^k g^{N-k}$ を二項展開し $z^{3M}$ より高次の項を落とす.上の式は以下と等しい: \[ \sum_{k=0}^M \binom{N}{k} [z^{3M-k}] \frac{1 - k z^{2M-2} - (N-k) z^{2M}}{(1-z^2)^N}. \]
  • 負の二項定理 \[ \frac{1}{(1-z)^n} = \sum_{k=0}^\infty \binom{n+k-1}{k} z^k\] を使って $(1-z^2)^{-N}$ を展開すると,各項が $O(1)$ 時間で計算できる.

上では後半部分を FPS で殴りましたが,包除原理を使っても解けます.後で追記するかも.

AtCoder Grand Contest 030

D - Inversion Sum

  • 期待値の線形性を使いたくなる.各 $(i, j)$ に対し,全ての操作の後,$A_i > A_j$ となる確率を求めたい.
  • $k-1$ 回目の操作直後での確率が求まっているとき,$k$ 回目の操作直後の確率が簡単に求まるか?
  • $i, j \notin \{X_k, Y_k\}$ なる $(i, j)$ については,$k$ 回目の操作前後で $A_i > A_j$ となる確率は変化しない.
  • そうでない $(i, j)$ についても,確率の変化は容易に計算できる.場合分けはほぼ必要ない.
  • 更新が必要な $(i, j)$ は $O(N)$ 個しかないので,in-place 更新により全体で $O(N^2)$ 時間となる.

DP の更新式がかなりシンプルであることに気づけず,無駄に場合分けしてしまいました.

AtCoder Grand Contest 027

B - Garbage Collector

  • ゴミ集合を $G := {1,\dots, N}$ とする.ゴミ $S \subseteq V$ を回収して戻ってくる時は,番号が大きい順にゴミを拾うのがよい.
  • 例えば $S = \{1, 2, 5, 7\}$ のとき,移動コストは \begin{align*}&\indent(1^2 + 2^2)x_7+ (3^2 - 2^2)x_5+ (4^2 - 3^2)x_2+ (5^2 - 4^2)x_1 \\ &= 5x_7 + 5x_5 + 7x_2 + 9x_1.\end{align*}
  • 上の式で,$x_i$ の項を $i$ の降順に並べたとき,係数が単調増加になっていることに注目.これは一般に成り立つ.
  • ゴミ $G$ を $m$ 回に分けて回収するとする.$m$ を固定したときの最適値は貪欲法で簡単に分かる.ただし,愚直に計算すると $O(N^2)$ 時間かかる.
  • 典型: 前計算で計算量を落とす.
  • 典型: $n/1 + n/2 + n/3 + \dots = O(n \log n)$
  • $x_i$ の累積和を前計算しておくと $O(N \log N)$ で解ける.

$O(N^2)$ 解までたどり着いた後,$m$ についての凸性を予想して三分探索したら通っちゃった(正当性は未だに分かっていない).この計算量の落とし方は本当に典型なのにすぐに出てこなかったのは反省.

AtCoder Grand Contest 013

C - Ants on a Circle

  • 蟻本に載ってる有名な問題「Ants」と同様に,$T$ 秒後の蟻の座標の集合は分かる.
  • 蟻の番号は,常に時計回りに $1,2,\dots,N$ の順を保っている.特定の $1$ 匹について $T$ 秒後の座標が分かれば OK.
  • 「蟻 $1$ の $T$ 秒後の座標は?」と考えると難しい.
  • 典型: 全単射の逆写像を考える.
  • 逆に「$T$ 秒後にこの座標にいる蟻の番号は?」と考えると解ける.

逆写像を考えるというのはかなり典型なのに抜けていました.

CODE FESTIVAL 2016 qual A

D - マス目と整数

  • 線形方程式の解の存在判定に帰着されるが,素朴にやると変数が多すぎる.行と列を独立に考えたい.
  • マス $(i, j)$ に書く数を $a_{ij}$ とすると,ある $x_1,\dots,x_R$ と $y_1,\dots, y_C$ が存在し,$a_{ij} = x_i + y_j$ と書けることが必要なのでは? と気づく.
  • 実際これが必要なことは条件 2 の式を移項すると簡単に示せる.
  • 結局 $x_i + y_j = a_{ij}$ 型の線形方程式になる.二部グラフを作り,各連結成分について $1$ つの頂点の値は決め打ち,そこから DFS すれば解ける(奇閉路がある場合はもう少し厄介).
  • 一般解も分かる.自由度は連結成分の数だけあることに注意.
  • 一般解が分かれば,条件 1 を満たすような解が存在するかの判定も容易.

一般解の自由度が連結成分の数だけあることに気づかず,ペナを出してしまった(ペナ率高いので同じことした人多そう).解法の正当性をもう少し慎重に確認すべきでした.

AtCoder Grand Contest 003

D - Anticube

  • 素因数分解して「指数 $\mathrm{mod}\ 3$」のベクトルで考えたくなる.ベクトルが同じになる数は同一視する.
  • 数を頂点とし,同時に選べない数を辺で結ぶと,重み付き最大独立集合になる.
  • 次数 $1$ の頂点しかないので簡単(立方数だけは例外).
  • ロー法など高速な素因数分解を使えば間に合う.
  • 数 $x$ と同時に選べない数を求めるために,素数を列挙するなどしても解ける(こちらが想定らしい).
    • $x$ を $10^{10/3}$ 以下の素数で試し割りしていくと,最終的に素数 $2$ つ以下の積になる.
    • $x$ が平方数(素数の平方)なら $\sqrt{x}$ が,そうでないなら $x^2$ が同時に選べない数.

ベクトルが同じになる数を同一視するためにも「$10^{10/3}$ 以下の素数で割る」のは自然です.割った結果が素数 $2$ つ以下の積になるのがポイントでした.

タイトルとURLをコピーしました