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

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

AtCoder Regular Contest 117

C - Tricolor Pyramid

問題

  • 規則について理解するために,まず $3 \times 3$ の演算表を書く.
  • 斜め方向に一定値をとるので,加算に似た演算だと気づく.ちゃんと考えると $-(x+y) \bmod 3$ という演算だと分かる.
  • あとは 123 Triangle と同じ.Lucas の定理.

D - Miracle Tree

問題

  • 第一印象:
    • まず(実行可能性の)判定問題を解く.
    • まず簡単なグラフ(パス,スター)で考える.
    • 絶対値を外したい.問題を緩和する?
  • 不等式がたくさんあるが,本質的な不等式は少ない.$\mathrm{dist}$ についての三角不等式より.これで判定問題は解ける.
  • 全ての頂点を一度以上訪れる最短のウォークを考える問題だと分かり,解ける.

E - Zero-Sum Ranges 2

問題

  • (後で追記)

F - Gateau

問題

  • 区間和制約なので累積和で考えたいが,円環なのが厄介 → 二分探索で総和を固定.
  • 差分不等式系の解の存在判定問題になる.つまり,グラフ上の最短路問題(負辺あり)になる.
  • Bellman-Ford とか一般的なアルゴリズムだと TLE.グラフの構造に着目した高速化が必要.
    • DAG ならば負辺があっても高速に解ける.この問題のグラフも「ほぼ DAG」 になっている?
    • 頂点番号の差が $1$ or $N$ である $2$ 頂点間にしか辺が無い.
  • グラフを $2 \times N$ のグリッドグラフのように描いてみると,ほぼ DAG だと分かる.DP で最短路が分かり,解ける.

AtCoder Regular Contest 111

F - Do you like query problems?

  • 総和ではなく期待値で考える.0-indexed で書く.
  • 適切に場合分けして足せばよさそう.まずは細かめに場合分けして,計算量重めの解を作ることを目指す.
  • そこで
    • $p_i := ($各クエリで $a_i$ が $\mathtt{ans}$ に足される確率$)$
    • $q_{i,j,k} := ($$j$ 回目のクエリの直前に $a_i \geq k$ である確率$)$
    とおく.問題の答えは $\displaystyle \sum_{i=0}^{N-1} \sum_{j=1}^{Q-1} \sum_{k=1}^{M-1} p_i q_{i,j,k}$.この $p_i,$ $q_{i,j,k}$ は割ときれいに書けることを期待している.
  • $p_i$ は簡単.各クエリ範囲に $a_i$ が含まれる確率は $\displaystyle r_i := \red{ \frac{(i+1)(N-i)}{\binom{N+1}{2}}} $ なので,$\displaystyle p_i = \frac{r_i}{2M+1}$.
  • $q_{i,j,k}$ は漸化式が立ちそう.
    • $a_i < k$ のとき,$1$ 回のクエリ後に $a_i \geq k$ となる確率は $\displaystyle \frac{M-k}{2M+1} r_i$
    • $a_i \geq k$ のとき,$1$ 回のクエリ後に $a_i \geq k$ となる確率は $\displaystyle 1 - \frac{k}{2M+1} r_i$
    なので,\[ q_{i, j+1, k} = (1 - q_{i,j,k}) \frac{M-k}{2M+1} r_i + q_{i,j,k} \Big( 1 - \frac{k}{2M+1} r_i \Big). \]この漸化式は解けて,\[ q_{i,j,k} = \frac{M-k}{M} \bigg( 1 - \Big( 1 - \frac{M}{2M+1}r_i \Big)^j \bigg). \]
  • $q_{i,j,k}$ の形を見ると,$\sum_{j, k} q_{i,j,k}$ は計算できることが分かる(嬉しい誤算).計算して,あとは $i$ についてループを回せば $O(N \log Q)$ 時間で問題が解ける.

漸化式を解いたり和を求めたりするところは Wolfram に投げました.(この方針だと)手計算の分量が多めですが,素直な問題だと思います.

AtCoder Regular Contest 109

