問題の解き方

この記事は Competitive Programming Advent Calendar 2014 のために執筆されました。

前書き

これの話をします。

去る11月8 - 9日、パソコン甲子園本戦が行われたので観戦に行ってきました。ニコ生やったり *1 選手と喋ったり、楽しませて頂きました。

作題委員の先生ともお話ししたりして、興味深い話を聞きました。予選の5問目で大虐殺が起きていたらしいのです。予選問題は こちら にありますが、軽く要約するとこんな感じです。


問題5: 鉄道路線

頂点数 n の円環状のグラフ (頂点 i と i + 1 (0 <= i <= n - 2) の間、および頂点 n - 1 と 0 の間に重み 1 の辺が貼られたグラフ) がある。このグラフ上の m 個の頂点が与えられるので、ある頂点から出発して、与えられた全ての頂点を訪問する (最後にいる場所はどこでもよい) 最短経路を求めよ。n <= 100,000。

この問題セットの最初の4問の正答率 *2 はだいたい 9 割から 6 割程度と、良い数字でした。が、5問目になると正答率はがくっと落ち、だいたい 3% ぐらいでした。実際に本戦に来た選手からも、この問題で WA を出しまくったという話はよく聞かれました。最初の4問は純粋な実装力を問うものであるの対し、この5問目はアルゴリズム力を問うものです。ここにある種の分水嶺があるように思われ、上のツイートに繋がるのでした。

この問題は配点からも分かる通りそれほど難しいものではありませんし、コーナーケースの罠が仕掛けられているわけでもありません。黄色コーダーともなれば5分で苦もなく一発ACできるでしょう。しかし、それができるようになるにはアルゴリズムを設計するという特別な訓練が必要です。この技術はオンラインジャッジでひたすら問題を解き続けることで自然に習得されていくことが多いように見えますが、今日はこの問題を解きながら、経験知をできるだけ言語化してみたいと思います。

対象読者としては、TopCoder で Div2 だったり、ICPC国内予選やPCK予選の突破を目指しているぐらいの層を考えています。特にこの5問目で WA を出した人たちに役立ててもらいたいです。

設計の重要性

私が弱小競技プログラマだったころ、しばしばこんな解き方をしていました。

  • こんな方針で行けるんでは・・・と考えながら実装する
  • WA を出す
  • バグっぽそうなところを修正してみる
  • WA を出す
  • もうちょっといじってみる
  • WA を出す
  • ...

つらい人生です。このスタイルではデバッグ中ずっと PC を占有することになり、パソコン甲子園ICPC のようなチーム戦では大きく不利になります。そもそも WA が積み上がるほどソウルジェムも濁っていき、生きる気力をなくしてしまいます。これはよくない。

優れた競技プログラマは、実装を始める前にアルゴリズムを設計し、それが正しいことを証明します。うまく証明できず反例が見つかってしまえば、それを実装する手間が省けたことになります。またアルゴリズムが正しいという証明を持って実装を始めれば、たとえ WA となったとしても、証明のミスと実装のミスという二つの問題を切り分けて考えることができます。

証明といわれると敷居が高くてひるんでしまう人もいるかと思います。私も昔 この解説資料 を見て、「なんで楽しいプログラミングコンテストで証明なんてしなきゃいけないんですか・・・」と思ったことを覚えています。ですが、証明は自分の考えが正しいと確認するための重要なテクニックです。使いこなせばエンバグを抑えることができ、プログラミングが一層楽しくなります。

とはいえ、アルゴリズムの正しさを証明するにはまずアルゴリズムを組み立てないと始まりません。どうやってアルゴリズムを組み立てるか、というところから始めましょう。

問題5: 鉄道路線


問題5: 鉄道路線

