第18回日本情報オリンピック予選の感想

概要

お疲れ様でした!ABC3完 + D15点 + E10点 + F6点 でした。合計331点。

本番の流れ

まずは22分でCまで解きました。Bで焦って15分使ってしまった。
そこから愚直にDを書いて、7点を取りました。とりあえず部分点を取っていくことにして、Eで10点まで取りました。
それから2時間半ほどDにつぎこんで、「二分探索か?」「キュー2つ用意してみよう」「DPではないだろうな」とかやって結局15点まで取り、終了直前にFで6点取りました。

A

愚直にシミュレーションをする。

B

実装が少し面倒でした。愚直にシミュレーションをしましょう。

C

マルとバツの列を左から見ていきます。最後に見たスタンプの形を覚えておきましょう。
マルバツスタンプを使って押したところから十分に離れているかどうかを判定して、そうであってかつ最後に見たスタンプと違う形をしているならば、使った回数をインクリメントします。

D

部分点(15点)でした。
与えられた配列をソートして、各要素から0を引き、そこから0より小さい要素を除外した配列を作ります。
それをforeachして、それぞれを海面の高さとし、島の数の最大値を出しました。(TLE)

E

部分点(10点)でした。
 2^N通りの飾りつけを考えられるので、これを全探索しました。(TLE)

F

部分点(6点)でした。
nextPermutationしました。これだと、同じ国の人が複数いるとき、彼らを一人一人区別することができません。
そのため、条件を満たす並びがあったときは、「与えられた配列のそれぞれについて階乗を計算し、それらをかけあわせた値」を場合の数として足しました。(TLE)

感想

AtCoderのレート相当の点数だったと思います。予選落ちでしょ。
Dの解法が思いつかなかったのが悔しいですが、「部分点を取るぞ!」という気持ちを忘れずにEやFも考えることができました。

docs.google.com

この表を見てると「オア〜〜〜〜〜」という気持ちになりますが(TLの人つよすぎ)、逆にまだまだ伸びしろがあると考えるのがよさそうです(ポジティブになりたいね)。
ボーダーがどうなるのか非常に気になります。TLの人々は本選でも頑張ってくださいね!!