OMC210 参加記
おはようございます。
本記事では2024/2/28に開催されたOMC210 (エリジオン杯)の感想などを書いていきます。
expertです！ようやくratedが月一という所に慣れが出てきました。前回結構失敗したので、なんとか頑張りたいなと思っていました。加えて、エリジオン杯ということで、賞金付きのコンテストになります。「エリジオン杯」はどれくらい続くんでしょうかね？
また、事前情報で、Niov0256さん単独writerということで、何かしらのコンセプトと高い難易度のセットが期待できて、始まる前から楽しみでした。
参加時の動き
配点は3-5-6-7-7-9
時間も15分延長されて、165分と、前回の120分とは変わってじっくり取り組めそうな配点になります。こちらの方が途中で少し失敗してもリカバーできるので、個人的には好み。また、参加したコンテストの中では初の900点の問題を含むセット。ただ、それよりも前に600,700,700があるため、おそらく取り組めなさそうだなと思いつつ、300,500,600をしっかり解ききるイメージで臨む。
A
整数で乗法的関数、上から約数関連の制約がある、という問題。
小さい方の値から吟味してみると、f(1)=1で、乗法的関数なので素数の挙動だけチェックすれば十分。ここで乗法が分解するところと二つ目の条件から立式を試みるも、煩雑になり、少し迷走。
ためしに素冪を見ると、p^nのn→∞で(σ(p^n)d(p^n))^{1/n}がpに収束するので、f(p)<=pが得られ、逆にこれを満たすものはすべて条件を満たす。
二つ目の条件の分解に着手するのが速すぎて迷走しかけたものの、泥沼にはまりすぎなかったのは良かった。FEをOMCで出すのは難しいという認識だけど、丁度よくて、作問が上手だなと思った。
B
集合内の部分和で整数を網羅できるようにするには、どのように選べばよいか、という問題。この問題でいうSが与えられたときにフレキシブルかどうか判定する際に、Sの元を小さい方からチェックして、○×を埋めていく、ということを考えることで、S内の要素a_1<a_2<…<a_k の条件がわかる
具体的にはT(k) = a_1+…+a_kとして、T(k)まで部分和で書けるとわかっているときに、a_(k+1)を追加すると、T(k)+1 < a_(k+1)のケースで、a_(k+1)-1を構成できなくなり、詰む。(a_(k+1)以降の元についても同様の不等号がわかるので作れない）よって、T(k)+1 >= a_(k+1)が必要。これを満たす時、T(k)以下の構成を活用すれば、そこにa_(k+1)を加えれば達成でき、十分である。
あとはこれを丁寧に数える。1~5の和 < 16 < 1~6の和に注意してカウント。
この手の部分和系の問題は競技プログラミングとかでありそうなタイプの問題だなと思った。意外とこの聞き方での数え上げはしたことが無かったので面白かった。ところで分野判定はＡらしい…？
C
これを大分簡単にしたような問題（単調増加なものを数えるだとか、条件付きで操作が止まるものの確率をもとめるだとか）はbeginnersとかにも出てきている印象。
ただ、手数の3乗の期待値、ということで何かしら大変な計算がどこかで要求される。
まずは確率分布を確認。ボールに書かれた整数が長さnの単調増加な列になるものを数えて確率を計算したい。（また、そうでないとき終了する。）
n回丁度かかる確率は、最後に出る数によって数が変わってくるため、n回以上と言い換えて確率を計算してみる（条件付きで操作を終了するタイプの確率ではよくある手段）と、単調な列n個を固定するだけでよいので、256Cn-1/(256)^(n-1) となり、これの差を見ることでn個で終わる確率がわかる。
後は、(n-1)^3の重みをつけて和を見る。
Σ(3n^2-3n+1)256Cn/256^n を求める。あとは多項式*256Cn*p^n みたいなものを必死に求める。二項定理を部分的に使う。
解説では(m-n)/nという形することで、計算の煩雑さを回避していた。表示もきれいだし、賢い。
D
設定がとてもシンプルなので、即座に座標…のはずが、符号を間違えて、計算間違いを踏んでしまった。概算した数値もそこまで変な箇所の無いものが答えとして出てきたので、そのまま投げてしまった。
あまり幾何学的考察をしていないので、書くことがないけど、スピードを重視した結果結局60分溶かしていて、前回と同じような失敗になってしまったが、最終的に計算を合わせられたので良かった。40分ぐらい計算ミス除去と格闘していて、成長していない。。
CA後解いた人数を初めて確認。Fは誰も通しておらず、C,D,Eともにそこまで多くない感じ。Dの計算ミスが見つからない間にEの題意は何となく把握していたので、これを解けばそこそこ良い結果になると信じてEへ。
E
2^k個入りパックをa_k個買うとして、
Σa_k*2^k=11111
a_1は偶数
という状況で、a_kを決めたときの四種類への振り分け方が (a_k+3)C3 通りあるので、Σa_k=奇数となる範囲でのΠ(a_k+3)C3の和とΣa_k=偶となる範囲での同じものの和を比較する、という問題。
まず (a_k+3)C3の重みを無視して、対応付けを考える。あるパックを合わせて次のパックとみなすような対応付けがよさそう。ただ、これだと重みをうまく反映できない。
この近辺の操作でよい対応付けを与えようと頑張っていたが、結局わからなかったので、小さい方のｎで計算を試みる。2個入りパックでの制約的に、小さいnとは言っても小さすぎると全部奇数個のケースなどが漏れるので、最低でも8以上の分を計算。
8,9,10,11,12,13,…
376,560,800,1104,1480,…
前述の「重み」が3次式なので、ここでも3次式になるのかもなと予測し、時間切れに気づかず、計算を遂行して3次式を出したところ、手元で求めていたn=16までよさそうだったので、投げてみたらCAで、先にこれをやっておけばよかったと後悔。Dでの浪費がここで効いてきました。
ちなみに、公式解説は形式的冪級数を用いたもの。問題の整理の記述にたどり着いた時点で気づくべきでした…
また、ユーザー解説で最初にやろうとしたうまい対応付けを追いかけたものが説明されていて、目から鱗。
内容としては、
品種Xの2^k個パックa個 2^(k+1)個パックb個ある状態と
品種Xの2^k個パックa-2個 2^(k+1)個パックb+1個ある状態
の対応をつけて、そこ以外を動かさないようにすれば、良い買い方と悪い買い方の対応が付く（つまり差としては相殺される）。この対応付けで、a+2bが一定で、[(a+2b)/2]が偶数の時、対応付けで余りが生じる。この余り分を2^k個のパック0個、2^(k+1)個のパック[(a+2b)/2]＝[a/2]+b個のケースに割り当てる．
以上を帰納的に繰り返す（[(a+2b)/2]が偶数の時に、2^(k+1),2^(k+2)個パックに対して同様の議論を行う）ことで、どこかで相殺させることができ、差として考えるべきものとして、個数が大きいパックは考えなくてよさそう、ということがわかる。
あとは初期条件。「2個入りパックの合計が偶数個の中で」という制約があるので、これに基づくと、2個入りパックを奇数個買う品種を先に固定して、奇数個買う品種に対して2個入りパックを1個購入したことにして引いておくと、各品種で2個入りパックの個数が偶数異なり、前述の帰納法のk=1の話がスタートできる。
したがって、最初に決め打ちした2個入りパックの奇数個買う箇所（あらかじめ1個購入したことにした箇所）の決め方と、残りを1個入りパックで分ける方法の分が差として残る（良い状態/悪いを変更できない）。これを計算すればよく、8以上のnで
2個入りパックを奇数個買う品種が4つ:(n-8+3)C3
2個入りパックを奇数個買う品種が2つ:4C2*(n-4+3)C3
2個入りパックを奇数個買う品種が0つ:(n+3)C3
と計算できるので、これらを合わせて4/3 (n-2) (n^2-4n+15)となる。
感想と反省
4問正解126分29秒2ペナで7位でした！コンテスト中は順位表は確認しておらず、700点の幾何にしてはシンプルで計算のやりようが結構あるDで大分時間を消費した上にペナルティもかさんだので、問題を解いた人数分布的に厳しいかなと思ったら、CとDを両立している人があまりいなかったため、想像以上の高順位になりました。嬉しい誤算ですが、時間切れの後Eを通すまでの時間とDでロスした時間を鑑みると、5問正解する可能性もあったなあと思うと悔しいです。コンテスト時間中に900点以上の問題にチャレンジしてみたかったですが、その夢は叶わず。
一方で制限時間が長めだったおかげで、Dでの計算修正も(時間はかかったものの）落ち着いて取り組めました。思えば、過去のexpert失敗回は計算修正に追われているものが殆どですので、そこの技術は自分の認識よりも本質要素かもしれません。また、Fに難問が置かれており、そちらを一発逆転で取りに行った人たちが何人かいたことも想定以上の好成績の要因のようです。
問題セットは少しC成分が大きい気もしましたが、数オリなんかも、「実質的に組み合わせ」みたいな問題が多かったりすることを考慮する（「典型化、既出を避けた結果幾何と組み合わせだけになってきた」と主張する過去の猛者を複数人観測しています）とこれぐらいの比率でも別に違和感はないかもしれません。個別の問題について、コンテスト中に向き合った問題はすべて面白かったです。AはFE(数列)で変な設定はない中ちょっと極限の議論も出てきて最近の数オリっぽい傾向かつお手軽な難易度で素数のみ考察した人を適度にふるい落とせる良問で、Bはよくある設定の中地道に考察/計算を重ねて数え上げていく求値Cお手本みたいな問題、Cは二項係数および剰余の上手な処理方法、Dは少し計算が重いながらもシンプルな設定で幾何でも計算ゴリ押しでも向き合える問題、Eは母関数かうまい考察かで分かれますが、これも適切な難易度で面白かったです。本番触れられなかったF問題は後述しますが、分野複合に該当する問題で、こういう複合系の問題に対してはシンプルに検算や誤り検索のステップが膨らむので解く側としてあまり好きではないという持論を持っています。一方で作問体験みたいな設定でそこは面白いなと思いました。極論、全く関係ない問題を複数問並べて、それぞれの答えの積とかにしてしまえば時間的にも難易度的にも（分野跨るという性質上）難しくなるので、なるべく「関係性」「つなぎの自然さ」が欲しいなと感じるのと、そもそも「複合」とは何なのか、というところが観点としては挙がりそうです。今回の問題は分解した各々の問題は面白いと思いましたし、複合元の「つなぎ」もそこまで不自然ではないかなと思いました。
ともかく、重くて面白い問題をじっくり考える、というタイプの4eっぽいコンテストだったので、非常に楽しかったです。次回の4eで年度内最後と思われますが、年間ランキングで意外といい位置にいるので、現4強に次ぐぐらいの位置には入り込みたいなと思っています。
年間ランキングの方を見ていて思うのが、自分が失敗した174,204は上位勢がしっかり成績を残しているのに対し、割とうまくいった180,186は上位勢が渋めなので、奇をてらった（？）回に強いのかもしれません。回ごとの特徴が個人の順位からも読み取れる気がしますね。
5～8位は計算式的には団子といってよい
解ききれなかった問題
F
時間が無かったこともあり着手できなかった問題。一応、メタっぽい感じ（OMCでは割とあるイメージ）で、複合分野だな～ぐらいの認識で本番は考察は全くしてませんでした。
メタ要素の前に最初の問題が難しそう。ある意味作問体験コーナーみたいな感じですが、今回は計算機とかを使えないという観点ではかなりハードになることが容易に想像できます。
まず幾何部分ですが、そもそもこれがコンテスト時間内でどうやっても解けなかった説が濃厚です。内接円の半径をrとすればp^2=R^2-2Rrなので,
rをうまいことa,p,qで表すのが目標。
ゴリゴリ座標計算（OMC,OABの中心とそれを通る直線lを求め、PはlでＯを対称移動させたもの、I,Oはいつも通り。）したものの、式がきれいにならない。いろいろ線を引いてみる。
CI∩AB=X,MD∩OI=Y としてX,P,Yが同一直線上、といったところまで何とか角度追跡で追って、計算をしてみたものの非常に汚い形になり、全然いい条件に落とせてなさそうだったので、解説を読んでしまいました。
→方針、幾何事実の着眼点はかなり良いが、計算のまとめ方が下手。反転すると見通しが良い。
R^2(-p^2+2q^2+a^2) = (pq)^2を得た後についてもa,p,qからABCが存在するかどうかの議論については反転の部分が効いてくる議論を行っており、この部分はもう一度考える必要がありそう。
後半の整数パートは、剰余と不等式から(-p^2+2q^2+a^2)=1を言って、そこから剰余を見つつしらみつぶしに見る。これ単体ならそこまで難しくはなさそうですが、三角形の成立条件のところの言いかえがうまくいっていないと、ここもかなりハードになり得ますね…
全体的に解説見ただけになってしまいましたが、幾何パートでの正確な計算整理、三角形成立に関する議論のエスパー、整数パートの剰余での範囲絞り＋愚直探索 をすべて満たしてたくさん時間をかけても自分の現状の実力だと解けるか怪しいです…
あと、複合問題とはいえ、各要素がそこまで独立した直和っぽい問題にはなっていないかなと思いました。
雑多なトピックス
作問
不採用問題を投稿しました。証明問題向けのものはありますが、皆さんどうぞ。
NGC
ポロロッカにて2/21~2/23に開催されたnatsunekoさん開催の幾何コンテストについて少しふれておきます。212のwriterのようなので、出場予定の方はやっておくと良いかもしれません。
A:共円を見つける求角。少しつまりました。
B:全力でペナルティを狙っている問題。ペナルティポイントが複数あります。問題としては適度に相似を探す感じで面白いです。
C:少し幾何情報を追った後はいろいろ長さを求めた。幾何情報は追いやすい方。
D:登場する情報がとても具体的なので、ひたすら計算してしまった。幾何学的性質は殆ど何もわかっていません…
この記事が気に入ったらサポートをしてみませんか？