科目Bの順位を付ける問題の解き方｜自分より大きい値を数えて追う

並べ替えていないのに、どうして順位が出てくるのか分からない。

科目Bの問題で、点数の配列から順位の配列を作るコードを見て、首をかしげたことはありませんか？

ソートの処理はどこにも見当たらない。それなのに、1位や2位が正しく決まっていく。その仕組みが見えずに、なんとなく選択肢を選んでしまう人も多いのではないでしょうか。

大丈夫です。並べ替えずに順位を出す問題は、自分より大きい値がいくつあるかを数えているだけです。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務でも、売上や得点のランキングを画面に表示する機能を作る場面が何度かありました。

ある時は、同じ得点の人が並ぶと順位が1つずつずれる、という不具合の報告を受けました。比べる条件の等号が1つ余計に付いていたのが原因で、小さなデータで比べた回数を表に書き出したことで、ようやく気づけました。

この記事では、順位を付ける問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中でこうした問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

順位を付ける問題は何を聞いているのか¶

最初に、順位を付けるとはどういう処理なのかを短く押さえておきましょう。順位とは、ある値が全体の中で上から何番目にあるかを表す数です。

自分より大きい値の個数に1を足したものが、その値の順位になるというのが、この問題の正体です。

身近な例で考えてみましょう。クラスのテストで、あなたより点数が高い人が3人いたとします。

このとき、あなたは4位です。上に3人いるから、その次の4番目というわけですね。並べ替えなくても、自分より上の人数さえ数えれば、順位は決まるのです。

並べ替える方法と数える方法を比べる¶

順位を出す方法は、大きく分けて2つあります。どちらにも向き不向きがあるので、違いを表に整理しました。

科目Bでよく出るのは、2行目の数える方法です。元の配列の並びを崩さずに、同じ位置に順位を入れた配列を作れるからです。

右端の列にも注目してください。数える方法では、同じ点数の人は同じ順位になり、その次の順位は人数ぶん飛びます。85点が2人で2位なら、次の人は3位ではなく4位です。

ソートや出現回数の問題との違い¶

順位を付ける問題とよく似ているのが、値を入れ替えて並べ直すソートの問題です。ソートは配列そのものを書き換えますが、順位を付ける問題は元の配列には手を付けず、別の配列に数を書き込みます。

値を交換しながら並べていく処理は、ソートの記事で詳しく扱っています。

【関連記事】科目Bのソート問題を解くコツ｜交換される値を追ってみよう

また、条件に合う値を数えるという点では、出現回数を数える問題とも似ています。違いは、出現回数がある値と等しいものを数えるのに対し、順位は自分より大きいものを数える点です。

【関連記事】科目Bの出現回数を数える問題の解き方｜カウント用の配列を追う

まず目を付ける場所¶

順位を付ける仕組みがつかめたら、次はコードのどこから読むかを決めます。この問題では、目を付ける場所が3つあります。

ひとつ目は順位の配列の初期値、ふたつ目は比べている不等号の向き、みっつ目は等号が付いているかどうかです。この3か所を確かめれば、どんな順位が出てくるのかが分かります。

初期値は0か1か¶

最初に確かめたいのが、順位を入れる配列をいくつで初期化しているかです。1で初期化していれば、自分より大きい値を数えて足すだけで、そのまま順位になります。

0で初期化している場合は、どこかで1を足しているはずです。ループのあとに1を足しているのか、等号付きの比較で自分自身を数えているのかを確かめましょう。

不等号の向きはどちらか¶

次に見るのが、if の中の不等号の向きです。自分以外の値が自分より大きいときに数えていれば、大きい値ほど上位になる順位です。

逆に、小さいときに数えていれば、小さい値ほど上位になります。タイムのように小さいほうが良い値では、こちらの向きが正解になることもあります。問題文がどちらを上位と言っているのかを、先に確かめてください。

等号は付いているか¶

最後に見るのが、比較に等号が付いているかどうかです。大きいだけを数えるのか、等しいものも数えるのかで、同点の人の順位が変わります。

等号が付くと、自分自身も数えてしまう点にも注意が必要です。比べる相手の中に自分が含まれているかどうかを、内側のループの範囲で確かめましょう。

例題：自分より大きい値を数えて順位を付ける¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のプログラムは、整数型の配列 score を受け取り、各要素の順位を同じ位置に入れた配列を返す関数です。値が大きいほど上位とし、同じ値は同じ順位とします。配列の添字は1から始まります。

○整数型の配列: ranking(整数型の配列: score)
  整数型: n ← score の要素数
  整数型の配列: rank ← {n 個の 1}
  整数型: i, j
  for (i を 1 から n まで 1 ずつ増やす)
    for (j を 1 から n まで 1 ずつ増やす)
      if (score[j] が score[i] より大きい)
        rank[i] ← rank[i] + 1
      endif
    endfor
  endfor
  return rank

ranking は、rank のすべての要素を1にしてから始めます。外側のループで順位を決めたい要素 score[i] を1つ選び、内側のループで全員と比べて、自分より大きい値があるたびに rank[i] を1増やします。

