AOJ 1169 : 最強の呪文

The Most Powerful Spell | Aizu Online Judge

嘘解法くさいです。

ダイクストラに見えるけど違うのかな・・・?
と思ったらダメになるケースがある。

あらかじめ幅優先探索をして各ノードからゴールまでの最小文字列を求めておき、
これをヒューリスティックスコアとしてA*探索を行う。

ループが発生したら2400文字(ループさせないでまっすぐ行ったときに考えうる最大の長さ)まで
ループ部分を付け足しておき、最後にループさせないでゴールに着いた文字列と比較する。

としたらACできた。

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2355848#1

嘘解法くささ1

幅優先探索している部分。遠回りして辞書順最小になるケースは十分ありえる。
比較処理を工夫したダイクストラか、深さ優先をしておく必要がありそう。

嘘解法くささ2

ループ判定。2度目にたどり着いて一定の条件を満たせばループ扱いになってしまう。
nが最大で40ぐらいだからbitで経由したノードを記録しておく必要がありそう。

嘘解法くささ3

そもそもこのアルゴリズムで正しい答えが出るのか・・・?


なんかすっきりしないACの仕方をしてしまった。
他のブログを参照するときちんと考察の上解いているので見習いたい。
少し背伸びをして難しい問題が解きたいと思って
700点でかつサークルの人たちが解いているこの問題に手を出してみた。
黄色ゾーンが埋まったらまた解きなおしたい。