読者です 読者をやめる 読者になる 読者になる

JOI 2011-2012 本選(読みにくい)

結果から書くと、100+100+100+20+0 = 320でAランク、つまり合宿に行けます。

恐らく去年合宿行った高1で300点台を取ってしまったのは"僕だけ"っぽい?のでこれはちょっと悔しいですが、何はともあれ通過です。

まあ土日にあったことを記録しておきます。

オリセン移動セッション(2/11土)

  • 朝に同級生の子と新大阪で待ち合わせして11:27発ののぞみに乗る。
  • 新幹線の中では暇だったのでjubeatPlusしたりしていた。
  • 結構早く到着、と言っても観光している暇がないくらいの時刻だったのでオリセンに。
  • 二階堂がいる。変な帽子が見える。逃亡したくなる。
  • ぺりゃうどが作っていたきゅうり帽だった。なんか手作り感満載だった。パーティー帽っぽい。

プラクティス

  • とりあえず3:00~の手続きオリンピック1位取った。去年とまったく同じ席だった。
  • 色んな人が自分の席の周りにいる。名刺とか渡す。一番前に座っているあの方はtouyouさんではないか!沖縄高専の人とか中学生勢とかにも会った。
  • jubeatしたり、持っていったペロリングッズ投げられたりしていた。
  • 1番を無駄にBITを使って解いたり、2番を無駄に分割統治的に解いたり(結局ループを複雑にしただけ)、3番を乱数を使って解こうとしてTLEしたりしていた。
  • 暇だったので同級生にSTLの使い方を教えてあげていた。
  • プラクティスが終わりかけの時にJMO本選勢が来る。tozangezanがぱなかった(詳しくはsnukeブロ
  • プラクティスが終わる。採点結果が出る。1~3番が0点。なぜだ!
  • 僕が席を外している間に意図的にTLEしたりREしたりするプログラムを送りつけられていたらしい。テロである。
  • プラクティス終了後、講義。有益だったと思う。(中並感)

懇親会セッション

  • hogloidと恐い高2・りんごさんとかがいる円卓に着席した。
  • hogloidとtozangezanに喧嘩を売られまくる。
  • 自己紹介タイムで悪質な無茶振りが発生する。内輪ノリはNG。僕は無難に自己紹介をした。しかし・・・
  • hziwaraがテロを起こした!なんかよく分かんないけどとんでもないこと言ってる!びっくりだよ!
  • その後予選満点おめでとうタイムがある。図書券もらった。2000円分でしたヤッタ。
  • さくさんも歴代女子選手の中で一番優秀で賞みたいな特別賞受賞していた。
  • hogloidとtozanが相変わらず火花を散らしていて草が生えた。とばっちりくらったりもするよね。

談話室セッション

  • 談話室に戻ったらダラダラ過ごす。基本的にtozanとjubeatか、同級生がやっていたmagic pen 2 ?とかいう物理ゲームをやったり普通に難しいゲームとかをする。
  • お風呂入る。ぬわあ疲れたもぉん。
  • 夜遅くはtozanとjubeat協力プレイをしたり、rngさんの相変わらず独特なプレイを見たりする。
  • 1時半くらいに寝る。

朝セッション(2/11日)

  • 3時半くらいにおきる。めちゃくちゃ目覚めいいと思ったのに2時間しか経ってなくて焦って寝る。
  • 今度は6時半くらいにおきる。みんなで朝飯タイムしにいく。やはりオリセン飯は朝飯が一番おいしい。
  • 9時になるまで様々なところで待機。LCAの復習(を適当に)したりする。
  • 藤原がもこうのフィギュアを持ってきていた。痛いなあ!
  • さて試験開始。

試験セッション (時間はうろおぼえ~)

00:00 試験開始
  • まず1番(JJOOII)読む。圧縮して数えるだけじゃね。書く。ろくにサンプル通さず提出。
00:06 35件正解 15件不正解
  • ファ!?とりあえずソース見る。あ、これって真ん中(O)が膨れ上がってたら駄目じゃん。対策する。投げる。
00:09 50件正解(100%)
  • 一安心。B読む。んー、Bの最初を決定すれば後は二分探索で後ろの最大の長さが決定できそうで、O(5000^2 log 5000)みたいな解法がすぐさま浮かぶがTLEしそうな気がして10分くらい悩む。とりあえずトイレに行く。
  • O2オプションあるから通るんじゃねw完全フィードバックだし。とか思って書く。
00:27 30件正解(100%)
  • えー通るの・・・。
  • C読む。読解できない悩む。トイレ行く。T=100000くらいだと思っていて悩んでいる。
  • 分からないどうしようと思っていたらTが3000だということに気づく。
  • ただのナップサックやん・・・。と思ってSを適当に処理して普通に後ろからまわすの書く。
00:47 3件正解 3件不正解
  • ファ!?って思ったらサンプル通ってないじゃん。dpを-INFで初期化していたかららしい。0で初期化する。
00:51 6件正解
  • 3番までに時間かけすぎィ!!4読む。もう試験開始前のオーバービューシート見た時からデータ構造かな~?と思ってかかっていたのでクッソ悩む。(後で冷静に考えると2.5s はO(5000^2)ですよって教えてくれているようなものだった。)
  • 50分~60分くらい考える。条件うまく整理できないな~。少し方針が固まったので5番読む。
  • あれ、5番簡単そうに見える。とりあえずダイクストラ実装してから考えよう。
  • 手計算してたら、ダイクストラしたら、それに基づいた別のコストの辺が出来上がって、あとは連結性が重要な問題になるよね~ってなって、高速にする方法ないかな~と思ったらUnionFindとかいうデータ構造の名前を思い出す。距離が遠いやつから順番に追加していけばよさそう。
  • UnionFindどうやって実装するんだっけ・・・。あれunite()関数が1行で終わったぞ?
  • 実は自分で実装したことないけどあれ実装軽かったしいけるでしょとか思って実装する。
  • とりあえず連結されたタイミングでクエリ全部見るようにする。
  • 効率が悪いし木だから経路は1つしかないからsegtree使って何か上手いことしたら速くなりそうな気がしたが、以下のような事故を発生させる。
  • 辺追加したときにもし既に連結グラフであれば追加する必要がないので追加しないことにすると、高々N-1回しか更新されないので、満点が得れる!となぜか勘違いする。この時からN=5000に頭の中で勝手にすり替わっていた。
  • サンプル合わない。なんでだろう。UFがバグっているらしい。修正する(したつもりになる)。
02:40くらい 2件正解
  • まあ"例のみ"なので・・・。ソースを吟味する(したつもりになる)
  • ここで少し休憩する。問4見る。やっぱり難しいなあ。
03:30 コーディング開始
  • とりあえずBITにsetをつっこむとかいう怪しいのを実装したが嘘解法だったらしくサンプルすら合わなかった。
03:49 かなしみ
  • もうここまできたらナイーブなアルゴリズムで点数もらおうと思ってlistで少し小手先の最適化をしたソースを提出。
03:55 5件正解 7件時間超過? (覚えてない)
  • まあこんなもんだろ。03:57くらいにset使ったら悪質なケースでもやばくならなさそうみたいなことを思いつくがパニくっていたので実装できず。
04:00 コンテスト終了
  • きたゆたが勝ち誇っている。問4は普通に解ける問題だったらしく、自分の頭の固さに絶望。問5の解法を周りに聞いている時にN=100000だったことに気づきデデドン。
  • 満点多いらしい。同率メダルが特に多いらしい。金500-銀430-銅410みたいな感じかな?

昼飯セッション

  • チャーシュー麺美味しい。peryaudoとかが死んだと言っている。問1バグるってどういうことなの・・・。(未知のエリア)

解説セッション

  • 解説聞く。qnighyドヤに集中線が入っている画像をiwiwiさんが流していた。
  • たしかにみんな説明分かりやすいが、問1満点解法思いつかなかった人にあの説明は重いのではないかhosさん...。って今年から得点分布とか見せられるようになったらしい。
  • 問2は、まあないさんぱないという感じで。
  • 問3の説明のときに、Sを適当にしか考慮せず、1つのナップザックとして解いてしまったことに気づきroxionと共にうわあああああああああってなる。胃がキリキリする。
  • 問4の解法聞いて泣く。別解の方は思いつくべきだったと思った悔しい。
  • 問5の解説のときに、自分の解法は30点だな!と確信を持つ。想定解はLCAだったぽいので、これは直前にsemiexpとLCAは出そうだよね~みたいな話をしていたのでびっくりした。ていうか自分復習までしたんだから解けろよ問5...。
  • なんと暫定結果開示まであるらしい。もらうのが恐い。
  • もらった。え、何で3番100点なの。何で5番0点なの。パニくる。

新宿に行くセッション

  • 帰りにsemiexpに問3のことについて聞いたらDPしてたら自然にうまくいくということを教え

てもらった。よく考えたらSは一瞬だから詰めちゃって連続にしてしまえば問題ないのか。

  • で、さらにUFの実装について周りに尋ねたら間違っていたことに気づく。どんびきされる。恥ずかしい。ライブラリ厨と罵られる。
  • 新宿に向かう。新宿までいもすさんがいもした。ぺりゃうどとも新宿で別れる。

ゲーセン探すセッション

  • 集団で日本道迷いオリンピックする。
  • 見つけたが人がたくさんいたので別の所を探す。迷いまくる。
  • 別の所を見つけたが諸々の事情によりfailedした。時間も押しているし食事くらいにしようというということになる。

恐い場所セッション

  • 危険な地域(歌舞伎町と呼ぶらしい)とかに迷いこみ客引きの恐さを知る。
  • 歌舞伎町から解放されしばらく歩いて結局マックで夜飯とかいうことに。twitterのプロフィール読み上げてIDを推測するゲームとかをする。
  • 食ったら解散。

帰宅セッション

帰りの新幹線はsnukeとその後輩と一緒に自由席車に乗る。後輩とても賢そうでぱなかった。理論だけ覚えてプログラミングはほとんどしないらしい変わり者であった。

  • 暇だったのでsnukeの作ったpracticeを解いたりして問1をWAしたりする。彼らは専らjubeatしていた。
  • 新幹線で問5実装しようと思ったが諦める。
  • 後輩さんとは新大阪駅で別れる。snukeとは大阪駅で別れる。
  • 疲れた。

感想

メダル欲しかったナァ・・・。