OMC218 参加記
こんにちは。
本記事では2024/4/19に開催されたOMC218の感想などを書いていきます。
チーム戦は何とか決勝に進出できたので、このままいい成績をキープしたいと思っていました。
問題ページは以下です。
参加時の動き
配点は2-2-3-5-5-5
作戦としては、後ろの三問から解けそうなものを拾って、2,2,3を拾って、最後に解けなかったものを考察という、いつもの流れ。
問題を開くと、後ろ三問の分野がC,G,NでCが図示するもややこしそう、Nも条件が複雑そうだったので、一旦300点に逃げる。
C
条件より、10^3+1でも12^3+1でも割り切れる。また、12^5~10^6の範囲の数である。lcm(10^3+1,12^3+1)=1729なので、[10^6/1729]-[12^5/1729]=39
条件の整理と最小公倍数の計算にちょっと時間がかかった。200点と思う
F
条件がややこしそうだけど、writerから条件の言いかえ自体はできそうと判断してFから着手。
n=2^a3^b5^cとおけてa>=b>=c>=0で条件3の式はp=2で計算してみると
左辺が
(a+1)(b+1)(c+1)(12a+12)(12b+1)(12c+1)-6(2a+2)(2b+1)(2c+1)(6a+6)(6b+1)(6c+1)+5(3a+3)(3b+1)(3c+1)(4a+4)(4b+1)(4c+1)
となり、12(a+1)^2でくくると
(a+1)^2{(b+1)(c+1)(12b+1)(12c+1)-6(2b+1)(2c+1)(6b+1)(6c+1)+5(3b+1)(3c+1)(4b+1)(4c+1)} で
(kb+1)(kc+1)(12b/k+1)(12c/k+1)
= (12b^2+kb+12b/k+1) (12c^2+kc+12c/k+1)
= 144b^2c^2 + bc(12kc+12c/k+12kb+12b/k)+bc(k+12/k)^2+1
となるので、(bc)^2,bc^2,b^2c,定数項が消えることが確認出来て、bcの係数は30であるから結局
360(a+1)^2*bc と一致する。（約数の個数を経由しているけど、別にそこから綺麗な解釈があるわけでもないらしい）
1110^(2m+1)と比較して、
(a+1)^2bc=2^(2m-2)*3^(2m-1)*5^(2m)*37^(2m+1)
となる。ここで、p=3のときはa(b+1)^2c,p=5のときはab(c+1)^2となるので、xy(z+1)^2=2^(2m-2)*3^(2m-1)*5^(2m)*37^(2m+1) の解を一つ求めたときに、（右辺が平方数でないことから）x,y,zを大きい順に並べ替えたものをa,b,cとすれば条件を満たす。一方で(x,y,z)と(y,x,z)を重複して数えるので、
素因数の振り分け方を二で割ったものが(a,b,c)の個数、すなわちf(m)となる。
指数が2t-1のとき t(t+1)通り、指数が2tのときは(t+1)^2通りの素因数の分け方があるので、f(m)=m^3(m+1)^4(m+2)/2 となる。これが1110で割り切れることとなるが、37の倍数であることが必要で、35が最小。これは30でも割り切れるので、f(35)/1110を計算すればよい。
計算できてほっとしてしまい、f(35)を答えて1ペナ。即座に直せるミスはよくない…
D
C着手前に図示だけしていた問題。
まず、3回まで手計算する。（どうせ漸化式を立てるとしても必要になる上に、検算にもなるため）
すると、具体的な座標情報はそこまで必要でなく、領域と点を指定すれば移動後の領域も決まってくる。実際、合同な9個の小三角形領域に分解すると、推移が比較的うまく書ける。ただし、境界をきちんと追わないと、対称性が消えたり誤答に繋がってしまうため、そこだけうまく領域分けを遂行する必要がある。重心や頂点、外周は通らないので、これは除いてよい。
外側の三角形（境界含む）の領域をX
A1A2を含む小三角形の三つの領域（内部）をY
それ以外をZとすると、推移が描けて、結局X,Yにいる確率x_n,y_nについて漸化式が立つ。後はそれを解くだけ。
案の定境界条件で頭が混乱したが、手計算の準備と漸化式自体がそこまで煩雑でなかったことが幸いして、ペナルティもなく計算できた。
途中漸化式と答えが大まかに見えたところで、あとでもう一度検算することにしてAをチェックしてた。
A
|sinx|,|cosx|をそれぞれ書いて、和を見る。結局端点と真ん中で最大最小が決まり、それ以外のところでは8つ解がある。
(1+sqrt(2))を電卓でチェックして提出。
B
2^(2^(2^(…)+1)+1)的なことだけど、mod素数を見るときに、p-1の剰余、φ(p-1)の剰余…となってよくわからない。φ(2^16+1)=2^16,φ(φ(2^16+1))=2^15..と減っていくものの、+1があってちょっと複雑…と思っているところで、そもそも2^(2^大+1)という形なので、フェルマーの小定理から2と合同だった。
E
最後に残していた幾何。条件がよくわからないので、計算に走ることになりそうなタイプ。
図を書くと、ミケル点の構図なのが直ぐわかる。AB∩CD=Eとして、円ADEと円BCEの交点をXとすると、XAB≡XDCで、角度を追うと∠ADC=∠XCDが従う。
ここからうまい相似が見当たらなさそうだったので（実際にはADの中点、BCの中点を取るとよい）、BC^2=xとして、ミケル点の性質と角度から立式。
AC^2=a BD^2=b ∠BAD=3t,XA=XD=sとすると∠XAD=120-2tで
89+80cos(120+t)=a
89+80cos(3t)=b
(s^2+25-x(s/8)^2)/10s = (89-a)/80 (= cos(120+t))
a+b=x+78
cos(-2t-240)=cos(120-2t)=4/s
となり、120+tをtと置きなおしてもcos(3t)は変わらないことに注意して
x=100+80(cos(3t)+cos(t))=100+160cos2tcost
(s^2+25-xs^2/64)=10s*cost
cos2t=4/s
->頑張って解いてs=5sqrt(3)で、代入していってxを計算できる。
この計算における立式、ミケル点を経由している必要があまりなくて、直接EA,EDを変数でおいて余弦定理で立式した方が機械的だし速いという…
感想と反省
6問正解88分5秒1ペナで3位でした！Eの計算判断や立式がもうちょっとうまくいってればという反省こそありますが、すべて正答できたのは良かったです。Eで時間がかかったのは多少は仕方ないとはいえ、ミケル点などの考察はしなくても最初から計算で突破できたようなので、そこは判断を誤ったかもしれません。
問題セットとしては、前半と後半の難易度差が大きいものの、後半3問は計算のステップ数が多めでじっくり時間をかけてやれるタイプの問題であったため、常に何か手を動かしていた印象の残るセットでした。3問ともdifficulty 2000オーバーということで、結構重めの問題が並んでいた感じです。
個別の問題としては、D問題が好みでした。いい感じの座標を取ればもっと簡潔に導けそうな気もしますが、どうなんでしょう？他にはC問題がgcd(n^3+1,m^3+1)でそんなに大きくなるものがあるのは数字的にちょっと面白かったです。F問題はいろいろな典型が凝縮されていて教育的かつ作業量が多く、サクサク進められるので気分は良かったですが、やはり約数の個数のところがやや消化不良という感じがしました。（式変形の代数的背景自体は面白かったです）指数の振り分けは頻出なのでもっと脳を整理しておきたいところ。ちなみに、久しぶりのdifficulty2000オーバーの整数分野の問題でした。B問題は作問の種としてストックしていた問題の影響で余計な考察をしてしまいましたが、もう一段階面白くできると思いました。
ちなみに、チーム戦は優勝できました！Captainということでちょっとだけ力んでましたが、いい緊張感になったようです。
雑多なトピックス
ネタがやや不足しているのでまた統計データで遊ぼうと思います。
今回は問題の点数とdifficultyの相関と、内部レートランキングを調べてみました。
問題の点数とdifficultyの分布
問題の点数とdifficultyが本当に一致しているのかどうか、また、古い問題と新しい問題とで特徴があるのか、ちょっと調べてみました。
問題番号1000番ごとに点数でのdifficultyの平均値を出しました。
薄い点ほど昔で濃い点ほど最近です。
まず一般的な傾向として、200と300にはdifficutlyの数値上は大きな差があります。（ただし、difficultyの幅を線形に見るのが正しいと仮定する場合ですが）
また、300点までの問題は昔の方がdifficultyが高いですが、400点以上からは一気に傾向が入れ替わります。
400点と500点 および 600点と700点 の間はあまり大きな差はみられず、感覚とは一致しています。
もうちょっと有用そうな数値計算できそうですが、面倒なのでこの辺で。
「内部レート」のランキング
内部レートというのは、こちらの記事を参照していただきたいですが、OMCのレート計算において参照されると思われる値です。（AtCoderと同様というのを仮定しています。実は詳細が異なるかもしれません）式で書くと以下です。
正確には上限がついてしまうパフォーマンスに対しても「内部パフォーマンス」によってpf_iを定める必要がありますが、参照先がわからないので、パフォーマンスを参照することとします。
上位50人を張ってみます。
diffでのマイナスが大きい人は
・まだ出場回数が浅く収束していない
・直近で失敗している
といったことが考えられます。参加回数とdiffの分布も見ると、以下です。
この記事が気に入ったらサポートをしてみませんか？