OMC作問をしよう！
はじめに
こんにちは。OMC015,032writerのsimasimaです。今回はOMC作問のコツを紹介します。作問の提出方法などはOMCサイト内のRuleに書いてあります。
OMCのサイト→
https://onlinemathcontest.com/
0.水solverになる
$2021$年$9$月からHighestレートが$1200$(水solver)以上ないと作問出来なくなりました。
コンテストにまだ一度も出ていなくて、腕に相当自信がある(AtCoder橙とかJMO春合宿レベル)人は「for beginners」がついてないコンテストに出ましょう。$2400$以上のパフォーマンスを出せば一発で水です。
1.問題の種を生やす
まずは問題の原案を生やしましょう。原案の生やし方には2パターンあります。
問題設定を先に考える
solverとしての実力が高い人におすすめです。しかし、solverとしての実力に自信がなくても大丈夫です。
solverが時間に追われながら苦手な分野の問題も解かなければいけないのに対し、writerは好きな分野の問題を好きなだけ時間(と外部ツール)を使って解くことができます。なので、暖色solverでなくても600点以上の高難度の問題を生やすことができます。
ネタを入れたい時は問題設定の時点で仕込んでおきましょう。
解法を先に考える
この定理を使いたい！とかこの性質を使いたい！といったものがある時におすすめです。発想力が求められる良問が生まれやすいです。しかし、問題を改良していくと簡単な別解法が生えてきたりするので、いい感じに作問が成功する確率は低くなります。問題がなかなか生えなくてもめげずに頑張りましょう。
2.問題を改造する
生えた問題を頑張って改造しましょう。面白くない要素を減らしたり、逆に新たな考察要素を追加して難易度を上げたりします。
ここで、余剰ヒント(問題を解くのに必要ない数値や情報)を追加すると難易度が跳ね上がることがあります。
しかし、自分の問題を難しくしたいからといって非本質部分を増やしすぎるとsolverから嫌われるので気を付けましょう。
また、C(組み合わせ)分野やN(整数)分野の難しい問題(400点以上)はプログラミングによる不正への対策を行うと良いです。
単純な総和を求める問題はプログラミングにより瞬殺されがちです。プログラミングは1秒間に$10^9$回も計算できます。
試しに次の問題を勝手に改造してみましょう。
OMC039-A です。
この問題はプログラミングによって$81$回の掛け算で求められてしまいます。
$i$と$j$の上限を$12345678$などにすれば$10^{14}$回程度の掛け算が必要になり、プログラミングでは解けません。しかし、答えの桁が$15$桁を超えてしまいます。OMC公式電卓は$15$桁までしか正確に計算できません。どうしましょう。
こんな時は計算が簡単になるような設定にすると上手くいくかもしれません。
$i$の上限を$19999999$にして$j$の上限を$20000000$にしてみましょう。すると、$\frac{19999999 \times 20000000 \times 20000000 \times 20000001}{4}$になります。
まず、$20000000 \times 20000000$ と$4$が相殺して、$19999999 \times 100000000000000 \times 20000001$になります。$19999999 \times 20000001 = 20000000 \times 20000000 -1 $なので、$399999999999999\times 100000000000000$になり、$39999999999999900000000000000$が答えになります。このような計算の工夫が組み込まれている問題はOMCに実際に出題されています。
OMC???-A(ネタバレ注意)
3.実践
さっそく作問してみたいと思います。
設定の発想はメダルゲームからです。
問題
siosio君は$1$円を持っています。siosio君は所持金が$0$円になるまで次の<勝負>を行います。
<勝負>
表と裏が等確率で出るコインを投げて、表なら$1$円貰える。裏なら$1$円払う。
siosio君が<勝負>をする回数の期待値を求めてください。
早速解いてみましょう。
---$100$時間後---
うーん中々解けませんね。
siosio君が$n$円に到達できる確率は$1/n$ということは、siosio君が最大枚数に到達したときの勝負のみをカウントすると、$ \sum_{k=2}\frac{1}{k}$になります。
あ！(絶望)
期待値が発散してしまいました。こういうことも多々あります。諦めずに答えが出るように改良しましょう。
表の確率を小さくすれば収束しそうです。
問題(改)
siosio君は$1$円を持っています。siosio君は所持金が$0$円になるまで次の<勝負>を行います。
<勝負>
表が$\frac{1}{3}$の確率で出るコインを投げて、表なら$1$円貰える。裏なら$1$円払う。
siosio君が<勝負>をする回数の期待値を求めてください。
早速解いてみましょう。
---$1000$時間後---
$1$円から$0$円になるまでの回数の期待値を$x$とすると、$2$円から$1$円になるまでの回数の期待値も$x$になります。
ということは、$2$円から$0$円になるまでの回数の期待値も$2x$になります。
ここで最初の勝負を考えると、$x=\frac{2+2x}{3}$が成り立ち、$x=2$と求まりました。めでたしめでたし。
(2021/9/21追記)間違ってますね。$x=\frac{3+2x}{3}$が成り立ち、$x=3$が正しいです。全然めでたくありません。
解答は記事の本質ではないので、チェックが甘かったです。(言い訳)
このように橙solverであってもミスる事があるので、自分の問題が間違っていないかのチェックは何度もしましょう。
siosio君の所持金が$n$円の場合も$n$倍すれば求まるのでちょっと難しくできそうです。
問題(改改)
siosio君は$310$円を持っています。siosio君は所持金が$0$円になるまで次の<勝負>を行います。
<勝負>
表が$\frac{1}{3}$の確率で出るコインを投げて、表なら$1$円貰える。裏なら$1$円払う。
siosio君が<勝負>をする回数の期待値を求めてください。
表なら$n$円貰えるという部分も変えられそうです。
問題(改改改)
siosio君は$310$円を持っています。siosio君は所持金が$0$円になるまで次の<勝負>を行います。
<勝負>
表が$\frac{1}{3}$の確率で出るコインを投げて、表なら$514$円貰える。裏なら$1$円払う。
siosio君が<勝負>をする回数の期待値を求めてください。
最初の勝負を考えると、$x=\frac{3+515x}{3}$が成り立ち、$x=-\frac{3}{512}$ あっ
調子に乗り過ぎました。コインの確率をいじって何とかします。
問題(改改改改)
siosio君は$310$円を持っています。siosio君は所持金が$0$円になるまで次の<勝負>を行います。
<勝負>
表が$\frac{1}{1000}$の確率で出るコインを投げて、表なら$514$円貰える。裏なら$1$円払う。
siosio君が<勝負>をする回数の期待値を求めてください。
最初の勝負を考えると、$x=\frac{1000+515x}{1000}$が成り立ち、$x=\frac{200}{97}$
あとはこれを$310$倍して$\frac{62000}{97}$が答え
これでいい感じになりました。払うお金をいじるのは「$n$円の場合も$n$倍すれば求まる」が崩れるのでめんどくさいので改造は終わりです。
問題(完成版)
siosio君は$310$円を持っています. siosio君は所持金が$0$円になるまで次の<勝負>を行います.
<勝負>
表が$\frac{1}{1000}$の確率で出るコインを投げて, 表なら$514$円貰える. 裏なら$1$円払う.
siosio君が<勝負>をする回数の期待値を求めてください.
ただし答えは互いに素な正整数$a, b$によって$\frac{a}{b}$と表されるので, $a+b$を解答してください.
OMCの解答方式に合わせて完成です。
ちょっとエスパーが通りやすいかもしれませんが、大体難易度は$500$点くらいだと思います。
4.おわりに
みんなでOMC作問をしまくって週100でコンテストが出来るようにしましょう！
ここまで読んでいただきありがとうございました。