はじめてのにき

_ wait

なんか長いジョブ始めてしまってから、 これ終わったらアレを実行して欲しいよなーとか思うことがある… とかいう話をしていて自己解決した。

% sleep 10
^Z
zsh: suspended  sleep 10
% bg
[1]  + continued  sleep 10
% wait && ls
[1]  + done       sleep 10

sleep 10 が長いジョブで ls が終わったら始めたいコマンド。

(00:09)

_ shinh.org

どうでもいいけどいまさらながら一応ふっかつ。

kwskk.shinh.org がまだみたいだけどまぁどうでもいい…

あとは mirc とかを daemontools の管理下に置くのと、 twitter と…

それとゴルフ場は lighttpd 捨てたいな… virtual host の設定が簡単なのはいいので、 ゴルフ場だけを apache の管理下に移動すればいいのかな。 apache の fcgi ってどうなるんかね…

(02:24)

_ kernel VM advent calendar

http://atnd.org/events/10701

http://twitter.com/yuyarin/status/26664147030642688 を見て、いくつか見てみた。 読んでないのが多いので、かなり面白かったから暇な時にもっと読みたい。

(03:13)

_ dc の話

dc のなるべく短いコードを書きたいという話をして そのへんの研究とかってどういうの調べればいいんですかねえ、 と聞いていたら x87 とかと提案してもらった。

なるほどたしかに…

(23:02)

_ starcraft2

しばらく 1v1 はしんどいので suspend してたのだけど 今日はたくさんやってみた。

ここ2ヶ月くらいの進捗は…

• 3v3 dia になった
• 4v4 dia になった(今日)
• 1v1 と 2v2 は platinum のまま
• キャンペーン hard でクリアした。ミッション系の achievement は全取得。
• チャレンジ全部 gold にした。
• チーム戦のドサクサに紛れてどうでもいい achievement をそこはかとなく取ったり。 zerglot とか…

gateway unit + colo という展開は まぁ結構勝てたし相手の行動次第では それも相変わらずいいんだけど、 あまりにもそいう P が多すぎるのか どうも勝率が悪くなってきた気がする。

というわけで色々試したりしている…

• vZ は即 VR で 2 台程度出すと強い。 7roach とかもギリギリかえる。 VR 出し続けるんじゃなくて、すぐに colo に移行するといい感じに hydra さんを焼ける
• vP は悩ましかったのだけど、 gas core 遅らせて zealot*4+stalker*2 で殴りつつ expo という BO が teamliquid に書いてあったのでやってみた。良いかも。
• vT はよくわからん。うまい人は VR 出してたりするからマネしてみたりしたけど全く役にたたない… DT が面白いと思うんだけど、 MM rush に普通に殺されたりするからなあ…

(03:35)

_ そうそんなことより

w3m ってリリースとかするんだな…って感じだった。 とりあえずがんばって全パッチを CVS head からのアレにするか。

ていうか開発してるんだったら無難な patch は入れてもらいたいなー ということで頑張るか。 というか cookie の時間とかはオプションつけてくださってるんだなー

(04:18)

_ anti virus

無料体験な mcaffee の期限が切れるようだった。 どうせ SC2 しかやってないマシンだし セキュリチーソフトとか無くてもいいのかなぁ とか思ったけど、

• 一応ブラウザくらいはリプレイダウンロードする時とかに使う
• ゲーム系のサイトとかっていつも見てるようなサイトに比べて diversity デカいから危険度高めかも
• windows マシンはともかくこのネットワークの packet とか見られるとうざいかも。 twitter のパスワードくらいは平文で飛んでそう

とかいうこと考えて、まぁ無料のを入れておくことにした。 いい時代になったなぁ。

でまぁ無料のも色々あるみたいなんだけど、 Panda Cloud Antivirus というのにしてみた。 理由は

• 名前が面白い
• 名前に Cloud とか入ってて興味をそそる
• MS essential とかは芸が無い感じ
• 2ch によると速いらしい

あたり。 下の方は割と後付けなんで、名前重要だなぁとか思った。

SC2 の邪魔したりしなければいいなぁ。

(23:04)

_ pric

http://d.hatena.ne.jp/colun/20110110

おおおすごいなー

全く覚えてないので適当に思い出すために手元のコードについてメモ。

