各単語をエッジと考えたグラフでオイラーパスが存在するかどうか調べる．SPOJの方にも同じ問題がある．こっちはRubyで通したかったのだけど，入力を読んで初めの文字と終わりの文字をとってくるだけでTLEになるので保留．

実家の方で大きめの地震があったと今日知った，大丈夫なのだろうか．昨日，電話したときには特に何も言ってなかったけど．

卒業しました．

Time Limit 5000ms のところを14218msで通すのはどうかと思う.片側探索では通らないので両側からbfsする.ただし，終了状態のほうが状態数が多い(2^8)ので前側からの探索手数を多めに取って，後ろ側は10手ぐらいしか読まない.

3/16〜3/22まで実家に帰ります．

http://download.wikimedia.org/からダウンロードできるXMLファイルからタイトルとそのタイトルからのリンク(今のところリンクというよりも［［*］］の部分)を取り出すプログラム追記： とりあえず，タイトルにauto_incrementなIDをつけてDBに吐いたのだが，…

書類とかを提出してきた．と思ったら電話がかかってきて，写真が貼ってないといわれるので証明写真を急遽撮ってくる．昼休みだったから入学手続き会場は休みになってたのだが事務室にいったらちゃんと名前とかを把握されてたので提出．

まだ，中身には目を通してないのだが，ここで提案されているアルゴリズムによりO(n(log^2 n))でコミュニティの抽出がおこなえる(nはノード数，グラフは疎)大規模なネットワークな例としてはamazon.comの商品409,687点と，"この商品を買っている人は〜"のリン…

今日，大規模ネットワークの可視化という話の中で，ノードの相互作用のO(n^2)の計算を，これを利用することにより100倍近い速度で実行できるということを聞いた．値段はアカデミック版で\120万，Pen4×100と同じぐらいの値段だから妥当と言えば妥当だと思う．

半日，プログラムを書いててeclipseのコードアシストが利いてなかったことに今気づいた．そりゃ補助なしに$bean->getLongLongName()とか打ってれば作業速度が遅れるのも当然か．

最近，色々とばたばたしてたので久々に更新．といっても明日の夜に卒業式まで実家に帰るのでしばらく更新は止まります．

16日のセッション2だけ聞きに行く予定．

前半部分については，そこそこに興味深かったのだけど，後半のSPBに対しての有効性を示すところでランダムに作ったグラフに対して行ってるのがかなり微妙だと思う．完全にランダムに作った二部グラフに対して，そのコミュニティ抽出とかしてもあんまり意味が…

Finding and evaluating comunity structure in networksと同じ著者の論文(共著ではない)，前の論文では最短路betweenessの大きいものを切ってくというやり方で，1つのグラフを複数の部分グラフに分けてくという方法をとったが，今回はそのときのクラスタの…

グラフが与えられた時に以下のような方法でクラスタリングする． 全ての枝に対してbetweennessを計算する 最も大きなbetweennessをもつ枝を除去する betwennessを再計算する. 2にもどる betweennessの定義は色々あり，一つの定義としては任意の2点間の最短路…

昨日は来年度からの指導教官とミーティングをしてきた．まだ，あまり方向性は固まっていないのだが，今はネットワークのコミュニティの抽出に興味があるという話をした．そうすると，とりあえず論文が8本ぐらい送られてきたので，3月はそこらへんに目を通し…

今日は大学の前期の合格発表で，図書館の近くが結構こんでた．僕は合格発表は郵便で受け取ったので，どうやるか知らなかったんだけど，合格者番号の掲示自体は11:00ぐらいから初めて，そこの前に入れるのが13:00ぐらいになるわけですね．

生協にいったらアルゴリズムイントロダクションの第二版がでてた． http://www.kindaikagaku.co.jp/bookdata/ISBN978-4-7649-0334-0.htm http://www.kindaikagaku.co.jp/bookdata/ISBN978-4-7649-0335-7.htm 身近に先週第一版を買った人がいるのだが，もう少…

三井住友銀行で入学金を支払ってきた．手数料をけちって，東京三菱で金を下ろしたので，ポケットに30万いれて自転車で走ってるとわりかし緊張した．

http://acm.pku.edu.cn/JudgeOnline/problem?id=2631 与えられた重みつきグラフの直径を求めよという問題．ただし，グラフは木である．なお，グラフの直径とはグラフの任意の点対の最短距離の中の最も大きい値のことをいう．Floyd-Warshallとかは計算量的に…

Javaの言語仕様によると，配列に対してのインデックスはint値しか許されておらず，longをインデックス値とするとコンパイル時のエラーとなる．ただ，これって32bit環境の時は当然の制約だけど，OSの環境が64bitになって，PCにメモリを8GBとか乗せることも可…

研究もそろそろ概要だけはつかんでおかないとと思い，Newmanのサーベイを夕食後，サイゼリヤで流し読みをしていた．卒論のときもそうだったけど，こういう最近になって発展してきた分野って，色々な人が様々な方向から意見を言っているから，自分の立ち位置…

今日解いた問題はhttp://acm.pku.edu.cn/JudgeOnline/problem?id=24111×2のタイルでh×w(h,w再帰的に全探索する．ただし，h段目を埋めるときにはh-1段目のタイルの形状だけに注目すればよいので，メモ化が効いてmax(h,w)*(2^min(h,w))ぐらいの記憶領域を用い…

卒論正式版まだ出してないのにもう単位が来てる．計85単位で1単位あまして卒業確定．そろそろ，来年度からの研究室に挨拶に行かないと．