Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2005年12月30日(金) C with GC

[]C with GC C with GCを含むブックマーク C with GCのブックマークコメント

C言語コピーGCを実装できるような気が突然したので、

家に帰って早速作ってみた。

C言語から使えるGCとしてはBohemGCが有名であるが、

あれはmark-and-sweepだったはずなので、

あんまりパフォーマンスはよくないと思われる。

(mark-and-sweepはストレージに比例する時間、

コピーGCは生きているデータに比例する時間がかかるゆえ)

なお、今回の実装は原理的にはジェネレーショナルにするのもたやすいので、

潜在的パフォーマンスはもっと高いと言える。


今回の実装を説明する。

int with_gc(int (*f)(),int heap_size=1024*1024);
void *gc_malloc(int size);
void force_collect();

with_gc() は後述。

gc_malloc() はメモリを確保する関数

確保したメモリは参照が外れると勝手に回収される。

force_collect() は明示的にGCを起こさせる。使う必要はない。

int main(){ return with_gc(gc_main); }

with_gcはこのように使う。

gc_mainをユーザプログラムエントリポイントとする。


<中略>


実装が完成。

テストプログラムを走らせて見る。

#include <cstdio>
using namespace std;

#include "gc.h"

int gc_main()
{
  for (;;) gc_malloc(16);
  return 0;
}

int main(){ return with_gc(gc_main); }

実行結果

$ ./a.exe
start gc ...
0 roots marked
0 alive objects, 0 bytes used ...
start gc ...
0 roots marked
0 alive objects, 0 bytes used ...
start gc ...
0 roots marked
0 alive objects, 0 bytes used ...
(以下略)

見事落ちることなく走り続ける。

ポインタをどこにも保持しないので、

当然のことながら生き残るメモリは0バイトである。

この時点でBoehmGCとの性能比較を行ったところ、

大体数十倍の性能を記録した。


次にオブジェクトを生存させてみる。

#include <cstdio>
using namespace std;

#include "gc.h"

int gc_main()
{
  int *p=(int*)gc_malloc(16);
  p[0]=0x12345678;
  printf("bef_ptr: %p\n",p);
  for (int i=0;i<1024*1024/32;i++){
    gc_malloc(16);
  }
  printf("aft_ptr: %p\n",p);
  printf("*** %X\n",p[0]);
  return 0;
}

int main(){ return with_gc(gc_main); }

丁度一回GCが起こるようにmallocの回数を調節する。

実行結果。

bef_ptr: 0x4b01b0
start gc ...
2 roots marked
1 alive objects, 32 bytes used ...
aft_ptr: 0x5b01b8
*** 12345678

今度はルートマークされ、

メモリが残っているのが分かる。

バイト数がおかしいのは、gc_mallocでは

メモリブロックにヘッダを付与しているためである。

さらに、コピーGCなので、pの値が勝手に変わっていることに注目。

メモリの内容はちゃんと最初と等しい。


次に構造体経由での参照を扱ってみる。

#include <cstdio>
using namespace std;

#include "gc.h"

struct bar{
  int *p;
};

struct foo{
  bar *b;
};

int gc_main()
{
  foo *f=(foo*)gc_malloc(sizeof(foo));
  f->b=(bar*)gc_malloc(sizeof(bar));
  f->b->p=(int*)gc_malloc(sizeof(int)*2);
  f->b->p[0]=0x12345678;
  f->b->p[1]=0x87654321;
  force_collect();
  printf("%x %x\n",f->b->p[0],f->b->p[1]);
  return 0;
}

int main(){ return with_gc(gc_main); }

実行結果

$ ./a.exe
start gc ...
4 roots marked
3 alive objects, 64 bytes used ...
12345678 87654321

4 roots markd となっているのは些細なことなので、気に留めないように。

ちゃんと3オブジェクト生き残っている。


次に循環参照を持つ場合を試す。

#include <cstdio>
using namespace std;

#include "gc.h"

struct foo;
struct bar{
  foo *f;
};

