競プロチャレンジ供養会場: Kick Start Round D 2021 Final Exam

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

供養

解法

• 各セットの最小値の集合 $A$ と、$A$ の各要素 $a_{i}$ を最小値とするセットの最大値 $b_{a_{i}}$ の集合 $B$ を持っておく
• $A$ から、$s_{j}$ 以下で最大の $a_{l}$ と、$s_{j}$ 以上で最小の $a_{r}$ を見つける
• このとき、選択される問題は $\min(b_{a_{l}}, s_{j})$ と $a_{r}$ のうち $s_{j}$ に近いほうである
  • これによって選択される問題を $p_{j}$、$p_{j}$ が所属していた問題セットの最小値を $a_{i}$ とする
• $p_{j}, a_{i}$ の値で $A, B$ を以下のように更新する
  • $p_{j} = b_{a_{i}}$ ならば $b_{a_{i}} = b_{a_{i}} - 1$ とし、その結果 $a_{i} \gt b_{a_{i}}$ となるならば $a_{i}$ を$A$ から除外する
  • $p_{j} \lt b_{a_{i}}$ ならば以下の操作を実施する
    • $p_{j} + 1$ を $A$ に追加し、$b_{p_{j} + 1} = b_{a_{i}}$ とする
    • $p_{j} = a_{i}$ ならば $a_{i}$ を $A$ から除外する
    • $p_{j} \gt a_{i}$ ならば $b_{a_{i}} = p_{j} - 1$ とする
• $A$ をAVL木で持てば探索・追加・削除がすべて1回あたり $O(\log (N + M))$ で可能になる
• 全ての操作が終わったら $p_{j}$ を出力する

計算量はテストケースあたり $O( (N + M) \log (N + M) )$

公式解説

躓いた点

• 時間内にAVL木を実装できなかった

競プロチャレンジ供養会場: AtCoder Beginner Contest 209 E - Shiritori

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 2153 (記事作成時点)

供養

解法

• 任意のアルファベット3文字の文字列に対応する頂点からなる頂点集合 $V$ および、各 $s_{i}$ の先頭3文字に対応する点 $u_{i}$ から末尾3文字に対応する点 $v_{i}$ への辺 $u_{i} \to v_{i}$ からなる辺集合 $E$ からなるグラフを考える
• $s_{i}$ でしりとり開始のとき、$v_{i}$ から交互に辺を辿っていき移動できなくなったほうが負けとなる
• 先手番が到達したときに先手番の勝利が確定する頂点集合を $W$、先手番の敗北が確定する頂点集合を $L$ とすると、以下のようにして $W, L$ を決めることができる
  • 頂点 $u$ を始点とするある辺 $uv$ について $v \in W$ であれば $u \in L$
  • 頂点 $u$ を始点とするすべての辺 $uv$ について $v \in L$ であれば $u \in W$
• 各 $v_{i}$ について、$v_{i}$ から出ていく辺がないものについて $v_{i} \in W$ とし、上記の方法で $W, L$ を順次拡張しながら決めていく
  • 新しく追加された頂点 $v$ を終点とする各辺 $uv$ について $u$ を評価していけば拡張は最大で辺の数だけ行われる
• 各 $v_{i}$ について、$v_{i} \in W$ ならば Takahashi、$v_{i} \in L$ ならば Aoki、どちらでもなければ Draw を出力する

実装

計算量は $O(N)$

公式解説

躓いた点

• プレイヤーの挙動に関する記述が曖昧で出題意図を正しく汲み取れなかった

競プロチャレンジ供養会場: AtCoder Beginner Contest 207 E - Mod i

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1820 (記事作成時点)

供養

解法

