#総合結果
- [Score] 1500 pts
- [Time] 56:43 + 05:00 $\times$ 1 = 61:43
- [Ranking] 221 st [Rated内: 109 th]
- [Performance] 2142
- [Rating] 1916 → 1941 (+25)
##各問題ごとの詳細, 提出コード
| Question | Score | Time/Result | Penalty | During Contest | After Contest |
|---|---|---|---|---|---|
| A問題 | 100 pts | 01:43 | ■ | ||
| B問題 | 200 pts | 02:56 | ■ | ||
| C問題 | 300 pts | 08:31 | ■ | ||
| D問題 | 400 pts | 48:05 | 1 Penalty | ■ |
■ 辞書式小さい地点に限定 |
| E問題 | 500 pts | 56:43 | ■ | ||
| F問題 | 0 pts | --:-- | |||
| Total | 0 pts | 56:43 | 1 Penalty |
#問題ごとの略解
## A問題 (100pts, diff: 19) Cabbages
問題文から, 素直に以下の整数を出力すれば良い.
$$\begin{cases} NX & (N \leq A) \\ AX+(N-A)Y & (N>A) \end{cases}$$
なお, 場合分けしなくても, $\min(N,A)X+\max(N-A,0)Y$ とでも表せる.
## B問題 (200pts, diff: 22) Bouzu Mekuri
文字列 $S$ を左から見ていき, 最初に現れる ${\tt 1}$ が $k$ 文字目 (1-index) だったとき, $k$ が奇数ならば, 髙橋君の負け, $k$ が偶数だったら青木君の負けである.
## C問題 (300pts, diff: 359) Colorful Candies
$R_i:=\{i,i+1,\dots,i+K-1\}$ とする. この $R_i$ は取るキャンディのうち一番左端が左から $i$ 番目のキャンディであるときに取る $K$ 個のキャンディ全体の集合である.
$R_i$ と $R_{i+1}$ の間の関係性について調べてみると,
$$R_{i+1}=(R_i \setminus \{i\}) \cup \{i+K\}$$
になる. これは, $R_i$ から $i$ を除き, $i+K$ を加えると $R_{i+1}$ になることを意味している. このことを参考にすると, 以下のような手順で答えができる.
- $D$ を $0$ で初期化した辞書 (連想配列) とする. この $D$ にはある区間におけるキャンディ $i$ の個数を記録させる.
- $i=1,2,\dots, K$ の順に $D[c_i]$ を $1$ 増やす.
- $D$ の非ゼロ成分の個数を $Y_1$ とする (この $Y_1$ は $R_1$ におけるキャンディの種類数である).
- $i=1,2,\dots,N-K$ の順に以下を行う.
- $Y_{i+1}=Y_i$ とする.
- $D[c_i]$ を $1$ 減らす (キャンディ $i$ を取り除くことに対応する).
- $D[c_i]=0$ ならば, $Y_{i+1}$ を $1$ 減らす (色 $c_i$ のキャンディがなくなることに対応する).
- $D[c_{i+K}]$ を $1$ 増やす (キャンディ $i+K$ を加えることに対応する).
- $D[c_{i+K}]=1$ ならば, $Y_{i+1}$ を $1$ 増やす (色 $c_{i+K}$ のキャンディが新たに加わることに対応する).
- (この $Y_{i+1}$ は $R_{i+1}$ におけるキャンディの種類数になる)
- $\max(Y_1, \dots, Y_{N-K+1})$ が答えである.
計算量は $O(N)$ である.
## D問題 (400pts, diff: 1507) National Railway
$f((i,j),(i',j')):=A_{i,j}+A_{i',j'}+C(|i-i'|+|j-j'|)$ とする. ここで, 絶対値が現れているので, $i-i', j-j'$ の正負で場合分けをする.
以下, $(a,b), (c,d)$ に対して, $(a,b) \sqsubset (c,d)$ を $(a,b)$ は $(c,d)$ より辞書式順序の意味で真に小さいとする. つまり,
$$(a,b) \sqsubset (c,d) \iff (a<c) {\rm ~or~} (a=c {\rm ~and~} b<d)$$
である.
以降では, マス $(i,j)$ とマス $(i',j')$ に駅を建てると考え, 対称性から $(i',j') \sqsubset (i,j)$ としてもよく, 特に, $i' \leq i$ である. そして, マス $(i,j)$ を固定し, $(i',j') \sqsubset (i,j)$ の範囲で $(i', j')$ を動くことを考える.
- $j' \leq j$ のとき
\begin{align*}
f((i,j),(i',j'))
&=A_{i,j}+A_{i',j'}+C((i-i')+(j-j')) \\\\
&=A_{i,j}+C(i+j)+A_{i',j'}-C(i'+j')
\end{align*}
ここで, $(i,j)$ は固定していることから, $A_{i,j}+C(i+j)$ は定数と見なせることから, $A_{i',j'}-C(i'+j')$ の最小化を目指すことになる. よって, $P_{i',j'}:=A_{i',j'}-C(i'+j')$ とすると,
$$\min_{\substack{(i',j') \sqsubset (i,j) \\ j' \leq j}} f((i,j),(i',j'))=A_{i,j}+C(i+j)+\min_{\substack{(i',j') \sqsubset (i,j) \\ j' \leq j}} P_{i',j'}$$
が成り立つ.
ここで, $\min_{\substack{(i',j') \sqsubset (i,j) \\ j' \leq j}} P_{i',j'}$ について考察する. $L_{i,j}:=\min_{\substack{(i',j') \sqsubset (i,j) \\ j' \leq j}} P_{i',j'}$ とする. ここで, 最小値について, 以下の性質が成り立つ. ただし, $x,y,z$ を実数とする.
- $\min(x,y)=\min(y,x)$
- $\min(x,y,z)=\min(x,\min(y,z))=\min((x,y),z)$
及び, $U_{i,j}:=\{(i',j') \mid (i',j') \sqsubset (i,j) \}$ としたとき,
$$U_{i,j}=U_{i-1,j} \cup U_{i,j-1} \cup \{(i,j)\}$$
であることから,
$$L_{i,j}=\min(L_{i-1,j}, L_{i,j-1}, P_{i,j})$$
である. よって, 上での $L_{i,j}$ を用いて,
$$\alpha_{i,j}:=\min_{\substack{(i',j') \sqsubset (i,j) \\ j' \leq j}} f((i,j),(i',j'))=A_{i,j}+C(i+j)+L_{i-1,j}$$
であることがわかった.
ここで, $L_{i,j}$ を求める計算量について, 各 $P_{i,j}$ は $O(1)$ で求めることができ, $L_{i,j}$ の更新も $O(1)$ でできることから, $L_{i,j}$ の全ては $O(HW)$ で求めることができる.
- $j' \leq j$ のとき
上のときと同様にすると,
\begin{align*}
f((i,j),(i',j'))
&=A_{i,j}+A_{i',j'}+C((i-i')+(j'-j)) \\\\
&=A_{i,j}+C(i-j)+A_{i',j'}-C(i'-j')
\end{align*}
である. よって, $j' \leq j$ のときと同様に, $\beta_{i,j}$ を求めることができる.
- $Q_{i',j'}:=A_{i',j'}-C(i'-j')$
- $K_{i,j}:=\min_{\substack{(i',j') \sqsubset (i,j) \\ j' \geq j}} Q_{i',j'}$
- (更新式): $K_{i,j}=\min(K_{i-1,j}, K_{i,j+1}, Q_{i,j})$
- $\beta_{i,j}:=A_{i,j}+C(i-j)+K_{i,j-1}$
このようにして求めた, $\alpha_{i,j}, \beta_{i,j}$ を用いて, 答えは
$$\min(\min_{i,j} \alpha_{i,j}, \min_{i,j} \beta_{i,j})$$
であり, 計算量は $O(HW)$ である.
補足
$L_{i,j}$ はマス $(i,j)$ よりも左上にある $(i',j')$ における $P_{i',j'}$ の最小値で, $K_{i,j}$ はマス $(i,j)$ よりも左下にある $(i',j')$ における $Q_{i',j'}$ の最小値である.
## E問題 (500pts, diff: 1618) Ring MST
この問題は, あるグラフが与えられるので, 最小全域木を求めよという問題である. 一般的な重み付きグラフ $G=(V,E,C:E \to \mathbb{R})$ における最小全域木は以下のようにして求めることができる (Kruskal).
- $T=(V, F)$ を頂点集合が $V$ の空グラフとする. つまり, $F=\emptyset$
- $E$ を $E=\{e_1, \dots, e_m \}$ とする. ただし, $C(e_1) \leq \dots \leq C(e_m)$ とする.
- $e=e_1, \dots, e_m$ の順に以下を実行する.
- 辺 $e$ の2つの端点を $u,v$ としたとき, $T$ における $u,v$ が別の連結成分だった場合, $F$ に $e$ を加える.
- $u,v$ が同じ連結成分だった場合, 何もしない.
- $T=(V,F)$ が最小全域木になる.
この Kruskal 法を参考にして, 解法を述べる.
$(a_1, c_1), \dots, (a_M, c_M)$ を $c_1 \leq \dots \leq c_M$ となるように並び替える.
ここで, 空グラフ $G=([\![N]\!], \emptyset)$ と $(a_1, c_1)$ における考察をする. $G$ において, サイクルを生み出さずに, $(a_1, c_1)$ をできるだけ行うと, どのようなことが起こるかを考える. すると, 操作後, 以下のような結論が得られる.
$\gamma_1=\gcd(N,a_1)$ とすると, $G$ は $\gamma_1$ 個の連結成分からなり, 各連結成分は $N/\gamma_1$ 頂点の木になる.
例: $N=12, a_1=3$ のとき, $G$ にできるだけ $(a_1, c_1)$ を行うと, $G$ は $3=\gcd(3,12)$ 個の連結成分からなり, 各連結成分は頂点集合を $\{0,3,6,9\}, \{1,4,7,10\}, \{2,5,8,11\}$ とする $4(=12/3)$ 頂点の木である.
このとき, $(a_1, c_1)$ による寄与は各 $N/\gamma_1$ 頂点の木を生成するために, $N/\gamma_1-1$ 本の辺が必要なことに注意すると, 全部で $\gamma_1(N/\gamma_1-1)=N-\gamma_1$ 本 1 であることから, $c_1 (N-\gamma_1)$ である.
ここで, $(a_1, c_1)$ を終えた後の連結成分に着目すると, $N$ 頂点は頂点の番号を $\gamma_1$ で割った余りが等しい頂点同士が同じ連結成分にあり, 逆も成り立つ. このことから, 各連結成分を $0,1,\dots, \gamma_1$ に代表させると, この問題は $\gamma_1$ 頂点で操作が $(a_2,c_2), \dots, (a_M,c_M)$ の場合に帰着でき, 問題の"サイズ" が小さくなった.
これを $(a_2, c_2), \dots, (a_M, c_M)$ の場合について見ていき, 最後に帰着されたグラフの頂点数が $1$ ならば全域木であり, そうでなければ全域木ではない.
以下が擬似コードである.
- $(a_1, c_1), \dots, (a_M, c_M)$ を $c_i$ の昇順に並べる.
- $X \gets 0$
- $i=1, \dots, M$ の順に以下を実行する.
- $\gamma_i \gets \gcd(N,a_i)$
- $X \gets X+c_i(X-\gamma_i)$
- $N \gets \gamma_i$
- $N=1$ ならば, $X$ を出力, そうでなければ, $-1$ を出力.
計算量は, 最初のソートがボトルネックになり, $O(M \log M)$ である.
## F問題 (600pts, diff: 2632) Coprime Solitaire
(正解でき次第加筆予定) Key Word: 2-SAT
#感想
##反省点
WA 理由
- D 問題 1箇所 $W$ とすべきところを $H$ にしていた.
-
$N$ 頂点で $\gamma_1$ 個の連結成分がある森 (各連結成分が木) の辺の数が $N-\gamma_1$ であるという理由でも良い. ↩