夏日・真夏日・猛暑日

作問・解説・精進メモ

yukicoder で共同コンテストをやった話

はじめに

yukicoder contest 297 で aspi(@aspirator_) とコンテストを開きました。

実は同校同期の 6 人（NatsubiSogan, aspi, AndrewK, Forested, kozy, seven_three）での共同作問だったのですが、原案として使うことになったのは我々 2 人のものだけでした。考察・準備等の一部は Writer 以外の 4 人にも協力してもらいました。

★3.5 以上の問題がなかなか生えずずっと唸っていたのですが、今回このようにしてコンテストを開催することが出来、嬉しい限りです。（aspi のおかげです）

以下ポエムです。読む価値はありません。

振り返り

原案

すべて設定から生やしました。解法を指定して面白い問題を作れるほどの実力はありません…

数え上げと構築しかないのも恐らくそのせいです（デ/ア 問題は…作れない！）

どの問題もそこそこ綺麗にまとまるようになっていますが、恐らくたまたまです（まとまらない問題を解けていないだけかもしれませんが）

準備

まあまあ楽しいので、A~G のケース生成、解説執筆などはほとんど私がやっています。

特に語ることはないですが、Validation における testlib.h の使い方をある程度心得たのは、かなりの収穫という感じです。制約違反や、末尾に余分な空白がある、などの不備はなかったので、よかった。

本番

祈るような思いでコンテストページを眺めていました。

全問題、順当な時間で FA が出て一安心していたのですが、その後逆転が発生したり、A と B の崖がすごいことになったり……と大変でした。

Clar は全体で一件のみでした。H の「単調増加」についての質問でしたが、$a_1,a_2,\cdots,a_N$ が相異なるというのは問題文の方にも書いておいた方がよかったな……と反省しています。

それぞれの問題について（Natsubi 担当分）

B: Simple Combinatorics (★1.5 -> ★2.5)

ご　め　ん　な　さ　い

適当な設定を考えていたら生えた問題です。

「Simple という文字列だけで嫌な予感がしてしまいますが、実際は簡単枠ですね、AtCoder で出たら茶 diff 下位かな」……と思っていたらかなりの虐殺問になっていました。やっぱり Simple Math の呪いかな……（いいえ）

aspi は「これが 1.5 はヤバいだろ」と最後まで主張していたので、本当にごめんなさい

主客転倒入門の問題みたいな感じがあります（本当か？）

自戒も込めてですが、自作問の考察過程で主客転倒に気づくと、そこから問題が超自明にしか見えなくなるので、気を付けましょう。

C: Diversity (★2)

塾で鳩ノ巣原理の話題が出てきて、「グラフの次数の種類数は頂点数とは一致し得ない」みたいなのを示す問題を出されたので、「じゃあ種類数最大のグラフを構築させようかな～」みたいに考えていたら、出来ました。

かなりの有名事実だとは思うんですが、具体的な構築方法まで言及しているものは見つからなかったので出した、という感じです（まあ知ってたら考察をだいぶスキップ出来るんですが）

D: Zigzag Sum (★2.5)

ふと、ジグザグを数え上げてみたいという衝動に駆られました。

「こんなん数えられるか！NP 困難だろ」みたいな見た目をしているけれど、こういった総和計算になるとめちゃくちゃ綺麗にまとまる、みたいなやつです。

数え上げ問題の答えが綺麗な二項係数の式に落とし込めた時の喜びを共有するための問題です。fav が 5 ついているので少しよかった。

若干発想が難しそうなので、★2.5 ということになっています。

Wolfram に投げて通した人が一定数いたみたいで、そこはかなり反省です。（こっちで確認したときは出てこなかったはずなんですが……）

Forested が（なぜか）解けなかったため、★3.5 ということになりかけたヤバイ過去を持ちます。（もしあのまま出してたらこの問題まで大炎上していた……）

G: +/- Tree (★3)

元ネタ（？）は +/- Rectangle です

Forested が天才をして、いくつかのパターンでの構築方法を示してくれましたが、その他の場合の構成/証明が出来ず、長いこと作問サーバーに眠っていました。

その後どうやっても証明が出来なかったため、そのままテスターさんを募集することになりました。テスターの nok0 さんには感謝してもしきれません…（本当にありがとうございます）

非想定がたくさん出てきて驚いたんですが、その中に嘘解法もいくつか紛れ込んでいたみたいです（！？）どなたか強いケースの作り方を教えてください……（今回に関しては、小さいケースを大量に入れておけばよかったみたいですが）

それぞれの問題について（aspi 担当分）

A: Party Location (★1)

1 問目なので簡単です。比を取る嘘解法を誘発するためにサンプルが意地悪になっているみたいです。意地悪すぎ。何人か引っかかっていて、aspi が喜んでいました（えぇ……）

E: Playing Musical Chairs Alone (★2.5)

典型だけど難しいだろ……と思っていたらめちゃくちゃ通されました。Ｄ より遥かに難しいと思っていました。どうしてこんなことに。

「行列累乗を ★2.5 で出していいのか」で割と議論が起こりました。結果的に出しちゃってますが、流石にこのくらいが妥当かなという感じの結果になりました。

$K$ の制約は「行列累乗を制約エスパーされたくない」という aspi の意思によるものです。

制約、かなりのところまで上げられるみたいです。びっくり（解法をちゃんと理解していないので、誰かブログに書いてくれないかな……などと）

F：Unfairness (★2.5)

このセットの aspi 問の中で一番面白いと思います。

ナップサック問題への帰着、天才的過ぎませんか？という感じが。aspi と得意分野が違いすぎる…

貪欲法的考察をベースにしているため、正当性がだいぶ不安でしたが、本人がちゃんと証明してくれたので、感謝です。

H：Upward Mobility (★4)

なんですかこれ？笑

私の理解が及ぶ領域ではありません。全然分かりません。なんですかこれ？（2 回目）

全体 tester の Nachia さんがすごい解法を編み出していました（100ms 切るとは……）。

意味が分からないので手も一切付けていません。嗚呼恐ろしや。世界の闇の部分を垣間見ました。

今年の JOI 春で既出だったらしいです（完全に想定外でした）が、彼はこれを春合宿前に作問していたので、もしかしたら爆破できたってことも……（いいえ）

セット全体について

6 問目くらいまでは標準的な ABC と同じかそれより簡単くらいの水準だと思っていました（過去形）

diff だけ見ると ARC でもいいかもというレベルですね、どうして……

B が想像以上に虐殺問になってて、本当にごめんなさい

G がけっこう重い枠です。H はとにかくめちゃくちゃ重いと思います。

ちなみに 8 問中 6 問が入力定数個なんですよね、な～んでだ？

おわりに

いかがでしたでしょうか。（ブログ定型文）

お楽しみいただけたのならば嬉しい限りです。

致命的な不備こそなかったものの、反省点がかなり残るコンテストとなってしまいました。

腕を上げて、必ず帰ってきます。とりあえず、次回は 技術室奥プロコン #6 でお会いしましょう。

ご参加下さった皆さん、そして tester の皆さん、本当にありがとうございました！

おまけ

これになってほしい