struct foo{
  int n;
  bar *b;
};

int gc_main()
{
  foo *f=(foo*)gc_malloc(sizeof(foo));
  f->b=(bar*)gc_malloc(sizeof(bar));
  f->b->f=f;
  f->n=0x12345678;
  force_collect();
  printf("%x\n",f->b->f->n);
  return 0;
}

int main(){ return with_gc(gc_main); }

実行結果

$ ./a.exe
start gc ...
3 roots marked
2 alive objects, 44 bytes used ...
12345678

当然ながらこれは回収されてはいけない。

#include <cstdio>
using namespace std;

#include "gc.h"

struct foo;
struct bar{
  foo *f;
};

struct foo{
  int n;
  bar *b;
};

void hoge()
{
  foo *f=(foo*)gc_malloc(sizeof(foo));
  f->b=(bar*)gc_malloc(sizeof(bar));
  f->b->f=f;
  f->n=0x12345678;
}

int gc_main()
{
  hoge(); // 注1
  gc_malloc(4); // 注2
  force_collect();
  return 0;
}

int main(){ return with_gc(gc_main); }

実行結果

$ ./a.exe
start gc ...
0 roots marked
0 alive objects, 0 bytes used ...

注1にて別関数にくくりだしているのや

注2でgc_mallocを読んでいるのは一時的に残ってしまうかもしれない

ポインタへを破壊するためなので、意味のある事ではない。

実行結果はこれまた当然のことながらちゃんと全部回収されている。

[]結論 結論を含むブックマーク 結論のブックマークコメント

http://fxp.hp.infoseek.co.jp/soft/cgc/gc.zip

今回作成したプログラムアップロードしておく。

とても小さいプログラムなので、解読はさほど難しくないだろうから

それについての説明は省略する。


今回、性能的にもコード的にもまずまずのものができたが、

致命的な欠点がある。これをどうにかしないととても常用はできない。

もちろん、ヒープを最初に全部確保しているとか、

ファイナライザに未対応とか、

グローバル変数やstatic変数がたどれないなど些細な(?)問題点もあるが、

運用に支障をきたすレベルの問題が他にあるのだ。

おそらくこれがあるためにBohemGCはmark-and-sweepをとっている

ような気がしないでもないが、やはりどう解消したものかと思う。


と、意味深な前振りをしつつ、次回に続く。

問題点が分かり、かつ、解決策を思いついた方はすごいです。

是非とも私にご連絡を。

[]妙に気になること 妙に気になることを含むブックマーク 妙に気になることのブックマークコメント

全然関係ないけど、今日某技術誌を読んでいたら、

紙面全体にわたって句読点(、。)がカンマとピリオド(,.)

になっていることに気が付いた。

不思議なことにぼーっと目を通しているときは全然気が付かなかったのに、

一度気づいてしまうと気になって仕方がない。

大体、Windowsの標準状態のIMEでは句読点は、。になっている。

ということは,.を用いているのはワザとそうしているのだろうか。

あるいは、Windows以外のOSの一般的なIMEがそのような設定になっているのか。

私の知る限りそんなことは無かったような気がする。

どちらにせよ、手書きで文章を書くときは当然のことながら、。を用いるのが

普通なので、,.は気になって仕方がない。

一体どういう意図なのだろうか。

t_kimatat_kimata 2005/12/31 02:46 >カンマとピリオド(,.)
僕の研究分野では卒修論や論文書くときは「,.」を使うので,研究室入ってから IME の設定変えて,常用するに至ってます.

tanakhtanakh 2005/12/31 02:55 なるほど、研究分野で取り決めがあるのですか。
参考になりました。

shiroshiro 2005/12/31 08:46 Boehm GCがmark&sweepをとっているのは単にタグ付けされていないポインタを許しているから (あるワードがオブジェクトを指しているポインタなのかたまたま同じビットパターンを持つ整数なのかわからない) なのでは。これは設計時に使い勝手および既存のCプログラムへのplug-in compatibilityを優先した意図的な選択だと思います。
もしそれが問題なのであれば、mostly copying gcなどを見てみるとよろしいのでは。