• $A_{1}$ から $A_{i}$ までの累積和を $C_{i}$ とする
• $i \lt j$ および $1 \le k \le N$ について $C_{i} \equiv C_{j}\; (\mathrm{mod}\; k)$ のとき、$A_{i}$ で終端している、合計が $k$ で割り切れる $B_{k}$ に $A_{i + 1}, \dots, A_{j}$ を追加した $B_{k}^{'}$ もまた合計が $k$ で割り切れる
• 上記の性質を踏まえてDPを実施する
• $\mathit{DP}_{i, j}$ を、$B_{i}$ を $A_{j}$ で終端するパターン数とする
• $\mathit{DP}_{0, 0} = 1, \mathit{DP}_{0, j \ge 1} = 0$ とする
• $1 \le i \le N$ について以下を実施する
  • 長さ $i$ の配列 $M $ を用意する
  • $M_{C_{i - 1} \% i} = \mathit{DP}_{i - 1, i}$ とする
  • $i \le j \le N$ について、$\mathit{DP}_{C_{j} \% i} = M_{C_{j} \% i}$ とし、$M_{C_{j} \% i} に \mathit{DP}_{i - 1, j}$ を加算する
• $\sum_{i}\mathit{DP}_{i, N}$ が答え

実装

計算量は $O(N^{2})$

公式解説

躓いた点

• $N^{3}$ のDPをしていてTLE

競プロチャレンジ供養会場: AtCoder Beginner Contest 206 (Sponsored by Panasonic) E - Divide Both

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1745 (記事作成時点)

供養

解法

• 整数 $g \gt 1$ について、整数 $a, b \ge 1$ を用いて $(x, y) = (ag, bg)$ と表せれば最大公約数が $g$ の倍数のペアとなる
  • そのような $a, b$ の候補の数 $k_{g}$ は $k_{g} = \lfloor \frac{R}{g} \rfloor - \lceil \frac{L}{g} \rceil + 1$ 種類
• 各素因数を高々1回掛け合わせて作成される $R$ 以下の合成数 $m = \prod_{i} p_{i}^{s_{i} \in \lbrace 0, 1 \rbrace}$ について $S_{m} = (-1)^{(1 + \sum_{i}s_{i})}$ とすると、$g \gt 1$ であるような $(x, y)$ の総数 $X$ が $X = \sum_{m} S_{m}k_{m}(k_{m} - 1)$ で求められる
• $m $ の集合 $M $ および $S_{m}$ を以下のように列挙する
  • $R$ 以下の素数を列挙し、$P$ とする
  • $M = \emptyset$ とする
  • 各 $p_{i} \in P$ について以下のように $M $ を更新する
    • $u = \lfloor \frac{R}{p_{i}} \rfloor + 1$ とする
    • $M \cap \lbrack 0, u)$ で最大の要素を次の $u$ とし、$M = M \cup \lbrace up_{i} \rbrace, S_{up_{i}} = -S_{u}$ とする
      • $u$ が更新できなくなるまで繰り返す
    • $M = M \cup \lbrace p_{i} \rbrace, S_{p_{i}} = 1$ とする
• $X$ は $\frac{x}{g} = 1$ もしくは $\frac{y}{g} = 1$ であるような $(x, y)$ も含んでいるので、$L \le g \le R$ について $2(k_{g} - 1)$ を引くことでそれらを排除する

実装

計算量は $O(R \log R)$

公式解説

躓いた点

• $g \gt 1$ である $(x, y)$ の列挙方法の整理と高速化に手こずった

競プロチャレンジ供養会場: AtCoder Beginner Contest 205 E - White and Black Balls

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 2025 (記事作成時点)

供養

解法

• $N \gt M + K$ のとき、自明に $0$
• $(x, y) = (0, 0)$ から $x = x + 1$ もしくは $y = y + 1$ を繰り返して $(M, N)$ に到達するパターン数を数える問題と同義
• 全パターン数は $_{N + M}\mathrm{C}_{N}$
• NGの経路パターンを以下のように考える
  • $K = N$ のとき、NGとなる経路は存在しない
  • NGのとき、少なくとも1回は直線 $y = x + K + 1$ に接触するような経路を通っている
  • そのような経路において、$(0, 0)$ から接触した点 $(x, y)$ までの経路を直線 $y = x + K + 1$ について対象となるように描くと、必ず $(-K - 1, K + 1)$ から $(x, y)$ までの経路となる
  • したがって、NGとなる経路は $(-K - 1, K + 1)$ から $(M, N)$ まで移動するパターン数 $_{N ＋M}\mathrm{C}_{N - K - 1}$ と同値
• 全パターン数からNGパターン数を引いた値が答え

実装

計算量は $O(N + M)$

公式解説

躓いた点

• $(0, 0)$ を直線で折り返して $(-K - 1, K + 1)$ に集約すればよいことに気が付かなかった

競プロチャレンジ供養会場: 東京海上日動 プログラミングコンテスト2021 (AtCoder Regular Contest 122) C - Calculator

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1818 (記事作成時点)

供養

解法

• 操作を次のように考える
  1. $x$ を $x + a$ にする、ここで $a \in \lbrace 0, 1 \rbrace$ である
  2. $y$ を $y + b$ にする、ここで $b \in \lbrace 0, 1 \rbrace$ である
  3. $x$ を $x + y$ にする
  4. $y$ を $x + y$ にする
• 上記からなる操作列を $1 \to 2 \to 4 \to 3 \to 1 \to \dots$ と繰り返すことを考える
• $n$ 回目の $1 \to 2 \to 4 \to 3$ を実行したときに操作 $1$ もしくは $2$ で増加した数を $a_{n}, b_{n}$ とすると、各ループが終わった時の $(x, y)$ の値は
  • $(2a_{1} + b_{1}, a_{1} + b_{1})$
  • $(5a_{1} + 3b_{1} + 2a_{2} + b_{2}, 3a_{1} + 2b_{1} + a_{2} + b_{2})$
  • $\dots$
• よって、$n$ 回目のループ終了時の $x$ の値に関する一般項 $x_{n}$ は $x_{n} = \sum_{i = 1}^{n}(f_{2i + 1}a_{i} + f_{2i}b_{i})$
  • ここで $f_{k}$ はフィボナッチ数列の第 $k$ 項を意味する
