Asa's Website

Maximum-Cup 2024 開催記

competitive programmingparticipation log

作成日 / 最終更新日

Table of Contents
きっかけ開催前2024 年 4 月2024 年 6 月2023 年 7 月上旬下旬2023 年 8 月上旬中旬下旬開催準備事前説明コンテストABCDEFGHI終了 + 解説懇親会 + 片付けまとめ

Maximum-Cup 2024 にご参加いただいた皆様、ありがとうございました！
今更すぎですが開催記を書きます。
以下敬称略です。

きっかけ

昨年度に Maximum-Cup 2023 を開催して、某オンサイト常連勢から「来年も生えますか？」と言われたので生やすことにしました。
とはいえ今年度は Maximum の代表を退いたので、大学とのやり取りは現代表に丸投げしました。
引継ぎのタイミングで会議したんですが、 Maximum-Cup やる？と聞いたらやりますかぁっていう感じで前向きに進んでた。

開催前

2024 年 4 月

Maximum 内の Discord で諸々運営の話が進んでいて、日程いつにするかみたいな話をしていた。
やるならとりあえずリポジトリ建てとくかということで、 a01sa01to/maximum-cup-2024 を Private で作って、共同作問陣の through に Collaborator 権限を渡した。
まあトラップ枠で Three Coins (B 問題) は (勝手に) 確定していたので、とりあえずリポジトリに作っておいた。

あとは Issue に、とりあえず Maximum Discord の作問チャンネルにあったやつをいくつか問題案としてコピペしておいた。
(悲しいことに、作問チャンネルに上がっている問題はあまり解かれていないので、まあ出しても問題ないやろという判断。結局ほとんどが新規作問でした)

2024 年 6 月

大学側とも話ついたし、 MOFE Admin の kichi と話して MOFE が使えるようになった。
ということで Maximum-Cup が開催できそうになったので、とりあえずカバー画像案を Maximum 内で募集。
作問側としては、 through に案上がったら適当に Issue 投げといて～という感じで進めていた。
あとは Maximum OB の m_99 に内部 (?) テスターとして参加をお願いしたところ、快く引き受けてくれたので、作問陣 Discord サーバを作った。

2023 年 7 月

上旬

外部テスターも募集したいよね + いい加減広報しないとまずいよねということで、カバー画像もできたので、 Maximum 広報にツイートをお願いした。 (もう代表じゃないのでツイート健が失われた)
外部テスターは Miryoku7 が興味ある～とのことなのでとりあえずお願いすることにした。

埼玉大学 プログラミングサークル Maximum
埼玉大学 プログラミングサークル Maximum
@Maximum03400346
·Follow

\ 今年も Maximum-Cup を開催します / Maximum-Cup 2024 を 8/31 (土) にオンサイトで開催する予定です！ 詳細は未定ですが、ぜひ予定をあけておいてください！ また、外部テスターを 2-3 人程度募集します ある程度作業が終わってからのテストを考えているので少し期間は空いてしまいますが(続く↓)

Image
39
Reply
Read 1 reply

下旬

問題もある程度たまってきたが、高難易度枠が微妙...でも時間もあまりない...というところで 7 月末まで問題案考えて、 8/10 くらいまでに問題確定 + 準備という計画で進めた。
結局ある程度の問題セットは決まったが、高難易度枠はまだ決まっていない。

とりあえず暫定的に connpass のページも作った。
https://saitama-maximum.connpass.com/event/325174/

一方大学とのやり取りでは、会場の Wi-Fi について eduroam を使うときに個人情報の入力も必要みたいなやり取りがあったらしく、かなり混乱しているようだったのでちょっと介在。
さすがに個人情報の入力は減らしたいよねぇということで交渉してもらった。
結果、トラブル防止のため全員から名前とメアドを集めることになり、 Wi-Fi (eduroam 除く) を使いたい人からは住所と電話番号も集めることになった。 (たぶん来年度以降もこんな感じになります)
ちなみに eduroam は学内全体で今年度から使えるようになりました (これまでは一部の部屋のみだった、逆になんでこれまで使えなかったんですかねぇ)

2023 年 8 月

上旬

ようやく connpass のページを公開。
外部テスターももう 1-2 人ほしいよなぁということで、もう一度募集をかける。
すると、 AngrySadEight から DM が through 宛に来たらしく、外部テスターとして参加してくれることになった。

Asa
Asa
@a01sa01to
·Follow

#MaximumCup2024 connpass 公開しました！ぜひぜひ参加登録してください！ Writer としては灰 - 黄くらいの想定です～ 外部テスターもまだ募集していますので、オンサイト参戦しない予定の方で興味があればぜひ DM いただけるとうれしいです！ (不備や難易度感のチェックをお願いする予定です)

埼玉大学 プログラミングサークル Maximum
埼玉大学 プログラミングサークル Maximum
@Maximum03400346

【Maximum-Cup 2024 参加登録のお知らせ】 8月31日に埼玉大学で開催される、 『Maximum-Cup 2024』の参加登録が開始されました！ 下記のリンクから登録できます。 皆さんのご参加をお待ちしております！ saitama-maximum.connpass.com/event/325174/ #MaximumCup2024

