Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2009-12-05

MazeMaker (SRM453.5 DIV1 Easy)

| 01:12 | MazeMaker  (SRM453.5 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - MazeMaker  (SRM453.5 DIV1 Easy) - TopCoder煮ブログ

本番前の練習。あらかじめ与えられた迷路とスタート地点でどこにゴールを設置するとクリアに時間かかるようになるか。迷路をうろつく人の移動パターンがあらかじめ与えられている。

当然、総当りはダメなので悩んだが、スタート地点固定で最大距離を求める、ということなのでダイクストラ法で解けることに気づいた。あとは書いていくだけ。Row/Column を x/y に置き換えて書き始めてしまってかえって混乱してしまった。ダイクストラは queue 使えば簡単だということを覚えてたので TopCoder やる前よりかは早く書けるようになってるかも。

無駄は多かったが 264.75pt/500.0pt の時間で submit(DIV2 Midium のほうで解いたので)。System Test も一発で通った。C++ 一位の人のソースと見比べたらシンプルさでは負けるものの方向性は同じだった。