OMC208 参加記

bzuL

こんばんは。
本記事では2024/2/21に開催されたOMC208の感想などを書いていきます。
regular回になります。事前情報で単独writer回であることが知らされていたので、何らかの一貫性のようなものがありそうで楽しみです。
問題ページは以下です。


参加時の動き

点数は1-2-3-4-4-4 なんとregularなのに500点以上がない！
というかそれはここにある必須要件を満たしていないような…

必須要件とは？

ということは、testerの意向で点が下げられた、という感じでしょうか。わざわざ下げる必要があるとういことは500としては相当弱かったという感じが想像できたので、早解き勝負を覚悟して後ろから解く作戦に。

F

OMC208 F問題

まだ2023の問題の在庫処理ができていない様子（年度と主張すればよさそうだけど）こういうのを見ると、やはり年号を設定しない方がよさそうだなとか思ったり。
約数は7^a17^b(0<=a<=2023,0<=b<=2023*2)という形で書けて、4|(a+1)(b+1)とならないようなa,bを用いて7^a17^b mod 100 を求めればよい。
一方で、mod 100ではφ(100)=40からその約数を調べていって
7->49->43->1
17^5 = 57, 57^2 = 49, 49^2 = 1 となることから、それぞれ周期が4,20となる。a,bの組について、mod4で(a+1,b+1)=(奇,奇)(奇,2)(2,奇)が解なので、(a,b)=(偶,偶)(偶,1)(1,偶) で17の冪を全列挙しつつ、17^5=57,17^10 = 49を用いると以下のようになる
17の指数で(0,10) + (偶数)
17の指数で(0,10) + (mod4 で1)
7* 17^偶
17の冪(mod4 で3は無視）→
17,89,-,21
57,69,-,41
97,49,-,61
37,29,-,81
77,9,-,1
これを列挙していく。
17^偶　は10進表記で偶9,偶1
7*17^偶　は10進表記で偶3,偶7
 1*17^(mod4 で1) は10進表記で奇7
49*17^(mod4 で1)は10進表記で奇3
これらをすべて足す。(0~9)*10+3*10 + (0~9)*10+7*10 +(偶数)*10+1*5 + (偶数)*10+9*5 = 900+100 + 200*2 + 10*5 = 1450
考察掘り下げから全列挙に切り替えるタイミングがかなり理想的だったので、比較的速く処理できた。FA取得！おそらくこの問題が400に下がったのだろうけど、確かに簡単…（加えて、無考察での全探索も容易）
あと「10以上」というのは結局考慮しなくてよくて、その議論をする割には10という数字が小さすぎるし、意図がよくわからなかった。（追記：この条件は問題文の「下二桁」の意味が通るようにするためのもののようです。ということは「100で割った余り」と思うのは考察ステップとして考えられている…？）

Eを少し取り組むも、ここでスピードを意識しすぎて誤読してしまい、難しそうだなと思ったのでDへ。

D

OMC208 D問題

比を移したり角度を移して相似を作りたいので、線をいろいろ引いてみる。
Eを通りBCに平行な線とADの交点をFとすると、△EFD~△ADBで、相似比がDE:AB = AE:AC と合わせると、AD=8が得られる。BD=4が得られて求まる。
（EF=xとしてDF=2x,AE=2x/(8-x),AF=2x^2/(8-x)とわかり、2x^2/(8-x)+2x=8からxが得られ、その後スチュワートの定理。）

C

OMC208 C問題

解をa1~a512として、P(-1)=10^1536より Π(a_i+1) =10^1536で、P(0)=Πa_iを最大化する。各変数が正であることに注意すると、ヘルダーの不等式を用いることができて結局すべて等しい。（ユーザー解説https://onlinemathcontest.com/contests/omc208/editorial/6082/420

に書きました）


B

OMC208 B問題

pが偶数→計算して不可能
pが奇数→p-1偶数なので偶数乗-偶数乗=345という形になるので積=345になって、絞れる。

A

OMC208 A問題

t=2sqrt(10)-1として、t+1の式に書き直す。3乗の係数が4なので偶数乗の身でうまく書ける。定数を調整して因数分解しやすく。
ちなみに、以下の通りで、表示の問題で誤答１。全体的に簡単だったため、このペナルティが命取りになるのはすぐにわかり、かなりテンションが下がるが、E問題が残っているので気を取り直す。

E

OMC208 E問題

最初、何も塗らないマスも許容すると読んでいたので、そのまま解こうとして小さいマス目で実験をして10分ほどロス。
気づいた後も、後ろのマスの状態で場合分けしようとしたものの、簡単な状態遷移にならない。
しばらく考えたのち、2*nマスで一番右の列の2マスが条件を満たすかどうかのみ考えれば（逆に2*(n-1)マス分は条件を満たすとしてよい）遷移が有限個の間で表せそうとわかる。
実際、
一番右の列の2マスが条件を満たすものの数をa_n
一番右の列の2マスのうち丁度1マスが条件を満たすものの数をb_n
一番右の列の2マスが条件を満たさないものの数をc_n
とすると，右の列の色の具体情報に関係なく以下のような漸化式になる
a_(n+1) = a_n + b_n + c_n
b_(n+1) = 2a_n + b_n
c_(n+1) = a_n
これをちまちま計算してもよいが、整理すると、a_(n+1)=2a_n+2a_(n-1)-a_(n-2) という4項間漸化式になる。これを計算すればよいが、実は(2fibonacci(n-1))^2と一致する。
漸化式の係数を間違えて小さいnで合わなかったり、そもそもこの方針はあまり目の付け所が良くないという感じで時間を使いすぎてしまった。
模範解の、白黒市松模様で塗って、異なる色は独立に考えることで一次元の話に帰着する方法は賢いなと思った。（こちらも一応自分の方法を書きました)

