OMCE005 参加記
こんばんは。
本記事では 2024/7/3 に開催された OMCE005の感想などを書いていきます。
引き続きスパン短めのexpert回になります！
writerは5人いらっしゃったので、高難易度の問題の分野が読めないながらも楽しみでした。
ところで年間ランキングの計算ってFAはカウントされなくなったんでしたっけ？計算的には入っているが表示されていないだけでしょうか。
問題ページは以下です。
参加時の動き
配点は4-4-5-7-7-7
135分にしては重めの配点。おそらく内容的には点数よりも簡単気味なのが並んでいるのかなと想像しつつ、前から順番に着手
安定よりも後ろから順に解くスタイルでもやってみたいなと思ったり
B
導入の考察が直ぐわかったのがこの問題だったので、これから着手
$${f(n)}$$は $${\mathrm{popcount}}$$ と一致。
条件は二進表記で11を含まないものの $${\mathrm{popcount}}$$ の総和に言い換えられる。
fibonacciのconvolutionを計算すればよい。
A
約数 $${d}$$ に対して
$${d|a_1|a_2| … a_{99} |100}$$
なる $${a_1,…a_{99}}$$ の列を数える。指数でみるとそれぞれ広義単調増加なので経路の問題に帰着する。$${d=2^a5^b}$$ に対して $${\binom{101-a}{99} \binom{101-b}{99}}$$ 通りある。
300点くらいの感覚だけど、まあ4eで難易度査定が絶対的でないのは良くある話
C
見てすぐに直方体に埋め込むことを考え、三辺を求める。傍接円の半径と面積の式から比は $${612:625:637}$$ で、埋め込んだ直方体の各辺は $${2\sqrt{78}:5\sqrt{13}:10\sqrt{3}}$$
…と計算してから、要求されているものが各三角形の傍心になるので、あまり直方体での考察が意味をなさなそう。
愚直計算を考える。$${V_2}$$ は $${\angle{BDC},\angle{CDA},\angle{ADB}}$$ の二等分線と $${BC,CA,AB}$$ の交点を $${X,Y,Z}$$ とすれば $${D-XYZ}$$ の$${DP/DX \cdot DQ/DY \cdot DR/DZ}$$倍になる。
$${D-XYZ = D-ABC \cdot \triangle{XYZ}/\triangle{ABC}=V_1 \cdot \triangle{XYZ}/\triangle{ABC}}$$
$${DP,DX}$$ はそれぞれの辺の外分点になることから $${V_2/V_1}$$ が計算できる。
D,E,Fの中で考えたことがある点が登場していたFを40分ほど考察するが、どうもうまいこと進まず、あきらめてDへ。
D
カッコ列はカタラン数個あって階段状の経路と対応
この中で()の個数分は〇を配置する必要性がある。残りは自由に配置できるので、()が $${k}$$ 個含まれる時、$${10-k}$$ 個を $${21}$$ 個に分ける分〇が配置できるので、$${\binom{30-k}{20}}$$ 個存在する。
あとは階段状の経路について()が $${k}$$ 個あるものがいくつあるのか。（階段状の経路でのピークが $${k}$$ 個あるものがいくつあるか。
narayana numberという名前は憶えていなかったが、二項係数*二項係数/kというような形になるということは何となく覚えていた。（ここを読んだことがあった）交差しない経路の組に帰着してLGV公式を使う感じ。
結局
$${\sum_{k=1}^{10} \binom{10}{k-1} \binom{9}{k-1}\frac{1}{k} \binom{30-k}{20}}$$
を計算したが、〇を()で置き換えれば直接計算できる…
ちょっと知識寄りではあるかなと思った
E
Dでちゃんとした式を導出するのに苦戦している間に考察を進めていた。
分母は結局 $${f(x)=\dfrac{x^{130}}{(x-a_1)(x-a_2)…(x-a_{127})}}$$とすると $${f(x)(x-a_i)}$$ に$${a_i}$$を代入した値になる。これは$${f(x)}$$ の $${a_i}$$ での留数と思える。各極での留数の和が問われているので、（無限遠点を追加して正則にすることで）無限遠点での留数を計算すればOK
$${f(1/x)=1/(x^{130}(1/x-a_1)(1/x-a_2)…(1/x-a_{127})=1/(x^2(1-a_1x)…(1-a_{127}x))}$$
となることから、$${g(x)=(1-a_{1}x)…(1-a_{127}x)}$$とおくと、留数は
$${1/3! \lim_{x \to 0} \dfrac{d^3}{dx^3} \dfrac{1}{g(x)}}$$
$${=-1/6(g(0)^2g'''(0)+6g'(0)^3-6g(0)g'(0)g''(0))/g(0)^4}$$
で計算できる。$${g(x)=a+bx+cx^2+dx^3+… }$$ とすると、
$${g(0)=a=1, g'(0)=b, g''(0)=2c, g'''(0)=6d}$$
で、計算すると $${2bc-b^3-d}$$ になる。
あとは $${b,c,d}$$ をそれぞれ計算する。
$${\cos(2a\pi/257)=(e^{i2a\pi/257} + e^{-i2a\pi/257})/2 (手前のiは虚数)}$$
を用いて、
$${b=-∑a_k=-∑(e^{i2k\pi/257} + e^{-i2k\pi/257})/2}$$
$${=1/2}$$
$${ c=∑_{k \lt l} a_ka_l=1/4∑_{k\lt l} e^{i2(\pm k \pm l)\pi/257} =-127/4 }$$
$${d=-∑_{k\lt l \lt m} a_ka_la_m = -1/8∑_{k \lt l \lt m} e^{i2(±k±l±m)\pi/257}=-63/4}$$
となるので（指数の計算）
$${2bc-b^3-d=-127/4-1/8+63/4 =-129/8}$$
個人的には三角関数の計算が本質で一番大変だった。
割とギリギリに通せたのでFでのロスで沈まなくてよかった。
F
問題に登場している $${DP\perp EF}$$ なる $${P}$$ について考察をしたことがあったので、D,E,Fをちょろっと見たときに真っ先に着手した…が知っている構図は円$${AEF}$$ と外接円の交点に関するもので、$${AP\perp BC}$$を落とし込めず時間を溶かした。本番は途中であきらめた。
$${I}$$ を内心として、角度を追えば $${APDI}$$ が平行四辺形とわかり、内接円の半径が$${321,AI=500}$$ → $${AEF}$$ が確定する。$${AP=321}$$ より$${AP}$$ についても確定。あとは $${AP\perp BC}$$ から計算できるところを見る。($${AP}$$ と$${BC}$$ の交点を $${X}$$とする）
$${AP=a,DP=b}$$ として
$${AF=\sqrt{b^2-a^2} }$$
$${FP=\sqrt{a^2-a^4/b^2}-\sqrt{a^2-(b-a^2/b)^2} }$$
$${EP=\sqrt{a^2-a^4/b^2}+\sqrt{a^2-(b-a^2/b)^2} }$$
$${FD^2=(\sqrt{a^2-a^4/b^2}-\sqrt{a^2-(b-a^2/b)^2})^2+b^2 }$$
$${DE^2 = (\sqrt{a^2-a^4/b^2}+\sqrt{a^2-(b-a^2/b)^2})^2+b^2}$$
$${AX=b^2/a}$$
$${DB=FB=FD/2 FI/\sqrt{FI^2-FD^2/4}=1/\sqrt{4/FD^2-1/a^2} }$$
$${DC=EC=1/\sqrt{4/DE^2-1/a^2} }$$
面積 $${=AX(DB+DC)/2}$$
あとは $${a=321,b=500}$$ を代入するのだが、そのままだと大変。解答形式的にも二重根号が外れるはずなので、チェックしてみると、各項で根号が外れて、
$${1/\sqrt{\dfrac{4}{\big(\sqrt{a^2-a^4/b^2}-\sqrt{a^2-(b-a^2/b)^2}\big)^2+b^2} -1/a^2} }$$
$${ = (b^2 a)/\sqrt{-2a^4+4 a^2 b^2-b^4+2\sqrt{(-a^4+a^2b^2)(-a^4+3a^2 b^2 - b^4)}} }$$
$${= b^2a/(\sqrt{-a^4+a^2b^2}+\sqrt{-a^4+3a^2 b^2 - b^4}) }$$
となり、もう片方は分母の根号の間の+が-になる。あとはこれを計算すればよい $${-a^4+3a^2 b^2 - b^4}$$ のところは大きすぎるが、打ち消しあうので無視していい。
解説の $${P}$$ が垂心である証明は面白い。
感想と反省
5問正解133分5秒3ペナで3位でした！
前回に引き続き終了間際に通せてなかなかいい成績になりました。ただ、Fで失った時間の分あまりリターンが出ていなかったり、DとEどちらも計算どうしようか悩んでいる時間があったり割と動きの面で反省点があるセットでした。
全体としては前半は点数の割には易しく、D,Eは知識要素が強いタイプで、Fが難しい幾何、という感じで、D,Eの関連知識を持っていてある程度Fの考察も落とせていた身からすると、もっとできるべきだったような気もします。
個別を見ると、E,Fが面白かったです。
Aは組み合わせっぽい問題ですが、お手頃でよい問題と思いました。Bはpopcountであることにすぐ気づけたので、そこまで印象がなく… Cについては計算がちょっと面倒だった以外にあまり記憶がないです（幾何的性質がある？）
DはNarayana数に該当する数の計算についてみたことがあったのでそれが割と有利に働いたと思います。問題にしやすいので経路の計算の典型は知っておきたいですね。Eは留数計算の形としては見たことがあるタイプだったので、cosの色々な和を計算するところにはすぐ帰着できましたが、その計算で少し苦労しました。Fは構図で飛びつきましたが、肝心の情報に気づけず解ききれませんでした。
セット内容的には経験でカバーできる問題が多く、全部解けるチャンスだったのでもったいなかったかもしれません。
ちょっとした宣伝
今日ポロロッカでコンテスト開きます！
私としては出題や答えに不備があるのが怖いですが、皆さん楽しんでいただけると幸いです。