コンテストでの時間切れや解けなかった過去問を振り返って供養していく
02/06: AtCoder Beginner Contest 191 C - Digital Graffiti
Difficulty: 1063 (記事作成時点)
供養
解法
- 左上から見ていって外周上にある点を見つける
- 自分がどの点の、上下左右どの辺上にいるかを意識しながら外周上を辿るように現在位置を更新していき、最初の辺に戻るまでに曲がった回数を出力する
実装
計算量は $O(HW)$
公式解説
躓いた点
- 正直まず問題文が理解しにくいと思う
- それはそれとして値の入力ミスに気付かなかった
02/07: AtCoder Beginner Contest 191 D - Circle Lattice Points
Difficulty: 1953 (記事作成時点)
供養
解法
- $x$ を固定した時に $(X, Y)$ との距離が $R$ 以下となる $y$ の範囲を二部探索していけばいい
- …が、この問題にはfloatで計算すると誤差が発生するポイントが複数ある
- 距離を比較するときに平方根をとってはいけない
- そもそも入力をfloatで受けてはいけない
- 文字列をparseして $10^{4}$ 倍したintを作るなどの処理をする
実装
計算量は $O(R\mathrm{log}R)$
公式解説
躓いた点
02/14: AtCoder Regular Contest 112 C - DFS Game
Difficulty: 1913 (記事作成時点)
供養
解法
- 点 $u$ を根とする部分木についての問題を考える
- $p_{u} \to u$ の移動をしたプレイヤー視点で、以下のパラメータを計算する
- $s(u)$: $p_{u} \to u$ の移動をするプレイヤーと $u \to p_{u}$ の移動をするプレイヤーが異なるならば $1$ 、同じならば $-1$
- $s(1)$ は計算に使用しないのでどちらでもいい
- $f(u)$: $T_{u}$ から自分が取得できるコインの枚数と相手が取得できるコインの枚数の差
- $s(v) = 1$ ならば $u \to v$ の移動をしたプレイヤーは $v \to u$ の（相手プレイヤーによる）移動の後に再度移動先を選ぶことになる
- $f(v) \gt 0$ の部分木は優先して選べばよく、 $f(v) \lt 0$ の部分木は極力選びたくない
- $f(v) = 0$ の部分木はいつ選んでも影響がないので適当なタイミングで選ぶ
- $s(v) = -1$ ならば $v \to u$ の移動後に移動先を選ぶプレイヤーが交代する
- そのような部分木の中では $f(v)$ の大きいものから選んでいくのが最適
- $s(u)$ は以下のように計算できる。ここで $c(u)$ は $u$ の子である点集合
\begin{align}
s(u) =
\begin{cases}
-1 & (u \text{が葉の場合})\\
-\prod_{v \in c(u)}s(v) & (\text{それ以外})
\end{cases}
\end{align}
- 各点 $v \in c(u)$ について、移動をするプレイヤーの選択優先順は以下のようになる
- $s(v) = 1$ かつ $f(v) \ge 0$
- $s(v) = -1$ かつ $f(v)$ について降順
- $s(v) = 1$ かつ $f(v) \lt 0$
- $f(u)$ は上記の優先順で $v_{1}, \dots, v_{k}$ と移動先を選んでいくとして、$f(u) = -1 + \sum_{i = 1}^{k} \left( \left( \prod_{j=1}^{i}s(v_{j}) \right) \times f(v_{i}) \right)$ と計算できる
- 最終的に高橋君が得られるコインの枚数は $\frac{N - f(1)}{2}$
実装
計算量は $O(N \mathrm{log}N)$
公式解説
躓いた点
02/15: AtCoder Regular Contest 111 B - Reversible Cards
Difficulty: 1334 (記事作成時点)
供養
解法
- 色を点、カードを辺とするグラフを考える
- グラフの各辺について両端点のうちどちらか一方を選んだ時に、最大でいくつの点を選べるかという問題になる
- よって、グラフの連結成分について考える
- $k$ 点からなる連結成分が単純な木の場合、$k - 1$ 点を選べる
- 適当な点を根とする木として見たときに、各辺が子になる点を選べば根以外を選べる
- それ以外の場合、$k$ 点全てを選べる
- 適当な最小全域木を作ったときに選ばれなかった辺の端点の一方を根として木の時と同様に選び、選ばれなかった辺でその点を選べばよい
- 連結成分が木であるかどうかは連結成分に含まれる辺の数が $k - 1$ 本か $k$ 本以上かで判定できる
実装
計算量は $O(N)$
公式解説
躓いた点
02/19: AtCoder Regular Contest 111 C - Too Heavy
Difficulty: 1750 (記事作成時点)
供養
解法
- 初期状態で $a_{i} \le b_{p_{i}}$ かつ $i \neq p_{i}$ ならば条件を満たす操作列は存在しない
- 操作可能な任意の $(i, j)$ について、$a_{i} \le a_{j}$ のとき、$(i, j)$ を交換しても $b_{p^{'}_{i}} \lt a_{i} \le a_{j}$ なのでその操作後に $j$ が疲れることはない
- $p^{'}_{i}$ はその時点で $i$ が持っている荷物の番号
- よって、$a_{i}$ の昇順に自身が本来持つべき荷物を持っている人と交換をしていくことで操作列を作ることができる
- この操作列の長さは $(i, p_{i})$ を辺とするグラフを作成したときに作られるサイクルの数を $C$ としたときに $N - C$ で表され、これが最小となる
- 疲労の制約を考えずに交換した場合でも $N - C$ が最小であるため
実装
計算量は $O(N\mathrm{log}N)$
公式解説
躓いた点
Difficulty: 1461 (記事作成時点)
供養
解法
- $S + Kx = Nz\; (x \ge 0, y \ge 1)$ より、$y = 1 - z$ として $Kx + Ny = N - S(= M)$ を満たす$(x, y)$ について、$x \ge 0, y \le 0$ の範囲で $x$ を最小化する
- $D = \mathit{GCD}(K, N, M), K^{'} = \frac{K}{D}, N^{'} = \frac{N}{D}$ としたとき、$D^{'} = \mathit{GCD}(K^{'}, N^{'}) \neq 1$ ならば解なし
- $D^{'} \neq 1$ のとき、$M^{'} = \frac{M}{D}$ は $D^{'}$ の整数倍ではないため $K^{'}x + N^{'}y = M^{'}$ について $(x, y)$ が整数解を持つ条件を満たさない
- $D^{'} = 1$ のとき、拡張ユークリッド互除法により $K^{'}x + N^{'}y = 1$ についての整数解 $(x^{'}, y^{'})$ が求められるので、$M^{'}$ 倍することで $K^{'}x + N^{'}y = M^{'}$ についての整数解 $(x, y)$ を求められる
- また、そこから一般化すると整数 $t$ を用いて $(x, y) = M^{'}(x^{'} + N^{'}t, y^{'} - K^{'}t)$ となるので、$x \ge 0, y \le 0$ の範囲で $x$ を最小化すると
\begin{align}
x &= M^{'}x^{'} + N^{'} \mathrm{min}( \lceil -\frac{M^{'}x^{'}}{N^{'}} \rceil, \lceil \frac{M^{'}y^{'}}{K^{'}} \rceil) \\
&= M^{'}x^{'} + N^{'} \lceil \mathrm{min}(-M^{'}\frac{x^{'}}{N^{'}}, \frac{\frac{M^{'}(1 - K^{'}x^{'})}{N^{'}}}{K^{'}}) \rceil \\
&= M^{'}x^{'} + N^{'} \lceil \mathrm{min}(-M^{'}\frac{x^{'}}{N^{'}}, \frac{M^{'}}{N^{'}K^{'}} - \frac{M^{'}x^{'}}{N^{'}}) \rceil \\
&= M^{'}x^{'} + N^{'} \lceil -\frac{M^{'}x^{'}}{N^{'}} \rceil \\
&= M^{'}x^{'}\; \mathrm{mod}\; N^{'}
\end{align}
実装
計算量は $O(T\mathrm{log}N)$
公式解説
躓いた点
- 数学部分をちゃんと理解できていなかった
- 拡張ユークリッド互除法を実装できなかった
02/20: SOMPO HD プログラミングコンテスト2021 (AtCoder Beginner Contest 192) D - Base n
Difficulty: 1425 (記事作成時点)
供養
解法
- $X$ を $n$ 進表記としたときに得られる値を $X_{n}$ とする
- $|X| = 1$ のとき、$X_{10} \le M $ ならば 1、そうでなければ 0 を返す
- 任意の $n$ について $X_{10}$ と同値になるため
- それ以外の場合、$X_{n} \le M $ である最大の $n$ を求め、$n - d$ を出力する
実装
計算量は $O(|X|\mathrm{log}M)$
公式解説
躓いた点
02/21: SOMPO HD プログラミングコンテスト2021 (AtCoder Beginner Contest 192) F - Potion
Difficulty: 1783 (記事作成時点)
供養
解法
- まず選択する個数 $C$ を決める
- それぞれの $C$ について、$\mathit{DP}_{i, j, k}$ を $A_{1}, \dots, A_{i}$ までで $j$ 個選択したときに、それらの合計値を $\mathrm{mod} C$ した値が $k$ であるような合計値の最大値であるようにDP表を作る
- （存在するならば）$\frac{X - \mathit{DP}_{N, C, X\%C}}{C}$ を求め、それらの最小値を返す
実装
計算量は $O(N^{4})$
公式解説
躓いた点
- DP表の作り方を間違えた
- $O(N^{4})$ に日和った
02/21: AtCoder Beginner Contest 185 E - Sequence Matching
Difficulty: 1468 (記事作成時点)
供養
解法
- $\mathit{DP}_{i, j}$ を $A_{i}, B_{j}$ までの数列の場合における $x + y$ の最小値とする
- 自明な値として $\mathit{DP}_{i, j} \le i + j$ である
- $A_{i}, B_{j}$ に着目した場合、それぞれを残すかどうかと、その場合の $DP_{i, j}$ の値の変化は以下のようになるので、これらの最小値をとる
- $A_{i}$ も $B_{i}$ も残す場合は $DP_{i - 1, j - 1} + c$
- $c$ は $A_{i} = B_{j}$ ならば 0, そうでなければ 1
- $A_{i}$ のみ残す場合は $DP_{i - 1, j} + 1$
- $B_{j}$ のみ残す場合は $DP_{i, j - 1} + 1$
- 両方消す場合は $DP_{i - 1, j - 1} + 2$ なので考慮しなくてよい
実装
計算量は $O(NM)$
公式解説
躓いた点
02/22: AtCoder Beginner Contest 188 F - +1-1x2
Difficulty: 1865 (記事作成時点)
供養
解法
- 操作列を $Y$ から $X$ の方向で見ると、以下の操作をしている
- $Y$ に 1 を足す
- $Y$ から 1 を引く
- （$Y$ が偶数の時に）$Y$ を $\frac{1}{2}$ にする
- 加算と減算は交互に現れることはない
- $k \ge 2$ 回加算してから除算する場合、$k - 2$ 回加算してから除算し1回加算することで、より少ない回数で同じ結果を得ることができる
- 減算についても同様
- よって、加算と減算は最後の除算以前は2回以上連続しない
- $y$ を $X$ にするための操作回数を求める関数 $F(y)$ を以下のように作ると、$F(Y)$ をメモ化再帰で解くことで解を出せる
\begin{align}
F(y) =
\begin{cases}
|X - y| & y = 1\\
\mathrm{min}(F(\frac{y + 1}{2}) + 2, F(\frac{y - 1}{2}) + 2, |X - y|) & y \text{が1以外の奇数}\\
\mathrm{min}(F(\frac{y}{2}) + 1, |X - y|) & y \text{が偶数}
\end{cases}
\end{align}
実装
計算量は $O(\mathrm{log}Y)$
公式解説
躓いた点
02/27: AtCoder Beginner Contest 193 E - Oversleeping
Difficulty: 1948 (記事作成時点)
供養
解法
- B駅で停車して $y$ 秒後の時刻 $t$ に、起きて $q$ 秒後の高橋君が下車するとすると、整数の組 $(a, b)$ を用いて $t = (2X + 2Y)a + X + y = (P + Q)b + P + q$ が成り立つ
- 上式より、$t \equiv X + y\; (\mathrm{mod}\; 2X + 2Y), t \equiv P + q\; (\mathrm{mod}\; P + Q)$ が成り立つ
- よって、Chinese Reminder Theoremより（解が存在すれば）$t$ を求めることができる
- $0 \le y \lt Y, 0 \le q \lt Q$ の範囲における $t_{y, q}$ の最小値、もしくは範囲全てにおいて解なしならば
infinity を出力する
実装
caseあたりの計算量は $O(YQ\mathrm{log}(X + Y + P + Q))$
公式解説
躓いた点
- Chinese Reminder Theoremを実装できなかった
