初見アルゴリズムの読解術

知らないコードが出たときにやること

ここまで定番アルゴリズムを見てきましたが、本番では見たことのない処理が必ず出ます。科目Bは、知っているかどうかではなく、その場で読めるかどうかを測る試験だからです。名前を知らないから解けない、ということは起きません。決まった手順で読めば必ず答えにたどり着きます。ここではその手順を固定します。

手順1 先に外側の形を見る

本文を1文字目から読み始めないでください。まず1行目の関数の宣言を見て、何を受け取って何を返すのかを掴みます。整数型の配列を受け取って整数型を返すなら、配列を調べて1つの数を作る処理だと当たりが付きます。配列を受け取って配列を返すなら、並べ替えるか作り替えるかです。

次にループの入れ子を見ます。全体を1周する for が1つだけなら、たいてい合計や個数を数える処理です。二重になっていれば整列か、総当たりの比較です。範囲が半分になっていく形なら二分探索の仲間です。ここまで15秒ほどで、処理の目的をかなり絞れます。

手順2 変数の役割に名前を付ける

擬似言語の変数名は短く、意味が読み取りにくいことがあります。そこで自分の言葉で役割を付け直します。0 で初期化されてループの中で足されている変数は「合計」、1 ずつ増えている変数は「個数」、条件が成り立ったときだけ更新される変数は「今までで最良のもの」です。この3つの型を知っているだけで、たいていの変数は正体が割れます。

特に大事なのは、ループに入る前の初期値です。0 なのか、1 なのか、配列の先頭の値なのかで、その変数の目的が変わります。最小値を求める処理で data[1] を初期値にしているのは、まだ何も比べていない時点の暫定王者を置いているからです。

手順3 小さい値で実際に動かす

読んでも意味が掴めないときは、考え込まずに手を動かします。要素数が3個か4個の小さいデータを自分で作り、変数の表を紙に書いて1行ずつ埋めます。ここまでの回でやってきたトレースそのものです。

このとき、問題文が与えている具体例をそのまま使うのが最短です。問題文に「data が {3, 1, 4} のとき」と書いてあれば、それが出題者の用意した最小の例です。自分で例を作るより速く、しかも設問とつながります。

手順4 空欄の前後だけを精読する

穴埋め問題では、全部を完璧に理解する必要はありません。空欄の直前で変数がどうなっていて、空欄の直後の行がその変数に何を期待しているかを見れば、入る式は絞れます。次の行で data[k] を使っているのに k がまだ決まっていなければ、空欄は k を決める行です。

選択肢を1つずつ当てはめて、小さい例で走らせるのも有効です。4択なら、明らかに型が合わないものや、範囲を外れるものを先に落とせば、実際に試すのは2つで済みます。

時間の使い方

科目Bは20問100分なので、1問あたり5分です。読み始めて2分たっても何をしているか掴めない問題は、いったん飛ばして戻ってくる判断をしてください。飛ばす判断ができるかどうかが、合否を分けます。手順1で目的が掴めたかどうかを、その判断の基準にするとよいでしょう。