Maximum Cup 2024 開催記

はじめに

2024/08/31 に自分の所属する埼玉大学にて、Maximum-Cup 2024 という競技プログラミングのオンサイトのコンテストを開きました！個人的な作問に関する感想を述べていきます。

※ 以下コンテストのネタバレを含みます

作問した問題

自分が今回の Maximum-Cup 2024 で作問した問題は下記の 3 問です。

Maximum-Cup 2024-B : Saitamaze

概要

• のグリッドがあり、それぞれのマスに高さ が定義される。
• 任意のマスの高さをコスト で変えることができる。
  • 移動途中に自身がいるマスの高さも変更可能
• 同じ高さのマスをたどって に行く時の最小コストを求めよ。

感想

これは、入力でグラフが与えられるわけではないが、 問題に沿ったグラフを構築することで解ける問題 を作成したくてこれを作りました。 マンハッタン距離的に遠ざかる遷移でも、同じ高さを進む場合はコストが 0 で移動できるのでそういうパターンもあり得るため、普通の探索では解けない少し捻りのある問題になったのかなと思います。

個人的に作成した 3 問の中で一番好きです。

Maximum-Cup 2024-G : Loneliness

概要

• 数直線上に人が直立しており、各人には の番号が割り当てられる
• 同じ番号の人同士でペアを組むことができる
• クエリが 個与えられるので順に処理をせよ
  • クエリ 1 : 区間 には番号 の人が奇数人、それ以外の番号の人は偶数人存在するという情報が与えられる。
  • クエリ 2 : 区間 にいる人を集めた時にペアが組めない人の人数を出力。ただし、答えが一意に定まらない場合は "Ambiguous" を出力

感想

これは ポテンシャル が関連した問題を作りたくて考えていたらできました。

問題作成をする際は、自分は問題に使いたいアルゴリズムから問題を作るのは個人的におススメです。 今回はポテンシャル使いたいな → 重み付き Union Find 使いたいな → 単純なポテンシャルじゃつまらないから XOR 乗せてしまおう → 今の問題設定に至るという感じでした。

ただ、作成した後に、Union Find を 60 個持てば解けるのでは ? とか、クエリ先読みして Ambiguous さえ判定すれば、それ以外は Euler Tour や Heavy Light Decomposion で解けるのでは ? と色々な解き方が出てきたので、競プロの面白さを実感した 1 問でした。

(色々な解き方があるので想像したよりは多くの方に解かれていてビックリしました。)

Maximum-Cup 2024-H : Maximum vs Merin

概要

• 種類のスライムがいて、 種類目は体力 で 体いる
• Maximum 君と Merin ちゃんは下記の二つの操作を、Maximum 君が先行として繰り返す
  • 操作 1 : スライム 1 体の体力を 削る
  • 操作 2 : スライム 1 体を体力の和が元と同じように 2 体に分裂させる
• スライムの波が 回押し寄せてくるので、それぞれにおいて両者が最適に行動した時に最後の 1 体をどちらが倒すかを出力せよ

感想

これは前二つと少し違って、最初は後退解析の問題を出したいと思って作ったが、結果的に Grundy 数で解けることを内部テスターとしてお手伝いをしていただいた m_99 さんに指摘されて進化した問題でした。

これは解説に添付する証明を作成するのが地獄でした…。Markdonw にして 930 行…。作問をするうえでは、面白い問題作りも大事ですが、できるだけ解説が書きやすい問題にしないと作問が大変すぎるという知見を得ました (当たりまえ)。

全体としての感想

楽しい

普段インターネット上で解く速度を競っている参加者の人々と実際に対面で会って交流をするのはとても楽しいです。

自分は幸い周りに競技プログラミングをやっている人がいるものの、普通はなかなか実際に競技プログラミングをやっている人と出会う機会は無いと思うので、競プロの話で盛り上がれる数少ない機会でした。

参加してくださった方々が競技をしている最中は運営者陣で順位表を見ながら全完してくれる方いるかなーと談笑しながら見ていたのですが、結果全完者が出てきちんと解けることが証明された時はホッとしました。

作問の大変さ

今回が初の作問 + Writer が二人で AtCoder の黄色以下の人が時間内全完できない程度に楽しめる難易度間を目指していたので、結構大変でした。

特に Maximum vs Merin の証明が地獄だった (というかこいつが大変だった元凶) ので、本当に作問する時は解説しやすい問題作りを意識すべきだなと感じました…。

また、今回は Rime を利用して Github 上で問題作成を行いましたが。普通に Github Actions でテストケースをチェックしてくれるのでとても安心して問題作成ができたので、オンサイトを開催したいと思われている方は Rime を使うといいと思います。

問題の言い回し

今回は AtCoder で作問をしている m_99 さんが内部 Tester として参加してくださったのですが、問題の言い回しにおけるアドバイスを沢山いただきました。

例えば Maximum vs Merin で言うと、初め自分が作問して PR を上げた時に 「『ダメージを与える』とかの表現は RPG 要素が強すぎるので、RPG を知らない人でもわかるようにもっと厳密に書いた方が良い」 とアドバイスをいただきました。

また SaitaMaze の方では、最初は隣接マスという表現をしていたんですが、「隣接マスだと 8 近傍 (斜め含む) とも解釈できるので、上下左右のマスという表現にした方が良い」 ともアドバイスいただきました。

他にも沢山アドバイスを頂きましたが、どれも様々な人が問題を読んだ時に齟齬が出ないように考えられていて、なるほどなーと思うことばかりでした。

普段の AtCoder のコンテストでは参加者から可能な限り疑問が出ないように考えられてると思うと、毎週これを開催してることに非常に驚きです。凄すぎです。

オンサイトコンテストの参加者の低迷

これは運営陣で話していたことですが、最近の競プロオンサイトの参加者が全体的に減ってるよねーという話をしていました。

これは Maximum Cup だけでなく、他の大学主催のコンテストも以前より参加者が全体的に減ってるのが Conpass の参加登録数を見て明らかなので、もっとオンサイトコンテストが人気になってくれるといいなーと思ったりしていました。

終わりに

昨年に引き続き今年も Maximum Cup を開けてとても楽しかったです！(もしかしたら来年も開くかも…?)

ということで、運営・Tester として関わった方々、並びに参加してくださった方々、ありがとうございました！