AtCoder Regular Contest 074

更新日時:

AtCoder Regular Contest 074

ソースコード

全て 1 人でといた。

解法のメモ

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 も類比的である。絶対に切れない辺である。

あとは最小カットを求める。

ポイント

実装当初は、頂点と辺をきちんと理解していなかった。冷静に考えれば、葉っぱをどれだけ取り除けばいいですかと言われているのだから、葉っぱが辺であると書いているようなものである。そこを意識すれば、頂点が行・列であるのに思い至る。

その他

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 点の問題を自力で解けたのは自信がついた。

コメントする