Osmium_1008のブログ

コンテストの感想とかどうでもいいこととか書き溜めるかもしれません

JOI'20本選参加記

はじめに

初投稿ですね。Osmium_1008というものです 予選で5問目をググったら予選通過し(おい)、本選に行ってきたので記録を残します。

1日目

午前

同じく本選に行った同期とJAXAの見学に行った。

秋葉原駅に9時に集合とのことだったのでのんびりと行ったら中央線快速が想定以上に早かったので15分ほど早くついてしまった。 他の同期も早くついたので、予定より早い電車に乗ることができた。

TXには初めて乗ったが、とても早くまた長距離移動にしては料金が安かったので驚いていた。 あと日立初期IGBTっぽかったので何故か興奮してた。

45分ほどで筑波に到着、予定より早くついたのもあって目的地まで色々喋りったり自転車レーンを歩いた同期に対して「やーいお前自転車ー」という謎の煽りをするなどをしながらゆったり歩いていた。 道中看板等を見つけたら写真を取ってツイートしていたが、一人だけ時間をずらしてツイートすることではぐれた人を演じようとしていた。

やはり予定より大分早くついたので、申し込んだツアーでは回らない場所を見ていたりした。人工衛星や探査機などの実物大模型がおいてあったが、想像していたよりも大きく、またソーラーパネルをたたんでいた状態でそれだということに気付き驚いていた。

このあともいろいろなことをしていたが詳しくはdefineの記事に書いてあるので書かないことにする。(丸投げ) JOI2020本選参加記 - #define int long long

午後

食事が終わったら本選の会場に向かった。早くついたかと思ったがhir35さんなどもその頃ついた様だったので安心した。やはりhairaさんは可愛い。

hairaさんが受付に手間取っているのを目撃して可愛いと思いながら待機部屋に向かった。待機部屋ではいろいろな人と現実で交流しようとしたが、結局twitterしかやっていなかった。

practiceでは、Eclipseが最初大量のエラーを吐いていたので使用を諦め、Emacsを使ってある程度問題を解いた。ある程度解いたところでEclipseを動かせるように設定方法を探し、Eclipseを使えるようになったことを確認したので使い始めた。

何故か1問だけバグを取り除けずにいたので交流に行った。美少女という言葉が聞こえた際に何も考えずに割と大きな声で反復してしまい注意されてしまった。このときはあったことある人としか話さなかったと思う。

バグを取り除くためにanmichiを膝の上に乗せながらコーナーケースを一緒に考えてもらった。結論から言うとnとmを間違えて書いていたというものだったので申し訳ない。

practiceが終わると夕食会に入った。偏食の極みみたいなことをしながら割といろいろな人と交流できたと思う。途中あった自己紹介では予選5問目が難易度6であると思っていることなどを話したが、過激と思われたらしい。

夕食会の後にはOSSについての話を聞いた。OSSには興味があったし、OSSの定義や有名企業のOSSへの姿勢など割と面白い話を聞くことができたので良かったと思う。

宿に向かった。ベッドメイキングをした後は周りと少し会話を交わして23時頃には寝た。割と寝心地はよく、よく眠ることができた。

2日目

朝

5時半頃に起床した。いろいろな人が起き始めていたが誰も部屋の外に出ていなかったので結果として一人で部屋の外を歩き回る怪しい人になってしまっていた。

朝食は鮭の切り身や納豆、味噌汁とご飯といった内容だった。普段朝はパンをたべていてしかも少食なので食べきれるか心配だったが食べきることができた。納豆をご飯に乗せて食べる派の人を観測することができた。hairaさんが納豆をご飯と食べようとしてご飯を先に食べきってしまっていた。かわいい。

バスで会場に移動した。起き遅れた人がいたようで発車が遅れた。

会場につくまでに

  • UnionFind
  • dijkstra法
  • 抽象化遅延SegmentTree

の3つを空で実装することができた。

基本緊張しない性格なので驚くほど気楽にいた。

競技

魔剤を持って入っていたが、蓋無し飲料がだめなことを知らずにいたので一気飲みをせざるを得なくなった。来年はボトル缶のものを持っていこうかと思う。

競技が開始したら前日に覚えたEclipseの設定をして問題をとき始めた

1問目

最初にとき始めたが何故かWAが出たので先に2問目を説いてから解いた。

前からと後ろからで累積MAXを取ることはわかり、実装したがWAが出た、コーナーケースを見つけてデバッグをしていたところまた変数名間違いをしていたようだ。変数名を直したところACをすることができた。

2問目

1問目で詰まったので見に来た。かんたんに解けそうであったので実装を始めた。

すべての文字について文字の数の累積和を持っておき、あるところを始点と見たときにJがK個以上現れるのはどこか、そこのあとにOがKこ...とやっていってその範囲の長さの最小を取った。尺取り法で解けたそうだが先に思いついていて実装も軽そうであった二分探索で解いた。難なくACすることができた。1問目よりもかんたんだと思っている。

3問目

2完をしたので部分点を集めに来た。解き切ることも考えたがわかりそうにもなかったので部分点に集中した。区間DPというものを知らなかったので解けなかったのはしょうがないと思っている。

0から始めて、次に左右どちらの台に進むかということを頂点につくたびにすることで、15点を取ることができた。時間を保存するところをlong longにし忘れたことで2回ほどWAを出した。やはり#define int long longは正義だと思う。

4問目

ぱっと読んでわからなく、またいくつかの頂点の向きを変えられると誤読をしてやる気が失せ、飛ばした。問題文をちゃんと読んでいればよかったと思う。

5問目

4よりも取りやすそうであったのでとき始めた。

すべての時間についてを事前に計算して累積和を取り、区間の和を見ることで1点の部分点を獲得できた。この部分点もlong longにし忘れたことで1回ほどWAを出した。この後のいくつかの部分点はSegTreeを書けば取れたが4問目を見たりしていて実装をする時間を取れなかった。

結果

問題番号 点数
1 100
2 100
3 15(小課題1,2)
4 0
5 1(小課題1)
合計 216
判定 Bランク

競技後

解析の時間はほしいデータをすべて保存してできる限り早めに部屋を出た。3完が多そうな雰囲気がしたので部分点の取り忘れで落ちると思った。

会場を出ると昼食だった。cobaltさんなどと会話を交わしながら昼食として出た弁当を食べた。割と美味しかったので店で売る弁当はすべてあの弁当にするべきだと思う。(過激)

昼食後には全部の問題の解説があった。3問目のAC数が23人であったことで全てを察した。かつっぱさんの解説がいろいろなネタを含んでいて面白かった。

何かの行事のPRもあったが、参加対象でなかったためほとんどtwitterをしていた。

帰り

またTXに乗った。同期がみんな優先席に座っていたので驚いていた。(基本は立っていた) スタッフの方々と会って、いろいろな話をしていた。

北千住で降りて千代田線に乗り換えようと思っていたら行きと違ってみんな北千住で降りるようだった。

余力があったのでABCも出た。

感じたこと

落ちた結果が経験不足であり時間不足や解き忘れでなかったので少しホッとしている。 しかし精進をしていないために経験が不足していたのでしっかりと精進をしようという気になった。(気になっただけ)

また交流等も結局あまりできなかったので積極的に交流するようにしたいと思った。

終わりに

読みにくい文章書いてしまってすいません。ここまで読んでいただいてありがとうございました。