E - 1D Reversi Builder

  • 0-indexed で書く.
  • 典型: まず簡単な問題を解く.初期状態と $s$ が与えられたときの,両者の最適戦略と終了時の黒石の数を調べる.
  • 手で実験すると,以下に気づく:
    • 石は常に連続した区間上にのみある.石の色の変化点は高々 $1$ つ.
    • 両端のマスが同じ色なら,終了時に全ての石がその色になる.両端のマスの色が異なる場合のみ考える.
    • 端に黒 or 白のマスが連続していたら,それらのマスには同じ色の石が置かれる.
  • これらから両者の最適戦略と,終了時の黒石の数が分かる.
  • マスの色の変化点が $2$ 以下の場合は簡単に期待値が分かる.
  • 左端に黒マスが $l$ 個,右端に白マスが $r$ 個連続しているとき,$2s \leq n+l-r-1$ ならば黒石が $n-r$ 個,そうでないならば $l$ 個になる.
  • 左端に白マスがある場合も考え,$O(N^3)$ 解を得る.
  • Wolfram に計算させると $O(N)$ になる.

別解(対称性を利用,固定するものを工夫)

  • 途中までは同じ.終了時の黒石,白石の数をそれぞれ $B, W$ として,$B - W$ の期待値を求めれば良い.
  • $B \neq W$ となるのは,マスが「b...b w (任意の $k$ マス) s (任意の $k$ マス) b w...w」の形の場合と,これの黒と白を入れ替えたもののみ.
  • 固定するものをよく吟味する.ここでは $s, k$ を固定するのが良い.上の形の場合 $B - W = 2(s+k+1) - n$ となる.黒と白を入れ替えた場合も考えると,$B-W$ の条件付き期待値は $2k+1$.また,そのような場合が生じる確率は $2^{2k - n}$.
  • よって $B-W$ の期待値は,$\sum_{k=1}^{\min\{s, N-s-1\} - 1} (2k+1) 2^{2k - n}$.

数え上げパートにかなり時間がかかってしまいました.完全に別解の方が良いですね.「対称性の利用」と「何を固定するとラクか?」をもっと意識すべきでした.

AtCoder Regular Contest 107

D - Number of Multisets

  • まず形式的冪級数を考えた.要素を整数化するなどしたが厳しそうだったのでこの方針は捨てた.
  • 次に $K = 1$ の場合だけ考えようとしたが,それが解けても一般の $K$ に拡張するのは難しそうと気づいた(ここでかなりタイムロスした).
  • 典型: 最初か最後で場合分け.
  • 先に最後(最小の要素は何か,その個数はいくつか?)で場合分けするのを考えてしまったが,場合が多すぎて明らかに良くない方針だった.
  • 最初($1$ の個数)で場合分けすると,$O(N^3)$ の DP が生える.問題の答えを $D(N, K)$ とおくと,\[ D(N, K) = \sum_{i = 0}^K D(N-i, 2(K-i)). \]
  • 右辺の項を書き並べると,これは $D(N-1, K-1)$ にかなり近いことに気づき,\[ D(N, K) = D(N, 2K) + D(N-1, K-1) \] を得る.これで $O(N^2)$ になって解けた.
  • この問題は分割数の DP と似ている.参考: 解説放送

別解(FPS)

  • 部分和問題系なので FPS が使える.$K$ を非整数にも拡張し,問題の答えを $a_{N, K}$ とおく.$f(z, w) := \sum_{N, K} a_{N, K} z^N w^K$ とおくと,以下が成り立つ: \[ f(z, w) = \frac{1}{1 - zw} \frac{1}{1 - zw^{1/2}} \frac{1}{1 - zw^{1/4}} \cdots. \]
  • $f(z, w)$ を直接計算するのは大変そう.そういうときは,$f$ の満たす方程式を見つけるのが定石.$f(z, w)$ の形を観察すると,$f(z,w) (1 - zw) = f(z, w^{1/2})$ を得る.
  • 両辺の $z^N w^K$ の係数を比較し,$a_{N, K} - a_{N-1, K-1} = a_{N, 2K}$ を得る.これは上の解法で得た漸化式と同じ.

今思えば明らかにハズレっぽい方針たちに拘ってタイムロスしてしまいました.考察中は,なぜその方針を選んでいるのかをもっと意識すべきですね.

E - Mex Mat

  • 何も分からなかった & 実験が簡単そうだったので,すぐに実験エスパー方針が取れた.

実験エスパーが想定の問題が出るとは驚きでした.