では、ranking({70, 85, 60, 85, 90}) の戻り値は何になるでしょうか？

トレース表で大きい値の数を追う¶

頭の中だけで二重のループを追うと、誰と誰を比べたのかが分からなくなりがちです。そこで、外側のループ1回ごとに、score[i]、自分より大きかった値、その個数、決まった rank[i] をトレース表に書きます。

ポイントは、大きかった値を具体的に書き出しておくことです。個数だけを書くと、数え漏れに気づきにくくなります。

できあがった rank は {4, 2, 5, 2, 1} です。元の score と同じ位置に、それぞれの順位が入っています。

2番目と4番目は同じ85点なので、どちらも2位です。そして、その次の70点は3位ではなく4位になっています。

上に90点と85点が2人、合わせて3人いるので、4位になるわけです。同点のあとに順位が飛ぶのは、この数え方の自然な結果だと分かります。

トレース表の書き方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

比べる回数を確かめる¶

この関数は、外側のループが n 回、その1回ごとに内側のループも n 回まわります。要素が5個なら、if の比較は 5 × 5 で25回行われます。

比較の回数を聞く設問が出ることもあります。自分自身との比較も回数に入っている点を忘れないようにしましょう。

自分自身と比べても、大きいという条件は成り立たないので、順位には影響しません。ただし、等号付きの比較に変えると話が変わります。この点は、次の段階で詳しく見ていきます。

同点のあとを詰める順位もある¶

同点のあとに順位を飛ばさず、85点が2位なら70点を3位にする数え方もあります。この場合は、自分より大きい値の個数ではなく、自分より大きい値の種類の数を数えます。

例題なら、70点より大きい値の種類は85と90の2種類なので、2に1を足して3位です。問題文に同点の扱いが書かれていたら、どちらの数え方なのかを必ず確かめましょう。

間違いやすい選択肢の見分け方¶

順位を付ける問題では、初期値や不等号を少しだけずらした選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

例題の ranking({70, 85, 60, 85, 90}) を使って、よくある誤りを表にまとめました。

3行目の誤りは、同点が無い人の順位はすべて正しく出ます。違いが出るのは、85点の2人だけです。

同点の人がいない例だと、正しいコードと同じ答えになってしまうのです。答えが合ったから正しい、と決めつけず、同点を含む例でも試すのが確実です。

同点を含む例を自分で作る¶

選択肢を絞るときは、例題とは別に、同点を含む小さな配列を自分で用意すると安全です。{3, 5, 5} のような3個の配列でも十分に違いが出ます。

正しいコードなら {3, 1, 1} になります。初期値0で等号付きの選択肢なら、5点の2人はお互いと自分自身を数えて {3, 2, 2} となり、すぐに見分けられます。

1位と最下位から検算する¶

計算結果を確かめるときは、最大値が1位になっているか、最小値が要素数と同じ順位になっているかを見ましょう。例題なら、90点が1位、60点が5位です。

この2つのどちらかが崩れていたら、初期値か不等号のどこかがずれています。表を全部書く前に選択肢を絞れる、手軽な検算方法です。

冒頭の不具合も等号だった¶

冒頭でお話ししたランキング表示の不具合も、原因は2行目と同じ等号でした。同じ得点の人がいるときだけ順位がずれるので、テストデータに同点が無い間は見つからなかったのです。

試験でも実務でも、境界にあたる値を含めて確かめることが大切だと、そのとき強く感じました。

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。二重のループで何度も同じ配列を見る処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数や配列の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの比較で予想とずれたのかがすぐに分かります。

試すときは、まず正しい ranking を動かして、rank が {4, 2, 5, 2, 1} になるのを確かめてください。そのあと、比較を以上に変えて、すべての順位が1つずつ下がる様子を見ると、等号1つで結果が変わることが体で分かります。

慣れてきたら、初期値を0にしたり、同点のあとを詰める数え方を自分で書いてみたりしましょう。どの比較で rank が増えるのかが、少しずつ見えてくるはずです。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、自分より大きい値を見つけるたびに順位が1つずつ下がっていく様子を確かめてみてください。

同じく余りや合計を表で追う力を試したい人には、番号の最後の1桁を求める問題もおすすめです。

【関連記事】科目Bのチェックディジット問題の解き方｜桁ごとの重みを表で追う

まとめ¶

科目Bの順位を付ける問題は、並べ替えの知識を問うものではありません。自分より大きい値を数えて1を足す、という手順を表に書いて追えば、落ち着いて解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、要素が3個から5個くらいの小さな配列で十分です。何度か表を書くうちに、初期値と不等号を見ただけで、どんな順位が出てくるのかが分かるようになります。

順位は、自分より大きい値の数に1を足したもの。同点を含む例で必ず試す。 この2つを習慣にしておけば、順位を付ける問題にも自信を持って向き合えます。次に順位の配列を作るコードに出会ったら、まずは先頭の値より大きい値がいくつあるかから表に書いてみてください。