Prime & Divisor Contest 001 開催記

milkcoffee さんと共同 writer で「Prime & Divisor Contest 001」を開催しました。MMNMM さんに全体 tester をやっていただきました。参加していただいた皆様、問題を解いてくださった皆様、mojacoder 様、関係者各位、誠にありがとうございました!

mojacoder.app

想定以上に参加していただけて嬉しい半面、ジャッジが重くなってしまい途中から順位表が見られなくなってしまいました。ここは申し訳なかったです。

準備は約 1 か月前から始まりました。自分が D 問題 (Coprime Path) の原案を投げたのが 7 月 23 日で、そのあたりからになります(毎日作業していたわけではないです)。あらかじめ決められた出題分野の問題を狙って作るのは意外と難しく、特に素数・約数という分野ではそれが顕著なのかなと感じました。

自分は作問とテストケース作成の経験は少しありましたが(mojacoder に投げてる問題たち)、writer/tester をやるのは今回が初めてでした。至らない点があればごめんなさい。

文章にまとめるのが面倒になってきたので、箇条書きでつらつら書きたいと思います。開催記と言いながらメモ書きみたいになってしまいました…

  • なぜやろうと思ったか

    • 本コンテストは元々 milkcoffee さんが温めていた企画の一つで、それに参加させていただいた形になります
    • 素数・約数などの整数論の分野は元々苦手でした(今はたぶんレート相応くらいになったと思います)
    • 苦手克服のために素数・約数に関する問題を以前作問していました(いくつかは mojacoder に投げてます)
    • その延長としてチャレンジしたいと思い、milkcoffee さんに声をかけて準備が始まったという経緯です
    • 原案作成・類題調査・テストケース作成・解説作成などの作問作業を通して、素数・約数に対する認識が「数学の不思議な概念」から「正の整数の中で定義できる、様々な面白い性質を持った DAG」くらいの認識に変わりました
  • 役割分担

    • milkcoffee さん
      • コンテスト企画者
      • writer は主に ad-hoc 問題を担当
      • コンテスト全体の管理
    • mts (自分)
      • writer は主に典型問題を担当
      • Python 想定解コードを担当
      • 嘘解法もいっぱい書きました
    • MMNMM さん
      • 全体 tester をやってくださいました(詳細は後述します)
      • 天才
      • 天才(大事なことなので二回言いました)
  • 推定 diff

    • あくまで自分の推定です(milkcoffee さんも大体同じくらいでした)

    • 問題名 点数 推定 diff コメント
      A. Odd Even Divisor 200 easy 強いて言えば 20~30 くらい
      B. Div All 300 100~200 もっと低いかも
      C. LCM Knapsack 300 400~600 1 年前なら 600~800 かなあ
      D. Coprime Path 400 1000~1200 個人差がありそう
      E. 3 perf Number 400 1000~1200 個人差がありそう
      F. Rich Primer 500 1200~1400 もっと低いかも
      G. Pairwise Coprime Segments 500 1200~1400 実装が大変なのでもっと高いかも
      H. Prime Collector 600 1600~1800 1800 を超えることはないと思ってます
  • 問題ごとのコメント

    • A. Odd Even Divisor

      • 原案・writer をしました
      • 「for 文 + if 文 + 偶奇 + 約数」です
      • easy 枠ということでサクッと作りましたが、特に怖いところもなくやるだけなので、そんなに悪い問題ではないんじゃないかと思います
      •  O(N \log N) で解けることは多くの人が気付けると思いますが、 O(N \log \log N)  O(N) でも解けることを MMNMM さんに教えてもらいました。まだ理解できていません…
    • B. Div All

      • tester をしました
      • これは一目で解けました。最大公約数は便利です
      •  N \leq 10^{5}, A_{i} \leq 10^{12} なので有力な嘘解法はなさそうと思いました
      • 既出な気がしましたが、同じものは見つけられなかったのでセーフでした
    • C. LCM Knapsack

      • 原案・writer をしました
      • B・D・E・F の原案が出ている状況で全体バランス的に「最小公倍数と DP を入れたいな」と思ったのが作問のモチベーションです。合体させたら丁度良さそうなのが作れました
      • ド典型ですが結構好きな問題です
        • 恐らくド典型すぎて AtCoder だったら出せない気がします
      • 既出な気がしましたが、意外と見つかりませんでした
        • とはいえナップサック問題は有名問題なので、ナップサック問題をまだ勉強していなかった灰〜茶コーダーさんの中にはその場で勉強しながら解けた人もいたのではないでしょうか
      • MMNMM さんに  O(NW) 解法を教えてもらいましたが、まだ理解できていません…
    • D. Coprime Path

      • 原案・writer をしました
      • このコンテスト向けに自分が最初に作問した問題です
      • 木 DP + bit DP の問題を作ろうとしたら失敗して(?)、この問題が出来上がりました
      •  O(N^{3}) の愚直解が落ちることは確認しましたが、定数倍高速化の神がいたら通されるかもしれません
      • HL 分解などの別解も色々あり、いろいろ考察しがいのある問題だと思います。この問題を最初に作れて良いスタートを切れました
      • テストケース作成が大変でした。木の問題に含めるべき典型的なグラフを色々盛り込みました。 \mathrm{gcd} の計算量を考慮して色んなケースを作りました
      • 最悪ケース  O(N^{2} \log A_{\max}) の作り方がずっと分からなくて、不可能なんじゃないかと思っていたのですが(実は解説にも元々そう書いてました)、MMNMM さんに速攻で思い付いてもらって非常に助かりました(このコンテスト全体で一番感動したのがこれかもしれません)
      • 二乗の木 DP でも解けることを MMNMM さんに教えてもらいましたが、まだ理解できていません… ABC のあの問題をちゃんと upsolve しておけばよかった…
    • E. 3 perf Number

      • tester をしました
      • 自分は F 問題よりこれの方が時間かかりました
      • ad-hoc ですが結論が綺麗で感動しました
      • こういう問題を作れるようになりたいですね…
      • 全完するためにはこの問題をどれだけ早く通すかが勝負所の一つだと思います。たぶん時間泥棒です
      • tester として解いたので証明寄りで考察していましたが、そうでなければ早々に実験する気がします
      • 自分は調和級数が発散することの証明と同じ要領で証明しました(本質的には milkcoffee さんの解説と同じだと思います)
        • 約数  \frac{N}{2} を使わないことにすると、最大ケース  \frac{N}{3} + \frac{N}{4} + \frac{N}{5} の和が  N より小さくなるので、 \frac{N}{2} は必要、みたいな感じで順次 3 つの約数を確定させることができます
      • 自分のゴリ押し解法が通ってしまったので制約及びテストケースが強化されました(オフレコで)
        •  \sqrt{A_{\max}} 以下の素数リストの埋め込み
        • 素数リストを用いた高速な素因数分解
        • 約数列挙をして愚直に三完数を判定(三重ループを回して適宜 break)
      •  O(N^{1/4}) 素因数分解で殴られる可能性がありそうだけど、対策は諦めようという話をしました
    • F. Rich Primer

      • tester をしました
      • 個人的には考察しやすくて割とすぐに解けました
      • 倍数の感覚と制約の謎解きがポイントになる考察メインの問題だと思います
      • 他の問題との相対評価も加味して 500 点になりましたが、ARC なら 400 点あたりに出て緑 diff になりそうな感じもします
      •  \lfloor \frac{(A-1)}{p^{n}} \rfloor \lt \lfloor \frac{B}{p^{n}} \rfloor のチェックで  p^{n} がオーバーフローしていても実は通ってしまうので、それを咎めるテストケースを作ることを考えましたが、探すのも大変で本質部分でもないので諦めようという話をしました(たぶん探索計算しないといけなくて、そもそも見つからないかもしれない)
    • G. Pairwise Coprime Segments

      • 原案は milkcoffee さんと一緒に作りました
      • tester をしました
      • milkcoffee さんの「pairwise coprime の判定を素因数について鳩ノ巣原理を使って解かせる問題を作りたい」から始まって、二人であれこれ考えた結果、区間クエリにすればいけそうということを自分が思い付いて何とか実現しました。かなりお気に入りの問題です
      • C++ なら素因数の登場数の累積和を持っても何とか間に合います
      • MMNMM さんが  O(\pi (A_{\max})) 部分を落としていて驚きました。鳩ノ巣原理さん「えっ…」
    • H. Prime Collector

      • 原案・writer をしました
      • 自信作です!!!
      • 素数とフローの問題を作りたい」という気持ちから始まり、適当にお絵描きしていたら偶然思い付きました(まさに天啓)。既出な気もしましたが特に見つからなかったので良かったです
      • 6 問 ABC の易しめの F 問題(青 diff くらい)のイメージです
      • 自分が調べた限りでは AtCoder と yukicoder に出た最小辺被覆の問題はこの問題(8 年以上前!)しかなかったので、本問の価値は高いのではないかと思っています
      • 本当は TL を引き上げて  N \leq 10^{5} くらいにしてフローとバレにくいようにしたかったのですが、mojacoder の仕様上 TL は変更できなかったので断念しました
      • 原案の時点で問題文は「重複を許さない集合  P, Q があって最初は空。1 回の操作で  i を選んで集合  Q に入れ、同時に  A_{i} の素因数を集合  P に入れる。それぞれ全種類を入れるための最小操作回数は?」という感じだったのですが、何だかストレートで無機質な感じがして本コンテストのボス問としては面白味に欠けると思ったので、後付けですが楽しめそうな問題設定を与えました(ギルドとかクエストとか)。ここは我ながら上手く書けたと思っています
        • 非本質な情報をあえて加えた形になるので、邪道と言えるかもしれません… 集合に入れる操作が直接的すぎたので、それを避ける問題設定にして考察ステップを若干増やしたかったという狙いもあります
      • 自分の実力を超えていることもあり、テストケース作成と解説作成が本当に大変でした。しっかり時間をかけることで手を抜くことなく最後までやり切れたのでよかったです
      • writer 作業初期では高速素因数分解も要請する制約を目指していたのですが、どうにも上手く作れなかったので断念しました。そんな都合よくあれこれ詰め込めるものではないですね…
  • 全体 tester さんについて (MMNMM さん)

    • コンテストまで残り 2 日間しかない急な募集にも拘らず引き受けてくださいました
    • めちゃくちゃスピーディーかつ丁寧にチェックしてくださり本当に頭が上がらないです
    • ここまでの作業を無償かつ迅速正確にやっていただいたことに少し罪悪感を感じてしまいました… そのくらい凄まじいものがありました
      • 確か 20 分くらいで 7 問目までの解き方を一気に見抜かれました(早すぎる)
      • 気付けば tester 募集してから 24 時間以内に全ての tester 作業が完了していました
      • コンテスト本番まで時間が差し迫っているので配慮してくださったのだと思います。大変感謝しているとともに負担をかけてしまって申し訳ない気持ちも… 募集するならもっと早くにするべきでした
      • 時間的にも体力的にも、たった半日で 8 問を完璧に tester するのは暖色コーダーでも結構大変なんじゃないかと思っていて、MMNMM さんがいかに凄腕であるかということを実感しました
    • 特に下記について非常に勉強になりました
      1. 一文字ずつの入力チェック(自分は C++/Python で読み込み + assert で制約チェック、で全て確認した気になっていました…)
      2. 論理的・数学的な文章の書き方
      3. 想定解より効率的な解法
    • 大変良くしてもらったので何か恩返ししたいなーと思いつつ、今できることはコンテストの準備を完全なものに近づけることくらいなので、いただいたアドバイスを最大限に活かして、出来る限り全て対応する努力をしようと心がけていました(二乗の木 DP などは実力不足もあり自分自身での確認が間に合いませんでした)
      • とりあえず、早く黄色になりたいと思いました
  • いつもお世話になっている某暖色コーダーさん
    • いつもお世話になっています(いつもお世話になっているので)
    • 準備期間の初期に D 問題と H 問題 の原案とテストケース作成についてコメントいただきました
    • 原案を投げたらどちらも数分で解かれました(H 問題が瞬殺されたのは悔しい)
    • D 問題
      • 「ランダムに頂点を選んでグラフを生成すると確率的に直径が短くなると思われるので、もし気になるなら適当な長さのパスグラフを作ってから頂点を適当に繋げていくケースを入れると良い」ということを教えてもらい、実際にそのケースもいくつか入れました
      • binary gcd というのを教えてもらいました(これ賢い)
    • H 問題
      • 自分の実力を超えていたので、問題として成立していることが分かっただけでも助かりました
      • 時間ギリギリまで乱択する嘘解法を教えてもらいました。この嘘解法が落ちることも確かめながらテストケースを作りました
  • 反省点
    • 作問するにあたりこの記事は参考にしていたのですが、yukicoder に置いてある便利なチェックリストの存在にコンテスト前日に気が付いて、これを使っておけば効率的かつ正確な準備ができたのではと思いました(とはいえ、ほぼクリアしていたようで、MMNMM さんの tester 作業によって細部が仕上がったので、今回は特に問題なかったと思っています)
    • コンテスト 3 日前の夜遅くに思い付きで「できれば黄色以上の tester さんを募集した方がいいのでは」と思って募集したのですが、tester さんを募集すること自体の判断は良かったものの、もっと早くに募集をかけて計画的にやるべきでした(tester さんに短期集中の作業を強いる負担をかけてしまいました。それを分かっていながら引き受けてくださった MMNMM さんには本当に頭が上がりません)
    • testlib.h を MMNMM さんに教えてもらって初めて知りました。これを知らずに writer 作業していたのは世間知らずだったなと思いました
    • 問題文だけでなく解説にも細かいところで甘さがあり、MMNMM さんの指摘によって色々修正しました。ここは場数を踏んで経験していくしかないのかなと思いつつ、日頃から意識していきたいと感じさせられました
    • 同じ日に writer 作業と精進をバランスよく行うことが全くできませんでした(実質どちらかしかできなかった)。なんか頭の使い方が違う気がしていて、一方をやるともう一方をやる気にならないというか、まあ半分くらいは言い訳ですね… writer 作業はコンテスト準備が間に合えばいつやってもいいんですが、精進は小まめにやらないとすぐに実力が下がる感覚があるので、毎日できるように writer 作業との折り合いを付けられるようにしていきたいです(しばらく writer 作業を封印して年内に黄色を目指すことに集中しようと思っています)
  • その他
    • mojacoder は yukicoder よりもゆるふわで作問やコンテスト主催ができる、みたいな印象を抱いていたので、かなり本格的な作り込みをしたコンテストを開催したことでハードルを上げてしまったのかもしれない?みたいなことを少し思いました(自意識過剰かもしれません)