感想と反省

6問正解55分39秒1ペナで15位でした！E問題で迷走した分がちゃんと順位に反映されて少し低くなりました。今回はdifficultyもregularとしては初の全問題水色以下ということで、スピード勝負の回になり、その影響をもろに受けてしまったという感じです。逆にE問題以外は（Aで表示の問題があったとはいえ）結構いいスピードで解けたので、そこまで反省点はないですが、難易度に対してかけた時間が大きすぎるとこうなりますね。
問題セットとしてはregularというよりは4bと思った方がしっくりくるものでした。とはいえ、4bと思えば全体としてはいいバランスと感じました。
個別で見ると、E問題はかなり面白いなと思いました。こういう発想が即座に出てくるようになりたいものです。逆にFは作業比率が大きく、考察多めな人ほど損しそうと感じました。10以上という謎の条件からも見えますが、もともとちょっと違う問題だったのでしょうか。（追記:「10以上」は問題文の下2桁というところの意味が通るようにするための条件のようです。）
D問題の幾何はいろいろときれいに解けて、こういう問題が作りたいなと感じました。
ちなみに、F問題は問題番号が7777でした。

雑多なトピックス

コンテストと直接関係ない話を書く節を設けようと思います（何も書くことがない時はこの節は消えます）
今回はOMCの残り時間を表示するタイマーについて簡単に言及します。

左上の"Time Remaining"

OMC207の時にスマホの時計ではまだ終了時刻前なのに、ページの表示がfinishedになっていて、これがexpertで発生したら困るなあと思っていたのですが、ここに表示されるのは使っている「デバイス内の時刻に準拠した残り時間」のようで、問題を見るのに使っていたPCの時刻がすこしズレていた関係でこういうことが起きていました。OMC上で時間外の時にデバイス側の時間を時間内にした時の挙動までは調査していませんが、なんにせよ注意が必要です。AtCoderとかのように、サイト内の時間を表示してくれると嬉しいのですが。

この記事が気に入ったらサポートをしてみませんか？