頂点数 n の円環状のグラフ (頂点 i と i + 1 (0 <= i <= n - 2) の間、および頂点 n - 1 と 0 の間に重み 1 の辺が貼られたグラフ) がある。このグラフ上の m 個の頂点が与えられるので、ある頂点から出発して、与えられた全ての頂点を訪問する (最後にいる場所はどこでもよい) 最短経路を求めよ。n <= 100,000。

問題を読んで最初にするべきは、「事実をかき集める」ことです。実際にアルゴリズムを組み立てるときに役立つかどうかはこの際置いておいて、まずはヒントになりそうなものを探しましょう。たとえば、

  • 最短経路の長さは n 以下

とか。グラフをぐるっと一周すれば全ての頂点を訪問できるので、これは明らかに正しいです。これを使ってアルゴリズムを設計できるでしょうか。厳しいです。ですが、この知見は役に立たないわけではありません。あとでアルゴリズムを設計したとき、n より大きい最短経路が出てきたら、そのアルゴリズムは間違いだと分かるのです。

いろんな知識を身につければ身につけるほど、ヒントを集める作業は捗ります。この問題ではグラフ上の指定された点を全て訪問することになっていますが、訪問すべき点だけに着目すれば、この問題は巡回セールスマン問題 と同じです。巡回セールスマン問題は NP困難 と呼ばれる問題なので、m = 10,000 というサイズを競技プログラミングでまともに解くのは無謀です。きっとまともじゃない解法があるはずです。特に円環状という恣意的なグラフの形が上手く使えるはずです。また、小さいサイズの巡回セールスマン問題を解けるのなら、自分の書いたプログラムが正しいかどうか、出力を比べてみることもできるでしょう。

出力といえば、これも忘れてはいけません。

サンプル入出力を図示してみる

例示は理解の試金石。数学ガールにもそう書いてあります。サンプルは問題文の読み間違いを見つけるのにも使えるので、ちゃんと図示して納得しておきましょう。

  • サンプル1


0 - 1 - 2 - 3 - 4 と移動するのが最短です。あるいは 0 - 4 - 3 - 2 - 1 でも可。おお、「最短経路は一つとは限らない」という事実が得られました。「時計回りまたは半時計回りに一直線に進むのが最適になる入力例が存在する」ということも。

これはアルゴリズムの設計に使えるかもしれません。「時計回りまたは半時計回りに一直線に進むのが最適になる入力例がある」を押し進めて、「どんな入力例でも、時計回りまたは半時計回りに一直線に進むのが常に最適」まで言えれば、この問題は解けたも同然です。これはどうすれば証明できるでしょうか。よくわからないときは、とりあえずこのアルゴリズムにいろんな入力を放り込んでみましょう。

  • サンプル2


1 - 2 - 1 - 0 - 6 が唯一の最短経路です。2 まで来たら折り返すのが最適。ここで、「一度折り返すのが最適になる入力例がある」ことが分かりました。これが「どんな入力例でも、時計回りまたは半時計回りに一直線に進むのが常に最適」の反例です。有効そうな方針が一つ閉ざされてしまったのは悲しいものですが、実装を始める前にダメだと分かったのはよいことです。

これらのサンプルを見て思いつきそうなのは、「『訪問すべきノードのうち、まだ訪問していなくて現在地からもっとも近いものに移動する』ことを繰り返す」という方針です。多分これを考えたチームも多いのではと思うのですが、結論を言ってしまうとこれもうまくいきません。このアルゴリズムの気持ちになって、意地悪な入力を作ってみると反例はすぐに見つかります。

より深い洞察

これまでいくつかの事実をかき集めてきました。

  • 最短経路の長さは n 以下
  • 最短経路は一つとは限らない
  • 時計回りまたは反時計回りに一直線に進むのが最適になる入力例が存在する
  • 1回折り返すのが最適になる入力例が存在する

これだけではまだアルゴリズムを組めそうにありません。問題やサンプルを読めばすぐに分かるような事柄だけでなく、もっと深い洞察をかき集める必要がありそうです。

