yukicoder contest 286でwriterを務めました。参加してくださった皆様ありがとうございました！
yukicoderには以前1問だけ出題したことがありますが、単独でコンテストを開催するのは今回が初めてでした。以前の出題については下の記事に書きました。
この記事では今回のコンテストについて書いていきたいと思います。
総括
7問2時間で、★4が2つあるので全完は出るかどうか微妙なラインだと思っていました。結果的には7人の方が全完でした。
以前出題したStone Skippingは今回のコンテストの一部になる予定でした。ですが初めての作問だったので様子を見るために1問だけ出すことにしました。結果、難易度判定がおかしかったことが発覚したのでコンテストも全体的に見直しを行いました。どの問題も★0.5ずつ上がったと思います。
実装例はC++,Python,Kotlinの3つを用意しようと心掛けました。途中で力尽きたのでできてない部分もあります。
途中でyukicoderにtestlibが導入されたので使うことにしました。以下のページが参考になりました。
testlibを使うということはC++という意味不明な言語を使うということです。かなり苦戦しました(普段Kotlinを使っているため)。
以下、個別の問題の感想です。
個別の問題の感想
No.1422 Social Distance in Train
テスター：Kazunさん
1問目です。四則演算とifで解けるので簡単ですが、罠があります。Nが偶数のときに2通りと答えるのが想定誤答です。これでWAを出している人が多そうです。
この問題が生まれたきっかけはAtCoder Beginner Contest 162 F - Select Halfです。コンテスト後の感想で、偶数のときに2通りしかないと勘違いしていたというのを結構見かけました(ぼくも勘違いしてました…)。そこで、この部分を抽出して問題にしてみました。
問題文は、もっと日本語力があればもっとうまく書けた気がします。人じゃなくてボールとかでもよかったかなという気もしています。
ちなみに、元々の問題タイトルは「Social Distance」でしたが、ARCで同名の問題が出たので変えました。
出題を待っている間に東大入試があり、文系数学の問2がこの問題と似ていた、ということをテスターさんに教えていただきました。
No.1423 Triangle of Multiples
テスター：lynmisakuraさん
この問題が1問目になる予定でしたが、前述の問題が足されました。
こどふぉDiv2Aにありそうなギャグ問題を作りたいと思って作りました。こういう感じの問題です。ギャグ問題を解くコツとして、「どうせこういうのが解になるだろう」というのがある(かもしれません)。今回の問題も正三角形と決めうってしまえば、Aの倍数かつBの倍数かつCの倍数を求めればよいことになって答えに至ります。
制約は、全探索を落としつつ積をとる解法を通すようにしました。積をとる解法も落とせる(A,B,Cが1018以下でもできる解法がある)けどしませんでした。
No.1424 Ultrapalindrome
テスター：nok0さん
かなり昔に作問した問題だと思います。昔過ぎてこの問題がどれくらい難しいのかよくわからなくなりました。当初の予定では前回出題したStone Skippingとともに★2で出そうとしていましたが、Stone Skippingが★2.5になったのでこっちも★2.5にしました。
テストケースを作るには、木を作る必要があります。頂点をランダムにシャッフルし、すでに見た頂点の中からランダムに1つ選び現在の頂点と辺を結ぶ、という操作を繰り返して木を作りました。辺の順番はシャッフルしましたが、辺の左右はシャッフルしてなかった気がします。
グラフの問題でコーナーになりやすいパスグラフとウニグラフをお忘れなく。
答えが2択なので嘘解法が通りやすそうと思い、嘘解法対策を考えました。考えた嘘解法は次の通りです：2つの葉の距離の最大値と最小値が異なるかを調べればよいです。最大値は木の直径なので、2回BFSして最大値を調べるという方法が使えます。これと同様にして、2回BFSして最小値を調べます(ここが嘘です)。02_hand_06.txtがこれを落とすケースです。
しかし嘘解法が通ってしまいました。葉をランダムにいくつか選んで距離を調べるという方法のようです。嘘解法力が足りませんでした…。
No.1425 Yet Another Cyclic Shifts Sorting
テスター：ir_1st_vilさん
タイトルの元ネタはこれです。
2種類でできるということに気づくかがポイントです。0種類、1種類でできるかを判定して、できなければ2が答えです。
作問の元ネタは、n次対称群が(1,2)と(1,2,...,n)で生成されるという群論の命題です。雪江代数の演習2.3.9にあります。群論といえば、以前記事にしましたね。よければご覧ください。
この問題も答えが3通りしかないので嘘解法対策をする必要があります。正しい答えを出す関数f1と、実装を間違えてしまった関数f2を用意して、n=5,6あたりで数列を全部調べて異なる答えが出ないかを調べ、異なる答えがあったときはテストケースに加えました。先にランダム生成ケースを用意してましたが、全然嘘解法を落としてくれませんでしたね…。これのおかげである程度テストケースは強くなったと思います。嘘解法を落とすには、ランダムケースに頼らないことが大事です！
No.1426 Got a Covered OR
テスター：nok0さん
作った順番が「タイトル」→「問題文」→「解法」でした。タイトルには元ネタがあります。ヒント
Stone Skippingと同様問題文を先に作りましたが、包除原理がでてきてびっくりしました。包除原理の問題を作ろう！と思ってもこの問題は生まれなかった気がするので、たまたまいい問題文が生えるのを待つしかないんでしょうか。
(正直に書くと、最初は包除の式をうまく求めることができなかったので実験エスパーで出しました…。)
No.1427 Simplified Tetris
テスター：maspyさん
ACLを使った問題を作りたいなと思って作った問題です。Simplified ReversiやSimplified mahjongを意識した問題名です。
ACL Practice Contestの問題をベースにbit全探索を足した問題です。作った当初は「Practice Contest知ってれば自明なのでは？」と思っていましたが改めて見返してみると実装量も多くて結構大変な問題でしたね。
空中に浮いている場合と行全部が埋まってる場合は不可能です。前者はサンプルに置きましたが、後者には気が付きましたか？
テスターさんはbitDPで解いたようです。この解法だと復元が難しい？
解説の計算量の記述が間違っていたことをテスターさんに指摘していただきました。Hopcroft-Karpの存在も知りました。この分野はまだまだ勉強不足のようです。
No.1428 PeRmutation Question
テスター：butsurizukiさん
ボス問です。一言でいうと「交代群の共役類」です。群論といえば、以前記事に(ry
順列をサイクルの積に分解することは競プロでもたまに見かける気がしますが、ここでも役に立ちます。
WilsonのThe Finite Simple Groupsという本を読んでいた時期がありました。教科書というより辞典といった感じです。行間が広いのであまり初心者向けではない気がします。読んでいたといっても交代群以外のパートをほとんど読めていないので、いつかはちゃんと読みたいです。作問のネタがあったりする…？
交代群の共役類はWilsonの本で勉強したので知っていたんですが、これを自力で導出できる人はすごい…となりました。
おわりに
改めて、参加してくださった皆様、テスターの皆様、yukicoderさん、本当にありがとうございました！
個人的には、群論に関係する問題が2つ出せてよかったです(本当は3つ出す予定だった)。作問は自分の「好き」を詰め込めるのでいいですね。他の人がどういったものが好きなのか見てみたいので、皆さんもぜひ作問に挑戦してみてください！
またコンテスト開きたいなという思いはありますが、だいぶ先になると思います。単発で出題するのはやるかも？
あとは余裕があればテスターにも挑戦してみたいです。もう少し強くなる必要がありそう？
お読みいただきありがとうございました！
