ACM/ICPC Asia Regional Contest Tokyo Site
いい加減書かないと忘れそうです。
11/7 (Sat)
時間に余裕を持ってオリセンに到着。ちょっと早すぎたかなと思ったけど、kamingさんに会ったのを皮切りに、すぐにいろんな人に会えました。コーチ&id:iakasTとも合流してしばらくしゃべってたけど、-Wの残る2人がバスの遅延ですぐに来られないようだったので、Watch.dだけ先にResistrationを済ませました。
Practice Session
最初の2問は去年と同じで、3問目は初めて見る問題。言うまでもなく全部通りました。
ふと前のチームを見てみると@suzutreeadd1*1の姿が。
このあたりでちょっと頭が痛くなってきたので、机に突っ伏して寝ました。
懇親会
体調が優れないから仕方ないよね!と自分に言い訳しながら椅子に座ってまったりえらい人の話を聞いてたら、本当に気分が悪くなってきました。おとなしく目をつぶったままkamingさんとhyonさんによる俺の嫁合戦を聞いていました。あとautoすげー。
うちのチームの紹介の頃にはそれなりにしゃべれるようになっていたので、予定通りチーム紹介では私が「イケメン&リア充の新人が入りました!」と言ってきました。さらにアドリブで「@romanchuもリア充でゆるふわ系草食少年(自称)だよ!」と言おうと思ったけど、@romanchuにとっととスライドを切り替えられてしまったので諦めました。策士め。
懇親会中はほとんど動けなかったけど、広島大学の人とは少し話せました。つーささんというハンドルネームに聞き覚えがあったので、昔あそこのチャットルームにいませんでした?などと話してきました。世間って狭いね。
いよいよ座ってるのもしんどくなってきたので、早めに部屋に戻って休むことにしました。布団の上でぐったりしていたら、そのうちHITORI#の人たちと-Wの人たちがぷよぷよをやっているような声が談話室から聞こえてきて、参加したいーと思いながらも起き上がれませんでした。
後で知ったのですが、他の談話室ではフォロー合戦が行われていたそう。そっちも参加したかったなー。
この日は体調が悪いところを多くの人に気遣っていただきました。チームメイトとコーチと-Wの人たち、そしてきうぃさんに感謝。
11/8 (Sun)
起きたら随分体が軽くなっていました。けどまだ本調子ではなくて、朝食のバイキングは消化によさそうなものだけを選んだ挙句ほとんど残しました。
こんなコンディションでコンテストやるのは初めてだ。かつてない不安を抱えたままコンテスト開始。
コンテスト開始
.emacs と .xmodmap を書いた。設定をメモった紙を部屋に忘れてきてしまって焦ったけど、どうにかなった。
Bを読んでいたが、@romanchuにAを考えてくれと頼まれて読んでみた。
Problem A
- なにこれ全然分からん。
- 合宿最終日のトラウマが濃厚に蘇る。
- 難問かと思ったけど解いてるチーム結構多いな。
- まずは入力列をソートして。
- 対角線に置きながら適当に辻褄を合わせていけばいいのでは。
- サンプルの最後だけ通らない。
- ソートしちゃだめですよね、と@romanchu。そうですね。
- じゃあ next_permutation しますか。
- こんなてきとー解法でいいのかと思ったけどYes。O(n! * n)の愉快なアルゴリズムが生まれました。
- Aが通った時点でおよそ1時間弱経過。ひどく時間を浪費してますが、去年と同じ展開なので、むしろ今年も行けると思いました。
Problem B
- Aと同時進行で@romanchuが実装。
- 問題文の解釈ミスがあったりして手間取ったけど完成した・・・が、なぜか通らない。
- 他に解けそうな問題があったので、そちらに移行。
Problem D
- 線形分離問題。はいはい凸包凸包。
- 持ち込んだ参考書に書いてあったけど、開くまでもなく覚えてた。
- パーセプトロンも頭をよぎったけど、書ける気がしなかったので無視。
- 手元の凸包ライブラリも多角形の交差判定も、面積が0の場合を試したことがなかったので慎重に考えてみた。
- 多角形の交差判定はまずOK。
- 凸包は・・・分からん。書いてから考えよう。
- 書いた。入力が1点の時だけ凸包が求まっていないので例外処理を付け加えた。
- sample親切っぽいし大丈夫だろうと思ってsubmit。
- スナック菓子をつまんで戻ってきたら、風船が増えてた。
Problem B
- 簡単なはずなのにまだ通らない。WAしたりTLEしたりREしたりと謎な挙動を繰り返す。
- 業を煮やしてCを書いてもらうことにした。
Problem C
- @romanchuがあっさり通した。「Bより簡単」だそうです。
Problem H
- 解けそうだったので挑戦してみた。
- sample合わない。問題の解釈が間違ってる?
- 「全員を判別するのに必要な質問の最小数」を出すのか、それとも「『任意の一人を判別するのに必要な質問の最少数』の最大」を出すのか?
- いろいろ試してたらsample出てきた。submit。WA。
- 「全ての質問を一度にするのではなく、質問の答えを聞いてから次の質問を出来る」という点を勘違いしていたことには最後まで気付きませんでした。
Problem G
- リア充な後輩が頑張って書いてたけど、式が間違ってたらしい。
Problem J
- @romanchuがごりごり書いて通した。「Bより簡単」だそうです。
Problem B
- なんだかんだで残り10分ぐらいになったので、改めてBに挑戦。今度は私が書いてみた。
- 去年もこんな展開だったなぁ、と思いながら頑張ってstringのsplitとjoinを実装。
- が、惜しくも間に合わずタイムアップ。4問でした。
長くなってしまったので、今日はここまでにしておきます。
*1:高校時代のクラスメート