F - Sum of Abs

  • 典型: 絶対値 $|x|$ は「$x, -x$ の好きな方を選択できる」と言い換える.
  • 各頂点で $\{-1, 0, 1\}$ の $3$ 択から選ぶ問題になる.$2$ 択なら自明に最小カットになる.
  • 典型: $n \,(> 2)$ 択でも,各頂点をコピーしてパス状に並べ,容量 $+\infty$ の辺で繋ぐことで最小カットになる.
  • あとは符号に注意してフローを流すだけ.

$2$ つ目の典型は知らなかったけど,なんとか思いつけました.覚えておきます.

AtCoder Regular Contest 106

D - Powers

  • 典型: 和の順序交換.
  • 典型: 積の和を和の積に.(部分的に)因数分解.
  • 計算量的に $2$ つの添字 $L, R$ を(ほぼ)独立に処理したい.
  • 上の $3$ つを念頭に $\displaystyle \sum_{1\leq L, R \leq N} (A_L + A_R)^X$ を計算しようとすると,\begin{align*}\sum_{L, R} (A_L + A_R)^X &= \sum_{L, R} \sum_{k=0}^X \binom{X}{k}A_L^k A_R^{X-k}\\ &= \sum_{k=0}^X \binom{X}{k} \sum_{L, R} A_L^k A_R^{X-k} \\ &= \sum_{k=0}^X \binom{X}{k} \bigg( \sum_{L=1}^N A_L^k \bigg) \bigg( \sum_{R=1}^N A_R^{X-k} \bigg) \end{align*}となり,前計算をすれば高速に値が求まる.

最初なんとなく二項展開を避けてタイムロスしちゃった.$L, R$ を独立に処理するなら,展開は最有力な一手でした.

E - Medals

  • マッチングっぽい見た目.「従業員」と「日」を頂点集合とする二部グラフを考えたい.
  • さすがに頂点数は固定したいので,答えを二分探索する.上限は $2NK$ にすれば十分.
  • 二部グラフ型の最大流を $O(\log (NK))$ 回解くことになる.
  • 頂点数は $O(NK)$,辺数は $O(N^2K)$ なので,Dinic だと $O(N^4 K^3)$ 時間かかる.これは間に合わない.$N$ が小さいことを利用した別のアルゴリズムを考える.
  • 典型: 頂点数 $N_1, N_2$ の二部グラフ型最大流は $O(N_1 (N_2 + 2^{N_1}))$ で解ける.最小カットを考え,片側の頂点部分集合を全探索する.高速ゼータ変換を使う.
  • これを使えばこの問題も解ける.計算量は $O(N^2K + N (K + 2^N) \log(NK))$

上の典型部分は言われてみれば当たり前なんだけど考えたことなかったなー.最小カットを最大流に帰着することはよくあるけど,その逆パターンですね.

F - Figures

  • 典型: Prüfer 列.「頂点ラベルの付いた木」と数列(Prüfer 列)が一対一に対応する.これは木の数え上げに役立つ.
  • Prüfer 列の作り方から,次数 $d$ の頂点は数列にちょうど $d-1$ 回現れる.
  • よって,$N$ 頂点のラベル付き木のうち頂点 $i\,(=1,\dots,N)$ の次数が $d_i$ であるようなもの個数は,$\sum_{i=1}^N d_i = 2(N-1)$ のとき $\frac{(N-2)!}{(d_1-1)! \cdots (d_N-1)!}$.そうでないとき $0$.
  • 部分和問題系なので形式的冪級数が使える.$d$ 個の穴から $k$ 個を選び,それらに順序付ける方法の数は $\frac{d!}{(d-k)!}$ 通りなので,$f_i := \sum_{k=1}^{d_i} \frac{d_i!}{(d_i-k)! (k-1)!} z^k = d_i z (1+z)^{d_i-1}$ とおくと(二項定理を使った),問題の答えは $(N-2)! [z^{2(N-1)}] \prod_{i=1}^N f_i$.この値は(再び二項定理を使えば)明示的に書ける.

Prüfer 列,覚えました.これを知らずに解くのはかなり大変そう? 上では形式的冪級数を使ったけど,単に多項定理を使うだけでも計算できます.

AtCoder Regular Contest 105

