D問題に限っていえば、Warshall-Froydのアルゴリズム の方が楽なのでそっちに移行するかなぁ。今、D問題でいう冷凍ポイントの数だけDijkstra法ぶんまわしちゃっているので、実行に時間がかかりすぎる。

バグ発見！昨日の実装メモの中で これを細分化して、自分のプログラム上でどう表現されているか確認すると 訪れていない点の集合=先行点を納める配列中で、内容がNILの点 既に木に加わっている点の集合=先行点を納める配列中で、内容がNILではない点 交差す…

D問題のサンプル入力は通ったので、模擬戦で配布された入力を入れてチェックしてみた。何か、ところどころあってるけど、大体答えと違うぞおおおお！！Dijkstraがしっかりできてないぽいんだよな。ちょっと休憩した後に、自分でグラフ作って試してみるよ！

昨日の夜あたりから、bloglinesから登録サイト1つにつき200ものRSSフィードが送信され続けている。そして、つい先ほどbloglinesのサービスが一時停止していることを確認した。サーバー管理者は今必死になって復旧にあたっているのだろう。

もうひとパンチで解ける！・・・気がする。 先行点グラフの作り方がまずいんかなー。

先行点の管理の仕方がおかしいんだ。次に使用する先行点は、以下の論理で求まるはず。 まだ訪れていない点の集合のうち、既に木に加わっている点と隣接している辺を見つけ出す。そして、その中から重みが最小の辺を見つける。言い換えると、交差する辺のうち…

予期せぬハプニングが起こり、予定とは12時間遅れで学習進行中。[読んだ] 貪欲法 最小スパニング木 Kruskalのアルゴリズム Primのアルゴリズム 単一視点最短経路問題の基本概念-緩和(relaxation) 幅優先探索-先行点(predecessor)の考え方 Dijkstraのアルゴリ…

コ ー デ ィ ン グ 解 禁と思ったけど、動的計画法の学習にもう少し時間がかかりそう。一応今日学んだことをメモ。 グラフの表現方法 動的計画法の解法、手順(というより思考フローって言った方がいいかもしれない) 明日までに参考書を読んで、模擬問題のD問…

↑の日記見て気づいたけど、カタカナ表記だとイアフォンとアイフォンって似てる・・・というより、紛らわしいな。

テスト勉強をするのに、Mindmap Managerというちょっとうさんくさいソフトの体験版を使ってみる。マインドマップの是非はおいておいて、講義ノートをとる代わりにこれで整理するのはなかなかいい気がする。印刷もラクラクできる。

これ、今使ってるイアフォンなんですけど、なんかおかしいですよね。

すっかり忘れていたけど、今週テストとレポートがあるんだよね。優先順位的にはこっちの方が上なので、こちらをやらないと。まぁ、モチベーションは俄然ACM/ICPCに偏っているけどね！！

とりあえず模擬じゃー！ Super Princess Time!! 模擬の問題すべてにお姫様が出てきたよ！ ある貧乏な国のおてんばで勇敢なお姫様は，ある日部屋の壁を壊してお城を抜け出し，競馬などのギャンブルが行われている賭博場に入っていった．ところが，ギャンブル…

10問目に全く未知の問題がやってきた。 Unit Fraction Partition 1時間考えた時点で解法が全然思いつかなかったので、解説を見ながら問題を解いてみることに。1/2+1/6と1/6+1/2を区別するやり方なら思いつくのだが、この問題では区別しないんだよね。どうや…

Dirichlet's Theorem on Arithmetic Progressions(☆2) time 1:30 昨日に引き続きここの☆2問題を解く。実は、本日の1問目は2006年度のICPCで解いたことがある。せっかくなので昔と同じアルゴリズムで解き、PKUの正誤判定システムに提出。すると「Time Exceede…

Red and Black(☆2) time 1:30 Polygonal Line Search(☆2) time 3:00 ここの☆2問題が2問解けた。ただ、時間がかかりすぎである。3時間とかかかっているようでは、1問で競技が終了してしまう。しかも、時間がかかっている最大の原因が問題の意図の勘違いだった…

勘を取り戻すために、とりあえずここの☆1つの問題を4問解いた。昨日、一昨日で2問を解いたので、合計6問解いたことになる。 Hanafuda Shuffle Ohgas' Fortun Keitai Message When Can We Meet? Get Many Persimmon Trees Numeral System 1問目解いたときの凡…

ACM/ICPCに、後輩二人を引っさげて(笑)出場することになった。テスト勉強の合間をぬって練習DA！

はてなの人気エントリに、非常に便利なツールである「MyRemix」というサービスの紹介文があったので使ってみた。このツールはRSS非対応のサイトを無理やりRSS化するツールである。似たようなツールは何種類かあるが、mixiなどのログインの必要なシステムに対…

引越しをしてからというもの、「家にサーバがいいな！」と思う機会が非常に増えている。とりわけネットワーク関連の実験をする際には、自宅にサーバがあれば非常に便利である(認証に関する動作確認をしたりするときなど)。こういった実験に使用するPCには、C…

ICPC対策(まだ出るか不明だが)に、PKUをはじめてみた。ただ、頭から片っ端から問題解いてる時間もないので、こちらのサイトを参考に問題を選定し、解いている。しかし、この手のプログラム(=アルゴリズムの実装)はいつも行っているプログラム(=コンピュータ…

きたきたーー！！愛用ブラウザの最新版、Opera9.5がリリースされた模様。果たしてgmailの日本語の二重入力のバグ(「こんにちは！」と入力すると「こんにちは！こんにちは！」と入力されてしまう)は取り除かれているだろうか。期待。追記。 せっかくなので使…

VM(=仮想マシン)を沢山立ち上げて負荷実験中・・・。ウインドウが立ち上がりまくってる様子はかなりシュール。

「iPhone」について(by Softbank)ソフトバンクから発売かぁ。当方はdocomoなので買えないかな。そのうち、代わりにipod touchを買うことになりそうだが。docomoが漏れたのは、やはりimodeに固執したせいだろうか。もしそうだとしたら、凄くもったいない気が…

RubyVMのソケットはsocket/sys.hで定義されているsocket関数のラッパ。具体的には、./ext/socket/socket.cの中で以下の様に定義されている: #ifdef USE_WINSOCK2 #define open_socket(a, t, p) open_ifs_socket(a, t, p) #else #define open_socket(a, t, p)…

友達と本屋さんを歩いていたら、凄く面白そうな本を見つけた。H8マイコンによるネットワーク・プログラミング ~C言語ではじめる組み込みマイコン入門作者: 青木直史出版社/メーカー: 技術評論社発売日: 2008/06/05メディア: 大型本購入: 2人 クリック: 34回…