OMC221 参加記
こんばんは。
本記事では2024/6/10に開催されたOMC221の感想などを書いていきます。
前回の無印ではやや振るわなかったので、ここで取り返したいと思いつつ、writerメンバーを見て楽しみにしつつ… 4bに出なくなってからレート関係ないコンテストが無印のみになったからなのか、無印回への楽しみな気持ちが増しました。
問題ページは以下です。
参加時の動き
配点は 1-2-4-4-4-6
いつも通り中盤の問題から拾う作戦
C
何なら全部書き出せそうな問題
まず3^5-1通りがどういう計算なのかを理解する。各数の選び方が3通りでそれが5つ分なので3^5、空集合を除くので-1
{1,1}から初めて{k,k}を追加していくことを考えると、kを0個、1個、2個使うという3パターン分を各部分集合に対して考えることで（しかもkは後ろに追加される）漸化式が定まりそう。実際参照する部分集合の元の数で推移が決まる。具体的にはkを1個だけ追加したとき、参照先の部分集合の元の数によってkがかけられるかが決まる。
これを用いることで漸化式が立つ。空集合を除くことに注意。
競技プログラミングにありそうな問題と思った。
Dが幾何なので一旦飛ばしてEへ
E
Xは10の倍数でなく、X^2の桁数をkとすると 8*10^(k-1) <= X^2 < 9*10^(k-1)で、さらにある整数Yがあって X^2-8*10^(k-1)＝Y^2(<10^(k-1))である。
(X+Y)(X-Y)=8*10^(k-1)となるのでX+Y,X-Yは2冪5冪の積で書けて、
整数であったからその和や差は偶数であることが必要。よって
(X+Y,X-Y)=(2^a5^b,2^(3+k-1-a)5^(k-1-b))と表せて、1<=a<=k+1の範囲とわかる。X=2^(a-1)5^b+2^(1+k-a)5^(k-1-b)で、これが10の倍数でない。
5の倍数でないとするとb=0ork-1となるが、これは X < 3*(√10)^(k-1)<5^(k-1) と矛盾するため、5の倍数となることが必要。このときXは2の倍数でないのでa=1 or k+1 である。
(X,Y)=(5^b+2^k5^(k-1-b),5^b-2^k5^(k-1-b)), (2^k5^b+5^(k-1-b),2^k5^b-5^(k-1-b))
と表せる中で、各種不等式を満たすことを考える。Xの方は必要ならばk-1-bを新しくbと置きなおせば2^k5^b+5^(k-1-b)と書けるので、
8*10^(k-1) <= (2^k5^b+5^(k-1-b))^2 < 9*10^(k-1)
(2^k5^b-5^(k-1-b))^2 <10^(k-1)
ここからlog_10 を用いて計算。試して小さい方から解を見つけると、6番目は、k=13,b=3の時とわかる。
この後Dを考えるもなかなか進捗が得られないので、座標に入れてすごく汚い計算のみ行った後、B,Aへ。
B
平行四辺形で対角線と一個の角が与えられているとき、余弦定理から隣り合う辺の長さをa,bとすれば a^2+b^2±2abcos(なす角) が対角線の二乗。面積はabsin(なす角)なので、(対角線の二乗の差)/4 * tan(なす角)が面積。これを用いれば計算できる。4で割り忘れて1ペナ。
A
何が被っているのか数えてしまったが、書いてある。
和が54なので2a+r = 54-45 で、a,rに制約があり、他は自由(8!通り)
a,rの組としてありうるのはa=0~4の5通り…と見せかけてa=r=3は適さないので4通り。あっさり引っかかってしまった。
D
ちょろっと計算していたものの、めちゃくちゃ汚い関数の制約付きでの最大値を求めることに帰着してしまったいたため、再着手。
計算方法を変えてもいい感じにならないので、さすがに幾何的情報をつかみ取る方針に一旦切り替える。Rの特徴づけをしたい。PRD∽ABCは計算中も使っていたけど、他の情報が無い状態。一旦Ｑおよび関連する長さの情報を無視して、Pを動かしたときのRの軌跡をみることで特徴づけを行う。
綺麗に作図すると、ひし形の形に寄らず、AC上にRが乗ってそうということがわかる（図をきれいに書かずに考察していたこともあって、これを得るまでとても時間がかかった…）実際、APRD共円で∠RAD=∠RAPでひし形であったから直線ARと直線ACは一致する。
AB=ADなので、ACで図形を折り返すとDはBに重なる。よってBR=DR
ACが大きくなるのはPRとABが垂直な時と思い込んでしまい、（このとき、B=Pで少し状況としては変だが）誤答
その後も計算しようとするも幾何考察前の汚い式を活用しようとしてかえって時間を食ってしまい、答えにたどり着けず。
DQ=x,∠ABC=tとすればRB=RPから解くとx=(11+sqrt(121+720 cos(t)))/20
costを小さくすることを考えると-121/720のとき最小。このときx=11/20で条件を満たす図が取れるので、この時のACを求めればOK
結局、Rの特徴をつかんだ後はある程度道具を使う環境が整うので、そこから最大値を求めればよかった、という問題。
幾何情報→計算という流れに乗っかれず、計算してから幾何情報を追っている間に時間切れという感じ。構図は綺麗かつ割と単純だけど後半の最大値に関して幾何学的な意味が整理しづらい（+ある程度の計算必須）ので難しいと思った。別解がたくさん載っているけど、計算方法を複数紹介しているだけではある。結局これよりも∠ABCが大きくなった時にP,Qが取れなくなるのが図を見てもイマイチピンと来ていない。（腑に落ちたら追記します）
配点的にもこれを解いてからじゃないとまずいと思っていた上に、遅いながらも進捗は得られていたため、Fに行こうと思えなかった。
感想と反省
4問正解2ペナ35分30秒で15位でした。Dで時間が溶けに溶けて悲惨なことになりましたが、比較的速く解いていたのでなんとか20位以内ではありました…
全体としては、少し難易度順が歪な感はありましたが、出題者の味みたいなものは出ているセットだったかなと思います。言語化しづらいですが、sakuranoさん問題は数オリっぽくも受験数学っぽくもなく、その中で面白さを保っているような印象です。MARTHさん問題は少し競技プログラミングっぽさがあるように感じられました。
個別で見ると、Bが面白かったです。また、Fの公式解説の方法も面白かったです。B問題は二つ目の解説が印象に残りました。小学生にも出せるということですね。D問題は幾何性質と計算の塩梅が難しく感じましたし、要求されている最大となるケースの幾何学的な意味がよくわからなかったので、ちゃんと難しい問題なのではないかと感じました（tester時点では満場一致で400点評価だったらしい）ただ、そもそも幾何については難易度評価がブレやすい分野である上に自分自身もかなり普通とは離れた難易度感覚を持っているみたいなので、あまりアテにならないですが…
E問題は人工気味な条件が多いので綺麗さはそこまで感じないですが、こういう問題にしては答えが大きめになるようなタイプなので、ちゃんと性質を追えていないとできないような、いい問題だと思います。
F問題のような組み合わせ解釈の発想はすぐ出るようになりたいと思う一方で体系的に得られないのが難しいなと思ってます。
本番中着手できなかった問題
F
Dの進捗がもっと絶望的であれば着手していた問題。
x,y,z方向に動く操作をX,Y,Zとすると、これらを並べたときに、k番目のZからk+1番目のZの間にXがa_k個、Yがb_k個あるとすると
∑a_k = 400, Σb_k = 400 で、スコアはΠa_kb_kとなる。また、このような並べ方はbinom(a_k+b_k,a_k)通りとなる。よってスコアの総和は∑(Πa_kb_kbinom(a_k+b_k,a_k))となる。
binom(a_k+b_k,a_k)は 1/(1-x-y)を級数表示したときのx^a_k y^b_kの係数になる。これをa_kb_k倍するので各変数で一回偏微分しておけばよい。よって2/(1-x-y)^3のx^(a_k-1)y^(b_k-1)の係数に相当
∑(Πa_kb_kbinom(a_k+b_k,a_k))=∑(Π[x^(a_k-1)y^(b_k-1)](2/(1-x-y)^3))
=[x^299y^299](2/(1-x-y)^3))^101 （ここは少し注意）
=2^101 900C299 * 601C299
となる。
他にも組み合わせ論的にも解けるようで、たらればを言えばこれを先に解けばよかったなと思う一問だった。
雑多なトピックス
今回はOMCのVoluntaryに分類されている問題の紹介とちょっとした感想を書くことにします。（サボりともいう）
今年の灘中入試模試のF問題です。
円錐の側面の最短経路は中学生の数学で頻出ですけど、これを立体的に見たときにどのようになっているか、また上から見たときにどのようになっているか、というのはあまり考えたことが無かったため、結構盲点でした。
実はこの線は円錐に乗せたときに同一平面上にすらなく、問題を解く上ではPの位置を丁寧に追うことになります。下でその様子がチェックできます。
OMC卬高杯1のG問題です。証明含めて面白いと思います。
一瞬よくわからない最大値を要求されていますが、うまく作られています。
詳細は解説をどうぞ。グラフ理論だと、よくある題材なんでしょうか…？
第25回灘中入試模試のE問題です。
自由度を高くしている分、やや問題の意図がわかりにくいですが、ヒグマ君は嘘をつくことはなく、候補の数が1212個ある対象を14回の質問で絞っていく（一回の質問でYesの集合とNoの集合に分け、その片方に進行していくという感じ）ときに、各質問の後にYesの集合に解があれば宣言した点数をえられるときに、点数の最小値（最悪ケースでの値）を最大にする、という問題。
最初の11回で決定してから残りの3回で点数を増やすのがよいかと思ってしまいますが、そうではなく、候補がa個なら点数を2^n/a倍以上にできるというのが面白いです。