h_sakuraih_sakurai 2005/12/31 15:47 copy gcをしようとすると、スタック内のポインタを書き換えなくてはいけないが、ポインタであるかどうか怪しいので書き換えできない。だから、怪しい部分以外を移動すればいいってことですか。勉強になります。スタックの中身が怪しいポインタにならないようにする方法はないのかなぁ。関数呼び出し規約とかローカル変数の割り当ての規約を変えられればいいんでしょうけど、難しそう。

nobytnobyt 2005/12/31 18:44 組版ではJISで(,.)を使うことが推奨という話を聞いたことがあります。特に縦組の場合は (、。)よりも良いそうです。

tanakhtanakh 2006/01/02 01:38 > shiroさん
> もしそれが問題なのであれば、mostly copying gcなどを見てみるとよろしいのでは。
まさにそれが問題なのですよ。mostly copying gc はちょっと調べてみたのですが、conservative と copy を両立できるものですか。確かにこれかもしれません。見てみます。

> h_sakuraiさん
> スタックの中身が怪しいポインタにならないようにする方法はないのかなぁ。
たしかにまぁ、コンパイラに手を入れたらなんとでもなるでしょうけど、既存の処理系のライブラリとしてGCを作る場合はそうも行きませんしね。なかなか難しいところです。

tanakhtanakh 2006/01/02 01:39 > nobytさん
なるほど。JISですか。しかしなんでなんでしょうかね…

wdwd 2006/01/08 13:25 式の直後に句読点が来た場合、「、。」と「,.」のどちらが見やすいか比べてみると、おわかりいただけると思います.

トラックバック - http://d.hatena.ne.jp/tanakh/20051230

2005年12月29日(木) 年末に思う

[]歳をとった 歳をとったを含むブックマーク 歳をとったのブックマークコメント

なんだかんだでもう23歳にもなってしまった。

世間的には大抵すでに働いている歳のようで、

あそこの子はどこそこに就職したとか

なんとかさんは子供初任給でなんかしてもらったとか

いろいろとそのようなうわさを又聞きしていたりもするのだが、

普段私が身をおいている世界にはそのような雰囲気はとんと無く、

このような環境がむしろ当たり前のように感じられてしまうのは

きっと私の感覚がすっかりおかしなものになってしまっているのだろうと

そんな風に感じた。


とは言いつつも、このままの生活があと二年は続く道を選んだので、

来年以降もそのような世界に身をおくことになる。

それで、来年の身の振り方をいよいよ決定した。

東京に行くことにした。

何かの本で読んだのだが、別の世界を見ておくのも悪くないと思った。

今の自分にウンザリしているというのもある。

力が無いわけではないはずなのに、

ひたすらくだらないことに時間をつぶしてしまったり、

能力を伸ばしたいのに何もできていない、

そんな自分が嫌で嫌でたまらない。

環境の変化が私に何かをもたらしてくれるのではないのかと淡い期待を抱く。


先のことを考えるといつも暗い気持ちになる。

高校時代は自分の脳のピークが20歳ごろになると信じていたので、

それまでになにかすごいことをやりたいとずっと思っていた。

実際のところこの歳になって脳の衰えは感じる。

それは一時的に覚えることのできる事柄の数であったり、

会話中の言葉のつっかかりであったり、

新しいことを理解するスピードであったり、いろいろだ。

ではなにかすごいことがこれまでにできたか?

いいや、できていない。

できていていたかったことはそれこそいくらでもあるが、

なかなかに思ったとおりには行かない。

じゃあ、私はこれから一体なにができるのだろうか。

これまでだって大したことができていないのに。

−−− 将来の展望は果てしなく暗い。

[]思うところ 思うところを含むブックマーク 思うところのブックマークコメント

と、これが22歳終了時の心の内で。

不安と不満が私を逃がしてくれない。

