競技プログラミングの強みと「典型力」について

「典型問題」という言葉。競技プログラミングにおいて、皆さん絶対聞いたことがある単語だと思います。少し長くやっている人であれば「典型とか言われているけど全然わからない」みたいなことも、よくあるんじゃないでしょうか？

そこで、今回は、「典型問題って何なのか？」みたいな話を、ちょっとしっかり書いていこうかな、と思います。

誰もが「典型問題」と疑わない問題について

例えば、こんな問題が出たら、誰もが「典型問題」という言うでしょう。

• N個の地点があり、M本の道路で結ばれている。各道路には、反対側の地点に行くためにかかる時間が与えられている。
• A地点からB地点に行くまでの時間を出力しなさい。

これは、最短経路問題そのままですし、ダイクストラ法などのアルゴリズムをそのまま適用して解くことのできる問題です。これが、一番分かりやすい典型問題です。

まとめ：「名前をついているアルゴリズムをそのまま実装」が、一番わかりやすい典型問題

人によっては典型となる問題について

さて、じゃあこれはどうでしょうか？ 

• N個の地点があり、M本の道路で結ばれている。各道路には、反対側の地点に行くためにかかる時間が与えられている。
• A地点から、地点a,b,c,d,eを全て通った後、B地点に行くまでの時間を出力しなさい。

これは典型になったり典型にならなかったりします。

「最短経路はダイクストラ法！」というのは、相変わらず典型です。しかし、ダイクストラ法そのままのアルゴリズムでは、「この区間を全て通る」みたいなものは存在しません。

ここで、別の典型を組み合わせます。「やった/やってないを、整数のbitで管理する」という典型テクニックです。これを使うと、例えば二進数で10110は、a,c,dを通ったけどb,eはまだ、みたいな感じになります。

さらに、「複数の状態を纏めて一つのノードにする」という典型テクニックを組み合わせると、「今いる地点と、通った情報」を、新しいノードにしてしまえば、ダイクストラ法が適用できるわけです。３つの典型を組み合わせることで、さくっと解けるわけです。

今回の例はとても頻出なので、同じ組み合わせを見たことがある人は多数いると思います。ですが「グラフに特徴があるからダイクストラ法じゃないかも？」とか、いろんなパターンがあったりもします。それらのパターンの組み合わせをたくさん持っている人が、「典型問題に強い」といえるわけです。

まとめ：適用範囲のパターンをいくつ持っているかで、人によって典型の範囲が違う。典型と典型を組み合わせることもまた典型である

じゃあ「典型」の幅を増やすには？「典型」の適用方法は？

典型の範囲を増やす方法ってのは、実は簡単です。問題を解き終わった後に、「この問題は、この部分にこういう要素があったからこれで解けたんだな」ということを、確認する行為をすれば良いです。

さっきの問題に、さらに要素を追加しましょう。

• N個の地点があり、M本の道路で結ばれている。各道路には、反対側の地点に行くためにかかる時間が与えられている。
• （なんやかんやここに書いてあるけどここはまだ読んでいない）
• A地点から、指定された10個の地点を全て通った後、B地点に行くまでの時間を出力しなさい。

はい。こんな問題がありました。いや、こんな問題は存在するはずがないんですが、問題を読んでいる途中はこんな状態になることが割とあります。

さて、この問題の解法を考えてください。え？無茶？いやいや、これこそが典型力なんですよ。問題の一部が書いてないときに、「これかな？」って適用できるものこそ、汎用性が高いものだし、典型なんじゃないですか？

ってことで適当に考えてみましょう。