ここで、サンプルから得られた知見に注目してみましょう。「一直線に進むのが最適になる入力例が存在する」というのは、つまり「0回折り返すのが最適になる入力例が存在する」ということです。0回、1回折り返すのが最適になるような入力例が存在するなら、2回折り返すのが最適になるような入力例もあるのでしょうか?
一見2回折り返すのは無駄が多そうです。よくよく考えてみると、以下の理由で2回折り返す必要はないことがわかります。

2回目の折り返しの後、どこまで進むかによって場合分けしてみましょう。1回目に折り返した地点より前で止まるのは明らかに愚かなことです。

かといって、1回目に折り返した地点を通り過ぎると、今度は最初の折り返しが無駄になってしまいます。

ということは、2回折り返すのが最適になるような場合は存在しないことが分かりました。このアイデアは、3回以上折り返すような経路に付いても適用できます。3回以上折り返す経路も、最初の2回の折り返しの部分に既に無駄が含まれているので、やっぱり最短経路になることはありません。

これで、「どんな入力でも、最短経路は0回または1回折り返すような経路である」ことが言えました。これは大いに役立ちそうなヒントです。というのも、1回折り返す経路なんてそんなに多くはなさそうだからです。こんなアルゴリズムを考えてみましょう。以下の経路を全部試して、一番いいやつを答えにするのです。

  • 0回折り返すパターン
    • 時計回りに一直線に進んで全部訪問する
    • 反時計回りに一直線に進んで全部訪問する
  • 1回折り返すパターン
    • 時計回りに1頂点進んだあと、反時計回りに未訪問の目的頂点を全部訪問する
    • 時計回りに2頂点進んだあと、反時計回りに未訪問の目的頂点を全部訪問する
    • ...
    • 時計回りにn-1頂点進んだあと、時計回りに未訪問の目的頂点を全部訪問する
    • 反時計回りに1頂点進んだあと、時計回りに未訪問の目的頂点を全部訪問する
    • 反時計回りに2頂点進んだあと、時計回りに未訪問の目的頂点を全部訪問する
    • ...
    • 反時計回りにn-1頂点進んだあと、時計回りに未訪問の目的頂点を全部訪問する

できました!このアルゴリズムの証明は簡単です。0回または1回折り返すような経路のみが最短経路になり得ることはもう証明しました。このアルゴリズムは0回または1回折り返すような経路を網羅している *3 ので、その中の最短経路を取れば、答えになっています。これらの経路は合わせて 2n = 200,000 個なので、全部試しても間に合います *4

ここまで来ればあとは実装するだけ。

Key Insight

アルゴリズムを設計するにあたって、今回決め手となったのは「どんな入力でも、最短経路は0回または1回折り返すような経路である」という知見でした。このような洞察を、私は "key insight" と呼んでいます *5。問題を解くということは、おおむね key insight を見つけることだと言っても過言ではないです。

私の経験則から言えば、だいたいどんな問題も、たった一つの key insight が見つかれば、それを手がかりにするすると解けてしまうものです。たまに「key insight を使って問題を変形して、また key insight を使っていくつかの部分問題に分解して、それぞれこの key insight と key insight を使えば解けるよ」みたいなケースがありますが、そういうのはごく一部の極めて難しい問題だけです。

問題を解いたら、その問題の key insight が何であったかを記録しておくと練習に役立ったりするかもしれません。

つよいひとのあたまのなか

ここまで長い道のりでした。事実をかき集めて、仮説を立て、証明し、アルゴリズムを組み、計算量を見積もってからやっと実装に移れるのです。もしかしたら、こう思う人もいるかもしれません。「強い人たちって本当に問題を読むたびにこういうこと考えているの?一瞬で正しいアルゴリズムが見えているのではなくて?」

考えています。いや、本当に一人残らずそうかと言われるとちょっと自信なくて、りんごさんとかどう思考しているのか全然分からないし、緋笠カズミちゃんみたいに<解法解放ヘウレカ>使えるのではっていう人もちらほらいるのだけど、経験を積んだ競技プログラマの大多数はこのように思考しています。

