第16回日本情報オリンピック　予選５

2016年12月11日
情報オリンピック日本委員会

解説

愚直な解法として，各地域ごとに，そこから深さ優先探索または幅優先探索を用いることで到達可能なマスをすべて列挙し， その中に「周りのどの地域にも雨水が流出しない地域」が複数あるかどうかを判定するというものが挙げられる． 時間計算量は O(H^2W^2) となり，ひとつめのケースを正解するためには十分高速であるが，競技時間内にすべてのケースで満点を得ることは難しいだろう．

雨水は標高が高いほうから低いほうへしか流れないため，地域を標高の低い順に見て， そこに降った雨水が最終的に溜まる先がどこであるかという情報を順次更新していくという解法が挙げられる．

この解法は地域を標高の低い順に見ていき，周りにその地域より標高の低い地域がなければ雨水はそこに溜まる．

そうでない場合，周囲の最大 4 つの地域のうちいくつかに、その地域に降った雨水が流出する． もしそのような周囲の地域の中に尾根の地域があれば，今見ている地域も尾根である．

そうでない場合，周囲の地域のうち今見ている地域より標高が低い地域に対して， そこに降った雨水がどこへ溜まるかという情報がすでに計算されているので，その情報をすべて見て，雨水の溜まる先がすべて等しければ， 今見ている地域に降った雨水は必ずその等しい地域に溜まる．そうでない場合，今見ている地域は尾根であるので， その地域が尾根だという情報を記憶し，次に低い地域へ進む．

この解法では，各地域を見るときに高々定数回の操作しか行わないので，時間計算量が O(HW) となり満点が期待できる．