Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

問題のない問題との付き合い方

Competitive Programming Advent Calendar Div2012 の16日目の記事です。

本記事では,数学問題の考え方に関する古典的名著「いかにして問題をとくか」の紹介を通して,競技プログラミング/プログラミングコンテストにおける問題へのアプローチについて書いてみたいと思います。

とても有名な本ですので知っている方も多いのではないかと思いますが,これまで競技プログラミングの文脈で本書が話題に挙がることを見かけることがありませんでした。競技プログラマーの特に初級者の方には,問題を解く上での心構え/ヒントを得られる(かもしれません)のでご一読されることをお勧めいたします。

本記事は初級者がターゲットとなります。中上級者の方には箸休め的にお付き合い頂ければと思います。

本書と競技プログラミングとの関係

いかにして問題をとくか」は数学の問題を解くための考え方の指南書です。本書の内容は競技プログラミングの問題を解くための考え方としても有効だと考えています。

本書でいう「問題」は少し強弁かもしれませんが「試験問題としての数学問題」のことであり,「答えのある問題」に対して問題文から解答をどのように導き出すのかを手引きしてくれます。この観点で,競技プログラミングの問題も「答えのある問題」が与えられることから,本書の内容がピッタリと当てはまると言えます。

「答えのある問題」ということから,競技プログラミングの中でもショートラウンドものが対象となります。Topcoder マラソンマッチのように定まった答えがない(よりベターな解を求める)問題には本書のモデルは当てはまり難いように思います。以下では,「問題」という言葉はTopcoder SRM,Google Code Jamのようなショートラウンドのアルゴリズム問題を指すものとします。

数学問題の解法を指南する類書としては「エレガントな問題解決」,「数学オリンピックチャンピオンの美しい解き方」などがあります。これらの本も最初の章で問題へのアプローチについて書かれており,同様のことが述べられています。

問題の理解

問題を解くための第一歩は「問題の理解」です。当たり前のことですが,これが正しくできていないために泣く泣く時間切れなんてことが初級者にはよくあるかと思います。本ブログの過去のエントリにも,問題の理解で苦悩するボヤキが書いてあったりします。

「問題の理解」と何か?それは次の3つの事を明らかにすることです。

  1. 求めるべきもの(未知のもの)/ What is the unknown?
  2. 与えられているデータ / What are the data?
  3. 制約条件 / What is the condition?

実にシンプルな3項目ですが,これらを意識して問題文を読むかどうかで問題文の理解の時間と正確性が変わってくるのではないかと思います。

これら3つの要素は,問題文の中から簡単に見つけられることもあれば,問題が複雑すぎて見つけられないこともあるかと思います。見つけられない場合(または,より明確にするため)の補助手段として,次のことが挙げられています。

  1. 図を描く
  2. 記号をつける
  3. 条件を記号/式で表せないか?

問題理解の3項目を明らかにしたら,いよいよ解の検討を始めます。3項目が明らかでない場合は,まだ解の検討を始めるべきではありません。

解法の方針

問題の解法には当然ながら一般的な方法というものはありません。問題ごとに解き方・考え方が異なります。異なっているからこそ問題としての価値(解く楽しみ)があるわけです。

このため,(未知の)問題を解くためには色々な問題に対する解法(解法のカタログ)を集めておくことが必要です。「いかにして問題をとくか」の中の解法検討の指針の一つにも,

  • 似た問題がないか(未知のものが同じ,または似ている問題)

が挙げられています。解法の分かってる似た問題を知っていれば,同様のやり方で問題が解ける可能性があります。逆に,似た問題を全く知らなければ(=解法を持っていない),問題を解くことができないと言ってしまってもよいと思います。

さて,問題文を読んだとき(理解したとき)に手持ちの解法カタログに合うもの/似たものを見つけられなかった場合にどうするか?前述の通り,知らなければお手上げです。そこで,カタログに合う/似た形になるまで問題文を変形することが求められます。いろいろと試すことで解法を見出していきます。

問題の変形には色々な考え方があるのですが,大きな概念で総称すれば問題の「分解」であると言えると思います。問題文を色々な角度から見て,問題の構成要素をばらして検討していきます。

以下,問題の変形のいくつかの考え方について幾つか挙げてみたいと思います。次のものは,わりと競技プログラミングの問題と親和性が高い考え方ではないかと思います。

  • 結論の一歩手前の段階を見る。逆向きにとく。
  • 特別なケースをいくつか考え,一般化する。

部分問題を考えてDPに持ち込んだり,簡単な数値例で考えて法則を仮定したりなどが,この考え方に従っていると言えるかと思います。

問題の「分解」の一般的な指針としては,問題の3要素をそれぞれ変えながら検討してみるということがあります。

  • 条件を変える  :条件の一部のみを満たす問題を考える。何が求まるか?
  • データを変える  :データが希望的な値(簡単に解が求まる)である問題を考える。
  • 未知のものを変える  :条件とデータから簡単に求まるものは何か?

これらのことは1つずつ考えるだけでなく,組み合わせて考えることも有効です。例えば,「未知のものとデータを同時に変える」ということも考えることができます。

終わりに

問題の考え方についてのエッセンスを紹介してきました。本の中ではこれらを具体例を交えて解説されていますので,より実感を持って理解できるかと思います。詳細を知りたい方は参照してみてください。

ここで書いたことは,競技プログラマーとしての力を即時上げるものではありません。これさえ知っておけばどんな問題でも解けるというものではないということです。問題を解くためにはそれに合った解法(カタログ)を持っていることが大事であり,これを拡充する問題練習の方がスキルアップの即応力があります。

それでは,この「問題の考え方」はどのように役立つのでしょうか?

(練習)問題を解く際にこの「問題の考え方」を意識しておくことで,問題とその解法をより深い理解・経験として自分の中に刻み込むことができると考えています。また,問題の要素を分けて考えることで似た問題を思い返すことも容易になるかと思います。従って,この考え方を身に付けることで解法のカタログの質が向上するということが言えるのではないでしょうか。

本記事が競技プログラミングのスキルアップの一助になれば幸いです。

姉妹記事「問題だらけの問題解決」も,よろしければご覧ください。

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://msirocoder.blog35.fc2.com/tb.php/81-f3d0e9a6
この記事にトラックバックする(FC2ブログユーザー)

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。