OMCE002 参加記
こんばんは。
本記事では 2024/4/29 に開催された OMCE002の感想などを書いていきます。
今年度初のexpert回で、OMCEナンバリングでの開催になります！
今までと違って、前回のexpertから4bが一回分多く、待ちに待った、という感覚でした。writerはshoko_mathさんで、実は今までOMC本番では解いたことのないwriterさんです。ただ、除夜の鐘コンテストやポロロッカなどで問題を見たことはあったので、何となく問題の傾向的な物は理解しているつもりです。
また、後で少し宣伝とちょっとした情報を付記させていただきますが、コンテスト前にOMC219のwriterになったことが分かりました。よろしくお願いします。
今回の問題ページは以下です。
参加時の動き
配点は3-3-5-5-7-7
shoko_mathさんは幾何が難しくなる傾向があって、ちょっと怖いところですが、前半4問をとにかく拾う立ち回りを意識。
問題を4つ開くとゲーム、角度、多項式、整数解探しという感じ。前半二問が沼にはまりそうと思い、500からチェック
C
見た瞬間にラグランジュ補完が浮かんだので、素直に式を書く
f(x)=∑(k+1)2^k*x(x-1)…(x-10000)/((x-k)*(k)(k-1)…(k-10000)) ただし分母の(k-k)は除く
という形になるので、
f(10001) = ∑(k+1)2^k*10001!/((10001-k)*(k)(k-1)…(k-10000))
となる。k項目を改めてみると p =10007として
10001!*(k+1)2^k/((10001-k)*k!*(10000-k)!(-1)^k)
=(k+1)(-2)^k*binom(10001,k)
で，これらをk=0から10001で総和すると(-1)^(10001)(2*10000+3)と一致。k=10001の分を引くと
-20003+2^10001*10002≡949
となる。
途中の二項係数計算のところで少し迷走しかけたので、Bを着手。
B
パッと思いつかなかったので、三角関数で立式していじると、
θ=12.3としたときに60-θ/3,θが答えになる…とおもいきや通らない。
いろいろ計算するも誤りが見当たらない。問題文を改めて見直すと、Dは直線BC上の点だった… ∠DAC=12.3で固定で計算していたので計算でも出るはずが無く… expertでこんなことで泥沼にはまってはいけない
ちなみに、BCの中点を取ることで即座に幾何的に解ける。
Cを通した時すでに55分も経過していてBの正解者（この時まだCAしていない）も100人ほどいる状況と、相当悲惨な出来になっていた。
D
B,Cで迷走中に一応題意だけ確認していた問題。何らかの積だったり変数がまとまった形にしたい。
f(a,b,c,d)=a^4+b^4+c^4+d^4-2(a^2b^2+a^2c^2+a^2d^2+b^2c^2+b^2d^2+c^2d^2)-8abcd
を（場合によっては定数ずらして）うまく扱いたい
変数にもう少し制約を加えたときの挙動をチェックする
d=cのとき
f(a,b,c,c)
=-4(a^2+b^2)c^2-8abc^2+a^4+b^4-2a^2b^2=(a^2-b^2)^2-4(a+b)^2c^2
=(a+b)^2((a-b)^2-4c^2)=(a+b)^2(a-b+2c)(a-b-2c)
と積の形にできる。これがどの二つの変数についても等しい場合は上のように因数分解できることとなる。ここから、a+b+c-dみたいな形の式で割れそうと思ってd=a+b+cを代入すると0になる。よって(a+b+c-d)のサイクリックな積*-1であることがわかる。a+b+c+d=xとすれば結局
(x-2a)(x-2b)(x-2c)(x-2d)=(n^2+1)^(n+2)-1となる。
A=(x-2a)と置きなおすとA,B,C,Dについての制約はすべてmod2で合同であり、逆にA,B,C,Dが与えられているとき
x=a+b+c+d=2x-(A+B+C+D)/2 -> x=(A+B+C+D)/2
a=(-A+B+C+D)/4 となる。分子が4の倍数であることが必要となる。以上を整理して
A=B=C=D mod2
-A+B+C+D=A-B+C+D=A+B-C+D=A+B+C-D=0 mod4
よって、mod4で以下のパターンがある
(0,0,0,0),(0,0,2,2),(2,2,2,2),(1,3,3,3),(1,1,1,3)
a,b,c,dに正負の制約などはないので、上記の素因数に分解出来ていればa,b,c,dが定まる。
右辺が偶数のときは2で割れる回数、右辺が奇数の時はmod4で3かどうかで決定できる。g(n)=(n^2+1)^(n+2)-1とする
nが奇数→g(n)≡3 mod 4となるのでどれでもOK(A=B=C=1,D=g(n))
nが偶数→v2(g(n))=4のときは A,B,C,Dに2を振り分けて、残りの奇数はどれかに寄せる。v2(g(n))>=6の時は2冪を2^k,2^2,2,2と割り振ればOK 5の時は割り振り不可。よって、mod64で0,奇数,16,48,を足せばよい
因数分解がうまくいったこともあって、かなりスムーズに解けたと思う。泥沼にはまりそうなポイントは結構ある印象。
A
ゲームということで一旦敬遠していた問題。
後手必勝につなげられれば先手必勝。そうでなければ後手必勝。数字を書き出すとmod12での周期で、0,2が後手必勝とわかる。（grundy数）
OMC216Aのこともあって無視してたけど、シンプルな典型だったので特に困らなかった。
残った問題を見るとEが数人解いていて、Fは誰も解いていない状態。ただ、Eは幾何。Fを見ると、組み合わせのうまい解釈を探す問題っぽく見えたので、一旦回避してEへ。
E
まず、面積比の条件をもうちょっとうまく言い換えられないか考える。
上の図で、
△EFB-△FDC=△ABD-△AEC
△AGF=□AEFD/2-△AFD
となるので、これの比をうまく長さの条件に落とせれば（あわよくばEF,FD,BF,FCあたりの情報に落とせれば）円内の情報が確定するので計算ができるようになる。
AE=a,AB=b,AD=1として、面積比を計算してみる。
相似からAC=abで、
△ABD=bsin(ABD)だが、ここで一旦sinを無視してbとして面積比を追ってみる。
ABC=a^2b,CD=ab-1でメネラウスの定理から
a/(b-a)*(ab-1)/ab*BF/DF=1 → BF:FD=b(b-a):(ab-1)
1/(ab-1)*(b-a)/b*FC/EF=1 → EF:FC=(b-a):b(ab-1)
△EBF=b*(b-a)/b*BF/BD = (b-a)*b(b-a)/(b^2-1)
□AEFD=b-(b-a)*b(b-a)/(b^2-1)=b(1-(b-a)^2/(b^2-1))
△AFD=b*FD/BD=b*(ab-1)/(b^2-1)
△EFB-△FDC=△ABD-△AEC=(1-a^2)b
△AGF=□AEFD/2-△AFD=b(1-(b-a)^2/(b^2-1))/2-b*(ab-1)/(b^2-1)
(△EFB-△FDC):△AGF=2(b^2-1):1
とaによらない比になる。
また、方べきの定理からBF*FD=EF*FCなので、比について
BF:FD:EF:FC=b(b-a):(ab-1):(b-a):b(ab-1)
となる。よってBF:EF＝b:1となる。辺の比に還元できた。
これにより、与えられた図においてRA:RB:RC:RDが計算できて、
あとは直径1となす角から計算ができる。
（このあたり、計算しまくっているけど、ももっと簡潔にできますね…）
そもそも本質情報がどこなのか見出す部分にやや苦戦（60°でなまじ色々計算できるだけに…）
さらに、コンテスト中は面積比の計算で間違えて、aに寄らない比になるはずのところでaが混じり、ミスを発見できず難航。三次方程式を解こうとしていた。
終了10分前に計算ミスに気づけて、2(b^2-1)のところまで行けたが、その後の方べきを経由して円内の比に持ち込むところができず、さらに転記ミスで2b^2-1としていたので汚い数値になり慌てている間にコンテストが終了。
感想と反省
4問正解1ペナで15位でした。Bでロスした時間とEが解けなかったことがしっかり成績に反映された感じです。ちゃんと幾何にやられてしまった形になりました。Eはコンテスト後40分ほどかけたら正答できました。
ところが、ほぼノータッチだったF問題に誤りがあった関係で、unratedになりました。自分としてはほぼ影響がなかっただけに、失敗が無かったことになったので、レートやランキング的には良かったですが、モヤモヤする形に。自分の幾何の立ち回りの弱点をきっちり突かれた形になってしまいました。
全体としては難易度勾配もきちんとしていて、適切な難易度だったのかなと思います。どうせなら点数も勾配付けていいのではと思わなくもないですが、まあ戦略的なことも考慮してる感じですかね。
個別の問題ですが、Eは面白かったです。Bも併せて、幾何に相当苦しめられてしまいましたが、自分の動きに非があったなと思えるセットでした。Cはもっとシンプルに計算できたみたいなので、多項式の値に関する問題の引き出しとして持っておこうと思える教育的な問題でした。Dの因数分解はやや天啓感あるというか、どうせ積にまとまるだろう、という想定の下動いているのが難しいポイントですが、その後の倍数評価の議論や挙動は面白かったです。
Fは問題そのままだと、組み合わせ解釈が難しい上に、剰余でズレがいくつか消えるので、評価がちょっと変わってくると思います。ただ、模範解答の解釈ができる数列設定にした場合は結構面白い問題かなと思います。
本番中着手できなかった問題
F
経路っぽい解釈を試みる
ヨコakタテak+4bkの長方形の経路の積がΠ(2ak+4bk)C(ak)になり、最終的な長方形は9000,8998*4+9000 という形で、(∑ak,∑(ak+4bk))を通るような経路と何かしらの対応が付きそう。各種制約を言い換えて、経路の数え上げに帰着しようとするも、ここがうまくいかない。Snがn個の点を通る感じの何かで、その交代和がいい感じの解釈ができる、ということなのだろうけども、
(∑ak,∑(ak+4bk))としてカウントできる点の条件がいい感じにまとまらない。
経路を一つ固定して、その経路がSnで何回数えられるか、交代和で結局どれくらいカウントされるのか、という所に着目しても、必要十分な条件が整理できない。（実際、5/2現在の解説ではここが数列の条件と同値になっていないため、交代和できれいにならない）
問題的にも、母関数が刺さりそうなシンプルな二項係数の計算なので、これを実際に遂行するのが良いようです。→MARTHさんの解説
キーとなるのが
∑ binom(2n+k,n)x^n = (2/(1+sqrt(1-4x)))^k/sqrt(1-4x)
で、これをもとに級数で計算する。a_1,a_nの条件を丁寧に反映する必要がある、感じです。
今回解説を読んで手を動かしていろいろ勉強になりましたが、この辺の計算をすらすらできるようになりたいものです。
コンテスト宣伝など
OMC219のwriterになりました！
ページは以下です。
単独でのセットとなります。5/9(木)開催予定です。
あまり確認していなかったせいかもしれませんが、writerになったことをXの他の方の投稿で知りました。
作問開始したのが昨年の10月ごろで、審査が増え始めたのが12月ぐらいからですが、セットとして提出してからは意外と早めに決まったので想像よりも早い開催になりました。
現状セット提出されていない問題から出題する時、割と古いものから処理しているようなので、そういう観点で出題されるのは遅くなるみたいですが、セットで出せば別かもしれません。ただ、セット提出自体が、審査済の問題が分野と難易度のバランスよく6問以上存在する必要があるので、ハードルが高そうですけども。
今回の開催が決まったとき丁度審査済が30問でした。不採用は15問。最初の方に出した問題が結構不採用になっています。
皆さんに解いてもらった時のフィードバックをもらわずに大量に問題を作ってしまったので、このコンテストでの皆さんのフィードバックはぜひ作問工程の改良の参考にしたく思います。私の問題に対しては忌憚なく意見を言っていただいて構いません。（面白くない、つまらない、といったシンプルなネガティブ意見も歓迎ですが、その判断の根拠の記載があると大変助かります。また、他の作問者にもそれをやっていいという意味ではないです。）
昨今出題されている問題の問題番号的にも、セット採用がこんなに速いとは思っていなかったので、ポロロッカの方で不採用問題を少々いじってコンテストを開催して、そこでのフィードバックを糧にしようと思っていたのですが、OMCの方が先になりました。
ともかく、皆さんの参加と解いてみた感想お待ちしております。
この回の参加記はwriterとしてのものを書く予定です。