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

前書き

運良く予選を通過することができたので(190位くらい)、本戦に参加してきました。オンサイト決勝は初参加です。

移動

東京駅には何度か行ったことがありますが、一人で行くのは初めてでした。迷子になったときのために早めに出ました。会場の最寄り駅(?)の神田駅に行くためには、東京駅で山手線に乗り換えれば良さそうで、少し心配でしたが、新幹線の出口の近くに標識があったので無事乗り換えられました。神田駅についたのが10:30頃で、少し道に迷いつつも11:00頃には会場に到着しました。受付開始の12:00まで時間があったので、近くでごはんを食べようと思ってうろうろしましたが、コンビニ以上の見つかりやすさと入りやすさのお店がなかったので、結局コンビニでおにぎりを買って食べました。

会場入り

12:00頃に会場に入りました。受付では名札とウイダーinゼリーをいただきました。座席は決まっており、二人で一つの長机を使う形でした。トークショーが始まるまでは、vimでクリップボードに貼り付ける方法を調べたり(?)、最近(昨日から)使い始めたonline-judge-toolsの使い方を確認したりしていました。そうこうしているうちにトークショー(インタビュー?)が始まりました。若くて強い競技プログラマーがたくさんいるんだなぁとなりました。

コンテスト

コンテストは13:15から開始でした。カウントダウンがあったので緊張しました。配点は2-3-6-8-8-?だったので、6までは解きたいなぁと思っていました。

A問題
なるの組の個数を求める問題です()。3つあるときは真ん中を固定するとうれしくて、これも真ん中を全探索すればで解けます。が大きくてもBITを使うと解けるみたいです。

B問題
文字列を空でない6つのsubstringに分割して、"NIKKEI"のように3番目と4番目、2番目と6番目の文字列を等しくする方法が何通りあるかという問題です。2個ずつ区切る境界を全探索すればいい気がしたのでその方向で考えました。3つに分けた文字列のうち、真ん中が同じ文字列を2つくっつけた形になっていればよくて、そうであれば最初の文字列と最後の文字列の後ろ何文字かを一致させる方法だけ答えを加算すればよいです。計算量はでなので間に合います。

ここまではうまくいっていて、順位表見たら44位だったのでビックリしました。online-judge-toolsは神です。

C問題
01からなるのグリッドから、最大のNを見つけるという問題です。ここでNとは正方形のグリッドであって、両端の列と、左上から右下への対角線がすべて1であるもののことをいいます。とりあえず正方形の左上と右下を全探索すれば3乗くらいで解けそうで、高速化を考えていました。setとmultisetを使えばできそうだなぁとなって実装を始めましたが、考察が詰めきれていなかったので、途中でできない気がして諦めてしまいました。解説を見た感じ方針は大体あってそうだったので、悔しいです。聞いたところによると全探索も枝狩りをするとかなり早くなって通るみたいです。まだ想定解を理解していないので、理解したら解説を書こうと思います。

結果はABの2完で114位でした。AC数的にCに取り組んだのは良かったっぽいですが、1.5hかけてCが解けないのは実力不足を感じました。

表彰式

入賞された皆さん、おめでとうございます。

懇親会

圧倒的コミュ症力を発揮して一人懇親会をしていました(完)。2人以上集まっているところに入っていくのは難しいです。頑張って近くにいたpotooooooooさんに話しかけて、コンテストの結果について話したり、コンテストの戦略について教えていただいたりしました。またオンサイト決勝にこれるように頑張ろうと思いました。

帰宅

電車に乗り遅れて1h待ちました。ここは田舎です。

まとめ

せっかくのオンサイトコンテストだったので、もっと懇親会で話しかけていればなぁと思いました。強くなってまた参加したいです。まだまだ実力不足なのでいっぱい問題を解きたいと思います。