• グラフがだいぶ小さいならダイクストラで十分そう？　地点10個のbit情報＋場所を状態にして適当に遷移させてあげれば解けそう。　（300点問題くらい）
• V=1000とかだと状態数が多くてダメそう。工夫しないとダメ
• 状態情報が圧縮できればうれしい。例えば「10個の訪れるべき順番はなんやかんや決まるから、いくつ訪れたかだけで十分」とか。 (500点問題くらい)
• そもそもダイクストラが要らないとか？例えば木構造なら地点の順番を全探索する10!なんかで解けちゃう。bitDP使えばさらに早い。木じゃなくても、木と同じとみなせるパターンなんかもある？ (600点問題くらい)
• そもそも直線として見做せたららくちんよね (300点問題くらい）
• DAGとして見做せても十分らくちんよね(400点問題くらい)

適当に考えた問題が多かったのかあんまり浮かびませんでした。これくらいまではパターンとして 処理できると嬉しいな、って感じです。

ってことで、実際の問題で、どんな感じで考えるかを見ていきましょう。

（かなり難しいので、競プロ経験者以外は「さいごに」まで飛ばしておっけーです。）

問題文例（AGC022C 700点問題）

アオキは数列 a₁,a₂,…,a_N で遊んでいます。1 秒ごとに、アオキは次の操作を行います。

• 正の整数 k を選ぶ。数列のそれぞれの要素 v について、アオキは v を「v を k で割った余り」に置き換えるか、v をそのままにするかを選べる。この一連の操作のコストは（書き換えた要素の数によらず）2^k である。

アオキは、数列を b₁,b₂,…,b_N に変えたいです（要素の順番も考慮します）。この目的を達成することが可能か判定し、可能である場合は必要な最小のコストを求めてください。

解説なんかだと、正しいルート以外はすっ飛ばされちゃうので、この問題をパっと見て、存在しそうな解法をひたすら列挙していきます。ここで書く箇条書きの典型テクニックは、この問題の直接な解法ではなく、部分的に見たときに、こういう特徴が存在したら解けるかもしれない、みたいな要素を列挙しています。

• 数列 a₁,a₂,…,a_N 
• 数列を b₁,b₂,…,b_N に変えたいです。可能か判定してください。

まずこれだけで色々出ると思います。

• aとbに対して、それぞれf(a), f(b)を求めて、その関係性で判定 (200点～）
• aとbをそれぞれソートして、前の要素から比較していく (200点～)
• aとbの同じ要素を潰す(200点～）
• a1とb1、a2とb2・・・と独立に比較して、全部が条件を満たせばよい(300点～)

雑に考えてこんな感じでしょうか？

• 可能である場合は必要な最小のコストを求めてください。

ここまで読むともうちょっとそれっぽい解法が浮かびだします。

• a1とb1、a2とb2・・・と独立に比較して、それぞれのコストの和や最大コストが答え(300点～)
• コストを決め打ちして、そのコストで実行可能かを決めた上で二分探索(400点～)
• 可能でない場合は「コスト最大でも解が見つからなかった場合」で、最小判定と同じ方法で処理(300点～)

ここら辺までは典型として扱う人がかなり多いんじゃないかな、と思います。この辺を典型として簡単に処理できるようになると、水色は十分行けるかな、って感じです。

さて、ここからが本番です。

• 正の整数 k を選ぶ。数列のそれぞれの要素 v について、アオキは v を「v を k で割った余り」に置き換えるか、v をそのままにするかを選べる。この一連の操作のコストは（書き換えた要素の数によらず）2^k である。

結局これがどうにかできるかが典型力です。「ここが結局アドホックだから典型じゃないじゃん」と言っているうちは、なかなか問題ができるようにはなりません。

んじゃどうするか、っていうと、この一文をさらに崩します。

• 正の整数 k を選ぶ。数列のそれぞれの要素 v について、 v を k によってなんやかんやしたりなかったりします。この一連の操作のコストは（書き換えた要素の数によらず）2^k である。

 さっきとおんなじ、「アドホックっぽい部分は『なんやかんや』にしちゃう」みたいなテクニックですね。この状態で、さらに分解していきましょう。

• 正の整数 k を選ぶ。数列のそれぞれの要素 v について、 v を k によってなんやかんやしたりなかったりします。

これの典型を考えられるかどうかが、一番の典型力の分かれ目でしょう。

• kの選び方は、各要素の最大値や最小値などから貪欲に求められる(400点~)
• kの選ぶ順序に決まりがない(300点)
• kの選び方は、ある程度大きい数を用いて、大きい方から、または小さいほうから試すことが出来る(400点~)
• kによってなんやかんやするかどうかは、a,bの関係性とかから貪欲に判断できるので、探索等がいらない(200点~)
• （上のものたちを組み合わせて）kの選び方の整数列が与えられた時に、a,bに対して実現可能かどうかが簡単に求められる(400点~)
• 同じkの選ぶ回数はある定数回に収まる(500点~)
• あるkを選んだ時、次のkは一定の間隔が開く。２倍とか、1以上離れるとか(500点~)
• なんやかんやするかどうかは、vの要素だけを見れば決まる。(200点～)
• なんやかんやするかどうかは、vの要素と、その前後の要素で決まる。(300点～）
• なんやかんやするかどうかは、全体の偶奇などの、全体の特徴で決まる(300点～）
• なんやかんやできるなら絶対なんやかんやしたほうが良い(300点～）
• kの列が与えられたときに、なんやかんやしてどうにかなるかどうかは探索やbitDPで求められる(300点～）
• 前の要素や次の要素で過去になんやかんやしたかどうかは、今見ている要素でなんやかんやするかどうかに影響を与えない。つまり、独立に判断できる(300点～)

雑に並べたけど、「整数全体をある法則で並び替える」って超頻出なんで、典型パターンは超たくさんあると思います。まだ全然列挙できていない。大小関係ーとか素数ーとか色々あるのです。

• この一連の操作のコストは（書き換えた要素の数によらず）2^k である。

最後です。これは数学的な感覚があると、最初から身についている人も多いし、そうではないと苦しいテクニックが多いです。

• 同じコストが２度発生しない場合は、最大のkの最大値をまず下げる問題を解けば良い(kを使った場合のコストは、k-1以下のすべてを使ったコストより高いため)　最大値を見つけたら、その最大値を固定して、次の値を求めれば良い。 (500点～）
• k-1を2回使うことが、kを1回使うことによって上位互換となる場合、各kを使う回数は1回に抑えられる(500点～)
• 最大値を下げる問題は、最大値の上限が大きくなければ、上から順番に試すだけで解ける (500点～）
• 最大値を下げる問題は、二分探索をすることで解くことが出来る。出てくるbit数が少ないときしかこれの繰り返しでは解けない。(600点～）

ってことで、パっとパーツだけ眺めた時の印象はこんな感じでした。実際は、ここまでバラバラじゃなくて、例えば「ｋを選んで全体操作」＋「コストが2^k」みたいな組み合わせがあったら「こんなん各k一回ずつやろ」みたいな、典型同士の組み合わせ方の典型、みたいなのもあります。上位陣が１０分もかからず正解している問題は、こんな感じで典型パーツを列挙して、適当に組み合わせるだけで解けちゃう問題です。正直これができるだけでRedCoderにはなれます。

まぁ、これができるだけ、というほど簡単じゃないんでしょうけど、こういうテクニックは本当に膨大にあって、各問題にたくさん含まれています。これらを見落とさないように問題を解いていけば、どんどん解けるようになっていくはずです。

さいごに

問題文を魔改造して、いろんな典型テクニックを紹介しましたが、こういうテクニックは、問題を解くごとに何かしら見つけられると思います。そうしたテクニックを意識しながら勉強していけば、自然と問題は解けるようになっていくんじゃないでしょうか？

正直な話をぶっちゃけると、「○○法」みたいなのを覚えたところで、そんなんが適用できる問題なんてそんなにないし、それで適用できちゃう問題は、別にググれは誰でも解けちゃいます。そんなんは競技プログラマの強みではありません。有名知識を典型テクニックとして身に着け、ググるだけじゃ解決の難しい複合問題を解けることに、競技プログラマとしての価値があります。

人によっては、「数学」とか「プログラマとしての経験」とかで、すでに最初からそうした典型テクニックを持っている可能性があります。そういう人の初動は早いですが、勉強すればこうしたテクニックは確実に身に着けられます。「典型」を増やす練習を、ぜひぜひ試してみてください！