久しぶりに考えてみる

今年のＷＥＢ予選がいつの間にか終わってたみたいですね．私が参加していた時期は，１０月初めとかだったから，すっかりチェックしてなかったよ．
で，問題を読んでみた．
今年の問題は難易度の壁が激しいなあってのが第一印象．問題Ａ，Ｂ，Ｃに関しては，１５分コース．なので，コメントなし．
問題Ｄ，Ｅ，Ｆがちとムズイかも．てか，現役退いて，ヌルいプログラミングしかしていない俺にはキツイ．
問題Ｄは，バックトラックで解くのが一番簡単なんだけど，最大３０Ｐ８＊８！（でいいのか？）の計算をしないといけないから，バックトラックだと計算時間的に解けない．ようするに，答えが出ない．で，この手の問題は，ダイクストラのアルゴリズムを使うことを考えるんだけど，チケットの使用方法によって距離が動的に変化するので，単純にダイクストラを使えないのがつらい．
まず，仮定を立てる．ルートが決定されている場合，距離が長い区間に高価なチケットを使ったほうが良いので，ルートが決定されれば，所要時間は自動的に求まる．でも，そのルートを求めるのがこの問題なわけで．．．これを使っても，さっきの式が３０Ｐ８になるだけだから．．．
てことで，逆を考える．チケットの使用順序を決定した上で，ダイクストラをかける．いやまて，使用順序を決定しても，ダイクストラは無理じゃないか？　あるノードに到達した時点での残りチケットが違うなら，どちらを優先するか決定できない以上，ダイクストラを使えないんじゃないか？
となると，幅優先探索か．ルート到達時点で，各チケット使用状況とそれまでの時間を保存しておき．．．って，これだと，バックトラックとほとんど変わりがないような．．．
一番理想的な状況は，チケットの値の関係と，ルートの値の関係が近似することなんだよなあ．例えば，チケットが（１，５，２５）とあったとき，ルート（１０，１０，１０）よりもルート（１，５，２５）の方が良いってこと．
う〜んどうしたらいいんでしょう．頭がわけ分からんことになってきた．
問題Ｅは，問題の制約の意味が良く分からん．イベントシミュレータよろしくで解くのが一番なのか？　ステップシミュレータだと，計算時間が足りなさそう．イベントシミュレータで解くにしても，なんか，数式を弄る必要がありそう．う〜ん，今の俺の頭には無理．
問題Ｆは，あらかじめ幅優先探索で，各汚れたタイル間の距離を求めておく．そして，その距離を重みとして，完全グラフを構築する．で，後は巡回セールスマン問題ということで，面倒なのでバックトラック仕掛ける．１０！で求まる．１０！ならぎりぎり計算が終わりそう．
とりあえず，問題ＤＥＦについては，アルコールが抜けてから考えるか．