2006年09月29日

[diary] 地底大掃除

地底(端末室,休憩室)の大掃除.ビフォーアフターの写真を撮っておけばよかった.  

Posted by azounoman PermalinkComments(2)TrackBack(0)

2006年09月22日

[PKU] 2820 TN's Kingdom II

Acceptキターーーーーー.

メモリ消費量をさらに減らせるということに気がついて,GCによる遅延を減らせたのが勝因.

とはいえ,制限時間ギリギリ.多分,運が悪いと通らないレベル.  
Posted by azounoman PermalinkComments(0)TrackBack(0)

[PKU] 2820 TN's Kingdom II

きのうから色々頑張って,計算量を減らしたりメモリ消費量を減らしたりしたのだけれども,どうやらGCがボトルネックになっているらしいことがわかってきた.これ以上メモリ消費量を減らせる気がしないし,Javaで解くのはあきらめたほうがいいのかなあ.クラスを使わずにプリミティブの配列を使ってゴリゴリやればどうにかなるかもしれないけれど,そんなことをするくらいならCないしC++で書き直した方がまだましだろうし...

まあ,実はうまい解決方法方法があるのかもしれないので,今度kosakに会ったら相談してみよう.  
Posted by azounoman PermalinkComments(0)TrackBack(0)

2006年09月19日

[PKU] 2820 TN's Kingdom II

2820 TN's Kingdom II.100000頂点の Euclidian MST.

Euclidian MST では,MSTの辺は必ずDelauney三角形分割の辺になっていることを利用する.Delauney三角形分割は O(n log n) の確率的アルゴリズムが存在するので,まずDelauney三角形分割を求めてからその上でMSTを解くことでO(n log n) で解ける.

ここまで実装するのでも大変なのに,メモリが足りないという罠に.手元でテストケースを生成して実験してみたところ128MBあれば足りるのだけど,問題の要求は64MB.クラスを配列にしたり,ラッパークラスをプリミティブを使って自分で書き直したりすれば収まるのかもしれないけれど,正直やる気が起きない...

追記
メモリ足りないよと掲示板に書いたらfrkstyc氏(中の人)がメモリ容量を増やしてくださったようです.でも今度はTLE...  
Posted by azounoman PermalinkComments(0)TrackBack(0)

2006年09月18日

[diary] 牛丼祭り

今日は吉野家の牛丼祭りに参加するつもりだったのですが,雨に負けて家に篭ってしまいました.10月初頭にまたやるようなのでそれを待つということで.  
Posted by azounoman PermalinkComments(0)TrackBack(0)

2006年09月17日

[comp] CoreDuoの力その2

今度はメモリアクセスがある場合を試してみた.  続きを読む
Posted by azounoman PermalinkComments(0)TrackBack(0)

[comp] CoreDuoの力

新マシンのCPUはCoreDuo,マルチタスクに強いはずということで,次のプログラムを実行して性能を確かめてみた.  続きを読む
Posted by azounoman PermalinkComments(0)TrackBack(0)

[PKU] 2801 KnockDown

Posted by azounoman PermalinkComments(0)TrackBack(0)

2006年09月16日

[diary] 新マシンの設定作業

新マシンの設定作業.石川先生の課題のためにLinuxをインストールしようとしてみたのですが.

Fedoraをインストールしようとしたけど,グラフィックボードが対応していないらしく,かなり面倒になりそうだったので取りやめ.Debianをインストールしようとしたら,ネットワークカードのドライバが未対応らしく,やはり面倒になりそうだったのでやめ.

というわけで,課題は学科ノートの方でやろうと思います.  
Posted by azounoman PermalinkComments(0)TrackBack(0)

2006年09月15日

[diary] うわぁぁぁ

Google Code Jam Round1 参加し忘れたぁぁぁ.  
Posted by azounoman PermalinkComments(0)TrackBack(0)