D - Let's Play Nim

  • XOR を $0$ にしたい人としたくない人の戦い.
  • XOR を $0$ にするのはかなり大変そうなので,$0$ にしたい人(= $N$ が奇数のときの先手 or $N$ が偶数のときの後手)が必勝になる十分条件を考える.
  • 典型: ミラー戦略.
  • $0$ にしたい人が勝てる十分条件に気づく.ミラー戦略を取れたら $0$ にできる.
  • 実はこれが必要条件だと示せる.$a \oplus b \leq a + b$ を念頭に,$a_i$ の最大値に着目するとよい.

本番ではちゃんと示さずに,「反例見つからないし,たくさん通されてるしとりあえず投げるか」とやったら通っちゃった.コンテスト後に解説読む前にちゃんと証明考ればよかったなー.

AtCoder Regular Contest 104

D - Multiset Mean

  • 部分和問題系なので形式的冪級数.空な多重集合も数えることにする.$f_i := \sum_{k = 0}^K (wz^i)^k$ とおくと,\[ \sum_{(a, b):\,ax = b} [w^a z^b] \prod_{i=1}^N f_i = \sum_{a=0}^\infty [(wz^x)^a] \prod_{i=1}^N f_i \]が答え.
  • $w = z^{-x}$ を「代入」すると,$\displaystyle f_i = \frac{1 - z^{K(i-x)}}{1 - z^{i-x}} $ となる.$\displaystyle [z^0] \prod_{i=1}^N f_i$ が答え.
  • $\displaystyle g_i := \frac{1 - z^{Ki}}{1 - z^i}$ とおき直すと,$\displaystyle [z^0] \prod_{i=1-x}^{N-x} g_i$ が答え.
  • あとはスパースな冪級数の乗除を使えば解ける.負の次数の項が出ないように適当にゲタを履かせると良い.

本番では自分の冪級数ライブラリの定数倍が重くて TLE しちゃった……悲しいね.

E - Random LIS

  • $N \leq 6$ という特徴的な制約.$N$ 項の大小関係(例えば $X_3 < X_5 = X_2 < X_1 = X_4$ など)の全探索もできる.
  • $N$ 項の大小関係を固定すると LIS の長さは一意に定まる.固定した大小関係を満たす数列の数が分かればよい.
  • つまり,$ \displaystyle \sum_{x_1 = 1}^{b_1} \sum_{x_2 = x_1 + 1}^{b_2} \sum_{x_3 = x_2 + 1}^{b_3} 1$ のような和が計算できればよい.これは $b_1, b_2, b_3$ の多項式.
  • $x$ の $D$ 次多項式を $ \displaystyle f(x) = \sum_{i=0}^D c_i \binom{x}{i} $ という形で保持すると,その「累積和」は \[ \sum_{y = 0}^{x-1} f(y) = \sum_{i=0}^{D} c_{i} \binom{x}{i+1} = \sum_{i=1}^{D+1} c_{i-1} \binom{x}{i} \]と簡単に計算できる.これを使うと,求めたい和が内側の $\sum$ から順に計算できる.

多項式の累積和,知識としては知っていたけど使うのは初めてでした.気持ち的には $\int_0^x y^i dy = \frac{1}{i+1}x^{i+1}$ の離散バージョンかな? 公式解説のように座圧して DP するのも習得したいです.

ACL Contest 1

E - Shuffle Window

  • 期待値の線形性を使いたくなる.が,固定するものの選択肢が多く,方針に迷う.
  • 簡単に計算できそうなものを考える.初期状態と最終状態で,$p_i$ と $p_j$ の位置関係が逆転する確率 $q_{ij}$ は簡単に計算できそう.
  • $q_{ij}$ を使うと,答えは以下のように書ける: \[ \sum_{i < j,\, p_i < p_j} q_{ij} + \sum_{i < j,\, p_i > p_j} (1 - q_{ij}) \]
  • あとは $q_{ij}$ を明示的に書き,上の和を転倒数と同じ要領で計算すればよい.

「何が計算できたら嬉しいか」だけでなく「何が簡単に計算できるか」も考えて,両側から攻めるのが有効ですね.

この問題,問題文が曖昧だと思っていて,サンプルを確認するまで別の問題を解いていました.

第一回日本最強プログラマー学生選手権-予選-