私がこの問題初めて見たときには、たとえば「最短経路の長さは n 以下」などは考えませんでしたが、

  • 時計回り・半時計回りで折り返さずに進むのが最短経路になる場合がある
  • 折り返した方が良い入力はあるかな・・・?
  • 1回折り返すのが最適になる入力はすぐ見つかる
  • 2回以上折り返すのは最適になりうるかな・・・?
  • 直感的にはなさそう
  • 脳内で証明できた
  • 折り返す場所然探索すればよい。
  • 計算量も間に合う。
  • 解けた!

というステップは踏みました。書き下してみると長いように見えますが、この種の思考は慣れれば慣れるほど速くなっていくので、実装に比べればずっと短い時間ですみます。競技プログラミングで強くなりたいなら、これらのステップを飛ばして正しい解法を閃けるようになることを目指すのではなく、これらのステップを素早く正確に行えるようになることを目指しましょう。

何を練習したら良いのか

証明が大事と言われても、証明なんて自分には書けない、という人もいるかもしれません。証明が苦手な人にお勧めしたいのは、よく知られたアルゴリズムバブルソートダイクストラクラスカルなどの証明を読んで理解してみることです。よく知られたアルゴリズムの証明には使い回しのきくテクニックが使われていることが多く、それらを使いこなせるようになれば、単にダイクストラを使えるようになるよりもずっと強くなれます。

よく知られたアルゴリズムの証明を理解することには、もう一つの効果があります。証明を理解せず実装だけを身に付けてよしとしてしまう風潮への警鐘を意図した問題が出題されることがしばしばあります。これが有名ですね。このような問題も、ちゃんとアルゴリズムを本質的に理解していれば怖くありません。*6

あとは、コンテストに参加する度に参加記録を付けて、コンテスト中に何を考えていたのかを書き残すのもいいかもしれません。

まとめ

  • プログラムを書き始める前に、ちゃんとアルゴリズムを考えよう、証明しよう
  • アルゴリズムはやたらめったら閃くものではなく、観察と洞察から組み立てるもの
  • 有名なアルゴリズムの証明はちゃんと押さえておくと捗る

問題を良く観察して事実を集めることが大事だと言いましたが、これは競技プログラミングに限ったことではないように思います。Web サービス運営の現場でも、原因不明の障害が起きたときにはまず状況から事実をかき集め、そこから考えられる原因の仮説を立て、そして仮説の正しさを検証するものです。競技プログラミングを通じてこのような考え方が身に付けば、「月刊『月刊競技プログラミングは役に立たない』は役に立たない」創刊の流れに持っていけるのではと思います。

アルゴリズムを設計して証明することは、競技プログラミングの中で一番楽しいフェーズだと私は思っています *7。今回取り上げた問題はアルゴリズムを問う問題の中でもほんの入り口に過ぎず、この先にはもっと難しい、もっと面白い問題が何千問と待ち構えています。より多くの人が競技プログラミングの面白さに触れられることを願ってやみません。この記事がその一助となれば幸いです。

*1:関係ないけど灘高のチーム名「三上」と「和馬」にどこまで踏み込んでいいのか分からなくてすごい困った

*2:accepted / submitted

*3:厳密には網羅していなくて、時計回りに何周もするような経路を無視しているけど、それが最短経路にならないことは自明なので無視しちゃいます。「最短経路の長さは n 以下である」ことは言ったし。

*4:訪問しなくてもよい頂点で折り返すのは無駄であることも証明できるのですが、これも無視しちゃいます。どうせ全部計算しても TLE にはならないので

*5:私がこの言い回しを知ったのは、確かoxy神によるJAG合宿での解説資料だったはず

*6:とはいっても、私も証明を理解するのが辛くて暗記に逃げてしまうことはあるのですが。よくない。

