MojaCoder でコンテストを開催しました！【MRC002】
お久しぶりです。riano_ です。
このたび、MojaCoder という自作問題を投稿できるサイトで、
milkcoffee さんと共同でコンテストを開催しました。
ご参加いただいた方、本当にありがとうございます。
せっかくなので感想を書いてみることにします。
■ 各問題の解説まとめ
以下のリンクの通りです。ご質問は twitter までお願いします。
■ 小学生並みの感想
MojaCoder でコンテストを開催するのは 3 回目ですが、
毎回本当に楽しませてもらっています。
多くの方にご参加いただけて、嬉しい限りです。
本当にありがとうございます。
ちなみに、MRC ( milkcoffee and riano Contest ) の開催は 2 回目ですが、
コンテスト中に順位表を眺めながら通話するのが恒例となっています。
自分の作った問題を解いてもらえるのは本当に楽しいですね。
■ riano_ 作問の裏話（注：ネタバレを含みます）
Never Surrender
bit DP の問題です。
制約から大体解法の検討はつくと思うのですが、
（そういう意味では今回のセットで一番取っ掛かりやすい問題かもしれません）
最後に残る全域木のなかで主要な部分だけを自由に決めていい、
というところがちょっと嬉しい気分になったので出題してみました。
One-way and Once a Way
「一筆書き」をテーマに作ってみました。
面白そうなテーマがあると、
問題を解くやる気が上がる気がするのは僕だけでしょうか。
最初は別のところに使おうかと思っていたのですが、
期限までに解けなかったのでこちらでの出題としました。
（僕はいつも問題を適当に思いついて、解けたら作問ということにしています）
問題の内容としては、
ARC に似たような問題（というか部分問題？）があるのですが、
それに気づくこと自体も個人的にはかなり時間を要しました。
それを前提としてさらに丁寧に場合分けして帰納的に求めていきます。
正直めちゃくちゃ難しいと思います。解けた人はすごいです。
Binary-Search Game
個人的に大好きな問題ができました。
「最適に行動したときの確率」という
一見どう手を付けたらよいのかわからないものを聞いているのですが、
適切な言い換えと、最善手の決め打ちをすると解法は実にシンプルです。
実は最初は「 N 枚から偽物を確実に特定するために何円必要ですか」
という問題のつもりだったのですが、
途中でなぜか「勝率の最大化」という発想が降ってきました。
そして、解いてみると実は全く同じ問題になってしまって本当に驚きました。
こういう「気づいたときの快感」みたいなものを共有できるのが
作問・コンテスト開催の何よりいいところだと思います。
（相当な難問になったので、何人に共感してもらえるかはさておき…）
■ テスターをした感想
milkcoffee さんの問題、面白いんですよね。
今回も、一足先に楽しませていただきました。
Gears は簡単枠ではありますが、一瞬累積積的なものが頭をよぎります。
ちゃんと気づけるとほっとする問題でした。
Long Digits Number も、答えがとてもきれいで面白かったです。
最初10のままやろうとして、1の位で場合分けを生じさせてしまい、
想定解を聞いてやや敗北感を感じました。
そして、サンプルがおしゃれです。
「C0FFEE」がちょうど10で割り切れるの、いい感じすぎませんか？
ちなみに Blue と Cyan に気づいた方はどれくらいいるでしょうか。
A+BC、これは難しかったです。
N*sqrt(N) の全探索解法がすぐに見えるのですが、
DP を工夫すると N*logN のきれいな形になります。
前者の解法や、そこから派生する嘘解法（探索範囲をいい感じに絞る）を
できるだけ落とすために制約の調整をがんばりました。
（提出欄に嘘解法作成を頑張った形跡が残っています）
想定解がきれいな問題は、解けると嬉しくていいですね。
■ コンテスト本番の感想
E が全然解かれなくてずっとひやひやしていました…
chinerist さんありがとうございます！！
部分問題が既出なので少し過小評価してしまったかもしれません。
ごめんなさい。
F は N^3 の DP が想定解なのですが、
答え埋め込みで通された方も多かったです。
正直全く想定していなかったので、なるほど頭いい！と思ってみていました。
（考察の途中で、5 乗 DP が出来るようになるのでこういうことができます）
答えになるパターンを全列挙して O(1) で通している方もいて、
完敗という気分です！
■ おわりに
ここまでお読みいただき、ありがとうございます。
MRC、楽しんでいただけたでしょうか？
実力は（ Solver としても Writer としても）まだまだではありますが、
この楽しさをみなさまと分かち合っていけるのなら、
こんなに嬉しいことはないと思います。
「解けた！を私も作りたい。」
そんな想いを運んでくれる MojaCoder と、全ての受け手への感謝を込めて。
2021.07.19 by riano