去年の今頃のこのページの記録を見返してみたら、

案の定今年と大してかわらぬ心境だった。

今年の私はその点で良かったとは言えない。

もはやいえることはひとつだけ。

努力が足りない。


来年への抱負を書いておこう。

24歳になった時点では、いくらかでも心の充足が得られていますように。

そのためにはやはり頑張らねばなりますまい。

[]というわけで、 というわけで、を含むブックマーク というわけで、のブックマークコメント

ひどく陰鬱な文章になってしまいましたが、

東京の皆様、是非ともよろしくお願いしますね。

[]研究 研究を含むブックマーク 研究のブックマークコメント

最近は研究に時間を割かなければならなくなったので、

なかなかやりたいことをやり続けることができない。

なんだかGCに関してやっているようなのだが、

(自分がやってることだけどね…)

私は別にGCに興味があるわけでもなんでもない。

考えたいことはプログラミングパラダイムシフト

それをいかにうまく現実に応用するかということで、

それを実現する処理系の実装の細かいところなんか

別にどうだっていい。

…といってももはやそう言うわけにもいかんのだよなぁ


…といいますか。

ええ…このままだとこのページが愚痴日記になるので、この辺で。

たまにはこんな文章もいいじゃない。

トラックバック - http://d.hatena.ne.jp/tanakh/20051229

2005年12月19日(月) HAL研プログラミングコンテスト

[]HAL研プログラミングコンテスト HAL研プログラミングコンテストを含むブックマーク HAL研プログラミングコンテストのブックマークコメント

http://www.hallab.co.jp/progcon/2005/index.html


後でやろうやろうと思っていたら終わってました。

がががががーーーん。とてもショックです。(賞金が…)

22日までと思っていたら、22日に結果発表だったのですね。


というわけで、腹いせにコードを書きました

適当な実装ではありますが、ローカル(PM-1.2G)にて452847のスコアマークしております。

サンプルをサブミットしたらローカルの半分ぐらいのスコアたっだので、

だいたい20万は越えているのではなかろうかと。

ちゃんとシステムに投稿された方がおられましたら、

私のコードがいかほどのスコアになるか推測していただければうれしいです。


プログラムの方は、

連結判定にunion findを使っているので、

これを単にDFSにすればやや高速化されるはずですし、

BridgeListを何回も参照しているにもかかわらず

毎回メソッドを呼び出しているので、これをどこかメモリにおいておけば

これまた速くなるはずで、

グラフを辺のリストじゃなくて隣接リストにすればルート作成が速くなるはずで、

一方通行辺が二つあったときのルート修正のループ探索が馬鹿サーチなので、

工夫すれば速くなるはずで、

いろいろ面倒な高速化を全くやっていないので、

きっと全部やれば1.5〜2倍ぐらいは速くなると思われるのですが、

どんなもんですかね。


ところで、これを書いてる途中でVisual C++ 2005 Express Editionを

導入したのですが(そのためコードのインデントががたがたですが…)

なかなかいいですね、久々のビジュアルデバッガは。

でも、2003との違いはツールバーしか分からなかった。

トラックバック - http://d.hatena.ne.jp/tanakh/20051219

2005年12月09日(金) いろいろ

いろいろしわ寄せが来ております…

[]PKU1145番 PKU1145番を含むブックマーク PKU1145番のブックマークコメント

ついにPKUのセキュリティーホールが見つかるにいたったようですね。

いやはや、まさかここまで行くとは、当初は思いもよりませんでした。

しかし、どうやるんでしょうなぁ。

ソースは消えるし、ファイルも作れないし、

こっそり教えてもらえるとうれしいかもしれません…

ちなみに、私の65Byteのやつはclock()を使っていました。

getchar()より2バイト短いし、1/4ぐらいの確率で通ることが期待されましたので。

[]世界大会選出ルール 世界大会選出ルールを含むブックマーク 世界大会選出ルールのブックマークコメント

World Finals のワイルドカードが発表された模様です。

