もふふろぐ

by

全国統一プログラミング王決定戦 参加記

atcodercompetitiveeventprogram

2月17日の全国統一プログラミング王決定戦本戦に参加しました。

予選では100 + 200 + 400 + 500点（47:42）の291位でした。 予選通過の条件が日本在住の上位200位とのことで、何とか本戦に進出することができました。 （予選の順位表で国籍を「日本」に絞ると204位でした。） なお、上位201位から上位500位までの参加者にも、本戦以外のイベントに参加する権利が与えられました。

会場は東京ドームホテルB1Fにある大宴会場「天空」です。 コンテストとトークセッションで使われた部屋にはそれぞれ天空A、天空Bという名がつけられており、RPGのダンジョンのエリア名みたいだと思いました。 これまで参加したオンサイトコンテストの中で最も豪華な会場に見えます。

開会式は12:30に始まるので、CODE FESTIVALのような軽い昼食があるだろうと踏んで入場したところ、何もありませんでした。 オンサイトコンテストではよく見られる菓子コーナーすら無い、飲食を禁止された厳しい環境でした。

同様に、オンサイトでよく配布されるような衣類もありませんでした。

また、大きなコンテストだったので満を持してぬいぐるみを持参しましたが、会場は撮影禁止だったため、何も記録に残せずに帰ることになりました。

本戦

全国統一プログラミング王決定戦本戦

3時間8問の長めなコンテスト。 5完で1900点（ペナルティ2, 171:47）の110位になりました。 予選順位が200位付近であったことを鑑みると大健闘であったと思います。 レーティング変動が無いコンテストであったことが少々残念です。

A Abundant Resources

長さNの数列Aが与えられるので、連続するk要素（1 <= k <= N）の和として考えられる最大値をそれぞれ求める問題。 累積和を求めたうえで、ありうるN - k + 1通りを全て調べます。

B Big Integers

長さNの整数列Aと長さMの整数列Bの各要素をK進法の各桁と解釈し、AとBの大小を判定する問題。 実際の値を計算しているとintやlong longには収まらなくなってしまうので、数列の形のまま比較をします。

誤ってA問題のコードを提出したため1WAになりました。

C Come Together

H行W列のマス目上に置かれた駒をどこか1マスに集めるために必要な最小の操作（隣接するマスに移動する）回数を求める問題。 操作回数がマンハッタン距離になることから、縦の座標と横の座標を独立なものとして考えます。

入力で与えられるのは駒が無い座標であり、すべての駒を列挙すると時間が足りなくなるため工夫が必要です。 この問題に30分以上掛けてしまいました。

D Deforestation

N本の長さ0の竹があり、それぞれ時間1ごとに高さが1増えます。 竹を伐採すると、その竹は高さ0になりますが、以降も同様に伸び続けます。 これらの竹について、時刻T[i]にL[i]番からR[i]番までを伐採するという情報がM個入力されるので（1 <= i <= M）伐採された高さの総和を求めるという問題です。

ある竹を最後に伐採する時刻をtとすると、それより前にこの竹を何度伐採しても、得られる高さの総和はtです。 ゆえに、各竹が最後に伐採される時刻さえ分かれば、すべての竹から得られる高さの総和も分かります。

竹を1番からN番まで走査することを考えます。 今見ている竹kが伐採される時刻の集合をstd::set<int> sで持つことにすると、k == L[i]であるようなiが存在するときにs.insert(T[i])、k == R[i]であるようなiが存在するときにs.erace(T[i])をすることで、集合を効率的に更新できます。 （このために各竹kについてL[i]（R[i]）がkであるようなT[i]の集合を事前にまとめておきます。） あとは、その都度集合の中の最大値*std::rbegin(s)、すなわち最後に伐採される時刻を足していけば答えが求まります。

懇親会ではセグメント木を使ったという声も多く聞きました。

E Erasure

数え上げ問題。 普段あまり解けない分類の問題でしたが、90分ほど掛かってなんとか解くことができました。 N個のブロックについて計算するには1, 2, …, N - 1個の場合の答えが必要だったので、メモ化再帰的に考えていくことで解法に辿り着くことができました。

F Flights

E問題と並べて読んでいましたが分からず。

トークセッション

AtCoderのchokudai社長が、Preferred Networksの方々と競技プログラミングについて話していました。 競プロのプロたちが集まっているので濃い対談になりました。 chokudaiさんがとても元気でした。

エキシビション

全国統一プログラミング王決定戦 エキシビジョン

本戦の上位3名だけが参加する20分8問の超早解きコンテスト。 Writer chokudaiさんによる面白い問題が揃えられていました。 コンテスト中の3名のラップトップの画面が並べて表示され、chokudaiさんが実況するという新しい試みでした。

懇親会

会場がホテルであったためか、かつてないほど豪華な料理が振舞われました。 会場での撮影が禁じられていたことが悔やまれます。 500人の参加者に対して会場は狭く、料理が並ぶテーブルも少なかったため、終始長蛇の列ができていました。

まとめ

本戦の規模や会場を見るとすばらしいコンテストであるかのように思われました。 実際には、対外的な見栄えが重視されており（例えば、スタッフがスーツ姿であること、表彰式が堅苦しかったこと、撮影や飲食が禁止されていたこと、など）、他の企業コンテストよりも満足感は小さいように思えました。

しかし、日本経済新聞社というメディアの企業がコンテストを開いたことは、競技プログラミングの宣伝・普及に対する大きな一歩になるはずです。 日頃のコンテスト参加の甲斐あって、このような場に居合わせることができ、嬉しく思いました。