ARC040 - C - Z塗り
概要
任意の自然数r, cを使って、(i==r && j <= c) || (i == r + 1 && j >= c)の部分を1円をかけて塗ることができる。
N*Nのグリッドが与えられて、そのうちのいくつかが既に塗られてるかもしれない。既に塗られたものに上書きにして塗ってもよい。
この時、全部塗り切るのにかかる最低金額を答えよ。
制約： 1 <= N <= 100
ACするまで
1. 貪欲法っぽいなぁ
2. 1行に連続してる塗られてない区間が2つ以上あればよくない。1つあるのならば、その下にあるものをZ塗りする。、的な感じで考察を進めるも、WAの山。
3. グリッドの塗り分けの貪欲のにおいがするものは、「ここで塗らなければ後で塗っても絶対損する」ようなものに着目する。
4. 今回の場合は、z塗りの1行目の右端に該当するので、それを塗りつぶすように塗れば、最適になる。->AC
考察
貪欲っぽい問題で、貪欲であると証明しきるときによく使う手法として、
ある状況Xで、操作をしてPを満たす、ということをしないと、「状況Xより後ろのどの状況でもPを満たすのに余計な操作をする」がありうるような状況Xでは、操作をしてPを満たさないといけない。
当たり前のことを書いてます。
そして、これをグリッドの特徴的なものを使っての塗り分けに落とし込んでみると、
塗ってる時に、とあるマスを塗らないと、「今より後ろのどの状況でもそのマスを塗るのに余計な操作をする」がありうるようなときでは、そのマスを塗らないといけない。
グリッドでは、そのようなマスがどのような特徴を持つかをつかむために、実際に手元でぬってみるとわかりやすい。
今回の場合、手元でZ塗りをいろいろ試してみると、
oooo .oAo .oo. o...
これのAの部分のように、上の行から見て、その行の右から見て空いてるようなマスは、そこをZ塗りの曲がり角にしなければ、後々これを塗るには1回の操作を余分にして塗る必要がある。
よって、これの貪欲は、この部分を常に塗りつぶすように動くことで、結果的には最善となる。
一言
落とした問題は、二度と落とさなければいい。
後輩が受験で苦しんでもがいてる中で、これぐらいの苦しみはどうってことない。