Image
4
Reply
Read more on Twitter

夏休みに入ったので問題準備を追い込んだ。
なんか MOFE のベータ版の動的得点機能がうまく動かないのでいろいろ試行錯誤してみたり、 kichi にバグ報告したりしていた。
とりあえず何とか問題を作り終えて、 GitHub から MOFE に移植した。

中旬

テスターに暫定コンテストを走ってもらって、修正案をいくつか出してもらった。
m_99 が解法や問題の齟齬などについて事前にテストしてくれていたところに、外部テスターの目線を加えることで問題の難易度感や質を向上させることができて、とても助かった。
特に大きな変更点はなかったので、問題案はそのままでいくことにした。

下旬

ネームプレートを作った。
システムとしては去年の使いまわし。

台風によりすべてが狂わされた。
とりあえず延期も視野に入れて、アンケートを取った。
そこから数日間気象庁とかウェザーニュースとかの情報を毎時間監視して、めちゃくちゃ台風がゆっくり来そうということで最終的には開催することに決定した。

埼玉大学 プログラミングサークル Maximum
埼玉大学 プログラミングサークル Maximum
@Maximum03400346
·Follow

【8/31 開催予定の #MaximumCup2024 について】 台風 10 号の影響により延期を検討していましたが、 8/31 関東への影響は小さいと判断し予定通り開催します。 オンサイト枠はまだまだ空いているので、これから参加登録していただくことも可能です。 無理のない範囲で、楽しみにお待ちしております。 ↓

13
Reply
Read 1 reply

開催

準備

めちゃくちゃ早めに会場に向かった。
みんなには 10 時くらいに来てね～って言っておいたけど 9 時着。
現代表が部屋借り処理をしてくれる予定だったが、寝坊したとのこと (あの...) なので、急遽自分が行って部屋を借りた。
みんな遅刻します～って連絡が来て、まあいっか... になった (ちゃんと来てほしかったなぁ)

あといろいろ手違いでホワイトボードが支給されたので、その場の発案でメッセージボードが作られた (なんか書こうと思ったのに書き忘れた...)
好評だったので来年度もやるかも？

肝心のネームプレート持ってる人も遅刻します～とのことだったので、とりあえずデータは印刷だけして、後で詰めればいいや～とした。
結局開場時間ギリギリに来たので、来た人の目の前でネームプレートを詰めることになった。

事前説明

「皆来てくれてありがとう～」とか、会場での注意事項を話したりとか、 MOFE の参加登録パスワードの説明したりとかした。
いろいろ説明したら、今年度は作問側なので運営部屋に移動し、実況の準備をした。

すると、参加登録できないよ～との声が多く上がったらしく、様子を見に行くことに。
みんな Internal Server Error が出ているので、 kichi に相談し、通話しながらトラブルシューティングしてた。
原因は DB のカラム制約によるエラーだったらしく、よくあるやつ... と思いながら会場対応をした。
開始予定時刻に間に合いそうになく、結局 30 分遅れで開始することになった。
まあ会場の雰囲気的にもう少し早くできたかも...？

コンテスト

コンテスト中は実況をしつつ、 clar が投げられたらその対応をする予定でいた。
実況は from:a01sa01to until:2024-09-01 で検索すると出てきます (24 ツイートあるので載せません)。
裏側では全員の提出が見れるので、「お！この人出した！」とか「トラップ引っかかってますねぇ」とか言って楽しんでました。
clar は実は投げられなかったので、良かったと思うと同時に投げられたらどんな表示になってたんだろうと気になってもいた。

問題の背景・裏話でもしましょうかね (ほぼ解説スライドに載ってるけど...)

A

まあ 1 問目は簡単なのがいいよね～ということで、ただただ max をとればいいだけの問題。
読解がめんどくさかったかも。
埼玉大学は大雨の時に「埼玉ヴェネツィア大学」と揶揄されることで有名 (?) です。

B

はい、問題だけ見ると難しいけど、制約見ると実はやるだけな問題。
前述した通り、実は Maximum の Discord の作問チャンネルにあった問題案をほぼそのまま使ってたりする (の割に Maximum 勢遅くないですか。。。)
最初は XOR ではなく総和を求めよ、にしてたんですがそれだと別解を簡単に思いつけちゃうよね、ということで XOR に変更。
誤読してそうだな～という提出もいくつか見受けられたんですが、サンプルでは落とせてなかった、すみません。
雑貨の 3COINS をテレビで見たときに原案が浮かんだので、タイトルはそのまま Three Coins です。
ちなみに AGC050 B - Three Coins とはまったくの無関係です。

C

ペナ率から見てこっちがトラップだったかもしれない。
というのも「良い彩色」の定義として「使われない色が存在しない」という定義になっているのを見落とした人が多かった気がする。

