OMC184 参加記
本記事では2023/10/23 に開催された、OMC184 の参加記を書いていきます。
OMCを始めた当初と違いコンテストの頻度が非常に高く、とても楽しめています。何度も出場している兼ね合いでそろそろ177を超える大失敗回も来るんじゃないかなと思いつつも、ちょっと緊張慣れしてきたかなという感じがします。（ただし、開始5分前はだいたい緊張に負けています…）
問題ページは以下です。
参加時の動き
チーム戦も継続して参加しているので、C,D,Eあたりを開き、即答できそうなCから着手しました。
C:
見た感じ1/7の小数部分っぽいので、7倍したらいい感じに10の冪がでて、因数分解から素因数が特定できるんだろうなとめどが立つ。
実際、7倍すると10^18+27で「3乗+3乗」なので因数分解できて、あとは49で割れるのを探して計算するだけ。7の倍数探しでちょっと混乱して（電卓使えばいいだけなのに。。）遅くなりました。
DとEだとDは計算できそうな幾何で、Eは泥沼化しうる不等式。ちょっと考察して厳しそうだったらA,Bで安心するという立ち回りを意識してDへ。
D:
シンプルな問題文とわかりやすい情報という印象だったので、ひとまず図を書き、本当に計算可能か吟味することに。
三角形EACと三角形EDBが相似なので、CD:BD=3:7 よってCD=3xとおくと、この相似からAB=5x^2-6, BD=CD=7xがわかる。円周角の定理から∠BACと∠BDCは等しく、余弦も一致。よって、それぞれの余弦定理の式が立ち、統合で結べる。x^2に関する三次方程式を解くことになるが、実はＡとＤが一致するケースを含むことからx=2を解に持つ、つまりx^2-4で割れるということを意識すると計算しやすい（そもそも全部整数解になる）
5x^2-6>0とあわせてx^2=3がわかり、あとは相似比でもトレミーでもなんでもいいのでADをもとめて足すだけ。
そんなに計算も重くないので、もうちょっと早く解けるべき問題だったかも。
Eを見るも、即座にはわかりづらそうだったので、A,Bで落ち着くことに
A:
1001の素因数分解は有名（大きい数が7,11,13の倍数か判定したい時に3桁ごとに見る、という帰着で使えますよね。）で、あとはそれを配分するだけ。
典型の塊なので、200点でこれを出題するのか？と（最近作問してる都合で）疑問に思ったものの、結果を見てみると結構解かれていないので、出題者の意図は正しかったという… NとCの複合みたいな問題なのも解かれにくい一因？
難易度判定の難しさがよくわかる一問。
B
濃度についての漸化式が立ち、それを解いて評価する問題。
最初50mlをかわりに入れると思っていたり、漸化式の途中で二倍を忘れていたりして、1ペナ。
そのあとも方程式立式と評価の二次方程式を解く部分で妙に苦戦してしまい、結構時間を食ってしまった。
difficulty的にはAよりも易しいらしい。受験数学っぽいものはみんなできるんですね。
E
まず式を書き下すとa1の部分は0になり（したがってa1は任意）、残りの部分も係数が正なら0以上になるようなことがうかがえる。実際に、それぞれの中身はヘルダーの不等式で不等式が示せる。負のケースでの扱いをきちんと調べる必要があるものの、だいたいx=yで下から良い評価ができそうというのは雰囲気としてある。
実際いったん係数をわすれて整理すると、2^(k-1)(x^k+y^k)-(x+y)^kはすべて(x-y)^2で割り切れる。割った後の形は順に1,3(x+y),7x^2+10xy+7y^2 となるので、あとはこの二次式の最小値を評価することになる。
具体的にはa4(7x^2+10xy+7y^2) + a3(3(x+y))の最小値を求めることになるが、まずa4>0が必要。また、偏微分などを行うことで、x=y=-a3/(8a4)の時に最小値 -3a3^2/(8a4)を取ることがわかる。したがって-3a3^2/(8a4)＋a2 >= 0が必要十分条件となり、あとはこれを満たすものを数えるだけ。
ここまで40分程度で、割と良いパフォーマンスを維持してFへ突入。
F:
最初条件がよくわからず、{7a+c,…}としてありうるものを列挙しようとしていると、よく見たらa,bは7倍されていて、c,dはそのままという形なので、縦に7での商、横に7の剰余を書くことにすると、部分集合Sとして選ぶ元に印をつけて、印をつけた元が長方形になっていないものを数えればよさそう、という言い換えを思いつく。
しかし、ここからちゃんとした進捗をえられず。。
終了数分前にN=21っぽいというところまで評価できたものの、それを数え上げるに至らず。以下思考
---
まず、小さい盤面a*aで実験。端っこに置けばいいのではないかと、そもそもN=2a-1なのではと誤った考察をする。これの数え上げを考えるも、よい帰着を思いつかない。最短経路から置換を行ったもの、と思ったものの、経路の長さでいろいろ話が変わってくるため、うまく一本で計算できない。
さらなる言いかえを模索するも、思いつかないので、一旦小さい数で実験する。（この判断があまりにも遅い。。後盤面が小さいので直接数え上げようと思うべき）
実際にa=4を調べているとそもそも7個よりもおけることが発覚し、完全にフリーズ。もっとシンプルな評価を考えるべく、印が2個以上ある列に着目し、印がついている部分の行を考えると同じ列に高々1個、という評価から、その領域に関しては高々(n-1)/2+2個か置けない、という評価ができる。
ただし、これをk個で考えても普遍的な評価にならず、5や6で考えていると2個おけたり3個おけたりする部分が複雑に関係していて、行き当たりばったりの評価にしかならず、思考がまとまらない。
そこで7で実際に構成して愚直にやろうと考えてみると、7のケースでは評価がきれいになり、各行列に3個ずつ印をつけられるということがわかる。
実際に7*7のマスに書いてみるときれいに印をつけられる。これを漏れなく数えるにはどうすればいいのかわからないなあと思っているうちに時間終了。
----
振り返ってみると、数字の小ささから局所的議論にすぐ行くべきでした。こういう愚直な数え上げは時間がある場合はできないとダメですね。
感想と反省
5問正解45分41秒ペナルティ1で18位でした！
Eまでは比較的サクサク解けていたので、その保険もありなんとか高順位にはなりました。
60分あってFで愚直な書き出しを実施しないのはよろしくないですね。なんとしてでも解く、という心意義が足りていませんでした。
レートの方は一応上昇して、黄色まであと少し、という結果になりました。そこは素直に喜ばしいです。
グリッド入りの計算用紙を仕入れておく必要性を感じました。普段はコピー用紙を計算用紙としているので。
チーム戦の方はぼちぼち、という感じでしたが、前回触れた強いチームが本領発揮してとてつもない好成績を出していたため、差をつけられてしまいました。
ともかく、大失敗は避けられているのはよいですが、後半の難問に敗北する回が続いているので、もう少し考察力を上げたいです。