*7:私はどちらかというとアルゴリズムを考えたらチームメイトに実装をぶん投げる役回りだからそう思っていただけで、もしかしたらチームメイトは「実装だけしてれば良いから幸せだな」とか思っていたかもしれない

競技プログラマが知るべき97のこと (01/97)

この記事は Competitive Programming Advent Calendar Div2012 のために作成されました。

競技プログラミングを長年やっているうちに、「これを実装するときにはこう書くと楽」とか「問題文を読んでもアルゴリズムがさっぱりわからないときにはこう考えるといい」みたいな tips が溜まってきていることに気づきました。Tips と言っても大したものではなくて、おそらく上級者は皆同じアイデアを持っているのでしょうが、しかしそういった tips をまとめた記事はあんまり見受けられません。ICPCを引退したらそういうのをぼちぼちまとめていこうかなー、と思いつつ既に引退から2年経ってしまいましたが、Advent Calendar の勢いを借りて書いてみたいと思います。

「競技プログラマが知るべき97のこと」第1回のテーマは「許されるときはいつでも入力をソートしよう」です。企画名は完璧に nodchip 先生の同人誌のパクりです。たぶん96年後の Advent Calendar で完結します。

競技プログラマが知るべき97のこと (01/97) - 許されるときはいつでも入力をソートしよう

多くの場合、入力の値を書き換えることは何の役にも立ちません。[2, 1, 3] の最長増加部分列を求めたいときに、まずこの入力をソートして、[1, 2, 3] について思いを馳せてみる人はまずいないでしょう。しかし、幾つかの問題においては、入力の値をソートしても問題の意味が変わらないことがあります。典型的なのは、集合が与えられ、その要素の順番は考慮しないような問題です。たとえば、こんなの。

n 部屋の会議室があり、それぞれの定員は capacities[i] で表されます。
会議室を使いたいグループが m 個あり、それらの人数は members[i] で表されます。
グループに会議室を適切に割り当てて、同時に会議室を使えるグループの数を最大化してください。
1つのグループが複数の会議室を使うことも、1つの会議室に複数のグループが入ることもできません。

Sample:
capacities = [3, 5, 1, 2]
members    = [1, 4, 2, 4]

output     = 3
0 番目のグループが会議室 2 を、1 番目のグループが会議室 1 を、
2 番目のグループが会議室 3 を使うことができます。

この問題では、capacity や member を並び替えても問題の意味は変わりません。このようなときは必ずソートしてからアルゴリズムを考えましょう。

なぜソートするといいことがあるのか。それは、典型的で強力な次の 3 つのアプローチを考えやすくするためです。

ソートしなくても成功するなら、ソートしたときは絶対に成功することを示す

上の問題例は説明しづらいことに気づいたので一旦忘れることにして、SRM506 SlimeXSlimesCityを見てみましょう。問題を読むと、それぞれの町の名前について、それが最終的に市の名前になれるかどうかを判定することができれば幸せになれることがすぐわかります。ある町を大きくして市にしたいとき、例えば大きさ 5 の町を併合してから大きさ 3 の町を併合することが可能だったら、逆にして 3 の町を併合してから 5 の町を併合することだってできる。この考え方を推し進めていくと、成功パターンがあるときは、小さな町から順に併合しても成功する。つまり、小さな町から順に併合したパターンだけ調べればOK。という結論に至ります。
会議室の問題も、2人グループに4人部屋を割り当てて3人グループに3人部屋を割り当てる代わりに、入れ替えて2人グループに3人部屋、3人グループに4人部屋を割り当てるなどして、より小さいグループにより小さい部屋を割り当てても最終的な答えは変わりません。この発見がアルゴリズムの設計に大いに役立ちます。

1つ1つ入力を大きくしながら答えを求めていく