E - Card Collector

  • 分割マトロイド $2$ つの合併なのでマトロイド.貪欲法で解ける.独立性オラクルが実装できたら OK.
  • 各行・列を頂点に,各カードが辺に対応する二部グラフを作りたくなる.
  • サンプル $1$ を手で試すと,辺集合が独立であることは「各連結成分について,辺数が頂点数以下」と同値だと気づく.
  • あとは UnionFind を使えば解ける.

以前考察したときは,二部グラフを作りたくなれなかったけど,今回はなれた.典型ですね.

diverta 2019 Programming Contest 2

E - Balanced Piles

  • 操作過程において,高さ $i$ のマスの個数 $x_i$ のみが重要と気づく.
  • $N = 8,$ $H = 9,$ $D = 3$ でシミュレーションしてみる.状態をベクトル $[x_0,x_1,\dots, x_H]$ で表すことにする.例えば,\begin{align*} &[\red{8},0,0,0,0,0,0,0,0,0]\\ {}\xrightarrow{8 \times 7}{} & [\red{6},0,\red{2},0,0,0,0,0,0,0] \\ {}\xrightarrow{6 \times 5 \times 4}{} & [\red{3},0,\red{2},\red{3},0,0,0,0,0,0] \\{}\xrightarrow{3 \times 2 \times 1}{} & [0,0,\red{2},\red{3},0,0,\red{3},0,0,0] \\{}\xrightarrow{2 \times 1}{} & [0,0,0,\red{3},0,0,\red{5},0,0,0]\\ {}\xrightarrow{3}{} & [0,0,0,\red{2},0,0,\red{6},0,0,0]\\{}\xrightarrow{2 \times 1}{} & [0,0,0,0,0,0,\red{6},0,\red{2},0]\\{}\xrightarrow{6 \times 5 \times 4}{} & [0,0,0,0,0,0,\red{3},0,\red{5},0] \\{}\xrightarrow{3 \times 2 \times 1}{} & [0,0,0,0,0,0,0,0,\red{5},\red{3}]\\{}\xrightarrow{5 \times 4 \times 3 \times 2 \times 1}{} & [0,0,0,0,0,0,0,0,0,\red{8}]\end{align*} という変化がありうる(矢印の上の数は,その状態遷移を実現する操作の個数).矢印の上の数をすべてかけると $8! \times 2! \times 3! \times 6! \times 5!$ となる.
  • $y = 0$ から始め,$y$ に $1,\dots,D$ のいずれかを足す操作を繰り返し $y = H$ にすることを考える.そのような操作列で,長さ $k$ のものの個数を $a_k$ とおく.上の実験から,問題の答えが \[ N! \sum_{k=1}^\infty a_k \sum_{1 \leq m_1, \dots, m_{k-1} \leq N} \prod_{i=1}^{k-1} m_i ! \] だと予想できる.予想が正しいことも確認できる.
  • 部分和問題系なので FPS が使える.$c := \sum_{m=1}^N m!$,$f := \sum_{i=1}^D z^i = z \frac{1 - z^D}{1-z}$ とおくと,答えは以下:\[ N! \sum_{k=1}^{\infty} c^{k-1} [z^H] f^k = N! [z^H] \frac{z(1 - z^D)}{1 - (1+c)z + cz^{D+1}}. \]これは $O(N+H)$ で計算可能.

Tenka1 Programmer Contest 2019

D - Three Colors

  • $S := \sum_{i=1}^N a_i$ とおく.三角形の成立条件と $R + G + B = S$ を合わせると,$R,G,B < S/2$ となる場合を数えればよい.
  • 素朴に DP すると $O(N^3 (\max_i a_i)^2)$ になってしまう.
  • 数えたい $(R, G, B)$ の集合を $RGB$ 空間上で考えて,それを $RG$ 平面に射影したものを描いてみると,余事象の方が数えやすそうと気づく.
  • $R+G \leq S/2$ となる場合や $(R, G, B) = (S/2, S/2, 0)$ となる場合は DP で数えられる.これらを足し引きすれば答えが出る.

$RG$ 平面に図まで描いたのに余事象が出てこなかった(なぜ……).

