きろく

特筆すべき記録のまとめ

JOI '10 予選:6- 方向音痴のトナカイ

問題

www.ioi-jp.org

解法

プレゼントを配っていく動作を逆にして考える(すなわち,各家からプレゼントを回収する感じ).すると,次に行く家はプレゼントを回収していない家を通過することは出来ないので各方向一か所に定まる.なので,探索しなければいけない通り数を大幅に減らすことが出来る.つまり,各方向に進んでいき最初にぶつかった家からプレゼントを回収し,その家からまた各方向に進んでいき... の繰り返しをして,全ての家からプレゼントを回収し終わったら教会に戻れるかどうかを判定すればよい.O(nm*(n + m)).

解答

atcoder.jp

あまりにも分からなかったので解説を読んだ.手順を逆にして考えると見通しが良くなる問題だと思った.

f:id:babcs2035:20190202232735p:plain