• pric.c: なんかすごい遅い
• pric_ref.c: なんか強烈に遅い
• primechecker.c: -m32 だと 11.9 秒くらい、これが submit してあるバージョンぽい気がする
• pric2.c: -m32 だと 10.5 秒くらい。 oxy さんのやつを実装してみようと思ったけどアルゴリズムを忘れてしまった上に自力で再構成できなくてよくわからん実験を色々していたみたいだ
• perfect: 答えはこのファイルに書いてある
• pric_check.rb: なんか check してくれるらしいが謎
• pric_gen.rb: コードを短くしてくれるらしい
• pric_test.c: 今さっき書いたいいかげんなアルゴリズムでどの程度漏れるかをチェックするために書いた

(13:43)

_ 49.7 7.5

経験上50切るとやばいんですよ…

TODO ちゃんと喰う

(08:48)

_ facebook hacker cup

気がついたら終わっていた。 topcoder とか codejam 系だったのかな。 じゃあまあいいんだけど。

飯をたくさん喰うという努力をしたら 速攻で気持ち悪くなって元々体調悪いのとコンボでキツくなった。 なんとかならんかという貧弱さ。

dc は手で書くのがかったるいので 適当な言語から生成したいと思う。 bc がそれであるのは知ってるんだけど、 そうじゃなくて短い dc コードを出力させたいのだよね当然

なるべくレジスタ使わないで stack を… とかいう話はいくらでも研究とかありそうだが

(19:05)

_ 1位とりかえされた

のでまぁその人は64問全部解いてるし 60問縛りとか意味わからんことやめて残りも解くことに。 適当に codegolf.com のコードの流用とかしつつ romancal 解いたので 1位取り戻した。 久々に見るとローマ数字とか死んでいいな。 だいたいゴルフ的には 8 は IIX であるべきだろうに。

残り3問だけど、

• factorad はこの手の飽き飽き…解いてしまえばたぶん成績良いんだけどね…
• sqdiff はめんどくさそうというかどうせ数値誤差とかうんぬんで WA 喰らって試行錯誤するんだろうなぁ…
• spiral は oblongular number spirals の悪夢を思い起こす絵が描いてあったのでやりたくない

など、3つとも回避したい雰囲気なのであるがー

まぁ spiral はあきらかに簡単そうではあるよね…

(00:58)

_ 1位

http://www.spoj.pl/SHORTEN/ranks/

になった。 60問しか解いてないまんまなので伸びしろもそれなりにあるだろうっていうか そこらじゅう伸びしろだらけだろうと思う。

どうでもいいけどこの動画をずっと聞いている。 なんでこいうの好きなのか。

http://www.nicovideo.jp/watch/sm12628181

(17:01)

_ SIZECON

狂ったルールのおかげでたのしい。 ここまで来るとはなぁ。

http://www.spoj.pl/SHORTEN/ranks/SIZECON/

あと 2B は今の方針だと全然ダメ。 どうすればいいかなー

解いた問題数 60 のまんまでトップになりたいとか思いはじめてきた。

(11:39)

_ SHORTEN

http://www.typemiss.net/2011/01/spoj-shorten.html

で書かれてる通りテストケースかなり適当なんだよなぁ。

http://twitter.com/kinaba/status/23392088473214977

まず kinaba さんが書いておられる通り出力フォーマットが適当ってのがあって、 それはまぁたぶん scanf で読んでるっぽい感じの問題が多くて、 そっちはまぁ

https://www.spoj.pl/SHORTEN/embed/rules/

あたりにも書いてあるからまぁいいとして。

問題はテストケース見せてないからなんとかなってるだけーって程度に テストケースが十分に無いやつがあるってことだよな。 例えば SUDCHECK なんてテストケースの数の bit 数があれば 解答埋め込めちゃうから、 こんなもんすごい数のテストケースが無いと ルール無用なゴルフとしては全く成立してないのだよな。

https://www.spoj.pl/SHORTEN/problems/SUDCHECK/

そんなこんなでまぁ色々やる気は起きない要因はあるんだけど、 なんか BF 使う問題とかあったりとかはちょっと面白いかとおもう。

てかこのへんの制約は ICPC のためにほげほげな SPOJ だから、って理由がほとんどだよなぁ。 あくまでゴルフ場ではないっつーか。