F - Banned X

  • $0$ は重要でないので一旦無視する.
  • まず判定問題を解く.必要条件・十分条件から攻める.
  • 数列の総和を $S$ とし,$S$ の値で場合分けする.$S < X$ の場合は自明に OK.$S = X$ は自明に NG.以下 $S > X$ かつ OK な場合について考える.
  • $S > X$ のとき,数列の両端が $2$ であることが必要.
  • $S = X+1$ のとき,
    • $X = 1$ ならば $(2)$ のみ OK.
    • $X = 2$ ならば NG.
    • $X \geq 3$ ならば $(2,\ ($総和が $X-3),\ 2)$ のみ OK.
  • $S = X+2$ のとき,$(2,\ ($総和が $X-2),\ 2)$ になるが,これは NG.
  • $S = X+3$ のとき,$(2,\ ($総和が $X-1),\ 2)$ になる.$(2,\ ($総和が $X-1))$ と $(($総和が $X-1),\ 2)$ がともに OK なら OK.$S = X+1$ の場合に帰着される.
    • $X = 1$ ならば $(2, 2)$ のみ OK.
    • $X = 3$ ならば $(2, 2, 2)$ のみ OK.
    • $X \geq 5$ ならば $(2, 2, \ ($総和が $X-5),\ 2, 2)$ のみ OK.
  • ここまで来れば必要十分条件が分かり,判定問題が解ける.数え上げは二項係数をかけて足すだけなので容易.

最初 $S \geq 2X$ ならば常に NG だと勘違いしていて,サンプルで気付かされました.この方針だとかなり勘違いしやすい気がするので,あまり良い方針じゃないのかも?

キーエンス プログラミング コンテスト 2019

F - Paper Cutting

  • スコアの決まり方から,縦横に切った回数が重要.縦に $i$ 回,横に $j$ 回切った状態を $(i, j)$ と書く.
  • 状態 $(i, j)$ になった直後に得るスコアは $(i+1)(j+1)$.
  • 状態 $(i, j)$ を経由する操作列の数をかけて足せばよいが,和が簡単には計算できなそう.
  • 典型: 固定するものを変える.
  • 最終状態で場合分けする.状態が $(0, 0) \to (i, j) \to (p, q)$(ただし $p+q = K$)と遷移するような操作列の数は,\[ \binom{i+j}{i} \binom{p+q-i-j}{p-i} \frac{H!}{(H-p)!} \frac{W!}{(W-q)!}. \]
  • スコア $(i+1)(j+1)$ をかけて $i, j$ について $0 \leq i \leq p,\ $ $0 \leq j \leq q,\ $ $(i,j) \neq (0,0)$ の範囲で和を取る.Wolfram に投げると\[ \sum_{i=0}^p \sum_{j=0}^q (i+1)(j+1) \binom{i+j}{i} \binom{p+q-i-j}{p-i} = \frac{(2 p q + 3 p + 3 q + 6)(p + q + 1)!}{6 p! q!}\] が分かる.これを使えば $p, q$ を固定したときの問題の答えが明示的に書ける.
  • あとは $p$ についてループを回して足すだけ.

最終状態で場合分けをすれば,$i, j$ について和をとる範囲が簡単になって,割ときれいな式になりそうだなという勘が当たりました(パチンコ).

AtCoder Regular Contest 081

E - Don't Be a Subsequence

  • 典型: 辞書順最小問題は先頭から順に確定させる.
  • 典型:「$i$ 文字目以降で文字 $c$ が初めて登場する index」のテーブルは高速に前計算可能.
  • 答えの文字列の先頭の文字 $c$ について場合分けする.$c$ が初めて登場する index を $i$ とすると,$A$ の $i+1$ 文字目以降を取り出した文字列に対して同様の問題が解ければよい.これで DP が書ける.
  • ただし,答えの文字列を全て DP テーブルに持つと計算量がヤバいので,長さと先頭の文字の情報のみ持つ.その情報から答えを復元する.

公式解説は DP というより貪欲的な考え方をしています.ABC146: F - Sugoroku を思い出しました.そちらも身につけたいです.

F - Flip and Rectangles

  • 典型: まず簡単な判定問題から解く.
  • 「指定した長方形部分のすべてのマスを黒にできるか?」を考える.少し手で実験すると「$2 \times 2$ ブロックに含まれる黒マスの数の偶奇」に関連する必要条件に気づく.
  • これが十分条件であることも簡単に分かる.
  • あとは $(H-1) \times (W-1)$ グリッドの最大長方形問題を解けばよい(ググった & 蟻本を読んだ).

