yukicoder contest 404 の紹介
2023/09/09 開催の yukicoder contest 404 では、私 Nachia が作成した $6$ つの問題が出題されました。
私の作問ネタが乏しいので、コンテスト全体を $1$ 人で作問する形態の出題は二度とやらないと思います。（これも数年かけてネタをかき集めてなんとか作ったセットですし）
事件・反省
さて、このコンテストの F 問題はコンテスト開始時点でテスターが配置されておらず、すでに香ばしいものでしたが、あろうことかコンテスト時間に Nachia が居眠りをしてしまい、対応が一切できない状態になってしまいました。これについて、この場で状況の説明と反省をしたいと思います。
状況の説明
yukicoder でコンテストの供給が落ち込んで、予定が埋まらない状況がみられていました。私にはコンテスト用の問題原案が十分にあったので、この機会にと準備を始めました。
yukicoder slack において 8/23 10:07 から F 問題のテスターを募集しましたが、コンテスト開始までに応募はありませんでした。それ以外の問題に対してはテスターがついていました。
コンテスト当日のおよそ 20:00～25:30 の間、私は居眠りをしていました。その間に $8$ 名から F 問題に対して質問をいただいていましたが（質問の内容は公開している $2$ つと同じです。）、対応できませんでした。
これにより問題文に誤りが $2$ 箇所確認されました。このときに問題文ページに表示されている内容以外で誤りが確認された箇所はありません。題意の推測が致命的にできない形ではなかったため、多数の回答提出がありました。
反省
テスターをつけなさい、というのはまっとうな指摘の $1$ つですが、過去に $2$ 問テスター募集に失敗して出題を諦めたこともあったので、今回はとりあえず出題を決めておくことにしていました。早く出題できなければ登校がはじまってしまってまたしばらく出題できなくなるので、出題のためには仕方がなかったと考えています。
この時点で、出題ミスの発生の期待値は非常に高く、またそれに対して $1$ 人で対応する必要があるという状況であることは明白です。このときに危ないルートだったことを認識し、当日まで注意をもっと注いでいるべきでした。そうすればコンテスト時間中ずっと寝ているということはなかったはずです。今回はその認識が欠けていたのだと考えています。
そもそも yukicoder のシステムではコンテスト時間中に writer が寝ていることはコンテストの品質のためには大問題ではありますが、良い品質でコンテストを運営する責任があるというわけではないため、体調の調整と合わせた妥協点として寝る判断もあったと思います。テスターについていただいている問題ではある程度修正を経ているので事故が起きる期待値が低く、仮に事故が起こっても後悔はしなかったかもしれません。しかし今回はもっととるべき行動があったと捉えているため後悔を含めた反省としました。
解説
普通に解法ネタバレします。
A #強調# ★1.0
何でもよいので難度が低いもの、ということで基本的で汎用的な文字列処理であって、それゆえ複数のアプローチがとれる内容を選びました。
文字列中から特定の文字がある最初の位置を得るメソッドと、文字列の何文字目から何文字目までを切り出すメソッドがあればループなしで実装できます。また、 Python なら $1$ 行で AC できます。
B 一点張り ★1.5
高校入試とかでギリ出てきそうな確率の問題です。特に、操作が有限ステップで必ず終わるので数学的に扱いやすい設定です。
「 $n$ 回目のガチャを回すことになる確率」の値が等比数列をなすことは極めて身近な概念であり、この問題は実質的には等比数列の prefix sum を求める問題です。ここで等比数列の prefix sum の公式には場合分けがあるため $p=0$ に注意が必要である、というのが一応ポイントではありました。
もともと $T\times K$ の値を大きくして高速化を要求する意図もありましたが、誤差評価の厄介さが大きいため $O(TK)$ 時間を許容して、出題を優先することにしました。
C 七人カノン ★2.5
2 乗→準線形 系です。
輪唱の真ん中の人って明らかに注目度低いですよね。
$1/n$ という関係式には問題設定の面白さ以外に特に意味がありません。この例は割と露骨かもしれませんが、こういう考察のノイズになる性質を入れるといい感じで難度を上げられるのではないかという気持ちです。いつぞやに出したアドベコンの問題でもそういうのを入れました。
結果を見ると、やはり最近の競プロer は比較的データ構造が得意ですねという気持ちになりました。
D ストレートフラッシュ ★2.5
このゲーム全人類やったことあるだろ
DP とかを考えると死にます。信じて全探索を考察することで想定解にたどり着けます。
2 年前は★2 で出すつもりでしたが、最近の ABC での傾向を見るとどうも C<D っぽいという考えになり、配点を上げました。
E To DAG ★3.5
問題設定はフロー（実際、 MCF を流すと正当になる）ですが、この制約では一般的なフローアルゴリズムは遅すぎて使い物になりません。 Dinic 法の出力は正当とは限らないので、反例となるグラフを構築しテストケースに含めましたが、そのほかのランダムケースでは落ちませんでした。
想定解は、有名なアルゴリズムですし Dinic 法の実装方法を学ぶと知らないことはないものですが普段なかなか解法に現れないものなので、その点でかなり難しいです。実装も、サイクル検出しながら辺の削除を行うということで比較的難しいです。
もともとは条件を満たすグラフの存在を問題文で保証していましたが、テスターの方のアイデアを参考にして、存在しなければ -1 を出力するという説明を追加しました。
フローだと思えば非常にシンプルな問題設定です。先行研究くらいならあるのではないでしょうか。
この問題は作問過程において No.2160 みたりのDominator と関連しています。
F Dilated Water Simulation ★5.0
Water Simulation の出題時から、どうにか高速化できないか考え続けて問題にしました。
時間方向に走査する方針から抜け出すのが本当に大変でした。各容器にたまる水が周回ごとに非減少であることの証明をしようとして細かい定式化をしましたが複雑すぎてうまくできませんでした。
後ろから見ると処理できるというのは急な思い付きで、すべての小問題がすぐに解決しました。各容器に水が流れ込む量は、手順を見ると前に依存しそうですが、後ろのみに依存するんですね～。
実装もかなり難しいので高難度としては文句なしです。
結果的にどうしようもない問題児と化してしまい、どうしたものか…
後ろ $3$ 問が全部線形時間なのは偶然です。 F の制約が $L\leq 200\, 000$ なのはブラフというのと、別に $O(L \log L)$ とかの解が出てきたらそれはそれで面白いなという感じでした。