解法１．まだ使っていないパズルの選択 ２．回転方向の選択 ３．上下左右で配置に適当なパズルかどうか判定 ４．配置可能なら更にパズルをおく（再帰） ５．全てのパズルを配置できたら、答えの場合の数が１増加する ６．再帰関数の戻り値を利用して、全ての…

初めに素数洞穴のマップを作る。 渦状にマップを作るのはバグりやすいので、まずはdx, dyを使わずに渦を1方向ずつforループを回して作ると良い。これでかなり楽に書ける。後はDPすればよい。自分は初めの地点から下３方向の洞穴に向かってBFSしていきDP配列…

二部グラフの最大マッチング問題なのでフローを作り、最大流量を調べる。青と赤のカードのペアで gcd > 1 が取れるものに辺が引ける。

最短時間であるが、単一始点最短路問題である。 隣接リストを用いて拡張ダイクストラをする。状態として 「前の位置」「現在位置」「到着時の速度」「経過時間」 を持つとよい。これが分かれば後は書き下すだけ。priority_queue に push する条件として制限…

この記事は Aizu Advent Calendar 2013 7日目 の記事を想定して作成されています。 Let's Boost.Spirit! Boost.Spirit とは構文解析用のライブラリで、Spirit.Lex, Spirit.Qi, Spirit. Karma の３種類があります。 それぞれ字句解析器、字句＋構文解析器、パ…

Boost.Spirit Tutorials のXMLとかの詳しい解読内容。

OpenGL ES "3D Tutorials的な" "ちょっと古い記事"

月間目標 Boost::Spirit使ってゲームの構文解析部を動かす マルチエージェントシステムについて調べる。正月明けまでに半分実装を済ます。 AOJ solve数 350 未完成記事の完成

有向グラフ上の部分集合Sの任意の頂点u, vについて，uからvに到達可能であるときSは強連結である。Sにどの頂点を加えても強連結にできないとき，Sは強連結成分である。有向グラフGについて全ての強連結成分をつぶして一つにすると、グラフはDAGになる。編集中

TOPOLOGICAL-SORT(G) 各頂点 v の終了時刻 v.f を計算するために DFS(G) を呼び出す ある頂点の探索が終了するたびに、この頂点を連結リストの先頭に挿入する return 頂点の連結リスト

入力：有向グラフG, 非負の重み関数 c: E(G) → R_+ および始点 s ∈ V(G) 出力：sからすべての点 v ∈ V(G) への最短パスとその距離、より正確には、 すべての点 v ∈ V(G) に対する p(v) と l(v) ただし、l(v) は最短s-p(v)-パスと 辺(p(v), v)からなる最短s-v…

参考： 線形代数入門 EMANの物理学

s-t-パスの中でk番目に短いものを求める問題をk-最短路問題という。 Priority Queueを使ったダイクストラで実装するのが基本的な解法となる。 参考 Spaghetti Souce

解いてる途中のメモ MAPの中で数字のものだけを使って文字列結合をしていく。dpはstringの配列(vector) でもつとよい。 dp[i+1][j+1] = max(dp[i][j+1]+M[i+1][j+1], max(dp[i+1][j]+M[i+1][j+1])) Mが数値か文字かの判定が必要。数値なら、数が大きくなるよ…

任意の二点を選んでその点を通る円を作る。円は2個ある。 そのような全ての円それぞれが包含できる点の数を数えて最大値を求める。N 円の中心点の求め方 選んだ2点a, bの作る直線Aの生む垂直二等分線と、2点のうち一方の点と中心を結ぶ長さ１の線分から、三…

途中 メモ p, q, a, n が与えられる。 分数の値が等しいというのを確かめる際に浮動小数点に直してはいけない。 p/q, nume/deno の2つの値が等しい p*deno == q*nume であることを利用する また、問題文で指定されるような枝刈りを行うこと

途中 訪れたケーキの集合と現在地点を状態として持って拡張ダイクストラを実行する。 L, C, H, Dの種類のノードがあるが、全て一つのノードに詰める。その時、添字が例えば H, D, L, C の順になるように詰めて、予め種類ごとの場所を決めてやるのが上手い。

蟻本のそれで座標圧縮する。テープの区間を塗りつぶしたらDFSorBFSすればよい。座標圧縮する問題ではスタックオーバーフローの危険のないBFSの方が安全。まだ座標圧縮自体が掴みきれてない。

二部グラフの最大マッチング問題なのでフローを作り、最大流量を調べる。青と赤のカードのペアで gcd > 1 が取れるものに辺が引ける。

隣接リストを用いて拡張ダイクストラをする。 やりかた知ってれば書き下すだけだった。状態として 「前の位置」「現在位置」「到着時の速度」「経過時間」 を持つとよい。priority_queue に push する条件として制限速度を与えてやることに注意。

未解決 初めに洞穴のマップを作る。エラトステネスの篩を掛けて、マップのidと対応を見ると素数洞穴がわかる。 洞穴のマップがバグりそうならdx, dyを使わずに渦を1方向ずつforループを回して作ってみれば良い。これでまずバグらない。後はDPなのだが、私は…

二部グラフの最大マッチング問題なのでフローを作り、最大流量を調べる。青と赤のカードのペアで gcd > 1 が取れるものに辺が引ける。

記事作りかけのやつと1144 Curling 2.0