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

前日譚

atcoder.jp

第二回全国統一プログラミング王決定戦予選に出ていました.

Dにセグ木を貼るなど,脳死プレイをしていました (いつもTsutaJさんのをお借りしています,自分のを作らないとだめですね)

Cが難しくて,それっぽいGreedy (経験に基づいているので実質証明?) をして,通りました(通ることが証明なので)

そのあとは,誰もEなどを通さないことを祈っていました.

その結果,日本人順位多分180位ぐらいで通過することができました

3回目のオンサイトです!(うれしい!

当日の朝

朝五時半に起きます,地方学生には辛い時間帯です.

前日入りすると,もっと楽なんですが,前日入りする時間とお金と娯楽がありませんでした. (前日入りしてもあまりしたいことが考えられなかった><)

新幹線にのって,東京に向かいました, 群知能の本を読んでいましたが,難しくてよくわかりません,向いてない><

会場着

なんやかんやで会場につきました.

学生選手権よりは迷わずに来れました.

考察スペースもきちんとあって,ウィダーインゼリーももらえて嬉しい (お菓子も欲しかった(傲慢)) https://twitter.com/ganariya/status/1206042573061550080

知り合いがいないので,虚無を過ごしていました..

卯月コウの配信がかぶる!

コンテスト

下から数えて二十番目ぐらいなのと,配点も結構高めなので リラックスしてコンテストに出ました.

場違い感もあり,600まで通せると良いなぁ〜ってなってました.

A問題

A問題はかんたんで,真ん中を全探索する というテクニックを使えばいいです.

これをすると,[tex: O(N2)] で全組み合わせを求めることができます.

普段だと300な感じ(最近の配点だと400?)

B問題

atcoder.jp

B問題は,文字列の問題でした.

文字列系が苦手なので,結構焦っていました.くやしいね.

最初の自分の解法は,S6とS1を全探索するとS2もS2も自動的に定まり, あとは条件を満たすS3, S4, S5を探索する というものでした.

見積もり計算量は[tex: O(N3)]で行けるやろ!の精神でした. 当然TLEをします(は?)
文字列の一致の判定はO(N)ということを忘れていました,これはだめです.

そこで,先に文字列が一致しているか?のテーブルを作ると良さそうなのかなと思いましたが, 面倒だったので,神頼みでローリングハッシュを貼りました.
通りました(ごめんなさい)

今回のコンテストは結構C++じゃないと厳し目の制約っぽい気がします.

C問題

atcoder.jp

C問題は,H*Wのマス目が与えられるので その中に存在するNを探せ〜という問題でした.

解法が生えないので,色々とお絵かきをしていました.

まず,先に前計算をしておけばいいので up[i][j] = (i, j)の上に何個連続して黒があるか? down[i][j] = (i, j)の下に何個連続して黒があるか?

を作っておきます.

あとは,斜めの個数を全探索したいなぁとなりましたが, 斜めの探索にHWくらいかかってしまい,これだと間に合わない計算になりました.

そこで,最初の方は,長さを各マスから斜め方向に二分探索かなぁと考察しました. ただ,二分探索ができるような,単調性が存在しないため,ここでおじゃんになりました.

ここから「うるせぇ全探索だ!」という気持ちになり, 枝刈りが本質では?と気持ちを切り替えて,その方針でコーディングをしました.

斜めは一箇所をやると,その連続した斜めは2回以上探索する必要はありません. 長いときに,内側はすでにやっているからです.

あとは,上から(長さdの斜めは構築できるか?を試し,dができるとわかったら即終了)のコードを書いたところ

3562msで通りました. 3562msって,出たとき「3sでは?????」とジャッジを疑いましたが, 「サイトが正しい」のでした(おバカ)

Eは,考えてもN2奴〜〜〜になりました. 精進します.

懇親会

懇親会では,美味しそうな肉やご飯がでました.

でも,知り合いがいないので悲しい気持ちになっていました. (自分から話しかけるのができない)

ただ,koi_kotyaさんに話しかけてもらえたのと, chocoboさんと話せたので,嬉しかったです!

(最近ゴリラジ出れてないなぁ,)

もっとお肉が食べたかった (上品な料理はいらないんじゃ ラーメンとカレー200杯出して)

まとめ

今回のオンサイトでは,改めて自分の足りなさというか
雰囲気で競プロをやってしまっているなぁというお気持ちになりました.

数学問題や,組み合わせ問題がかんたんなやつでも解くことができず, 数式が出てくると一切溶けません. また,解説の数式的な証明も理解できていないため,最近は自分のレートや伸び代があまり感じられていない状態です.

表彰式や順位表を見て,レッドコーダーの人たちや暖色の人たちは どんな問題でも上位にきていて 「数学的・アルゴリズム的バックグラウンドに基づく,安定力と考察力と実装力」

が本当に大切な世界なんだなぁと感じました.

まだ,僕はこの世界の足元さえ見えておらず 「直感的コーディング+AC証明」というやばい状態にあるため

  • 数学的に必ず証明する
  • 考察力・実装力をつける
  • とにかく解く!

を頑張っていこうと思います.

最近の競プロ界隈は,全員一気につよくなっていて 取り残されそうです. 次はいつオンサイト行けるんだろう...(行きてぇ〜〜)