この問題、自分がグラフ頂点彩色の論文を適当に漁っているときに出てきた問題で、彩色数が 2 のときは自明と書かれていたのでそのまま出しました。
が、そのままだと自明すぎた (連結成分チェックしたら異なる部分を変えていくだけ) だったので「使われない色が存在しない」条件を追加しておきました。

問題形式について: 最初、出力は操作回数のみを出力させればいいやになってたんですが、自明すぎた + MOFE に動的点数設定機能があった (= ヒュ向けなんだろうけど、アルゴだと「答えが複数ある場合はどれでも良い」ができる) ので操作列も出力してねにしました。
ベータ版の機能だったので一応問題文に注意書きもした。

D

through が作った問題。彼は天才構築が好きなのでこういう問題が出てきた (たぶん)
同じ高さの地点は完全グラフにして結ぶのがポイント。自分は気づきませんでした。
A 以外のほかの問題に部分点があったので、「部分点あったほうがいい？」と聞かれたので、 H+W−2H + W - 2 を出力するだけの部分点をつけてもらうことにした。
意外とこの部分点に助けられた (?) 人も多かったみたい。

E

電車で寝てるときに、顔が左右に倒れて隣の人も気まずく同じ方向に倒れることがあるよねーというのを問題にした。
最初 DP で解けるんかな～とか思ってたんですが、実は (自分が想定していた) DP だと全然ダメで数学やるだけ... という問題でした。
N≤105N \le 10^5 は DP の痕跡ですが意味ない部分点でした 🤪
O(N)O(N) 解法は懇親会のときにいろいろ教えてもらいました。

F

これは ABC での誤読から生まれた問題です。
木のパス上の辺重み最小値を求めるアルゴリズム (なんでも) を知ってれば、ただただやるだけのやつ。

G

through 作問。
もともと制約は L,R≤105L, R \le 10^5 の l,r≤103l, r \le 10^3 くらいだった (気がする) んですが、 Python だと bitset どうなん？ということで l,rl, r が 6060 になって、これ座圧すればいいじゃんということで L,R≤109L, R \le 10^9 になりました。

H

これも through 作問。
最初は部分点 1 だけで再帰やるだけだった (はず) なんですが、 Grundy 数を見ると良さそうということで HH が大きくなり、さらに答えを観察すると規則性があるんじゃね！？ということでさらに大きくなりました。
規則性を見つけたのはいいが証明が大変だよ～と嘆いていました

I

ボス枠なんか生えないかな～ということで調べたところ、双対を目にしたので問題にした。
仮に MST を双対に落とし込んでみたけど、 m_99 にそれは嘘だと言われ、さらにいろいろ考えてもまた嘘だと言われ、いろいろやっているうちにトポロジカルソートを双対に落とし込めばうまくいくんじゃね！？ということで書いてみたら通ったので問題にした。
もともとトポロジカル順での index を決める感じの問題だったけど、辺に重みがついたりいろいろしているうちにこの形になりました。
t,ct, c の制約はもともと 10910^9 にしておくつもりだったんですが、 Python で試してみたところ答えがオーバーフローしてしまっていることに気づき 10410^4 になりました。

運営部屋で、これ重み 0 だったら閉路あってもいいからもっと難しくなったんじゃね？というのを m_99 に言われた。

終了 + 解説

終了後、急いで解説スライドの AC 数とか FA とかの部分を更新して、 GitHub に上げ、リポジトリを a01sa01to から Maximum に移動し、 Public にした。
一応後日アップロード予定とか書いておいたけど、我ながら 15 分でよくやったよ...

その後解説。
connpass だと 15 分で終了予定とか書いてあったんですが、まあ当然終わるわけがなく。

懇親会 + 片付け

懇親会はいつものように、いろいろ話していた。
今年はいろんな輪に参加できた気がする！

なんか数え上げがあったらうれしいな～みたいな話があったので、来年度は出すかぁと思ってたりする。

埼玉大学 プログラミングサークル Maximum
埼玉大学 プログラミングサークル Maximum
@Maximum03400346
·Follow

#MaximumCup2024 無事全て終了しました！ 足元も悪い中お集まりいただいた皆様、ありがとうございました！ メッセージボードにもたくさんのメッセージが集まりました😊 是非次回(は未定ですが…)のMaximumCupにもご参加していただければと思います！ 本日は本当にありがとうございました！

Image
12
Reply
Read more on Twitter

まとめ

初 Writer をできて、いろいろ反省点が残ったけど、全体的に楽しかった + 楽しんでもらえたようでよかったです！
リポジトリはもっと CI 効率化できたし (めんどくさかったのでしなかった)、 70 人収容可能だったのにそこまで来なかったり、いろいろ反省点はあるけど、次回に活かせるようにしていきたいです。

まだまだ upsolve もできるのでぜひ挑戦してみてください！
https://mofecoder.com/contests/maximum_cup_2024

今回アンケートも取ったんですが、 Maximum 知名度ないなぁになってます　かなしい 😢
次回 (あれば...) はもっと多くの人に参加してもらえるようにしたいですね。

来年度も開催できるのかわかりませんが、その時にはぜひ参加してください！
再び埼玉トラップを用意して待ってます！ (のつもり)