どうやら GNC も選出されたようなので、これはいよいよ負けていられませんね。

彼らは選ばれるかどうかを相当心配していたようですが、

結果をみるに結構余裕はあったみたいです。


世界大会の選出ルールは結構あいまいで、

具体的に記述してあるページも無いので、

私も、一位なら無条件で通過、二位でも大体通過、程度に思っていたのですが、

このたびもうちょっと詳しいところを知るところとなったので、

来年以降世界大会を狙う人のおそらく役に立つと考え、ここに記述しておきます。


・まず、地区ごとにスロットと言うものが割り当てられる


これは地区の勢力を元に全体の選出数から計算されます。

今年はアジア地区に割り当てられたスロットは26でした。

ちなみに、スロット数と同じだけそこから世界大会にチームが選出されます。


・次に、それが各大会に配分される


これも大会の規模に大体比例して行われます。

200チームほどが参加した東京大会は1.8スロット

1000チーム以上が参加したHangZhouはじつに6.7スロットも割り当てらていれます。

日本チームにとっての穴場と思われるマニラは参加チームが少ないために

最小の1.0スロットしか割り当てられていません。


大会の結果と割り当てスロット数を元にチームを選出する


サイトごとに上位チームから順に選出していきます。

チームにはそれぞれスロット数が割り当てられ、

その合計がサイトに割り当てられたスロット数を大体越えるまでチームが選出されます。

チームに割り当てられるスロットですが、

選出候補に挙げられた同一大学の(のべ)チーム数、の逆数、になります。

たとえば、今年の東京大学ですと、

マニラで二位のGNC、東京で四位のGNC、東京で五位のIHIののべ三チームがあるので、

東大チームに割り当てられるスロットは1チームあたり0.3です。

京大はうちのチームがのべ一回だけ候補になっているので、1.0です。

超強豪校である上海交通大学はわずか0.12スロットとなっています。


このようにスロットを決めることにより、

スロット数の合計と選出チーム数が一致するのが分かると思います。

(同一大学からは1チームしか選出されないため)

また、強豪校がひしめいているサイトは、上位のスロット占有率が下がるので、

実はかなり下位のほうまでチャンスがめぐってきます。

たとえば、今年の東京大会を例に取ると、

トップの上海交通大学が0.12スロット

二位の京都大学が1.0スロット

三位の復旦大学が0.25スロット

四位の東京大学が0.3スロット

五位の東京大学が0.3スロット

六位の国立台湾大学が0.5スロット

合計2.47スロットと言うことになっています。

実に六位まで世界大会に選出されているのです。

(ただし、上海交通大学は他サイトから選出、

復旦大学は他チームが選出、東京大学は他サイトから選出&他チームが選出、

なので、実質東京サイトから選ばれたのは京都大学国立台湾大学だけ)

これを見ると、なんかすごくいけそうな気がしてきませんか?


東京サイトは上記のように2.47スロット使われていますが、

割り当ては1.8スロットでした。

かなりオーバーしていますが、この理由は中国にあります。

アジア地区大会では中国の勢力が強くなりすぎて、

中国の三大会の割り当てスロットは13.7スロットにも至ります。

単純に考えると、中国チームが14チーム以上も選出されると言うことになるのですが

(中国大会はまずほかの国に割り込まれないし…)

それはあんまりにも多すぎると言うことで、

合計8+スロットしか使わないことにしたようです。

ということで、余ったスロットが他のすべてのサイトに0.5ほど上乗せされているのです。

中国があまりにも壮絶なつぶしあいをしてくれているおかげで、

他の国にかなりおこぼれが回ってきている、と言うような状況でしょうか。

実際に、HangZhouは6.7中3.43スロットしか使っていませんし、

中国全体でもかなりあまっています。

(それでもHangZhouは上位10チームまで選出されていますが…)


・分かること


以上からまず分かることは、強豪校はスロット占有率が低いので、

日本大会に攻め込まれても痛くも痒くもないということ。

上海交通大学が来たらむしろありがたいのです。

