season's quarterly

数学/物理/プログラミング

JOI2019/2020予選参加記

本選はこちらです。
season1618.hatenablog.jp

一次予選

一次予選はせっかくなので3回とも出ました。

第一回

一回目は弊校のパソコン部員(一年生3人、二年生1人)で集まってやりました。

  • A-3つの整数...数字が二種類しかないので全部足すとわかりやすいです。
  • B-母音を数える...mapを使って数えます。
  • C-マージ...アルゴリズムマージソートそのものなので、sort(v.begin(),v.end())をやるだけでよいです。

全完するのに7分弱かかりました。残りの時間は図書館で借りた「数学ガール ポアンカレ予想」を読んでいました。結果は3人が全完、1人が200点だったので、全員一発で一次予選を突破できました。

第二回

二回目は自宅のパソコンから出ました。

  • A-試験...高い方二つとありますが、全部足して一番小さいものを引くと簡単です。
  • B-文字列の反転...丁寧にやります。
  • C-最頻値...カウントして最大値を出力します。

第三回

今回は修学旅行中でした。少し前にノートパソコンを買ってもらったので、一次予選すべてに出ることができました。

  • A-Xに最も近い値...区間[L,R]と原点の位置関係で場合分けします。
  • B-キャピタリゼーション...順番に見ていって、joiが来たらJOIに変えます。
  • C-最長増加連続部分列...これも前から見ていって丁寧にやります。

二次予選

今年もJOI期間中にテストがあった(?)ので、少し辛かったです。

精進

コンテストはAtCoderだけでなくyukicoderにも積極的に出るようにしました。二次予選の2週間にJOI難易度表を初めて見たので、本格的に埋め始めました。


とりあえず難易度1から1問ずつ解いていって、自分に適当なのは難易度6くらいかなと思い、難易度6を埋め始めます。また、JOI予選ボーダーは難易度7くらいとも聞いたので難易度7も少し埋めました。前日にライブラリを整備しました。セグメント木が出るかも?ということだったので、一応実装しておきました。前日や当日はあまり問題を解くモチベーションが湧かず、解いた問題の解説を読むなどしていました。二次予選は再び学校に集まってやりました。

A:ポスター

4通り全部比較します。移動の回数を足すのを忘れないように注意。

B:いちご

貪欲でできるらしいですが、確信できなかったのでシミュレーションでやりました。ちょっと焦る。

C:桁和

典型的なDPの問題。

  • dp[i]:操作を何回か繰り返してiになるような整数の個数
  • d[i]:iの桁和

とすると、最初dp[i]=1として、j < min(55,i), d[i-j] = jなる整数jに対してdp[i] += dp[i - j]とすればよいです。

D:テンキー

まず前処理として各キー間のコストを求めておきます。座標にしてマンハッタン距離にすれば簡単です。(Mで割ったあまり,最後の桁)のpairを作ります。答えは(0,0)から(R,i)(i=0~9)まで移動するときのコストの総和の最小値なので、各pairに辺を張って最短経路問題を解けばいいとわかります。メモリが危なかったのですが、ダイクストラ法で通ります。
ここまで1時間30分ほどかかりました。

E:じゃんけん式

ワイルドカードのある数式が与えられるので、答えがAとなる数式の総数を求めよという問題です。僕と同じく解法以前に実装が分からなかったという人が多かったようです。単語だけは知っていたので、ポーランド記法とかで調べたのですが、入力として与えられるのは中置記法と呼ばれるもので、あまり検索に引っかかりませんでした(下手なだけ)。Dまでが比較的簡単だと思っていて、ボーダー付近にいるのではと感じていたので部分点だけでも取りたかったのですが、残り1時間30分なにもできませんでした。

終了後

TLを見ただけでも全完者がちらほらいて、400点もそれなりにという印象でした。当初はボーダー全完ありうるのではという言説も見かけましたが、最終的には330~350点に落ち着いたようです。

結果

400点ペナルティ0。一年生は1人が200点、2人が0点という結果となりました。
400点ならさすがに通るだろうと思っていましたがやはり不安でした。結果発表はその週の木曜日にあり、Aランクボーダーは350点でした。パソコン甲子園の本選に行ってからオンサイトにとてもあこがれていたので嬉しいです。本選は2月8日~9日にあるようですが、9日は僕の誕生日です(まあどうでもいい)。悔いのないように頑張ります。