C分野の問題で使えるかもしれない手法について

この記事は、競技科学people 2nd Advent Calendar 2025( https://adventar.org/calendars/12239 ) の21日目の記事です。

はじめまして、Germanium32と申します。
C分野の問題のテクニックについて書きます。
(この記事の内容が当たり前すぎると感じる人もいるかも知れませんが、ご了承ください)

この記事で言いたいこと

盤面に対して操作を行い、最終的な結果を最適化しよう、という問題には、盤面に対する量を定めることでうまくいくかもしれないです。

いくつかの例

①JMO2015本選 問2
https://www.imojp.org/archive/mo2015/jmo2015/problems/jmo25mq.html

あり得る有益な点の動き方として、
・次の段に進む
・同じ段の中で端に進む
の2つがあります。また、
・ある段の正六角形の頂点に来た場合、必ず次の段に進むものがある
・それ以外の頂点に来た場合、正六角形の頂点に近づくことができる
が分かります。よって、
・中心の点を除いて、正六角形の頂点の矢印の中で次の段の正六角形の頂点にそのままいくものがない
・それ以外の点は次の段に進むものがない
を満たす盤面の時、
①始め、どこか1つの頂点に進む
②それ以降は、
・頂点にいるなら次の段に進む矢印の中から1つ選んで進む
・それ以外の頂点にいるなら、同じ段の頂点に進む
を繰り返すことで、k=2n-2が構成できると分かります(最後の1回は頂点に進まなくて良いことに注意)。

これが最適であると示しましょう。有益な点の動き方が2つあるので、これらをまとめてスコアを構築します。
点がn段目にあり、その段の正六角形の頂点のうち、一番近いからものからの距離がkの時、スコアを2n-kで定めます。
すると、どの頂点についても、6方向のうち、スコアが増加する頂点が4方向あると分かります。
よって、どの4方向に矢印が書かれていたとしてもその中で1つはスコアが増加する矢印が存在することになります。
いま、始めはどこか1つの頂点に進むしかなく、この時点でのスコアは2です。
もし、k≧2n-1となる盤面が存在したとすると、2n-2回動かしても周上にある点にたどりつかないことになります。
この時、最終的なスコアは2+{(2n-2)-1}=2n-1以上にすることが可能になるはずです。
しかし、周上以外にスコアが2n-1以上となる頂点は存在しないため、矛盾が言えます。
よって、背理法よりk<2n-1がいえたので、構成と合わせてk=2n-2が答えだと分かります。

②EGMO日本代表選抜2025 問4
https://www.imojp.org/archive/mo2025/jegmo/problems/jegmo14q.pdf

後ろのものから等しくしていくという方針をとることで2026が達成可能です。
これが最小であることを示しましょう。
箱iに入っている個数をAiとして、ある状態の”スコア”を1以上2025以下の全ての整数iに対して、$Ai*2^{2025-i}$の総和と定めてみます。
すると、操作前のスコアは$2025×2^{2025}$で、操作後のスコアは最後に残る個数をcとすると、$c×2^{2025}$となります。
いま、1回の操作によってスコアは必ず増加すること、1回以上の操作が必要なことからc>2025が分かり、cは整数なのでc≧2026が示されました。

最後に

2つの問題のように、いくつかの要素を一つの変数にすることでうまく評価できる場合があります。
この手法が全ての問題に適用できるわけではないですが、有用な手段の一つだと思います。