AGC43 んー、実力としか言いようがない

AGC久しぶり。

初コンテストぶりですな。

今回が初コンテストだったら完全に終わってた。

A解けなっただろう。

atcoder.jp

問題文

$H$ 行 $W$ 列のマス目を考えます。上から $r$ 番目、左から $c$ 番目のマスを $(r,c)$ と表すことにします。 全てのマスはそれぞれ白か黒のどちらかの色に塗られています。

次のような経路が存在するとき、このマス目を"良い"状態と呼びます。

• 常に白いマスの上にいながら、$(1,1)$ から、一つ 右か下 のマスに移動することを繰り返し、 $(H,W)$ へ移動する。

ここで、"良い"状態ならば $(1,1)$ や $(H,W)$ が必ず白いことに注意してください。

あなたの仕事は、以下の操作を繰り返し、マス目を"良い"状態にすることです。最小で何回操作を行う必要があるか求めてください。なお、有限回の操作で必ず"良い"状態に出来ることが証明可能です。

• $4$ つの整数 $r_0,c_0,r_1,c_1(1\le r_0\le r_1\le H,1\le c_0\le c_1\le W)$ を選ぶ。$r_0\le r\le r_1,c_0\le c\le c_1$ を満たす全ての $r,c$ について、$(r,c)$ の色を変更する。つまり、白色ならば黒色にし、黒色ならば白色にする。

制約

• $2\le H,W\le 100$

 最初勘違いして一個づつしか塗り替えられれないのかと思った。

提出しておかしいなーってなって問題分読み直し。

注意深く読んでるつもりなんやけど、なんか見逃してしまったり思い込んだりしたりするねんなー。本番ではより注意しよう。

器物破損高橋君　みたいな問題に似てるなーって思い、それを思い出しながら幅優先探索の右としたしか動けないバージョンを作ってみた。

一気に塗れるところは全部塗っちゃう感じで、幅優先探索＋深さ優先探索みたいなイメージ。

次の問題は簡単そうだったけど、できなかった。

んー。もう30分あったら解けてたのかなー。遅すぎる気もするけど。

久しぶりに現状報告。じわじわしか上がってないなー。でもあと2回くらいで緑にはなれるかな。最近アルゴリズムの勉強おろそかにしてるから...だめだなー仕方ないけど。

今日は環境構築5時間、コンテスト2時間半、蟻本1時間

明日はコンテストx2、やってやるぜーー