あと、海外派遣される場合ですが、

スロット割り当ても考慮した方がいいかもしれません。

たとえば、マニラ日本チームに人気がありますが、

スロットが1.0しかないので、注意です。

(とはいっても、今年のマニラ2.3も使っていますが…)

マニラで1,2位をとるか、HangZhouで10位をとるかなのです。

まぁ、それでもマニラの方が簡単だとは思いますが。

ちゃんとスロット使ってもらえませんし。

とりあえず、1000チームも出ている大会は必ずしも上位を

とらなければならないと言うことは無いようです。


スロット数をどれぐらい超過して取ってもらえるかですが、

これはアジアディレクターの裁量に依存していると思われます。

典型的には、開催国の最上位までは取ってもらえることが

多いように思われます。将来的にもっと中国の勢力が大きくなっても、

日本から1チームも出せなくなると言うことは

よほどのことが無い限り無いと思われます。


・そういうわけで

来年以降も出られる人は頑張ってください。

今年を見るに、日本から三チームも有り得ない話ではないような気がするので、

来年は是非とも。

[]前の練習会 前の練習会を含むブックマーク 前の練習会のブックマークコメント

もう一週間たっていますが、

当時あんまり詳しいことを言っていなかったような気がするので、

一応書いておくことに。

結果は…GNCがんばれ。


http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1198

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1199

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1200

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1201

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1202

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1203

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1204

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1205

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1206


この日は私とM氏と二人でのスタート

来るって言ってたのに…。

まず最初に、当然のごとく回答数チェック。

1200と1201が多いらしい。

1200を聞く。問題のサイズがでかすぎるために一時保留。

NCが何でわざわざ与えられているのか分からない。スキャンすりゃ分かるのに。

1201を聞く。たくさんの人が解いているはずなのに、分からない。考える。

三十分経過。

1201はいわゆる中国人だけが得意なタイプの問題だと言うことで、捨てることに。

1201をnc^n<16Mであると仮定して解くことにする。

どこにもそんなこと書いてないけど、そうじゃないと解きかた分からないし、

どっちにしろ書くの簡単だし、投げやりに書く。

予想に反して問題なく通過。

1198はM氏が両側から探索だと言っていたが、

本当に両側から探索でいけそうなので、作ることに。

盤面をintにエンコードして持ってて、毎回エンコードデコード

かける実装になったので、ちょっと重いかな、と思ったら、かなり高速に終わった。

ちなみに、8手以内と書いてあるから、両側から探索かな?

と思ったけど、普通にBFSでよかったかもしれない。

というのも、盤面が64C4通りしかないから。

次に1205。漸化式がすぐに思いついて、すぐに終わった。

整数のために、久しぶりにJavaを使う。

次に1199をやる。

問題は迷路が解けるかどうかという単純なものだが、

問題の記述に明らかな誤りがあるので困った。

問題には通路とは、少なくとも二辺に壁が面しているところ、

とあるが、それでは十字路が通路じゃなくなってしまう。

と言うわけで、自分を含む2*2マスが全て壁じゃないようなものがあれば、

通路ではない、と言う条件を適当でっち上げて書いたら通った。

次にやったのは1204。

これも問題はマトリックスの中から単語を探すと言う簡単なものだが、

問題サイズがめちゃくちゃでかい。

あと、答えが二つ以上あった場合の記述が無い。

Discussを見ている限りでは、そういうものはあるらしい。

まぁ、左上、時計回りで調べれば大丈夫だろ、と言うことで実装。

普通に実装したら遅そうなので、先頭一文字でハッシュ

見事にTLE。

仕方が無いので、先頭二文字でハッシュ

これでもTLE。

この辺でようやくK氏が来る。遅いって。

1201番を考えてもらう。

1204はもはや怪しげだが、入力に大文字英字しか来ないと仮定して

先頭三文字ハッシュで力技で高速化。

送ってみると、ぎりぎり通過。やった。

次に1206をやることに。

この日はじめてのまともなアルゴリズム問題かもしれない。

