UECCPバーチャルコンテストを発起し、完走した
Published on 2024-08-08Last Modified 2024-08-08
Table Of Contents
UECCPバーチャルコンテストについて
私が電通大競プログラミングサークルに呼びかけて、4月から8月までAtCoder Problemsを利用したバーチャルコンテストを週1回開催しました。 某H先生のご厚意により、競プロサークルで利用できる教室があったため、そこをオンサイト会場(笑)として利用しました。 4月22日から8月5日まで合計13回開催しました。
まえがき
本エントリでは、しばらくのあいだUECCPバーチャルコンテストを定期開催して感じたことなど適当に書こうと思います。
きっかけ
せっかくUECCPという形で有志が集まっているのだから、なにか競技プログラミングの定期イベント的なものがあれば嬉しいなとずっと思っていました。 2023年前期はsepa_38さんが声掛けをして、ABC振り返り回的なものを行っていました。 しかし、その集まりも前期終盤になってなあなあで消滅してしまったりと、アクティブに活動する方は多くないという印象がありました。 こういった事情で、私がやりたいことは私が始めるしか無いなと思い、一念発起してみました。
私は競技プログラミングの話をするだけでも十分に楽しいので、あまりやることを固めていませんでした。 今になって思えばそんな集まり誰が来たいんだよという感じがあるので、バーチャルコンテストをやることにして正解でした。バーチャルコンテストを提案してくれたdyktr_06さんに感謝です。
実際に行ってみて
初回は物珍しさ + 学期はじめでスケジュールが楽な人が多かった(?)ため、沢山の人が参加してくれました。そのため椅子が足りなくなり、私は膝立ちでプログラムを書いていました。膝、めちゃくちゃ痛かったです。 所属「The University of Electro-Communications」で順位表によくいる人に実際に合ってお話する機会にもなりました。
第二回以降は人数も落ち着いて、だいたい同じ人が参加するようになりました。幸運なことに、私とレート帯の近い方がよく参加してくれたため、特にお話していて楽しかったです。
途中からdyktr_06さんによりUECCP Viewerという各回の結果を見れるツールが開発されました。(スゴイ)
終わっての感想
全体的にやってよかったなと思います。他の競技プログラミング勢とお話することは、私にとってとても新鮮で、毎週の楽しみでした。 しばらくは同じ部屋を利用させていただけそうな感じがするので、できるだけずっと開催したいと思います。 参加していただいた皆さん、ありがとうございました。またお願いします。
各回で一番好きな問題
-
第一回
Priority sumという興味深いアルゴリズムを適用できる問題です。全順序と加法のような二項演算の定まった要素の集合において、順序の(高い/低い)順に先頭$K$個の和を求めることができます。いい感じの平衡二分木を使えば都度$K$を変更することもできます。整数しか扱わないといった制約をいくつか入れると、より簡単に$K$を変更できるようになります。
-
第二回
迷いましたがこれにしました。私が競技プログラミングをはじめた頃に出題されて、わから無さすぎて困った思い出の問題です。典型的な取る/取らないdpとして解釈できます。この問題から多くを学びました。
-
第三回
グラフ多重化典型で解くことができます。この手の問題は自力で解法にたどり着くのが非常に難しいと考えています。私がグラフ探索の可能性を感じ始めた思い出の一問です。
-
第四回
dpについて考えるきっかけをくれた問題です。陽なDAG上のdpを楽に処理するはこの問題の解法に感動したのがきっかけで書きました。
-
第五回
組み合わせや場合の数に関する知識が問われる問題です。高校時代に非常に苦手だったジャンルですが、このような問題を解くうちに少しずつお気持ちがわかってきています。
-
第六回
確率/期待値の知識が問われる問題です。この手の問題は未だに苦手ですが、多分競技プログラミングで最も「数学」な部分なのでつい頑張って考えてしまいます。 好きではないですが、一番思い出深いということでここにあげました。
-
第七回
キーエンスプログラミングコンテスト2021C - Robot on Grid
バーチャルコンテストではじめて出会ったタイプの問題でした。解釈は2通りあります。ロボットの移動経路が何通りあるかの期待値を考える方法と、一つの経路からの主客転倒により数え上げる方法です。このタイプの問題についての解法はまだ自分の中に確立した理論がありませんが、この2通りの解釈はほぼ等価なのではないかという予想をしています。
-
第八回
difficultyの割に難しいと思っています。問題分の正確な理解とシンプルな実装方針を取れるかによって体感難易度が大きく変化します。間違いなく良問です。
-
第九回
解法自体はすっと見える人が多そうですが、きちんとACを得るには正確かつ高速な実装が要求されます。 下手な実装だと実行時間制限がかなり厳しくなりそうです。 グリッドの下処理は4方向でやってしまうのが良いという謎の典型でもあります。
-
第十回
桁dpとして解くことができます。この問題を考察しているうちに、桁dpへの理解が非常に深まりました。これまで私は桁dpを蛇蝎のごとく嫌っていましたが、この問題を通して好きになりかけています。
-
第十一回
ARCらしい発想の転換が必要な問題です。$X$側から$Y$を構築するのは難しそうなので、$X _ i \leq 50$の制約をうまく利用して解きます。
-
第十二回
累積和の累積和という非常にややこしいものについて考える必要があります。累積和が最大値を取るときとはどのような時であるかを丁寧に考察する必要があります。 実装も方針によっては簡単に破滅してしまう問題なので、十分な経験と自力が必要です。 ちなみに、累積累積和に$x _ i$がどのように関与するかの絵を書くと解きやすいです。
-
第十三回
ABC266F - Well-defined Path Queries on a Namori
なもりグラフの閉路を成す頂点集合を列挙するという典型問題が解ければ比較的簡単です。 functional graphと異なり、強連結成分分解を振り回せないので少し面倒です。 こちらも実装方針をちゃんと選ばないと実装が爆発しがちです。
以上です。ぜひ解いてみてください。 このリスト書くのに1時間くらいかかりました。疲れた…