JOI二次予選で爆死しました
はじめに
この記事は東京高専プロコンゼミ① Advent Calendar 2020 14日目の記事です。
JOI二次予選に参加しました
今年もJOI二次予選の季節がやってきましたね。競技プログラミングを嗜まれている諸兄姉におかれましては、日々の精進の結果を存分に発揮し、満足のいく結果を残せたのではないかと存じます。ちなみに自分は爆死しました。
1完+部分点の合計196点でした。どうしてこうなった。ちなみに僕は高専2年生なのでJOIに参加できるのは今年が最後です。さようならJOI。ありがとうJOI。
というわけで、今年のJOI二次予選の振り返りを適当にやっていきたいと思います。
A:往復すごろく
最初はただの簡単なシミュレーションかと思ったが、制約的にきつそうなので考察してみる。
駒の初期位置を境界にして#のマスを左右に分けて考えると、まず初めに右側の#に行き、それ以降は左側→右側→左側...と交互にマスを訪れることがわかった。
後はこれを基に実装するだけで、初期位置の右側と左側にある#マスをそれぞれ別の配列に保持し、交互に抜き出していい感じに加算していくように実装したらうまくいった。
B:パンケーキ
なにこれ(なにこれ)
パンケーキの状態を文字列で保持して条件を満たすまでひたすらBFSで回したらTLEで落ちた。
どうやら明らかに条件を満たさないような操作でも問答無用で遷移をしていたことが原因らしいので、場合分けで上手く乗り切ろうとしたらWAで落ちた。最終結果は74点でした。おわり
C:イベント巡り
なんとなくDPの香りがしたので、
dp[i][j]=開始時刻でソートしたイベントの下からi個目のイベントが始まる時刻にj番目の町にいた場合の今まで参加したイベントの数の最大値
のDPテーブルを立てて雑に遷移させたプログラムをダメもとで投げたら部分点で19点もらえた。やったー
D:安全点検
とにかく部分点が欲しいの一心で問題文を流し読みしながらクソ雑貪欲を書き殴ったら3点もらえた。
E:スパイ2
問題文を見る。なんか無理そうだなと思ったのでタブをそっ閉じした。今思えば部分点だけでも回収すればよかったなと思った。
いかかでしたか?
当初の予定ではA~C問題を開始1時間で片付け、D問題以降をじっくり考察しながら解き進めて栄光の本選ロードへ...などと分不相応な妄想に浸ってもいたのですが、B問題で完全に出鼻を挫かれる形となってしまいました。パンケーキだけは絶対に許さない。
ちなみに余談ですが、巷では今年の本選ボーダーは200~220点ではないかと言われているらしいですね。もし200点ボーダーだったら泣く自信しかないです。それでは。
