season's quarterly

数学/物理/プログラミング

JOI2019/2020本選参加記

予選参加記はこちらです。
season1618.hatenablog.jp
2月8,9日に行われた日本情報オリンピック本選に出場しました。

準備

取り敢えずJOI難易度表の難易度6,7をできるだけやりました。8以上は全く手を付けていません。
また今回は名刺を作りました。PCK本選の時に何人かの方から名刺を貰ったので、自分も作ってみたいと思い、Word で作成しました。

一日目

控室

午後2:50くらいに会場であるつくば国際会議場に着きました。


控室には続々と競プロerが集まっていて、KowerKoint2010 (@KowerKoint2010) | Twitterさん、1 (@1st_vil) | Twitterさん、square1001🌸 (@square10011) | Twitterさん、zer0-star (@0x_zer0star) | Twitterさんとエンカしました。受付を忘れていたので受付に行くと、IAのファイルや「みんなのデータ構造」を貰うことができました。

プラクティス

プラクティスでは、本選環境の確認をしつつ問題を解きました。エディタはEclipse,Geany,Vimなどから選ぶことができて、僕はGeanyを選びました。自動インデントもシンタックスハイライトもやってくれるので、この点に関してはPCKのTeraPadよりだいぶ使いやすかったです。それから二回質問をしました。二回目のトラブルでは、helloを出力するはずなのになぜか4が出力されるという問題に直面しました。どうやらコンパイルできてなかったらしい。早々に全完した
えくと (@ecto0310) | Twitterさんも横にいてアドバイスを貰いましたが、ずっと同じ出力で変わらなかったので、チューターの人を呼びました。結局コンパイルではなくビルドをしろということでした。ちなみにビルドが何かを知っていますか？僕は知りません（ア）。3完しかできなかったのでかなりやばいと思いました。


ちなみにプラクティスの問題は毎年同じらしいです。

講演

オープンソースソフトウェアのすすめというタイトルで、濱野賢一朗
Kenichiro HAMANO (@hamaken) | Twitterさんの講演を聞きました。高校の時は数オリに出ていて、19歳で本を書いたらしい。


本人からリプを貰えて嬉しかった。

夕食会

最初に予選全完者の表彰がありました。それが終わると今度は一人ひとり前に立って自己紹介をしました。自分の時が一番盛り上がらなかった気がします（泣）。


競プロerの自己紹介、Twitterネタが飛び出していてとても面白かった。「ACそのまさかだよ」の本人の方がいたり、「シンガポールに行きたいかーー」と叫んでいたりと熱狂していた。

宿

JOIの宿は筑波研修センターというところでした。部屋にトイレや風呂はなく、机とベッドだけが置いてあり、正に独房という感じでした。PCKの時に比べると大分快適さに欠けていました。あとトイレの便器が冷たかった（小便器はなかった）し、トイレには石鹸がなかったので水道で手を洗いました。


一階でWi-Fiが使えたので参加記を途中まで書きました。あとisooooo_19 (@19_iso) | Twitterさんに会いました。久しぶりにJOI難易度表を開いてみたら表示できたので、難易度7を一問解きました。この日の夜はコンテストがなくて残念でした。部屋に戻るとお腹が空いたので、ホテルを出て直ぐのコンビニでおにぎりとたまごサンドとチョコレートを買いました。

二日目

誕生日

コンビニに入ったタイミングで携帯を見ると、丁度0時になりました。実は僕の誕生日でした。


皆さんありがとうございます。おかかのおにぎりを食べてからは速やかに就寝しました。

朝食

朝は目覚ましをかけておいて良かったです。一日目は風呂に入っておらず、大浴場は朝は開いてなかったので、シャワー室を利用しました。その後朝食を食べました。これもPCKより簡素でした。


朝食後にAndroidのアップデートをしたのですが、
というわけでスマホが使えなくなりました。

本選競技

本選は9:00-13:00の4時間かけて行われました。結局小さなマスコットを用意することはありませんでした。

1-長いだけのネクタイ(Just Long Neckties)

ソートして順番に取っていけば良い。貪欲を確信するのに少し時間がかかった。微妙に誤読していて、max(A_i - B_j , 0)の和の最小値だと思っていた。ただ実装の方針はほぼ同じだったので助かった。B_iとペアになりうるのがA_i,A_{i+1}だけなので、pairの配列でそれぞれfirstとsecondに突っ込む。後は配列を二つに分けて（一方が空になることもある）、左側からfirst、右側からsecondを取っていったときの最大値を順番に求めればいい。一瞬セグ木がよぎったが、冷静になると左右から累積maxを取れば良いと分かった。

2-JJOOII2

予めJ,O,Iの累積個数をカウントしておき、それぞれの個数がK個になるような区間を求めていけばO(N)で解ける。それぞれ一時間ずつかけて、この時点で二時間経過していた。

3-スタンプラリー3(Collecting Stamps 3)

最初に考えたのは嘘解法でした。次に考えたのも嘘解法でした（）WAが各課題に散らばっていたので、部分点は取れませんでした。

暫定得点・解説

200点でした。競技中も思っていたのですが、3完が無限人いました。競技中は3で部分点を取っても結果には影響しないだろうと思っていたため、最初から満点解法を目指していたのですが、解説を聞いたら、もっと小課題を気にかければ良かったなあと思いました。あと後半は問題文を読んでいなかったので、少しでも目を通しておけば良かったです。5の解説がよく喋る人でとても面白かった。
ちなみに夜にABCがあったのですが、今回は出ませんでした。

結果と感想

後日ボーダーが発表され、Aランクは301点以上でした。僕は一応Bランクでした。本選の点数には多少悔いが残りましたが、交流もできたし、ファイルや本も貰えたし、色々な話を聞けたので有意義でした。