最初ダイクストラ30000回だね、間に合わないね、

と言うことで考えていたが、

M氏がよりレベルの高いものが近くにあった場合、

それ以降を探索しなくてもいいことを発見したので、

なんと30000回ダイクストラしても間に合うことが判明した。

まさに驚愕だ。

でも、ダイクストラごとにテーブルを初期化していたら

オーダがあがってしまったり、cinが遅いので、scanfに変えたりで、

いろいろはまりどころはあるので、

そんなこんなで残り10分ほどになってようやくアクセプト

もう残りは無理だし、一位も確定なので、

速攻で昼ごはんを買いに行く。

終了。

1201の解き方は結局分からず。

多分中国教科書とかに載ってるんだろうなあ、

ということでDiscussを見ると、

差分約束系統(日本語:差分制約システム)と言うものを使うらしい。

そんなの知らんて。

とりあえず検索してアルゴリズムを調べる。

分かったけど、速度がまにあわんのでは、

と思ったけど、一晩考えたら線形時間で解ける応用が分かった。

というわけで後日アクセプト

これもライブラリに追加した方がいいのかな。

残りの二問は訳を聞いていないので手付かず。


今回の問題はあいまいなのが多すぎ。

あと、問題サイズがでかいのが多すぎ。

もうちょっとしっかりした問題の方がうれしい。

OzyOzy 2005/12/09 19:02 こんちゃ。PKU1145のことでメール送りたいのですが、本体サイトにあるやつで良いですか??

OzyOzy 2005/12/09 21:10 続けてスンマセン。無事穴が塞がったので、あとで自分の日記にまとめて書いときます・・・。

dmikurubedmikurube 2005/12/10 01:14 スロット数その他については (特に Asia Regional は) 毎年かなりの変動があるので、来年も同じ計算式が適用できるかどうかはちょっとわかりません。 (少なくとも我々の年には Site ごとのスロットの概念は無かったと思われる)

それでも、
”アジアディレクター (C.J.Hwang 氏) の裁量に依存している”,
”開催国の最上位までは取ってもらえることが多い”,
”日本から三チームも有り得ない話ではない”,
あたりは変わらないと考えていいと思いますが。 :-)

個人的には、今年はアジア枠が 26 もあったことが最大の驚きです。

tanakhtanakh 2005/12/13 00:23 >Ozyさん
本体サイトのアドレスは最近見てなかったです…すみません。
私の65Byteは上のとおりで、今となっては普通ですね。
/windows/temp への書き込みは一度試してみたのですが、
そのときすでに書き込めなくなっていたので、
対処されたあとだったんでしょうか。
しかしまぁ、ご苦労様でした。
>dmikurubeさん
スロットの計算はそうですね。去年までどうだったかは分かりませんね。
今年は中国のサイト数が増えたり、いろいろ状況にも変化は出ていますね。
去年中国は2サイト650チーム程度だったのが、
今年は2500チームほどに大幅増加してますので、
アジア枠はそれでもむしろ少ないぐらいではないでしょうか。

トラックバック - http://d.hatena.ne.jp/tanakh/20051209

2005年12月03日(土) うそーん

[]北京のF 北京のFを含むブックマーク 北京のFのブックマークコメント

http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=2727

ふとアルゴリズムC++を開いてみたら、

動的計画法の項、681ページに最適二分探索木なるものがあるじゃないか!

というか、完全にまんまだし、プログラムも載ってるし、

いったい私は何をやっていたんでしょう…


これも教科書まんまだし、Gも中国教科書まんまみたいだし、

中国大会がちゃんと勉強している人ほど点が取れるというのは

よーーーーーーーく分かった。

来年以降、中国大会に乗り込もうと言う人は

くれぐれも、くれぐれも、く・れ・ぐ・れ・も。

猛勉強されることです。いや、ほんとに。

[]応募 応募を含むブックマーク 応募のブックマークコメント

単なる懸賞応募なので、読まなくて良いです。

続きを読む