input[0 .. n-1] に対する最適解を利用して、input[0 .. n] に対する最適解を求める。ここで、input[0] <= input[1] <= ... input[n-1] <= input[n] を利用する。という数学的帰納法っぽい戦略を取ることもできます。会議室の問題は、上のアプローチとこのアプローチの合わせ技みたいな感じですね。まず最初に capacities と members をソートしておくと、members[0 .. 0], members[0 .. 1], members[0 .. 2], ... に対する答えを求めていける。

このアプローチについてはじっくり語りたいのですが、簡単な例題がなかなか見つかりません・・・。情報求む。難し目な例題としてはAOJ2383 Rabbit Game Playingあたりでしょうか。

出現頻度を考える

[1, 1, 2, 2, 2, 3, 4, ...] のような入力を、「1が 2 個、2 が 3 個、3 が 1 個、...」といった出現頻度で考えるとうまくいく事もあります。
SRM499 ColorfulRabbitsとか、SRM507 CubeStickerとか。このような問題では、実装上ソートが必要になるわけではありませんが、紙の上でアルゴリズムを考えるときにはソートしておくと便利です。同じ値が一箇所に固まるので、出現頻度というアイデアが出てきやすくなります。


「可能ならいつでもソート」戦略の良い所は、外れることはあっても、邪魔になることはまずないという点です。たとえば「迷ったらDPで解けないか考える」のような戦略はうまく行かなかったときに時間のロスが大きいですが、ソートは多くの言語では1行実装するだけで済み、計算量もさほど問題にはなりません*1。「あのときソートさえしていなければ・・・!」と後悔することにはならないのです。*2

ですから、問題を読んだ瞬間に「この入力はソートしても大丈夫か?」と考えることは大事ですし、もしソートできたら上の 3 つのアプローチがうまくいく可能性が多いにあるのです。なおかつ、うまくいかなかったとしても失うものはほとんどありません。ぜひソートしましょう。

*1:TopCoder を除けば少なくとも入力に O(n) 掛かり、これを許容しながらも O( nlog(n) ) の中でも比較的速いソートを落とすような時間設定は難しいものです。

*2:ちなみに、ソートしても意味が無い問題としてはAOJ1027 A Piece of Cakeなどがあります。

競技プログラマが知るべき97のこと (01/97)

この記事は Competitive Programming Advent Calendar Div2012 のために作成されました。

競技プログラミングを長年やっているうちに、「これを実装するときにはこう書くと楽」とか「問題文を読んでもアルゴリズムがさっぱりわからないときにはこう考えるといい」みたいな tips が溜まってきていることに気づきました。Tips と言っても大したものではなくて、おそらく上級者は皆同じアイデアを持っているのでしょうが、しかしそういった tips をまとめた記事はあんまり見受けられません。ICPCを引退したらそういうのをぼちぼちまとめていこうかなー、と思いつつ既に引退から2年経ってしまいましたが、Advent Calendar の勢いを借りて書いてみたいと思います。

「競技プログラマが知るべき97のこと」第1回のテーマは「許されるときはいつでも入力をソートしよう」です。企画名は完璧に nodchip 先生の同人誌のパクりです。たぶん96年後の Advent Calendar で完結します。

競技プログラマが知るべき97のこと (01/97) - 許されるときはいつでも入力をソートしよう

多くの場合、入力の値を書き換えることは何の役にも立ちません。[2, 1, 3] の最長増加部分列を求めたいときに、まずこの入力をソートして、[1, 2, 3] について思いを馳せてみる人はまずいないでしょう。しかし、幾つかの問題においては、入力の値をソートしても問題の意味が変わらないことがあります。典型的なのは、集合が与えられ、その要素の順番は考慮しないような問題です。たとえば、こんなの。

n 部屋の会議室があり、それぞれの定員は capacities[i] で表されます。
会議室を使いたいグループが m 個あり、それらの人数は members[i] で表されます。
グループに会議室を適切に割り当てて、同時に会議室を使えるグループの数を最大化してください。
1つのグループが複数の会議室を使うことも、1つの会議室に複数のグループが入ることもできません。

