競技プログラミング in Scala
素人なのであてにはならないと思いますが。
UTPC2009
今年も参加しました。
http://www.utpc.jp/2009/
結果は7問で6位という残念なものでしたが、
面白い問題がいろいろあって楽しかったです。
一つの問題にはまって他の問題が全然考えられなかったのが悔やまれます。
当日の様子を書いておきます。
A
問題がなかなか開かず焦る。
とりあえず普通に簡単な問題だったので通す。
B
DP書いて通す。
12問中の2問目にしてはめんどい。
C
2人の人が9枚ずつ与えられたカードを一枚ずつ出して云々という問題。
はまった。
1ターンずつ適当にカードを出し合ってビットDPすれば
(2^9)^2*9^2ぐらいで終わるんで、それで組んだら手元で0.5秒ぐらいかかるプログラムができた。
サブミットするとTLE。どうしたもんかなあと。
E
そうこうしているうちに早くもEが解かれてしまったので、Eに変更。
ぱっと見分からなかったけど、こんなに早く解かれるなら簡単に違いないという推理から、
これはどうやっても同じなのではないかと予想。
足し算したときの数の総和は変わらないか10減るか。
なので、最後に残る一桁の数は常に同じ。
10減る回数も決まっているので、結局どうやっても足し算できる回数は同じ。
適当に書いて適当に通す。
D
Dが解かれたので、Dに進む。
完全に後手後手になってきてて、もう今日は駄目かなあと思い始める。
呼んでみると実装するだけで仕様も単純だったので
さっくり通す。
G
今度はGが解かれたのでGに進む。
よく分からなかったけど、TLEにならない程度回してWAもらったら後で考える、
ぐらいで実装を始める。
普通にAccept。
あとで考えてみたが、ループするケースは二者間往復しかなさそうなので、
これは正しかった。
C
ほかに解かれてる問題がなかったので、Cに戻ってくる。
もう一回一から考え直したら、これは片方出す順固定して
もう片方の出す順番を全部試すだけじゃないかとやっとのことで気づく。
こんなことに気付かなかったなんて、悔しくて仕方がなかった。
でも、一回解法を思いついてしまうと、それに思考が縛られてしまうのは
仕方がないのかもしれないと思った。
そうして、ようやくAccept。
F
とりあえず残り全部読むかと思って、読む。
Fがよさそうな感じがしたので、実装開始。
サイズが50000なのが心配だったが、O(nm)のアルゴリズムで、
bitsetでやれば間に合うんじゃないかと思った。
完成したプログラムはワーストケースで手元で0.7秒ぐらいだった。
Cのこともあったので、どうかなと思って出したが、
結果はTLEであった。
I
二時間ぐらいFの高速化をやってて、さすがにまずいんじゃないかと思ったので、
スコアを見てみるとIがそこそこ解かれてるっぽかったので、解くことにした。
猫が自力で行けるときは0。
そうでないときは人が最小限の扉を開けてやらなければならない。
人が最初にいる場所と、猫が動ける範囲と、ゴールに猫が自力でたどり着ける範囲の三つを
結ぶ最小ルートがどうなるのかなあと考えていたら、最適な時はY字になるはずと気付いて、
それが分かれば後はすぐであった。
と思ったが、自力で行けるケースを書くのを忘れていて1回WAを食らった。
直してサブミットしようとしたらコードを二重に張ってCEをもらった。
三度目の正直でAC。
F
残り時間1時間ぐらいで、Fをやるかほかにあと1問別のやつを解くかで、
結局Fに戻ってきた。
Hはサイズが大きすぎて厳しそうだったのでパス。
Jは幾何よく分からないのでパス。
Kは式をちょっと書いてみたら泥沼になったのでパス。
Lはなんかうまい方法があると思って少し考えたけど全然わからなかったのでパス。
一時オブジェクトを作らないようにしたり、
bitsetをやめてsetにして枝刈りを入れてみたり、
setをunordered_setに変えてみたりいろいろやったがダメ。
unordered_setに変えたときは結構テストケースが進んでいるような手ごたえがあったが
結局は通らず。
状態数が爆発するケースがあることが分かったので、それを突っ込んでみたら
setでは全然終わらず。
諦めてbitsetを高速化するが、手元で0.4秒ぐらいまでになったものの
相変わらずTLE。
もうだめだ、というところで終了。
終了後
twitterでF後ろからやったら一瞬と聞いて相当ショックを受ける。
なんで気付かなかったんだ。
ちょっとこれはしばらく立ち直れないかもしれない。
よくよくも考えると、こんなにたくさんの人が
こんなに激しいチューニングをして通しているわけがないじゃないか…。
勝負としてはC手間取った時点でスコアでは勝てなくなってたので、
もうこれは駄目だった。仕方がない。
参加しての感想としては、
参加者の層が、ちょっと前では考えられないほど
厚くなってきてるなあと思った。
7問以上正解者が16人もいるのがそれを示している。
現役が強いなあという印象も受けた。
今年の世界大会は期待していいかな。
最後に主催者の皆様、このような楽しげなイベントをありがとうございました。
また来年があればよろしくお願いします。
ACM-ICPC Japan Domestic Warm Up I
http://rose.u-aizu.ac.jp/onlinejudge/jdwu1.html
http://rose.u-aizu.ac.jp/onlinejudge/ContestRankList.jsp?contestID=JDWU2009I
ICPC参加資格も何もないですけど、
リハビリのために参加しました。
最近老化がひどいので…。
A
二つの列を一緒に読み込んで、0加えて、ソートして、前からスキャン、
が一番速そうだったので、そう実装。
B
3次元配列をつくって、適当に塗っていく実装。
C
シンプルなparser。
10分でかけるparserとかいう記事を公開しながら
20分かかったのは、多分老化のせい。
D
20個しか科目がないので、2^20とおりビットパターン生成して
条件満たしてるかチェックで書いたのだけど、
1秒の制限時間を5秒ぐらいかかっている。
ちょいちょい変えながら再送するが、
ちっとも速くならない。
TLE厳しすぎる…。
問題チェンジ
F
Eが図形でFが探索なのを見て、
どっちかというとFかなと思う。
起点からのばして探索する方針で適当に書いて
サブミットしたが、全然間に合わない。
これもTLEを量産した揚句、いったん中断。
D
Dに戻る。
枝刈りが入らないのがいけないんじゃないかなあ、というので、
DFSで書き直し。
普通にとおる。うーむ…。
F
こっちも枝刈りを入れることにする。
正のマスについて、
負のマスにつなぐことができないのがあれば、だめ。
負のマスについて、隣接する正のマスの合計が超えてなければだめ。
この二つを入れたら、0.01秒とかで通った。
探索は博打みたいなところがあるなあ…。
E
のこり25分ぐらいだったけど、一応書いた。
座標と向きをノードとしてダイクストラみたいなので、
一応書き終わってサブミットしたが、
バグバグだった模様。
SSD向け全文検索エンジン
ここのところ私がメインでかかわっていた検索エンジンがリリースされました。
こちらに紹介があります。
http://d.hatena.ne.jp/kzk/20090310
デモとしてWikipediaの全言語(記事が少ない言語は省かれているかも)の全記事
約50GBからの検索を1台のPCで行うものが公開されています。
よかったら試してみてください。
http://demo.sedue.org/wikipediasearch/
下の方でいくつか数字を出していますが、
正確に計ったわけではないので参考程度にしてもらえると。
ちょこっと宣伝
ボックスに単語を入れると検索できます。
一応、全言語で検索するデモなので、各言語での検索は
全言語の検索結果をフィルタしているだけです。
単語の列を入れると、AND検索できます。
検索速度のデモなので、結果のキャッシュなどはしていません。
すべてのクエリについて厳密な結果を出そうと試みまず。
100万docs程度までは1秒程度で求まるようです。
安全のため時間かかりすぎてやばいと思ったクエリ(数秒程度？)は結果を出しません。
AND検索ではそういう単語は無視します。すみません。
この辺は実際の運用時は概算などをするようになるはずです。
""で囲うと、空白を含む文字列を検索できます。""の中に"を書くには\でエスケープすればOKです。
アスキーアートなども検索できるはずです。
スコアリングは急きょ作ったものなのでかなり適当です。
この辺はチューニング次第だと思いますので、あまり気にしないでください。
形態素解析の結果など使えばもっと良くなるとは思います。
スループットは、C2Qの普通のマシンで、
平均的なクエリなら1スレッド50qpsぐらいは出ているんじゃないかなと思います。
構築速度のチューニングの方に時間をかけたおかげで検索にはなかなか手が回らず、
前日に10倍速くなるとそんな状況だったのでまだ速くなるとは思います。
インデックスの構築は、HDD*4のRAID0のマシン上でこのデータが25-6時間ほどでした。
HDD1台だとこの倍以上時間かかるかと思います。
どうでもいい話
CGIがC++で書かれている。
ちょっとキモかっこいいXHTML生成DSL in C++。
私の言語屋としての遊び心…ではなくてRPCとの兼ね合いですが。
これもいつか紹介したいなあ。
ちょこっと雑談
技術的に面白い側面はいろいろあると思うのですが、
詳しい話はセミナーでお話しすることになりそうです。
ここではちょっとそれ以外のことを書こうと思います。
なんでSSD向けの検索を作ることになったかはよく覚えていないのですが、
きっかけはX300というSSDを搭載したノートパソコンをもらったことだと思います。
プログラマなんてものはこんなもの物珍しげなデバイスを手に入れたら、
それをどう使い倒そうかとかしか考えないわけで。
ある日社内のミーティングで検索エンジンの話を聞いているときに
これSSDに載せればいいんじゃねえか？とかそういう軽い気持ちで
手元のマシンで実験を始めました。
適当に実験をして思った以上に性能が出そうだったので
これはいけるんじゃないかなということになりました。
-
-
-
- -
-
-
私にとってなんだか残念なのは、
Web上のレビューしかり、雑誌しかり、ブログしかり、
SSDを幾分か速いHDDとしか見ていないのが多いことです。
シーケンシャルリード200MB/sec超のベンチを取って、
Windowsの起動が数十秒速くなって満足、ではちょと勿体なさすぎると思うのです。
見るべきところは、どう考えてもランダムリードです。
ここをみるとHDDとは全く違うデバイスだということがわかります。
そうすると、HDDではできなかったことができるようになるかもしれない。
HDDではとても実用にならなかったアルゴリズムが、
SSDによって現実的になるかもしれない。
そういう可能性に思いを馳せることができるのです。
こんなデバイスが数万で買えるとか、
その価値に気付かなければあまりにも勿体ないです。
まあしかし、私は別にSSD関係者の回し者でも何でもないので、
結局のところあまりどうでもいいのですが。
しかし、SSDを応用できる分野はまだまだあると思いますので、
そういうのを考えてみるのも面白いかと思います。
従来メモリに置かなければできなかったことがSSDでできるとか、
同じことをするなら圧倒的にシンプルな方法でOKになるとか……。
SSDはLarrabeeやGPUと同じくとても面白いものだと私は思います。
C++のstreamの転送速度を調べる
はじめに
C++のstreamはとても良くできていて、これを用いたライブラリを作りたいのだけど、
本当に(主にパフォーマンス的な理由で)大丈夫なのとかそういう話。
初めにお断りしておきますが、以下の内容はすべてlinux+gcc4.3での話です。
streamは遅い
ふつうにistreamからget()して、ostreamにputしてるとめちゃくちゃ遅い。
C言語のgetchar, putcharより10進数で1.5桁ぐらい遅いよ。
istream::readとかででかいブロック読めば大丈夫なのだけど、
細かい単位で読みたいことの方が多いよね。
そういうわけで、そういう場合にも速く転送することが可能なのかどうか調べてみる。
テストプログラム
istreamの内容をostreamに転送するプログラムを6通り書いた。
その１：普通のプログラム
オーソドックスなプログラム。
void copy1(ostream &os, istream &is) { for (char c; is.get(c); os<<c); }
その２：ブロックごとに読み書き
今回の趣旨には会わないが速度の比較のため。
(readに失敗したときの処理があってるのか不明)
void copy2(ostream &os, istream &is) { for (;;){ char buf[1024]; if (!is.read(buf, 1024)) break; os.write(buf, 1024); } copy1(os, is); }
その３：istream_iteratorを使う
is>>c; os<
void copy3(ostream &os, istream &is) { istream_iterator<char> p(is), end; ostream_iterator<char> q(os); copy(p, end, q); }
その４：istreambuf_iteratorを使う
Effective STLおすすめの方法。
空白は大丈夫です。
void copy4(ostream &os, istream &is) { istreambuf_iterator<char> p(is), end; ostreambuf_iterator<char> q(os); copy(p, end, q); }
その５：ostreamにstreambufを突っ込む
あんまり柔軟性は無いけど、
この書き方がどのぐらいの速度なのか調べたかった。
void copy5(ostream &os, istream &is)
{
os<<is.rdbuf();
}
その６：istreamからstreambufに突っ込む
5と同じぐらいの速度になるという予測。
void copy6(ostream &os, istream &is)
{
is>>os.rdbuf();
}
六つ書いたけど、期待しているのはその4だけです。
これがどういうケースで速くなるのかを調べたい。
テスト
これらのルーチンを、ifstream&ofstreamと、cin&cout、
さらにそれぞれ組み合わせと、出力が/dev/nullになってるときの
計8通りでテスト。単位は秒。
ファイルサイズは1GB、
メモリ8GBのマシンにおいて実行。
ファイルの内容はキャッシュにすべて乗った状況ですので、
純粋にCPUの計算量のみが考慮されるものと考えてください。
file -> file(普通のファイル)
| copy1 | 40.310 |
| copy2 | 3.340 |
| copy3 | 46.900 |
| copy4 | 1.550 |
| copy5 | 1.870 |
| copy6 | 1.620 |
file -> file(/dev/null)
| copy1 | 38.610 |
| copy2 | 0.880 |
| copy3 | 45.390 |
| copy4 | 0.400 |
| copy5 | 0.390 |
| copy6 | 0.410 |
file -> stdout(普通のファイルにリダイレクト)
| copy1 | 47.780 |
| copy2 | 3.560 |
| copy3 | 53.990 |
| copy4 | 3.330 |
| copy5 | 4.120 |
| copy6 | 4.060 |
file -> stdout(/dev/nullにリダイレクト)
| copy1 | 56.530 |
| copy2 | 0.700 |
| copy3 | 66.580 |
| copy4 | 0.510 |
| copy5 | 0.500 |
| copy6 | 0.510 |
stdin -> file
| copy1 | 69.860 |
| copy2 | 3.390 |
| copy3 | 98.580 |
| copy4 | 34.540 |
| copy5 | 35.980 |
| copy6 | 34.880 |
stdin -> /dev/null
| copy1 | 68.000 |
| copy2 | 0.890 |
| copy3 | 100.190 |
| copy4 | 34.180 |
| copy5 | 34.040 |
| copy6 | 34.410 |
stdin -> stdout(file)
| copy1 | とても長い(>300) |
| copy2 | 6.080 |
| copy3 | とても長い |
| copy4 | 46.160 |
| copy5 | 70.310 |
| copy6 | 70.530 |
stdin -> stdout(/dev/null)
| copy1 | とても長い |
| copy2 | 0.870 |
| copy3 | とても長い |
| copy4 | 44.830 |
| copy5 | 44.210 |
| copy6 | 44.350 |
とても長いと書いてあるところは、長すぎたので切りました。
5分で切りましたが、多分10分たってもおわらないのじゃないかな。
考察
出力が/dev/nullか普通のファイルかは当然/dev/nullの方が速いものの、
systemの時間が変わるだけです。
計測する必要なかったな。
ブロック転送(copy2)はすべてにおいて速い。
これも当然ながら。
copy1はすべてにおいて遅い。
当然ながらほとんどuser時間。
copy4,5,6は同じぐらいの速度になった。
streambuf_iteratorだけ遅いという結果にならなくてよかった。
標準入力->標準出力で4と5,6で結果がだいぶ違う原因は不明。
以下はstreambuf_iteratorについて。
入力がifstreamの時はおしなべて速い。
入力がcinの時は速くない。
でも、cin.get()とかで読み取るよりは速い。
出力はofstreamでcoutでも大差はなし。
どちらかというとofstreamを使う方が速いようだ。
cin, coutが実際どういう型になっているのかは知らないが、
まあ実装がfstreamと違うのだろう。
速度の違いの理由を調べるため、straceをかけてみた。
基本的にどれもある程度まとまってread/writeされていた。
(サイズは8KB,4KB,1KB様々だが)
つまり、速度の違いはそれ以外のオーバーヘッドである。
しかし、許容しがたいほど遅かったもの(cin->coutのcopy1,3)は
出力が一文字ずつwriteされていた。
これは如何に。
ファイルからcoutへ転送する場合も再度調べたが、
たしかにバッファリングされている。
同じcoutへの出力なのになぜ？
調べるために、次の2つのコードを書いた。
for (char c; cin.get(c); ) cout<<c;
ifstream ifs("tmp"); for (char c; ifs.get(c); ) cout<<c;
すると、やはり、なんと、前者はバッファリングされず、後者はされるのだ。
私はこの結果を見たとき、
もうC++とはとっととおさらばしてユートピアへ行こう！
と思わずにはいられなかった。
今回この原因を探るのはめんどいのでしないが、
まあそのうち調べたいと思う。というか、調べないといかんのだろうなあ。
read/writeとの比較
FD間で直接転送した場合と比べてどうなのかを調べてみた。
void fdcopy(int to, int from) { char buf[1024*8]; for (int n; (n=read(from, buf, sizeof(buf)))>0; ){ char *p=buf, *q=p+n; while(p<q){ ssize_t ret=write(to, p, q-p); assert(ret>0); p+=ret; } } }
結果
| file-> file | 1.280 |
| file -> /dev/null | 0.390 |
| stdin -> stdout | 2.430 |
| stdin -> stdout(/dev/null) | 0.380 |
streambuf_iteratorのオーバーヘッドは1割程度と言うことになる。
(バッファのサイズが違ったりするので、単純には言えないけども)
Google Coe Jam 2008 World Finals
http://code.google.com/intl/ja/codejam/
というわけで、参加してきました。
結果はSmall全部+A-Largeの36点で43位でした。
英語が全く駄目な私にとっては、無事に帰ってこれただけで奇跡なので、
あまり高望みはしますまい…。
サンフランシスコへ
コンテスト本番以外には特にイベントのないCode Jamは
着いた次の日の午前9時から開始というキツキツのスケジュールなのですが、
それは疲れそうだったので、私は一日前から現地入りしました。
終わった後もせっかくサンフランシスコまで行って何もせずにというのは
あんまりなので、一日延長しました。
これがなぜかフライトに有利に働いて、
ほかの人たちは韓国経由とかでやってきているところを
悠々と成田→サンフランシスコ直通便で行けました。
ひとりで海外に行くのは初めてだったのでとても不安でした。
なにしろ言葉が通じませんのでね。
しかし、必要に迫られて頑張ってみると、
案外コミュニケーションはとれるもので、
通じなくてどうしようもない、という状況はおきませんでした。
だいぶ経験値が上昇したような気がします。
クレジットカードを持ってなかったのも不安だったのですが、
これもまあ何とかなりました。
15万円持って行った現金は2万円+200ドルぐらいしか残りませんでしたので、
ちょっと何かがあったらまずかったかもしれません。
最初に日本で5万円両替して、500ドル弱手に入れたのですが、
ホテルに着いたらデポジットが700ドルいるとか言われて、
向こうでドルを調達したら5万円が400ドル弱にしかならなくて、悶絶しました。
私の1万円はどこかに消し飛んだようです。
Googleへ
さて、そんなわけで、レジストレーションとか立食パーティーみたいなのがあった翌日、
ついに本番となりました。
朝6時半ホテル出発の9時コンテストスタートです。
いきなり厳しいですが、日本時間じゃないので何とかなりました。
サンフランシスコの街を抜け、海岸沿いのハイウェイをひたすら南下していくと
どんどん何もないところへと向い、
その何もないところの一角にGoogleはありました。
日本でいうと京阪奈みたいなもんなのかなあと思いました。
Google本社は、思っていたのとだいぶ違って、
きっとそれは日本Googleを先に見ていたからだと思うのですが、
広い敷地にあまり高くない建物がたくさん、
さしずめ大学のキャンパスのようでありました。
食べるところがたくさんあって、そこらじゅうに自由に飲める飲み物が設置されていて、
中庭にはビーチバレーのコートから恐竜の化石までありました。
中国か韓国かのテレビがインタビューに来ていました。
軽い気持ちでOKOKとか言ってしまったのですが、
何聞いてきているか全然わからないし、
終始しどろもどろの対応で(自分が)ひどかったです。
解答は日本語でOKですよ、みたいなことを言われたので
日本語で答えておきましたが、たぶんインタビュアーの人は
日本語わかっていないので、かみ合わない妙な雰囲気のまま終了。
コンテストの会場は、食堂の横のスペースに設営されていました。
たぶん食べるところだったのだと思うのですが、
そんなオープンなスペースでコンテストは始まりました。
本番
持参した日本語キーボードを取り付けたり、GNOMEの設定を変えたり、
テンプレートがコンパイルできることを確認したりして、開始を待ちました。
画面上にカウントダウンが表示され、それが00:00になってコンテストは開始しました。
開始しても会場はシーンと静まり返っており、
あれ、これ始ってるの？と不安になりましたが、
Enter Contestというボタンを押すと問題が見れたので、
確かに始まっているのだということがわかりました。
(問題はこちらを参照)
http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxjRzBQM
この日の戦略はノープランでした。
何をどうしたらいいか何も考えていなかったので、
とりあえずAを読みました。
読み始めたは良いものの、全然頭に入ってこなくて参りました。
英語が難しいのか、問題のシチュエーションが現実離れしているから
想像で補うことができないからか、とても解読に苦労して、
やはり例によって例の如く、読んでる最中にサブミットがされ始めました。
10分ぐらい経ってようやくなんとかサンプルと整合性のとれる理解が得られたのですが、
それでもそれが合っているか分からなかったので、
英語の理解を確信にするためにとりあえずSmallのコードを書くことにしました。
コードは数分で書き終わり、サブミットするとCorrectと帰ってきました。
よかった。理解は間違っていなかった。
Largeの解法は思いつかなかったので解く問題をBに変更。
Bも英文が全然頭に入ってこなくて参りました。
これもシチュエーションが不自然すぎるのです。
なんでネズミ捕りなのか意味がわかりません。
これもとりあえずSmallを通すことにしました。
普通に深さ優先的にペイントして終了。
Largeは計算しないとできなさそうだなあと思ったのでCに移動。
Cは問題文が素直で助かりました。
しかしLargeの解法はまるで思いつかなかったので
とりあえず全部調べろといわんばかりのSmallを適当に通しておきました。
この辺までは一問15分ペース
残るDとEは問題が長かったので、とりあえずDから手をつけることに。
Smallの解法も自明ではないように思えましたが、
少し考えると、とりあえずもう一つの森まで最短でつないで、
あとはBFSのminをとればいいように思えたのでそれを実装。
しかしなんだかコードがすっきりしなくて、
どろどろしてきたので、一旦Eにスイッチ。
Eもシチュエーションが現実離れしすぎていましたが、
解読は普通に終わり、Smallもできそうな感じでした。
15*2^15*2^15*15ぐらいの計算量だったので、不安もありましたが
ぐずぐずもしていられないので、実装を始めました。
コード自体はすぐにできて、サブミットしようとしたのですが、
テストケースを持ってきて、実行させてみると全然間に合わない。
これはやばいかなと思いつつ、
スコアの計算などをビットごとにループを回していた部分をテーブル引きに変えたり、
生成したパターンが有効かどうかのチェックもテーブル引きに変えたりして
15の係数を一つはずして、サンプルを再入力。
4スレッド並列で3分ぐらいで終わったので、行けるだろう、として、
二つ目のサンプルをサブミット、やっとこさSmallが通る。
かなり時間を消耗してしまいました。
この辺で残り一時間ぐらい。圧倒的に時間が足りない。
一通り問題を見たのでDに戻る。
ちょっとコードから離れていたので、見通しが良くなっていました。
するするとかけて、するすると終了。
さっき書いてた時に感じたのはなんだったんだろう。
そして残り45分ぐらい。
Smallが終わって、次に何をやるか。
といってももう全然時間がないので絞らないといけません。
解けそうなのはDのLarge。
Smallと同じような感じで、
森を全部spanning treeつないで、それから全森からのBFSのminでいいような気がしたのですが、
なんだかすっきり書く方法が思いつかず、17点というのも
本当にこんなんでいいのかという気にさせてくれて、やっぱりDはやめることに。
あと解けそうなのはAのLargeとBのLargeか。
AのLargeはかなりたくさんの人が解いていたので、
これはやるべきだろう、ということでAを考え始めました。
ジュースをミックスする割合を決めて、それぞれについてチェックしたらO(n^3)か。
これはn=5000には大きすぎる。
割合を決めるのにO(n^2)、あとは決めた時のカウントがO(1)かO(logn)かで
できれば何とかなると考えて、10分ほどうんうん唸っていると、
fenwick treeでできるんじゃないか、と気付きました。
分かったらコードはすぐできて、
しかし、万が一にもTLEなどあってはならないので、
手元で大きなケースを作って、
それでも十分に速いことを確認して石橋をたたきながらLargeをサブミット。
残りは15分。もう解法が今すぐに思いついても一問も
書けないような気はしていたのですが、
一番可能性の高そうなBを考えることにしました。
しかし考えてもいい案は浮かばず。
Dがもしかしたらすっきりいけるのかなあと思いながらDを眺めてみるも
これまた何も浮かばず。
そんなこんなで、ぐだぐだしながらのこり15分を過ごしました。
終わる時もあっさりと終了。カウントダウンぐらいあってもよかったんじゃなかろうか。
終了後
終わって一息ついていると、
今度は日本の記者がインタビューしたいらしいとのことなので、
これまたOKOKとか言っているとなんか別室に連れていかれて
そこでインタビューを受けました。
今度は日本人の方だったので、普通に日本語で対応しました。
外国でこう日本語で受け答えするのって、
ちょっと不思議な感じで、ちょっと楽しかったです。
それからご飯を食べたり日本人で集まって解法を言い合ったりしました。
Googleの食堂はいろいろな国の料理があって、なかなかおいしかったです。
もちろん和食もあって、と言っても寿司なのですが、
せっかくなのでカリフォルニアの寿司も食べておくことにしました。
目の前でサーモンの握りを握ってくれて結構本格的なんだなあと思いました。
味も結構ちゃんとしていました。
どうでもいいのですが、サンフランシスコの街には妙に寿司屋が多くて、
3分歩けば必ず見つかるほどです。
日本でもそんなにないと思うのですが、
よほどサンフランシスカンは寿司が好きなのでしょうか。
食事が終って、社内を見学したり、
Googleの技術の説明を聞いたりしました。
イベントがほとんどないのに、そういうアピールはするのだなあと思いました。
途中、Java Puzzlersという本？からJavaの奇妙なふるまいについての話がありました。
私はJavaはほとんど使わないので、そんな重箱の隅仕様は知っているはずもなく、
なんでアメリカくんだりまで行ってJavaの勉強をせねばならないのかなあ、と思いました。
それからホテルに帰って、表彰式でした。
アルコールが出たので、もらいに行くとIDを要求されました。
まあなんというか、年齢制限のあるものなのだからこれぐらいは当然なのか。
ディナーを食べながら下のほうから順に発表されていきます。
とりあえず97位から51位までには入っていなくてホッとしました。
AのLargeは通っていたっぽい。
しかし、次の50位から26位で名前が出て来て
やっぱりこんなもんだよなあという感じでした。
1位はACRush氏でした。鉄板過ぎる。
89点というのが自分との如何ともし難い距離を感じさせます。
久しぶりに、悔しいという気持ちが沸いてきました。
勝ちたい、終わってからだというのに。
来年ももしあればもっと自分を鍛えて行きたいと思いました。
観光
一日延泊して観光してきました。
サンフランシスコは坂が多い街です。
東京もたいがい凸凹した街だなあと思っていたのですが、
比べ物にならないぐらい坂だらけです。
とりあえず、坂道をがんばって歩いて日本人街に行ってみました。
あまりにも日本でびっくり。
紀伊国屋書店があったのですが、内装から置いてある本までどうみても日本で、
とても奇妙な感覚でした。
それから中華街とかを見て、
名物のケーブルカーに乗りフィッシャーマンズワーフに向かいました。
ガイドブックに載ってた、フィッシャーマンズワーフで自転車を借りて、
ゴールデンゲートブリッジを自転車で渡る、というやつをやりました。
英語がなかなか聞き取れなくて、自転車を借りるのに一苦労。
クレジットカード持ってないの？持ってないけどそこを何とか貸してくれ。
なんか店長みたいな人に話が行って、クレジットカードは？ないです。
うーん。とか何とか話が進んで、
じゃあ300ドル出せという話になったのですが、
所持金が260ドルしかない。
ちょっとそんなにお金ないです、と言ったら、
じゃあそれでいいやということになって、全財産と引き換えに
自転車を借りることができました。
閉店までに帰ってこなかったらお金返せない、
しかも閉店まで2時間ぐらいしかないという状況だったのですが、
がんばって自転車を漕いで、何とか間に合いました。
アメリカまで来てこんな危ない橋を渡る必要もなかったかなあ。
自転車は結構良くて、なんとGPS付きでした。
橋は結構高い所にかかってて、そこまで登るのにも一苦労。
橋からの眺めはなかなか爽快でした。
良い経験ができました。
そのあとはフィッシャーマンズワーフで買い物とかして、
書店でマンガとか買ってみたりして、ホテルに帰りました。
