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

取り敢えず読みたい本やテキストを色々列挙。進み遅すぎるので相対的に量が多く感じてしまう。期間は決めてない。持ってるものは進捗も書いてみた。重要度 赤→青→無印 コツコツ＝緑 アルゴリズム (！)蟻本（繰り返してる） (！)チーター本（まだ少ししか） (…

サイト http://i-health.u-aizu.ac.jp/CompuGeo/2013/handouts/chapter3/Chapter3S.pdf 最小のy座標をもつ点y0を発見する。y0から偏角が小さい順に他の点を全てソートする。

next_permutation stringや他のコンテナの全ての順列を生成する。 #include <algorithm> ... string str = "ABCDEF"; do { cout << str << endl; } while(next_permutation(str.begin(), str.end())); Result: ABCDEF ABCDFE ABCEDF ABCEFD ... FEDCBA (計 6! = 720個の</algorithm>…

繰り返し二乗法のアルゴリズムを答えよ。

L_iの紐N本から同じ長さの紐をK本切り出したときの最長の長さを求めよ。

AかBからなる文字列が有る。Aを反転するとBになり、Bを反転するとAになる。 連続するKの部分列は一度に反転できる。全てAにするために必要な最小操作回数Mと、そのときの最小のKを出力せよ。