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

4/8: AtCoder Regular Contest 030 C - 有向グラフ

供養

問題

Difficulty: 2076(estimated) (記事作成時点)

解法

同じ強連結成分の文字は任意の順番で拾えるので辞書順で小さい順に拾ってよい
強連結成分同士の連結のみに着目すればDAGになるので、ある点 $v_{i}$ を代表点とする強連結成分を始点に $k$ 文字拾った時の辞書順最小の文字をDPで求められる

実装は

について、下記の要領で強連結成分分解をおこなう
- 空の配列 $Q$ を用意する
- 各点 $u \in V$ について、それが未探索の点であったら $u$ からDFSをする
- 隣接点が存在しない、もしくは隣接点が全て探索済の点 $v$ を見つけたら、 $Q$ の先頭に $v$ を挿入する
- 長さ $n$ の配列 $R$ を用意する
- $E$ を全て逆向きにしたグラフ $H = (V, E^{-1})$ について、 $Q$ の先頭から、その点 $u$ が未探索なら $u$ からDFSをする
- の探索で発見された点について、とする
  - 全て $u$ と同じ強連結成分に属する
各辺について、に置き換えたグラフを作成する
- 自己ループ、多重辺は含まないようにする
について、下記要領で強連結成分の代表点でトポロジカルソートを実施する
- 空の配列 $Q^{'}$ を用意する
- 各点 $u \in V$ について、 $u$ が代表点かつ未探索ならば $u$ からDFSをする
- 隣接点が存在しない、もしくは隣接点が全て探索済の点 $v$ を見つけたら、 $Q^{'}$ の末尾に $v$ を挿入する
$\mathit{SCC}_{u} = \lbrace c_{v | R_{v} = u} \rbrace$ を辞書順にソートする
$n \times (k + 1)$ の配列 $\mathit{DP}$ を用意する
各代表点について、をの先頭から文字を連結したものとする
- $\mathit{DP}|_{u, l \gt |\mathit{SCC}_{u}|}$ については未定義のままにしておく
を先頭から取り出した順にとし、下記の要領でDP表を更新する
- 長さ $k + 1$ の配列 $\mathit{tmp}$ を用意し、 $\mathit{tmp}_{j} = \mathit{DP}_{q_{i}, j}$ とする
- について下記の操作を実施する
  - $\mathit{DP}_{q_{i}, j}$ が未定義なら何もしない
  - におけるの各隣接点に対し、について、下記操作を実施する
    - $\mathit{DP}_{p. l}$ が未定義なら何もしない
    - $s = \mathit{DP}_{q_{i}, j} + \mathit{DP}_{p, l}$ とし、 $L_{s} = |s|$ とする
    - $L_{s} \gt k$ なら何もしない
    - $\mathit{tmp}_{L_{s}}$ が未定義、もしくは辞書順で $s \lt \mathit{tmp}_{L_{s}}$ となる場合、 $\mathit{tmp}_{L_{s}} = s$ とする
- $0 \le j \le k$ について $\mathit{DP}_{q_{i}, j} = \mathit{tmp}_{j}$ とする
$0 \le i \lt n$ について、 $\mathit{DP}_{i, k}$ が全て未定義なら -1 を出力し、1つ以上定義されていればその中で辞書順最小のものを出力する

計算量は強連結成分分解に $O(n + m)$ 、DP表の初期化に $O(nk)$ 、更新が $O(mk^{2})$ かかるので、合計で $O((n + mk)k)$

公式解説

躓いた点

強連結成分のDAGにするとDPにできるという発想が無かった
強連結成分分解が上手く実装できなかった

4/9: Code Formula 2014 本選 E - ab文字列

供養

問題

Difficulty: 2082(estimated) (記事作成時点)

解法

の長さはフィボナッチ数列の第項となる
- $f_{1} = f_{2} = 1$ なので、そこだけは直接判定する
のとき、はとを前後で組み合わせたものであり、同様にはとを前後で組み合わせたものであることから、はもしくはとなる
- どちらのパターンになっているかにより $k$ の偶奇が分かる
- $F_{N^{'}, k^{'}} = F_{N - 1, \lfloor \frac{k}{2} \rfloor}$ とすると $\lfloor \frac{k}{2} \rfloor$ の偶奇も分かるので、再帰的に $k$ を求めていくことができる
$N \le 5$ のときは前方一致や後方一致を考えることになるので、それよりは $F_{N, k}$ を列挙して一致するものを探した方が早い

実装は

$|S| = 1$ のとき、 $S =$ b ならば $(p, q) = (1, 0)$ 、そうでなければ $(p, q) = (2, 0)$ を出力して終了
フィボナッチ数列を求める
- $f_{23} = 28657 \gt |S|$ となるのでそのあたりまで求めれば十分
$p = 3$ とし、 $f_{p} = |S|$ となるまで $p$ をインクリメントする
$N = 3, 4, 5$ および $0 \le k \lt 2^{N - 2}$ について $F_{N, k}$ を計算しておく
長さ $p + 1$ の配列 $Q$ を用意する
となるまで以下の操作を実施する
- $S \lbrack 0 : f_{p - 2} \rbrack = S \lbrack f_{p - 1} : |S| \rbrack$ ならば $Q_{p} = 0, S = S \lbrack 0 : f_{p - 1} \rbrack$ とし、そうでなければ $Q_{p} = 1, S = S \lbrack f_{p - 2} : |S| \rbrack$ とする
- $p$ をデクリメントする
$q = 0$ とし、 $F_{p, q} = S$ となるまで $q$ をインクリメントする
$i = 6, \dots$ について、 $q = 2 \times q + Q_{i}$ としていく
$(p, q)$ を出力する

計算量は文字列の比較で $O(|S|)$

~~公式解説~~

躓いた点

前計算を $N = 3, 4$ で判定しようとしてWA

4/10: AtCoder Regular Contest 021 C - 増築王高橋君

供養

問題

Difficulty: 2090(estimated) (記事作成時点)

解法

建物 $i$ の $x$ 回目の増築コストは $A{i} + D_{i} \times (x - 1)$ 、総コストは $A_{i} \times x + D_{i} \times \frac{x(x - 1)}{2}$ で表すことができる
増築単価の上限 $Y$ を与えると、建物 $i$ の増築回数 $x_{Y, i}$ は $x_{i} = \mathrm{max}(\lfloor \frac{Y - A_{i}}{D_{i}} \rfloor + 1, 0)$ で表せる
$\sum_{i = 1}^{N}x_{Y, i} \ge K$ となる最小の $Y$ を二分探索で求めることができる
$\sum_{i = 1}^{N}x_{Y, i}$ が $K$ を超える分はコスト $Y$ の増築を必要なだけキャンセルすればよい

実装は

$V = \mathrm{min}(A_{i} + D_{i} \times (K - 1))$ とする
上限 $V + 1$ 、下限0の間で $\sum_{i = 0}^{N - 1}\mathrm{max}(\lfloor \frac{V^{'} - A_{i}}{D_{i}} \rfloor + 1, 0) \ge K$ となる最小の $V^{'}$ を二分探索で求める
$0 \le i \lt N$ について $x_{i} = \mathrm{max}(\lfloor \frac{V^{'} - A_{i}}{D_{i}} \rfloor + 1, 0)$ とする
$\sum_{i = 0}^{N - 1}(A_{i} \times x_{i} + D_{i} \times \frac{x_{i}(x_{i} - 1)}{2}) - V^{'} \times (\sum_{i = 0}^{N - 1}x_{i} - K)$ を出力する

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

公式解説

躓いた点

増築単価ではなく総額で二分探索しようとして手詰まり
答えが64bit intに収まっていなくてoverflowしていた

4/11: AtCoder Regular Contest 056 C - 部門分け

供養

問題

Difficulty: 2093(estimated) (記事作成時点)

解法

部分集合 $U$ のスコア $S(U)$ を求めるために、ある1つの部署を $V \subseteq U$ で固定した場合を考える
$V$ を固定した場合のスコア $S(U | V)$ は $S(U | V) = K + S(U | U \setminus V) - \sum_{i \in V}\sum_{j \in U \setminus V}w_{ij}$ となる
$W(U) = \sum_{i \in U}\sum_{j \in U}w_{ij}$ とすると、 $\sum_{i \in V}\sum_{j \in U \setminus V}w_{ij} = W(U) - W(V) - W(U \setminus V)$ と表せる
上記をもとにDPを行う

実装は

長さ $2^{N}$ の配列 $W$ を用意する
について以下の操作を実施する
- $W_{2^{i} + j} = W_{j}$ とする
- $0 \le k \lt i$ について、 $j \; \mathrm{AND}\; 2^{k} \gt 0$ ならば $W_{2^{i} + j}$ に $w_{i, k}$ を加算する
長さ $2^{N}$ のDP表 $\mathit{DP}$ を用意する
について、DP表を下記のように更新する
- とし、となるまで下記操作を実施する
  - $\mathit{DP}_{u} = \mathrm{max}(K + \mathit{DP}_{v} - W_{u} + W_{u - v} + W_{v}, \mathit{DP}_{u})$ とする
  - とする
    - このようにすることで $u$ のbit subsetを列挙できる
$\mathit{DP}_{2^{N} - 1}$ を出力する

計算量は前処理に $O(2^{N}N)$ 、DPの更新は集合を $V, U \setminus V,$ それ以外に分類する操作となるので $O(3^{N})$ 、全体で $(3^{N})$

公式解説

躓いた点

$N!$ の解法しか思い浮かばなかった
bit subsetの列挙が遅くTLE

4/12: AtCoder Beginner Contest 162 E - Sum of gcd of Tuples (Hard)

供養

問題

Difficulty: 1621 (記事作成時点)

解法

$\mathrm{GCD}(A_{1}, \dots, A_{N}) = k$ となるのは $A_{i}$ が全て $k$ の倍数かつ $nk\; (n \gt 1)$ の倍数ではないこと
$\mathrm{GCD}(A_{1}, \dots, A_{N}) = k$ となる組合せの数 $X_{k}$ は $X_{k} = \mathrm{max}(\lfloor \frac{K}{k} \rfloor, 1)^{N} - \sum_{n = 2}^{\lfloor \frac{K}{k} \rfloor}X_{n \times k}$

実装は

長さの配列を用意する
- 添字を工夫すれば長さ $X - 1$ でも足りる
$S = (K^{N})_{p}$ とする
について下記の計算をする
- $X_{k} = \mathrm{max}(\lfloor \frac{K}{k} \rfloor, 1)^{N}$ とする
- とし、となるまで下記操作を実施する
  - $X_{k^{'}}$ を $X_{k}$ から減算する
  - $k$ を $k^{'}$ に加算する
- $(k - 1) \times X_{k}$ を $S$ に加算する
$S$ を出力する

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

公式解説

躓いた点

計算量の見積りを間違えてTLEすると思い別の方法を探していた

4/13: AtCoder Beginner Contest 162 F - Select Half

供養

問題

Difficulty: 1747 (記事作成時点)

解法

奇数要素のみ、偶数要素のみ、奇数要素→偶数要素で個とれる
- $N$ が奇数の場合、奇数要素のみの場合はどれか1つ抜く必要がある
$N$ が奇数の場合、さらに偶数要素→奇数要素、奇数用途→偶数要素→奇数要素の取り方がある
上記をDPで求めていって最大値をとる

実装は

$(N + 1) \times 3$ のDP表 [\mathit{DP}] を用意し、 $\mathit{DP}_{1, 0} = A_{0}, \mathit{DP}_{2, 0} = A_{1}, \mathit{DP}_{3, 1} = A_{2}$ とする
について下記のようにDP表を更新する
- $\mathit{DP}_{i, 0} = \mathit{DP}_{i - 2, 0} + A_{i - 1}$ とする
- $i \gt 3$ のとき、 $\mathit{DP}_{i, 1} = \mathit{DP}_{i - 3, 0} + A_{i - 1}$ とする
- $i \gt 4$ のとき、 $\mathit{DP}_{i, 1} = \mathrm{max}(\mathit{DP}_{i - 2, 1} + A_{i - 1}, \mathit{DP}_{i, 1})$ とする
- が奇数かつが奇数のとき、さらに下記操作を実施する
  - $i \gt 4$ のとき、 $\mathit{DP}_{i, 1} = \mathrm{max}(\mathit{DP}_{i - 4, 0} + A_{i - 1}, \mathit{DP}_{i, 1})$ とする
  - $i \gt 6$ のとき、 $\mathit{DP}_{i, 2} = \mathit{DP}_{i - 3, 1} + A_{i - 1}$ とする
  - $i \gt 8$ のとき、 $\mathit{DP}_{i, 2} = \mathrm{max}(\mathit{DP}_{i - 2, 2} + A_{i - 1}, \mathit{DP}_{i, 2})$ とする
$N$ が偶数のときは $\mathrm{max}(\mathit{DP}_{N - 1, 0}, \mathit{DP}_{N, 0}, \mathit{DP}_{N, 1})$ を出力する
$N$ が奇数のときは $\mathrm{max}(\mathit{DP}_{N, 1}, \mathit{DP}_{N - 1, 0}, \mathit{DP}_{N - 1, 1}, \mathit{DP}_{N, 1}, \mathit{DP}_{N, 2})$ を出力する

計算量は $O(N)$

公式解説

躓いた点

時間切れ
更新条件の整理に手こずった

4/14: AtCoder Regular Contest 042 D - あまり

供養

問題

Difficulty: 2094(estimated) (記事作成時点)

解法

$X = 1$ の場合もしくは $A \le (\lfloor \frac{B}{P - 1} \rfloor) \times (P - 1)$ の場合、自明な解として1を得られる
$B - A + 1$ が小さいときは、愚直に全通り試すことで最小値を求めることができる
$B - A + 1$ が大きいときは、Baby-step Giant-step algorithmを用いて $X^{k} \equiv Y\; (\mathrm{mod}\; P)$ であるような $A \le k \le B$ が見つかる最小の $Y$ が答えとなる
Baby-step Giant-step algorithmの計算量は $O(\sqrt{P})$ であり、確率的には $\frac{P}{B - A + 1}$ 回の試行で見つかる
より、で線形探索とBaby-step Giant-step algorithmを切り替えればよい
- $1 \lt P \lt 2^{31}$ より、 $2^{24}$ くらいを決め打ちで切り替えのボーダーとしてもよい

実装は

$X = 1 \lor A \le \lfloor \frac{B}{P - 1} \rfloor \times (P - 1)$ ならば 1 を出力して終了
のを求める離散対数問題を解くBaby-step Giant-step algorithm を下記のように実装する
- $m = \lceil \sqrt{p} \rceil$ とする
- 連想配列 $B$ を用意し、 $k = 1$ とする
- について、下記操作を実施する
  - $B_{k} = i$ とする
  - $k = k \times g \% p$ とする
- $G = g^{-m}$ とする
- について、下記操作を実施する
  - $B_{y}$ が存在すれば $i \times m + B_{y}$ を返す
  - $y = y \times G \% p$ とする
$A = A \% P, B = B \% P$ とする
ならば下記を計算する
- $x = X^{A} \% P, y = x$ とする
- について下記を計算する
  - $x = x \times X \% P$ とする
  - $y = \mathrm{min}(x, y)$ とする
- $y$ を出力する
ならば下記を計算する
- について下記を計算する
  - $x = \mathit{BG}(X, y, P)$ を計算する
  - $A\le x \le B$ ならば $y$ を出力して終了