Tsuzu's Notes

主にIT系備忘録

JOI2016/2017予選参加記

最後ということもあり書きます。
JOI(情報オリンピック)は中一から参加しているのでもう5回目ですね・・・。時の流れは早いものです。 前回、前々回は本選まで出場していますがいずれもそこで敗退しています。

事前準備

今回はいくつかのツールを事前に準備して挑みました。具体的には

  • テストケースの入力ファイルをダウンロードフォルダから自動分配するプログラム
  • 計5つのテストケースを実行ファイルの標準入力に渡して実行し結果をファイルに書き込むプログラム
  • 一度提出したファイルとローカルに残っているファイルが一致しているかを確認するプログラム。(結果として公式が公開した答えと自分の答えを照合するプログラムにもなりました。)

などです。
5回目にもかかわらず少し戸惑いながらなんとかログインなどの準備を完了しました。

1

JOI予選1問目恒例ifでとく感じの問題ですね。a≠0なので0を基準に考えればOKです。 gist.github.com

2

これもJOI予選2問目恒例forと配列でとく感じの問題ですね。 問題を勘違いしてやたらバグらせてしまったのが反省。 gist.github.com

3

O(NMD)で問題ないので3重ループしてあげれば終わりです。 gist.github.com

4

ここで難易度が急上昇してビビる。とりあえず問題を読んでDPっぽいなとは思いつつまだ思いつかなかったので飛ばして5問目。

5

UnionFindとかDBS/BFSとか考えて微妙にうまくいかなかったのでなにも考えず遡るようにsetでゴリ押すコードを書いたらケース5でも5sほどで終わってしまいまぁいいかとなってそのまま4問目へ。

gist.github.com

4

考察をすると最終的な状態を決めてしまえばどれを移動すればいいかが求められることがわかる。最終的な状態の並び方はM!通りあるがこれをbitDPで処理してやるとO(2M)で良いことがわかる。また、状態を確定させた時にいくつを移動しなければならないかはあらかじめ累積和を利用して数えておくことができる。

gist.github.com

6

ダイクストラに寒暖の異なる部屋に入れるまでの時間、寒暖、経過時間を持っておけば良さそうだとは思ったがそれでうまくいく確証と計算量がオーバーしそうな予感がしてそのまま終了。

結果

まだ結果は出ていませんが自分で答え合わせをした感じだと解いたところは全部あっていたようで5完(500/600点)でした。今回は各ツールのおかげでだいぶスムーズにできました。
本選にも出場できると思うので後悔の無いよう頑張ろうと思います。