Sample:
capacities = [3, 5, 1, 2]
members    = [1, 4, 2, 4]

output     = 3
0 番目のグループが会議室 2 を、1 番目のグループが会議室 1 を、
2 番目のグループが会議室 3 を使うことができます。

この問題では、capacity や member を並び替えても問題の意味は変わりません。このようなときは必ずソートしてからアルゴリズムを考えましょう。

なぜソートするといいことがあるのか。それは、典型的で強力な次の 3 つのアプローチを考えやすくするためです。

ソートしなくても成功するなら、ソートしたときは絶対に成功することを示す

上の問題例は説明しづらいことに気づいたので一旦忘れることにして、SRM506 SlimeXSlimesCityを見てみましょう。問題を読むと、それぞれの町の名前について、それが最終的に市の名前になれるかどうかを判定することができれば幸せになれることがすぐわかります。ある町を大きくして市にしたいとき、例えば大きさ 5 の町を併合してから大きさ 3 の町を併合することが可能だったら、逆にして 3 の町を併合してから 5 の町を併合することだってできる。この考え方を推し進めていくと、成功パターンがあるときは、小さな町から順に併合しても成功する。つまり、小さな町から順に併合したパターンだけ調べればOK。という結論に至ります。
会議室の問題も、2人グループに4人部屋を割り当てて3人グループに3人部屋を割り当てる代わりに、入れ替えて2人グループに3人部屋、3人グループに4人部屋を割り当てるなどして、より小さいグループにより小さい部屋を割り当てても最終的な答えは変わりません。この発見がアルゴリズムの設計に大いに役立ちます。

1つ1つ入力を大きくしながら答えを求めていく

input[0 .. n-1] に対する最適解を利用して、input[0 .. n] に対する最適解を求める。ここで、input[0] <= input[1] <= ... input[n-1] <= input[n] を利用する。という数学的帰納法っぽい戦略を取ることもできます。会議室の問題は、上のアプローチとこのアプローチの合わせ技みたいな感じですね。まず最初に capacities と members をソートしておくと、members[0 .. 0], members[0 .. 1], members[0 .. 2], ... に対する答えを求めていける。

このアプローチについてはじっくり語りたいのですが、簡単な例題がなかなか見つかりません・・・。情報求む。難し目な例題としてはAOJ2383 Rabbit Game Playingあたりでしょうか。

出現頻度を考える

[1, 1, 2, 2, 2, 3, 4, ...] のような入力を、「1が 2 個、2 が 3 個、3 が 1 個、...」といった出現頻度で考えるとうまくいく事もあります。
SRM499 ColorfulRabbitsとか、SRM507 CubeStickerとか。このような問題では、実装上ソートが必要になるわけではありませんが、紙の上でアルゴリズムを考えるときにはソートしておくと便利です。同じ値が一箇所に固まるので、出現頻度というアイデアが出てきやすくなります。


「可能ならいつでもソート」戦略の良い所は、外れることはあっても、邪魔になることはまずないという点です。たとえば「迷ったらDPで解けないか考える」のような戦略はうまく行かなかったときに時間のロスが大きいですが、ソートは多くの言語では1行実装するだけで済み、計算量もさほど問題にはなりません*1。「あのときソートさえしていなければ・・・!」と後悔することにはならないのです。*2

ですから、問題を読んだ瞬間に「この入力はソートしても大丈夫か?」と考えることは大事ですし、もしソートできたら上の 3 つのアプローチがうまくいく可能性が多いにあるのです。なおかつ、うまくいかなかったとしても失うものはほとんどありません。ぜひソートしましょう。

*1:TopCoder を除けば少なくとも入力に O(n) 掛かり、これを許容しながらも O( nlog(n) ) の中でも比較的速いソートを落とすような時間設定は難しいものです。

*2:ちなみに、ソートしても意味が無い問題としてはAOJ1027 A Piece of Cakeなどがあります。