内容 よくある最短経路や最小コストを求める問題。 ダイクストラの拡張例みたいなもの。 生成された状態空間の中でもっともコストの小さい状態を抽出。 抽出された状態がゴールならそれが最小。 抽出された状態から次の状態を状態空間に挿入していく。 集合…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2252 解き方 xorを使うと早いかも。 xorは変化ありならtrue,変化なしならfalseになる ソースコード #include <iostream> #include <string> using namespace std; bool is(char c) { return c=='q'||c=='w'||c=</string></iostream>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2253 解き方 マップの大きさが-30から30では無いので注意。死亡。 あくまで、スタート位置、障害物が-30から30の間にある。 それさえ分かれば、優先度のあるBFSするだけ。 ソースコード #inc…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2254 解き方 頂点数が16以下なので、ビットDPで解ける。 int s;で (0000...0000)2の各ビットを頂点に対応させ訪れたかどうかの情報を保持させる。 s == 1 == (0000...0001)2なら、1つ目の頂…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2255 例について考えてみる 6 / 2 * ( 1 + 2 ) > 6 / ( 2 * ( 1 + 2 ) ) > ( 6 / 2 ) * ( 1 + 2 ) 6 / 2 * ( 1 + 2 * 3 ) > 6 / ( 2 * ( ( 1 + 2 ) * 3 ) ) > 6 / ( 2 * ( 1 + ( 2 * 3 ) ) )…