あと与えられてる sample inputs が異様に簡単なものばかり、ってのも ICPC 的な感じなんだろうなぁ。 問題の spec から難しいテストケースを考える、 ってのは重要な能力ではあるものの、 なんかどうもプログラムコンテストとしては余計なものに感じちゃったりもする。

まあなんだかんだ言いつつ3位。

一番面白かった問題(というか解いてないが)は INTER で ruby だと gets するだけで TLE 。 https://www.spoj.pl/SHORTEN/problems/INTER/

(08:20)

_ latency

http://d.hatena.ne.jp/kawango/20110107

ニコニコではこのへんが問題になるのなーという感じもあるけど、 本当にそうなんか? グーグルだとなんか色々調べたけど、 ある程度高速な回線だと結局クライアントのオーバヘッドがデカいぞ、 って話で HTML を頑張って色々やったらユーザの幸せがだいぶ増えたとかいう話があって (たしかこの本…だっけ http://www.amazon.com/High-Performance-Web-Sites-Essential/dp/0596529309)、 ニコニコも体感だと動画とか以前に、最初にページ出るまでが結構長いんだけどな。

(10:09)

_ ruby 1.9 と gets

いくらなんでも gets だけでタイムアウトしてるのはおかしいが、 測ってみると ruby1.9 の gets はマジで遅い。 これは M17N の影響だったりするんだろうか。

> time sh -c "ruby -e 'puts %q(c)*10000000' | ruby -e 'gets'"
sh -c "ruby -e 'puts %q(c)*10000000' | ruby -e 'gets'"  0.19s user 0.17s system 91% cpu 0.396 total
> time sh -c "ruby -e 'puts %q(c)*10000000' | ruby1.9 -e 'gets'"
sh -c "ruby -e 'puts %q(c)*10000000' | ruby1.9 -e 'gets'"  1.32s user 0.19s system 94% cpu 1.591 total
> time sh -c "ruby -e 'puts %q(c)*10000000' | perl -e '<>'"
sh -c "ruby -e 'puts %q(c)*10000000' | perl -e '<>'"  0.21s user 0.12s system 93% cpu 0.360 total

(10:46)

_ golf場 TODO

なんか IRC で話してていくつか

• 8 characters hello world 。8種類しか文字使えない hello を書けというもの。 goruby が h だけでいいのはいいかげんあれだし HELLO, WORLD! とかにしてやればいいか
• edit distance がコードサイズになってないといけない cyclic な quine 。これ書けるかまだわからんからとりあえず解いてから…
• rejudge button 。 random base な解答はちょっとアレなので、 deadline つきの新しい問題は rejudge button をつけて、それを押すと解答の check をもう一度走らせる、ってもの。 time limit が厳しい解答がかわいそうになるかもなので、 rejudge の時は time limit を増やすと良い

(05:25)

_ random seed

rejudge よりは rand seed 全部殺すのが良いんじゃないかと言われた。 そんなの無理だと思ってたんだけど、結構できそうな気もしてきた

• rm /dev/urandom; cp /dev/zero /dev/urandom
• personality(personality(0xffffffff) | ADDR_NO_RANDOMIZE) で address randomization は全滅するらしい
• rdtsc は cr4.tsd というのをセットすると殺せるらしい
• gettimeofday はフック
• getrusage あたりが rdtsc 内部的に使ってたりしないだろうか

最後の3つは色々互いに絡んでる恐れがあるかな。

話としては、

• 基本的にはコードが長くならなきゃいいわけなんで、言語実装が勝手に呼ぶ srand の seed として使われてるシステムコールさえ殺せば問題なし
• rdtsc 殺しても kernel 内部で使っててかつそのシステムコールを言語処理系が seed として使ってると終わるので、やはり使ってる system call を全部殺すのが良さげ
• 今時の gettimeofday は vsyscall とかそのへんの仕組みで userland で rdtsc 呼んでるとか無いだろうか→となると libc hook を復活させないといけなくてだるい気もする
• 言語実装が勝手に自力で rdtsc を呼んでる…ってことはさすがに無いだろうか

あとは他に乱数源ってあったかなあ… 普通に考えると /dev/urandom とか time 系だけだと思うけど…

(11:09)