OMC215 参加記
こんばんは
本記事では2024/3/20に開催されたOMC215 (お茶ゼミ√+杯)の感想などを書いていきます。
二回連続の賞金付きコンテストになります！再び運営（natu_mathさん）出題のコンテストになっていて、賞金付きでは初の8問4bなので楽しみにしていました。
問題ページは以下です
参加時の動き
1-1-2-2-3-3-3-4そもそも賞金付きの4bは181以来で、この時は全体的に難易度が高かったイメージがあるので、後ろの何となくの題意を把握してから解けるものを選択する感じで（結局いつも通りかもしれない）
E
1~a*bまでに良い数xはab-(x-1)回カウントされ、
良い数は全部でa+b-1個
良い数の和は(1~b)a+(1~a)b-ab
なので、a=999,b=1001として上記を計算する。
abのところの処理に少し慎重になったが、考察が一瞬だったおかげでFA
別にFAの点数とかもないので、もっと慎重になった方がよかったかもとは思う。
A
一瞬とても難しい問題に見えるけど、分母と分子で変数が独立しているのでf(x)=x^2-1001x+1001^2の最大最小を取る整数を探せばよい。シンプルな事実だけど聞き方が面白い。
B
i行j列にi+j mod 3を書き込んである一つの数字だけ旗を置かないと最大になる。典型といえば典型だけど、214のEが400点でこれが100点なのは謎。
C
結局指数和が偶数 かなり典型
どうしても「これ審査通るのか…」という目で見てしまう。
D
|ACD|=1000とすると|ABC|=3004,|AXY|=1000*3/1000*1/4=3/4
|AYZB|=2002-3/4,|YZC|=1002+3/4で、3004*(1-x/3004)*3/4と一致するのでこれを計算する。
F
円ABDと直線ACの交点のうちAでない方をFとすると、EF=51*47/61 > 21より、Cは円の内部に存在する。角度条件より、DCFは二等辺三角形。
CF=2a,AD=x,DとCFの距離をhとして
h^2+(a+21)^2=51^2
h^2+(a+82)^2=x^2
(2a+21)*61=51*47(方べき)
と合わせればxがわかる。解説は円ABEと円DECがAD上で交わることを用いていて面白い。
H
頂点番号を0~3n-1として、正三角形になるのはk,k+n,k+2n で、n種類。これらをグループ1~nとすると、それぞれ共通部分を持たない。
2つ目の条件よりfは全単射
3つ目の条件より、あるグループ内の元は同じグループへと移る。したがって、グループでの写像と思った後に、細かい元の行き先を考える。
グループ間の写像として見たときに、あるグループiが同じグループiに移るときは一つ目の条件より、2通り
グループ間の写像として見たときに、あるグループiが別のグループjに移るときは一つ目の条件より6通り
したがって、同じグループに移るグループ番号がk個あるとき、
a(n) = (n,k)2^k6^(n-k)(k個の元でf(t)=tとなるもの、つまりモンモール数)となる。
これを計算する方法がパッとわからなかった（母関数で計算可能とのこと）が、a_nについての漸化式を考察することを試みる。
a(n+1)を求めるとき、
グループn+1がグループn+1に移るケース 2*a(n)
グループn+1がn+1でないグループiに移るケース
グループiがグループn+1に移るケースはa(n-1)*6^2通り
グループiがグループn+1に移らないケースは6*(a(n)-2a(n-1))通り
iの選び方はn通り
以上より
a(n+1) = 2a(n)+6n(4a(n-1)+a(n))
を得る。a(1)=2,a(2)= 2^2+6^6 = 40で、 a(n+1)-6(n+1)a(n) = -4(a(n)-6na(n-1))と変形できるため、b(n) = a(n)-6na(n-1)とすると(-4)^nとなり、あとは剰余を計算するだけ。4bにしてはステップが多くて難しめ。
G
Hに取り組む前に考察したものの、部分的にしか制約がわからず、いろいろ代入するものの不明点が多かったので、一旦飛ばした問題。
条件のi,jは等しくてもよく、この時(a_i)^2<=i^2+20なので、10以上ではa_i<=iが得られる。よって20から埋めていけば11以上では恒等とわかる。
続いて、a_20*a_j<=20j+20よりa_j<=j+1なので、今度は小さい方から検討すると、2冪とわかる。a_10は残りの元として一意に定まるため2^9
i=jの代入に気づくのにかなり時間がかかった
なぜか2^9=256としてしまい、1ペナ。前も2冪の計算で早とちりした記憶があって、よくない…
感想と反省
8問正解54分41秒1ペナで3位でした！前回と同じく、いい感じで終えられました。G問題でペナルティがあったりiとjが等しいケースを見ることによる評価に15分ほど気づかなかったりと振り回されましたが、E,F,H問題がすんなり解けたことが幸いして、15分のロスを取り返した順位になりました。H問題はかなり難しかったようで、久々に4bでdifficultyが2400オーバーになっていました。
セットとしては、A~Dがかなり易しめで、Eが最悪作業量でごまかせるタイプ、F~Hはかなり難し目というような二極化した問題内容で、特に後半はもはや無印でもよかったのではないかという歯ごたえでした。
それぞれの問題についてですが、A~Eだと、Aの聞き方が割と面白いかなと思いました。F,G,Hはどれも面白く、難易度を無視すれば解きごたえ的にも参考にしたい3問でした。Gでiとjが異なるものについても結構面白そうなので、考察してみると面白いと思います。Hはaがそもそも求まりますが、ああいう聞き方になって難易度が上がっているかもしれません。真似するにしても少し注意を払う必要があるかも？（指数型）母関数を用いた計算方法はちゃんと手札として持っておきたいなと思いました。
雑多なトピックス
前回に引き続き、分野ごとのOMC特徴づけを個人的見解に基づき列挙していきます。今回はC分野について書いていきます。
数え上げ、最大最小（構成/評価）、スコア計算、グラフ、bit/進数関連、二項係数計算、確率/期待値、マッチング、ゲーム
といった分野でしょうか。求値という性質上、競技プログラミングと被っている部分が多いようで、逆にそちらの勉強をするという方法もあるかと思います。
数え上げ
一番スタンダードなC分野の出題は条件を満たすものの個数を数えるタイプの問題でしょう。いろんな分野とも複合しやすく、C分野判定でなくても「数える」という問題はとても多いです。汎用的な手法というのは存在しないため、系統立てて記述しにくいですが、いろいろな典型や手法があり、数学オリンピックとも少し違う傾向のものもあります。
・対称性に注目してうまくサボる
様々な対象性を見つけて数える対象を小さくするのは頻出です。
他の項目でも共通ですが、OMCだと愚直数え上げはあまり出題されず、何かしらのきれいな式に準拠している（とても大きい数字に対して剰余などを求める）ことが多いです。逆に数オリだと対称性に着目することで落とし込んだ先も愚直数え上げ、という問題の比率が多い印象です。
・ダブルカウント/主客転倒
「主客転倒」というネーミングは競技プログラミング由来と思っていますが、ともかく、同じものに対する数え方を変える、視点を変える、というような考え方です。より狭めると、コストやスコア系の計算において、要素ごとの寄与率を見て数え上げやシンプルな計算に帰着する、というような話で典型技術としてくくられています。ネームのルーツ通り割と競技プログラミングの方が出ているというイメージです。ここで記載するより、検索する方が速いと思います。
同じものを複数通りの数え方で見ることで等式を得るという形であれば、証明問題でも見かけるパターンではあります。(ここやここを参照)
・漸化式/手動DP
状態を何か変数で表現した後状態遷移を用いて漸化式に落とし込むものを指します。証明だとあまり出てこないですが、OMCだと頻出です。
また、漸化式が複雑（状態遷移が複雑）でも、項数が小さい場合は一般式が分からないケースに手でメモ化再帰を行う方法もあります。
・包除原理
これも数え上げにおける常套手段です。集合関連で問われることが多いです。OMCでの頻度はそこまで高くないイメージですが、出ないこともないです。
・ソート
大きい順や小さい順に並べて考察すると見通しがよくなることがよくありますが、OMCだと出現頻度が低いイメージです。証明におけるテクニックの一つと思った方がいいかもしれません。
・母関数
様々な問題を母関数（⊃形式的冪級数の多項式部分）に着目することで解くことができる問題が非常に多くあります。この手法を模範解答とする問題はOMCの方が結構よく見るイメージです。また、模範解答でなくとも作業で計算できることがあるので、関数の置き方や級数計算を含めて習得しておきたいところです。（自分も苦手なのでとにかくいろいろチェックしているところです）
最大最小（構成/評価）
数学オリンピックでは頻出ですが、OMCではそこまで出題されません。上からと下からの評価のどちらかが自明だとエスパーされやすいためです。証明系のコンテストだと部分点をつけやすかったり、不等式評価および構成の二つの能力を一問で測定できるといった理由でよく採用されているという認識です。不変量/不変パラメーターの構成が大事だったりすることがあります。
スコア計算
数え上げと似ていますが、状態ごとに定まった数値を「スコア」として総和や総積などを計算するタイプの問題です。こちらも競技プログラミングの方が頻出というイメージで、OMCだとさらに計算がある程度楽になる、という制約もつきます。
・言いかえ
二項係数難化とも関係しますが、組み合わせ的な言いかえを行うと見通しがよくなることがあります。この辺は汎用手法がないです。
また、求められている状態を別のわかりやすいい状態と対応付けて計算する、ということもよくあります。1:n的な写像の構成という話であれば、証明でも聞かれることがあります。
・主客転倒
数え上げのところでも述べましたが、スコア計算においては常套手段です。
グラフ
証明においても一定の頻度で問われるイメージですが、OMCでも構造を意識しておくと整理がしやすいケースがよくあります。ただし、汎用的な超強力な定理があるわけではなく、あくまで思考の整理の道具として頻出です。
・関数
関数を有向グラフとみることで見通しがよくなるケースがあります（functional graph)
・木
木構造もそれなりに出てくるイメージがあります。
特に、ラベリングを行った数え上げについて出題されることがあります。prufer code(wikipdeia)やケーリーの定理を知っていると都合がよいです。この辺の数え上げはOMC（や競技プログラミング）特有と思います。
・そのほか
主に友人関係について、森やクリークなどのグラフ理論での分類を用いるときれいに整理できることがあります。
bit/進数関連
予選ではたまに出る印象です。証明では組み合わせ的な方向性では見かけない印象です。
・popcount
2進表記の1の個数について、よく聞かれます。割とOMCだと多い、というイメージです。
・様々な進数
10進数を別の進数で解釈したり、階乗進数を用いたりすることがあります。
二項係数計算
こちらは単体というよりは複合的に出てくるパターンになりますが、
二項係数に関する計算や等式を用いた問題はよく出てきます。
様々な等式があるので、チェックしておくとよいでしょう。母関数との関係も大きいです。
確率/期待値
こちらは出題範囲の関係でOMC特有といってよいでしょう。実質的には数え上げに帰着することが多いですが、「期待値の線形性」も意識しておくと良いです。
マッチング
Hallの結婚定理を知っていると良いことがあったりします。OMCでも数オリでも頻度は少ないですが、知っておいて損はないです。
ゲーム理論
こちらは数学オリンピックでもOMCでも一定の頻度で出るイメージです。OMCでもよく出る理由としては、先手必勝となるパラメーターの総和や数を聞くなど、求値化が容易であって、grundy数やNimなどの典型パターンと複合しやすいという所から作問が割と容易という所が挙げられると思っています。
ここでいい感じにまとめられるほど筆者が知識を持っていませんが、二人完全情報不偏ゲームはNimK、grundy数(xor,mex)を最低限知っていれば考察自体は何とかなる印象です。慣れが大事と思います。
この記事が気に入ったらサポートをしてみませんか？