割とスムーズでした.数え上げ以外でもまず判定問題を解くのは有効ですね.

AtCoder Regular Contest 067

F - Yakiniku Restaurants

  • 移動区間 $[l, r]$ を固定すると,チケット $j$ で得られる効用は $\max_{i \in [l, r]} B_{ij}$.
  • $s_i := \sum_{j=1}^{i-1} A_j$ とおくと,$l, r$ $(1 \leq l \leq r \leq N)$ を動かしたときの $s_l - s_r + \sum_{j=1}^{N} \max_{i \in [l, r]} B_{ij}$ の最大値が求める答え.
  • 全ての $(l, r)$ に対し,$\sum_{j=1}^{N} \max_{i \in [l, r]} B_{ij}$ を高速に計算したい.
  • $l, r$ を固定して考えるのでは厳しそう.そこで,$j$ を固定して $\max_{i \in [l, r]} B_{ij}$ を調べる.
  • 典型: 区間の問題は $lr$ 平面にプロットしてみる.
  • $\max_{i \in [l, r]} B_{ij}$ を $lr$ 平面にプロットすると,長方形領域上で一定値をとることが分かる.
  • あとは二次元累積和を使えば解ける.

「$j$ を固定しよう」まではたどり着いたのに,ド典型の $lr$ 平面プロットをすっかり忘れていました.かなり悔しい.

CODE FESTIVAL 2016 qual C

D - Friction

  • 素朴にやると $O(H^W)$ 状態の DP になってしまう.良い構造を探すしかなさそう.
  • コストが隣接する $2$ 列間でのみ生じることに着目.$W = 2$ の問題を $W$ 個解けばよい(操作列を順列と見なし,挿入 DP のように考えると分かりやすい).
  • $W=2$ の問題は,各状態から操作したときにかかるコストを前計算しておけば, $O(H^2)$ の DP で解ける.

操作列を順列と見なすのがポイント? 言われてみれば当然なんですが,なかなか気づかなかったです.

AtCoder Regular Contest 038

C - 茶碗と豆

  • 各 $i$ に対し,豆が $1$ つだけ茶碗 $i$ に入っているときの Grundy 数 $g_i$ が求められたら OK.愚直にやると $O(N^2)$ 時間かかるので高速化が必要.
  • 「$g_0, \dots, g_{i-1}$ が求まっているとき,$g_i$ が高速に求められないか?」と考えるが難しそう.
  • 典型: 主客転倒.固定するものを変える.
  • $g_i$ を求めるためには,各 $x=0,\dots,i-1$ に対し,以下をともに満たす $j$ が存在するかが分かればよい:
    • $i - C_i \leq j < i$
    • $g_j = x$
  • $a_{i, x} := (\,j < i$ かつ $g_j = x$ を満たす $j$ の最大値.存在しないなら $-1\,)$ と定義すると,$g_i = \min \{ x \geq 0 \mid a_{i, x} < i - C_i \}$ となる.
  • $a_{i, x}$ と $a_{i+1, x}$ は「ほぼ同じ」であることに注意し,in-place に更新すればよい.
  • $a_{i, x}$ から $g_i$ を高速に求めるために,$a_{i, x}$ はセグ木で持てばよい.$g_i$ の計算にはセグ木上の二分探索を使う.

良問でした.主客転倒がスッと出てくるようになりたい.

AtCoder Regular Contest 029

C - 高橋君と国家

  • 典型: グラフに頂点・辺を追加し,知っている問題に帰着.
  • 交易所に対応する頂点を追加すれば最小全域木になる.

「頂点・辺追加」という典型が,最短路やフローの問題だけと結び付いてしまっていて出てこなかった.当然全域木問題でも使えますね.グラフの問題なら考察序盤で考える価値がありそう.

AtCoder Regular Contest 026

C - 蛍光灯

  • 普通にセグ木使って DP で解ける.
  • 典型: $1$ 次元区間の(重み付き)集合被覆問題は,最短路問題に帰着できる.
  • この典型を使っても解ける.

この問題を少し捻ったのが PAST4: O - 宝箱 というわけですね.

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