• $N$ を表現するために十分な数の $n$ を用意して、$f_{k}$ の降順にgreedyに $a_{i}, b_{i}$ を決めていけばよい
  • $n$ を $f_{2k + 1} + f_{2k} \ge N$ となる最小の $k$ とした場合、$n = 43$ で十分であることがわかる
• 以下のように操作列 $S$ を作成できる
  • $f_{2i + 1} \le N$ ならば $1$ を $S$ に加えて $N = N - f_{2i + 1}$
  • $f_{2i} \le N$ ならば $2$ を $S$ に加えて $N = N - f_{2i}$
  • $4, 3$ を $S$ に加える
• この方法だと $N = 679891637638612257$ のとき $|S| = 129$ となるのがおそらく最長
  • greedyに選ぶと $b_{i}, a_{i - 1}$ や $a_{i - 1}, b_{i - 1}$ が連続して $1$ になることはない
    • それぞれ $a_{i}, b_{i}$ で選択してしまうため
  • そのため、$|S|$ は高々 $3n$ 程度で抑えられる
  • $n$ を用意するときに $\sum_{i = 1}^{k}f_{k} \ge N$ となる最小の $k$ で止めてしまうと、すべてのループですべての操作をする可能性があり、最大で $4n$ くらいになってしまう
    • この場合 $n = 42, |S| = 168$ くらいになってしまう

実装

計算量は $f_{k} \ge x$ である最小の $k$ を返す関数を $F(x)$ としたとき $O(F(N))$

公式解説

躓いた点

• 一般項からn進数を作ろうとしていた

競プロチャレンジ供養会場: AtCoder Beginner Contest 204 E - Rush Hour 2

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1710 (記事作成時点)

供養

解法

• 基本的には経路探索
• 時刻 $t$ 以降に辺 $i$ を使って移動する際に最も早く移動できるとき、移動先に到達する時刻は $f(x) = x + C_{i} + \lfloor \frac{D_{i}}{x + 1} \rfloor$ を $x \ge t$ の整数領域で最小化した値
• $g(x) = f(x) - C_{i} + 1 = x + 1 + \lfloor \frac{D_{i}}{x + 1} \rfloor$ とし、さらに $y = x + 1$ とした $g(y) = y + \lfloor \frac{D_{i}}{y} \rfloor$ を $y \ge 1$ の整数領域で最小化することを考える
• $g(y) - g(y + 1) = y + \lfloor \frac{D_{i}}{y} \rfloor - \left( y + 1 + \lfloor \frac{D_{i}}{y + 1} \rfloor \right) = \lfloor \frac{D_{i}}{y} \rfloor - \lfloor \frac{D_{i}}{y + 1} \rfloor - 1$ について、
  • $\frac{D_{i}}{y} - \frac{D_{i}}{y + 1} \gt 1$ ならば $\lfloor \frac{D_{i}}{y} \rfloor - \lfloor \frac{D_{i}}{y + 1} \rfloor \ge 1$ より $g(y) - g(y + 1) \ge 0$ なので $g(y)$ は広義単調増加
  • $\frac{D_{i}}{y} - \frac{D_{i}}{y + 1} \le 1$ ならば $\lfloor \frac{D_{i}}{y} \rfloor - \lfloor \frac{D_{i}}{y + 1} \rfloor \le 1$ より $g(y) - g(y + 1) \le 0$ なので $g(y)$ は広義単調減少
• 最小値を求めるため、$g(y)$ が広義単調増加であるような最小の $y$ を求める
  • 狭義単調減少であるような最大の $y$ を求めようとすると、$g(y)$ が非線形なので最小値とならない可能性がある
  • 広義単調減少であるような最大の $y$ を求める計算でも大差はない
• $\frac{D_{i}}{y} - \frac{D_{i}}{y + 1} \le 1$ より $y(y + 1) - D_{i} \ge 0$、$y \ge 1$ である最小の整数より $y = \lceil \frac{-1 + \sqrt{4D_{i} + 1}}{2} \rceil$
• 展開して $y - 1 \lt \frac{-1 + \sqrt{4D_{i} + 1}}{2} \le y$ より $2y - 1 \lt \sqrt{4D_{i} + 1} \le 2y + 1$
• $y \ge 1$ より $2y - 1 \ge 1$ なので、$(2y - 1)^{2} \le 4D_{i} + 1 \le (2y + 1)^{2}$
• 展開して $4y^{2} - 4y + 1 \lt 4D_{i} + 1 \le 4y^{2} + 4y + 1$ より $y(y - 1) \lt D_{i} \le y(y + 1)$
• $h(y) = y(y - 1)$ としたとき、$h(y^{'}) \lt D_{i}$ となる最大の $y^{'}$ を求める
• $t^{'} = \mathrm{max}(y^{'} - 1, t)$ が出発するべきタイミング

実装

計算量は $O(N + M\mathrm{log}N)$

公式解説

躓いた点

• $f(x)$ が狭義単調減少する最大の $x$ を二分探索してWA