Osmium_1008のブログ

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

JOI'21 二次予選参加記

はじめに

こんにちは。投稿は2回目、前回の投稿は10ヶ月も前です。 こういう時に更新しておかないといつまでも更新しなさそうなのでとりあえず書いておきます。

記録的な意味合いが強いのでわりと適当です。

結果

問題名 得点 経過時間
A 100 10:06
B 100 01:06:23
C 100 01:50:30
D 100 02:28:25
E 7 02:48:01
合計 407 02:48:01

といった感じでした。

407点は 得点集計表 でも16位(12/13 18:00現在)となっているので多分通るんじゃないかなーと思っています。

行動

競技前後でどのような行動をしていたのかを書いていきたいと思います

開始直前

集中力を上げるためにコーヒーを飲んだ上で手元には炭酸水とチョコを用意して、あと一応ノートを開いておきました。

その上で直前まで漫画を読んだりゲームをしたりして出来るだけ緊張をどこかに飛ばすように行動していました。

(集中力も一緒にどこかに飛んでいったような気がしましたが多分大丈夫でしょう)

競技中

A問題

問題を開くとわりと分かりやすそうな問題が目にはいります。Aを中心に左右に広げていけば解けそうなので実装します。 少しバグらせたこともありましたが難なくACします。

ここまでで10分ほど

B問題(ちょっとC)

問題のBです。

まずは初期状態をstringでmapなどに登録し、stringのまま全部の状態を列挙しようとしてみます。 実装が完了しACを確信しましたが結果はTLE、改善出来る場所が全く分かりません。

わからないので一度Cに目を通し実装しようとしましたがTLEしそうな解法だったので諦めました。ここまでで25分ほど経っていたはずです。

Bに戻ってすぐに3進数で管理することを思いつき、実装を始めます。 しかし慣れない数字の管理に実装を狂わせ、デバッグを重ねてACした時には1時間以上経っていてかなりの焦りを感じていました。

C問題

Cは先程諦めたので一度Dを覗いてみます。 pairで愚直に管理してみる解法を思いつき実装してみますがテストケースの途中で嘘であることに気付き、手が少し止まります。これが1時間と25分ほど。

心を落ち着けるためにコーヒーを飲み(2回目)Cを見てみるとどうやら

dp[今いる町][参加したイベントの数]=そこまでにかかる時間の最小値

のようなDPで解けそうだということに気付き、これなら更新時に二分探索しても O(NlogN) で通せるはずなので実装にかかります。 実装時に不注意によるミスを連発しましたが方針は合っていたようでAC、ここまで1時間50分ほどです。

D問題

4問通せれば通るだろうと考えていたため、一度目を通していたDに1時間残っていることで気持ちに余裕を持つことができました。

制約が正解の決め打ちで二分探索してほしいと言っているので何で判定しようか考えながら二分探索を書き始めます。 判定は後ろから適切に人を割り当てていけばいいことに気付き実装し、かなりすぐにACします。残り約30分です。

E問題

Dが案外すぐに解けてしまったためまた若干自信を失い、ちょっとでも通る確率を上げようとEのbit全探索解を実装し7点を得ます。ここで得点が確定。

この後は少し考えれば嘘であることがわかるような嘘解法を実装して提出しましたが当然WAでした。

競技終了後

全完もそれなりに見掛けましたが同期などのそこそこ強い人も同じ点数だったので若干安心しました。

集計表を眺めて意外な点数分布に驚きつつ、非公式難易度表への投票や感想戦などをしていました。

結局ノートを使うことはありませんでした

感想など

考察を重視して精進をしていましたが、実装でバグらせたり手間取ったりする場面が多かったため、実装力を鍛えることも重要だと再認識しました。 あと実装と見比べるために考察ノートはちゃんと書こうと思いました。

終わりに

やはり文章を書くのが下手です。こんな文章を最後まで読んでいただいてありがとうございました。

気が向いたら解法についても書くかもしれません。