AtCoder Regular Contest 074
Updated:
Source codes
全て 1 人でといた。
Solutions
E - RGB Sequence
DP の問題。どうやってこれを思いついたのか忘れてしまったんだけど、$i \geq j > k$ に対し以下の通りにする。
$DP[i][j][k]$ とは、 $i$ 番目まで色を決めたもののうち、 $j, j+1, \dots, i$ は同じ色であり、 $j-1$ は $i$ とは違う色、 $k, k+1, \dots, i$ は 2 色で塗られており、 $k-1$ は 3 色目である。そういうものの場合の数。
こうするとまず、条件を考慮しない遷移が書ける。
- $i+1$ 番目に $i$ 番目と同じ色(1 色目)を塗るのは、 $DP[i+1][j][k] += DP[i][j][k]$ と書ける。
- $i+1$ 番目に 2 色目を塗るのは、 $DP[i+1][i+1][k] += DP[i][j][k]$ と書ける。
- $i+1$ 番目に 3 色目を塗るのは、 $DP[i+1][i+1][j] += DP[i][j][k]$ と書ける。
初期条件は、 Index starts at 1 で、 0 番目に 1 番目と違う色を塗ったと仮定して始めればいい。この場合の数は $6$ 通りだが、実際はダブルので、 $DP[1][1][0] = 3$ として十分である。
区間の条件は以下の通り処理される。
- $[l, r]$ が 1 色であるとは、 $j > l$ ならば $DP[r][j][k] = 0$ であることである。
- $[l, r]$ が 2 色であるとは、 $j > l \geq k$ でないならば $DP[r][j][k] = 0$ であることである。
- $[l, r]$ が 3 色であるとは、 $l \geq k$ ならば $DP[r][j][k] = 0$ であることである。
答えは $\sum_{k < j \leq N} DP[N][j][k]$ である。
ポイント
1 時間半くらいうとうとしていたら思いついた。本番では解けなそうだ。
実装で間違えたところは、 3 色で塗るところで $l, k$ の大小関係をミスっていた。
F - Lotus Leaves
まず -1 なのは、同じ行列に $S, T$ がある時である。そうでない場合、最小カットの問題だとわかった。結論を書くと、
- スタートとゴールは、特殊な頂点 $S, T$ を用意する。
- 頂点は、行・列である。 $i$ 行目なら $i$ 、 $j$ 列目なら $j + H$ のようにする。
- 辺は、葉っぱである。$(i, j)$ の葉っぱは、 $i$ と $j+H$ を結ぶコスト $1$ の辺である。有向辺を両方張る。
Sの座標が $(i, j)$ の時は、辺 $(S, i, \infty)$ と $(S, j+H, \infty)$ を張る。Tも類比的である。絶対に切れない辺である。
あとは最小カットを求める。
ポイント
実装当初は、頂点と辺をきちんと理解していなかった。冷静に考えれば、葉っぱをどれだけ取り除けばいいですかと言われているのだから、葉っぱが辺であると書いているようなものである。そこを意識すれば、頂点が行・列であるのに思い至る。
Others
E - sample: 4, tle: 2.000, time: 19:28, from_submit: 49:14
F - sample: 4, tle: 2.000, time: 49:14, from_submit: 00:00
実際はこれに +1.5h くらい。
蓋を開けてみれば教育的な問題が多い。
800 点の問題を自力で解けたのは自信がついた。