milkcoffeeのブログ

競技プログラミングなど

【コンテスト開催記】Prime & Divisor Contest 001 【MojaCoder】

MojaCoder にて、mtsさんと共同でコンテストを開催しました!

mojacoder.app

 

こんにちは、milkcoffeeです。

前々からやろうと思っていた「素数・約数コンテスト」を

ついにMojaCoderで開催できました!

 

mts さんと共同でwriterをしました。また、MMNMMさんにtesterをしていただきました。本当にありがとうございます!

 

 

問題一覧

問題リンク集です。リンク先から解説も見れます。

★マークがついてる問題は自分が準備したもの、それ以外はmts さんが準備したものです。

A問題(200点):Odd Even Divisor

★B問題(300点):Div All

C問題(300点):LCM Knapsack

D問題(400点):Coprime Path

★E問題(400点):3 perf Number

★F問題(500点):Rich Primer

★G問題(500点):Pairwise Coprime Segments

H問題(600点):Prime Collector

企画段階

僕がTwitterで「何かのテーマに沿ったコンテストを開きたい、例えば素数約数関連のコンテストとか・・・」みたいなツイートをしたところ、mtsさんが「素数約数コン興味あります!」と声をかけてくださいました。これがキッカケです。

問題の構成なんですが、最初は6問にしようと思ってましたが、二人で問題案を出し合っていくうちに盛り上がってしまい(?)気づいたら10問くらいの問題案がそろっていたので、少し削って8問構成になりました。

お互いが持ってきた問題案をそのまま出すだけでなく、二人で少しずつ練りあって一つの問題を作り上げたのもかなり楽しい経験でした(今回のG問題が特にそれです)

コンテスト準備

8問の準備はめちゃくちゃ大変でした!!特にテストケース作成は力を入れて頑張りました。特に、mts さんのテストケースに対する視点が鋭くて、「こういうケースを入れたらこういう解法を落とせる」みたいなアドバイスをたくさんいただきました。

強いケースを増やしていくと、自分の問題が強くなっていくような気がしますね。

mts さんとお互いで準備した問題をテスターし合ってもう大丈夫!となったんですが、念のため(かなり直前になって)全体テスターを MMNMM さんにお願いすることになりました。直前のお願いになって申し訳なかったです・・・

もう大丈夫と思ってた問題も、テスターさんに鋭いご指摘をたくさんいただきました!流石暖色・・・

ちなみに直前に全問題を通して解いたところ、71分+3ペナでした。

各問題について

A問題(200点):Odd Even Divisor

約数コンのA問題って感じですよね。

直前に解いたときに1ペナを出しました。

これ、テスターさんによると O(N) で解けるらしいです・・・

★B問題(300点):Div All

公約数が何個ありますか、という問題。

塾講師のアルバイトで生徒に公約数教えてたら思いついた問題です。

普通にぱっと見難しいんじゃないかと思います。

これも1ペナを出しました。

C問題(300点):LCM Knapsack

ナップサック問題と約数問題の融合で、すごく教育的な問題だと思います。

テスターさんによると O(NW) で解けるらしい・・・?

D問題(400点):Coprime Path

シンプルだけど面白いです。

解けてみると単純なんですが、一瞬めっちゃ難しいことをしてしまいそうになります。

初見の時は普通に悩みました。

二乗の木DPでも解けるらしい?

★E問題(400点):3 perf Number

O(1) のギャグ問題ですが、実は一番の自信作です!!!

問題文にもありますが、完全数の定義を少し変えたらどうなるのか考えていたらこの問題が出来ました。

実験したら気づきやすいけど証明は難しいよな・・・という感じで、難易度推定が難しいです。もしかしたらいっぱい解かれるかも?

★F問題(500点):Rich Primer

この問題だけ唯一、このコンテストの企画が始まる前から出来ていました。

いつぞやのABCに「B-A≤72」みたいな制約があっておもしろ~と思い、その逆(逆?)の制約の問題を作りたくなったのが最初です。

制約の理由を考えると解きやすくなりそう

★G問題(500点):Pairwise Coprime Segments

準備したのは自分ですが、問題設定はほぼ mts さんが考えてくれました。

最初に僕が「鳩ノ巣原理を使った問題を作りたい」と言って、なんとかして鳩ノ巣原理を使わせる問題を作ろうと二人で考えて出来ました。

なんとか嘘解法を通されないようにテストケースを頑張って強くしました。mts さんがかなり強いテストケースを考えてくれました。WA出たらmtsさんを恨んでください。

実装が大変・・・

H問題(600点):Prime Collector

mts さんが考えてくれたボス問、これがどれくらい解かれるのか気になります。

これは是非自力で解いてみてほしいです!

素数約数と他のアルゴリズムを融合させるのが上手すぎます。

結果

f:id:milkcoffeen:20210827215845p:plain

MojaCoder の順位表が重くて見れなくなっていたので、mts さんがスプレッドシートに手打ちで順位表を作成してくださいました!

> PDC001_暫定順位表

合計参加者94人!全完達成者20人!

本当にありがとうございます!!! 

 

1位:sansen さん

2位:PCTp さん

3位:chocorusk さん

おめでとうございます!!

 

また、各問題のFAは以下のようになりました。おめでとうございます!

A: [01:28] ir_1st_vil さん

B: [01:00] tada72 さん

C: [05:20] emthrm さん

D: [10:24] sansen さん

E: [07:35] chocorusk さん

F: [16:50] sansen さん

G: [11:28] riano さん

H: [12:15] Nachia さん

 

コンテスト中の感想

開始30分で提出者数が80人近くいっていたのでビックリしました!

多くの参加本当にありがとうございます!

その後は参加者数が多すぎたためが順位表が見れなくなってしまい、実況できず・・・

MojaCoder に寄付をしてサーバー強めてもらいましょう!!

 

まとめ

8問コンテストの準備はやはりすごく大変でした。これを質を保って毎週開催してるAtCoderはやはり異常だと思います。

ただ、誰かと一緒に問題を考えたり、嘘解法を落とすテストケースを考えたり、当日順位表を見たりするのはすごく楽しいです。コンテストを開くのは最高です。

 

また、今回一緒にwriter をしてくださった mts さんの、色んな要素を合わせた問題を作る力、様々な解法を想定する能力は本当に凄かったです。

直前なのにtesterを引き受けてくださった MMNMM さんも本当にありがとうございます。

 

このコンテストの次回作「Prime & Divisor Contest 002」もいつかやりたいと思ってます。

 

コンテスト開催記は以上になります。

ありがとうございました!