Arc's blog

競プロなど

トップ > 競技プログラミング > JOI2017/2018 本選のレビューとか教訓とか、今後の話とか

JOI2017/2018 本選のレビューとか教訓とか、今後の話とか

競技プログラミング

さて、第17回 JOI（日本情報オリンピック）2017/2018 本選が終わりました。今回はそのレビューです。

あと、教訓・来年度JOIerへのアドバイスとかもあります。

コードレビュー

110点しか取れなかったので、あまり参考にならない。僕の思考ルートを追いかけて楽しんでください。

A ストーブ

最近の本選は累積和・いもす法を最初の問題で使ってきたので、今回もそうかと思ったけど違うっぽい。

ということはDPか。とりあえずこんな感じでDPテーブルを定義してみる。

dp[a][b]=a人まで考慮して、b回マッチを使ったときの最小時間

すると、

dp[a][b]=min{dp[a-1][b]+(a-1人目の人が来てから、a人目の人が来るまでの時間),dp[a-1][b-1]+1}

で求められる。minの前者は「ストーブをつけっぱなしにした場合」、後者は「ストーブを消してつけ直した場合」に該当する。

しかし、ここで問題発生。ACするにはdp[100000][100000]を用意する必要があるが、そんなにメモリ容量がない。

dp[a][b]の[b]の方は、bとb-1の情報だけ持っておけば漸化式を回せるので、dp[100000][2]にしてメモリ容量圧縮を図った。でもTLE。

そもそも、計算量がO(N*K)=10^10なのでメモリ容量があってもAC不可能。このことに気づいたときには1時間を過ぎていた。

一度コードをリセットして、「つけっぱなしにした場合の時間」から「消しておいても良い時間の区間」をできるだけ多く引く作戦にした。

「消しておいてもいい時間の区間」は、a人目が来る時間とa+1人目が来る時間をそれぞれtx tyとするとty-tx-1で求められる。

これを全てのaに対して求めた後、降順ソートをかける。

マッチがk本あるなら、途中で消して良い回数はk-1回。「つけっぱなしにした場合の時間」から、先程降順ソートした「時間の区間」を上から順にk-1回引いていってAC。

long longが必要であることに注意。計算量はソートがボトルネックとなってO(N log N)。

B 美術展

なんかもうパニクっててBFSしてました。10点。

美術品それぞれに対して「入れる」「入れない」を判定するだけ。O(2^N)。

「その美術品を入れることによってS-(Amax-Amin)の値が減少するなら打ち切る」って感じで枝刈りしてみようとしたが失敗。ここでタイムアップ。枝刈り可能なのかすら怪しい。

解説を聞いたところ、累積和を使うのはこのB問題だった。

ここからは駆け足で。

C 団子職人

DPかなぁ……と思ったけど実装せず。

解説はDPでしたが、当日解説では理解しきれず……。

D 定期券

なぜワーシャルフロイドを思いつかなかったのか。あのアルゴリズム好きだったのに。（なお部分点）

たぶん、この問題を解いていたほうが点を稼げた。

E 毒蛇の脱走

高速ゼータ変換、かっこいい。

解説時のDEGwerさんのギャグセンスが高くて面白かった。

コードレビュー編はここまで。多分この後がメインコンテンツ。

教訓編

JOIに参加して得た教訓を書いてみる。来年度以降のJOIerのアドバイスになれば幸い。

計算量見積もりはちゃんとしよう

こんなこと言ってるくせに何やってたんだか。

100,000,000(=10^8)　非常にシンプルな処理でない限り厳しい。（蟻本P20より)

とのこと。落ち着いて考えれば大体の計算量オーダーがわかる、と思う。

部分点戦略を考えよう

AtCoderだと部分点を得られる問題が少ないので、「ACかTLE（MLE)か」の二択になる。

しかし、JOIだと想定解より大幅に計算量が多くなっても(たまにO(N!)でも)点がもらえたりする。

今回の問題は全て、全探索すれば小課題1あたりで点がもらえた。

ただ、一度「妥協したコード」を書いてしまうと、そこから想定解コードを作るには結構時間がかかる。最悪、コードをリセットしたほうが早い場合もある。

もちろん全課題ACしたほうが嬉しいが、残り時間なども考えて「この問題はしばらく粘ろう」「この問題は妥協しよう」といったことを検討するべき。

(追記 2018-02-16)

JOI公式から本選Aランクボーダーが開示されたが、2完でボーダーに乗せるには多分上記の３パターンが現実的かと思われる。1完＋部分点で無理やり本選通過しようとすると、

「問題AをAC(100点)＋問題Bを課題3まで(50点)＋問題Cを課題2まで(33点)＋問題Dを課題3まで(55点)」

の、合計238点コースが妥当だろうか。けっこう非現実的ではある。

前日の睡眠を良質にしよう

今回宿泊した部屋は温度調節が大変だった……。

まあ、今回の宿泊場所に限らず、多くの人がホテルでは眠りづらいはず。

耳栓を持ってくる、加湿するなどして眠りやすい環境を作ろう。

競技中のエネルギー摂取手段を手に入れよう

だんだんネタに走っているような気がするが、結構重要。

今回は「粉っぽいモノ（ポテチなど）以外の菓子類を持ち込み可能」だったので、競技中にチョコレートを食べてた。（去年は違ったとの情報も耳にしているので、最新の規定はJOI委員会に尋ねてみることをおすすめします）

7時ぐらいに朝食を食べた後、9時から13時まで4時間頭を使ってたら、脳がエネルギー切れを起こすのは自明（僕だけか？）。

何か持っていったほうが良い。エネルギー切れ対策の他にもリフレッシュにもなる。

あと飲み物。魔剤を飲んでた人もちらほら。僕は飲めないが。

カフェイン取りすぎるとトイレが近くなるので注意。

体調管理のプロになろう

実は土曜日、若干熱っぽかったかも。体温測ってないので本当か分からないが。

無理して精進して体調崩したら元も子もないから気をつけよう。

あ、咳とか鼻水とかは無かったので、カゼでもないしインフルでもないと思います。ってかインフルだったら今ごろ倒れてる。

なにか思いついたら追加するかもしれないです。

まとめ

最初で最後のJOI本選だったわけですが、「もっと早く競プロやってればなぁ」と後悔しております。

実は、予選通過時にはまだ「競技プログラミング」ってのを知りませんでした。通過直後に知りました。

プログラミングは年齢より経験年数の方が遥かに重要だと思うので、まだJOI出場チャンスが残ってる＆たくさん経験値を稼げる中学生・高１競プロerが正直言って羨ましいです。

僕も頑張ってACM-ICPCに出たいですねぇ。そのためには受験を突破しなければならないわけですが。

でも、1年以上ブランクを空けるのが余りにももったいない気がするので、これからもAtCoderのコンテストにはたまに参加したいと思います。

ということで、帰宅後に勢いで書いたJOI本選レビューでした。今度のリアルイベントはCombNafかな？

更新情報

2018-02-16 タイトルと本文をちょっとだけ変更、部分点戦略について追記