基礎プロIの知識でICPC問題を1問解こう

ICPC（国際学生対抗プログラミングコンテスト）は難問が出題されますが、1問は基礎プロIの知識で十分解けます。しかし、ちょっとしたコツは知っておかないと手強いでしょう。このページでは1問を確実に解くためのコツと知識を紹介します。

どの問題を解くか

最初の問題、Problem Aです。後の方の問題は難しい順とは言い切れず、アルゴリズムの知識や解答者の得意・不得意が影響しますが、Problem Aは確実に一番易しい問題です。過去の傾向が今後も同じとは言い切れませんが……

問題の読み方

まず問題を読むのですが、ここでちょっとしたコツがあります。2019年のA問題を例に挙げます。問題文は次のように書かれています。

期末試験の成績
私は，中学校の教師である． ちょうど期末試験が終わったところで，すべての科目について全生徒の点数が手元にある． どれぐらい高い合計点を得た生徒がいるのか知りたいのだが，科目ごとの得点データになっているので，作業が容易でない． そこで，優秀なプログラマであるあなたに手助けしてほしい． 具体的には，合計点が最も高い生徒の合計点を求めるプログラムを書いてほしい．

この問題文はさらっと読み流せば良いです。期末試験とか中学校の教師とかどうでもよいのです。ここで読んでおくのは結局やりたいこと、「合計点が最も高い生徒の合計点を求めるプログラムを書いてほしい」です。それを踏まえて、実際にどういう入力でどういう結果を出力するのかを残りの説明で理解しましょう。Inputの項目には次のように書かれています。

入力は複数のデータセットからなる． 各データセットは次の形式で表される．

n m
p1,1 p1,2 … p1,n
p2,1 p2,2 … p2,n
…
pm,1 pm,2 … pm,n

データセットの最初の行は，二つの整数 n と m からなる． n は生徒の人数 (1 ≤ n ≤ 1000)，m は科目数 (1 ≤ m ≤ 50) である． それに続く m 行のそれぞれには，特定の科目に対する n 人の生徒の得点がある． pj,k は，生徒 k の科目 j に対する得点を表す整数である (1 ≤ j ≤ m，1 ≤ k ≤ n)． この値は，0 ≤ pj,k ≤ 1000 を満たす．
入力の終わりは二つのゼロからなる行で表される． データセットの個数は 100 を超えない．

慣れないと意味を読み取りにくい書き方です。そこでSample Inputも見ます。

5 2
10 20 30 40 50
15 25 35 45 55
6 3
10 20 30 15 25 35
21 34 11 52 20 18
31 15 42 10 21 19
4 2
0 0 0 0
0 0 0 0
0 0

これらを合わせて見ると、最初に2つの数字が来て、それは生徒の人数と科目数であることが分かります。その後に、人数分の点数が並び、それが科目数だけ繰り返される、となっています。人数と科目数が両方0でデータは終了です。データ例を見ると、1行が1科目分であることが分かります。これはInputの説明ではよく読まないと1行が1人分と間違えてしまうかもしれません（私は最初間違えました）。入力例と合わせて説明を読むようにしましょう。

次にOutput、何を出力するかを読みます。これも同様にOutput for the Sample Inputと合わせて読みます。

各データセットについて，合計点が最も高い生徒の合計点を出力せよ． 生徒 k の合計点 sk とは sk = p1,k + … + pm,kのことである．

105
83
0

Outputの説明の後半は別に読まなくても合計点でよいですね。実際にどう計算すればこの結果になるかを見ておきましょう。1つめのデータに対しては最後の人が50点と55点で105点、2つめは3番目の人が合計83点と、縦に足していくことがわかります。3つめのデータは全部0点なので最高得点も0点。そういうこともあるねんな、くらいでOK。

以上、コツとしては、InputとOutputの例を見ながら説明文は何を言おうとしているのかを理解する、です。

方針を立てる

プログラムでやりたいことが分かったので、どのように作るか、大雑把に考えます。「合計点が最も高い生徒の合計点を出力」ということは最大値を求める問題であることがわかります。このやりかたは練習問題でもやっていますね。各生徒の合計点をどうやって計算するか、ですが、データの入力の順番が1行で1科目ずつとなっているので、生徒1人の合計点をすぐに計算することはできそうにないです。少なくとも生徒の数だけの配列を用意するのが良いでしょう。2次元配列ですべての点数を覚えておいてもよいのですが、合計点だけ計算すればよいので、得点を読み込むたびにこれまでの合計点に加算することにします。プログラムの流れとしては、"0 0"が来たら終わる繰り返しがあって、その中でまず生徒数と科目数を読み取り、科目数だけ繰り返して点数を読み取っていき、合計点を計算して、最大値を求めて表示をする、というくらいを考えます。

どうやって数値を読み取るか

基礎プロIではscanfを使って標準入力から整数値を1つずつ読み込んでいましたが、この問題のようなデータ形式を読み取るにはちょっと違った使い方を知っておく必要があります。

まず、最初の行のように2つの数値がスペースで区切られて書かれている場合は、scanfの書式指定子に同じように書けばよいです。

scanf("%d %d", &student, &kamoku);

次に、1行分のデータですが、このデータの個数は決まっていない（生徒数で決まる）ので同じようにはできません。実は、scanfでデータを読み取るとき、標準入力から入力された文字は改行文字が来ると入力バッファと呼ばれる記憶領域に一旦蓄積され、そこからscanfの書式指定子に合ったデータを読み取っていきます。また、スペースはデータの区切り文字として扱われます。ですので、1行分読み込んだデータに対して1つずつ数値を、必要個数分繰り返して読み取っていくことができます。例えば次のようにして、"10 20 30 40 50"という1行の入力データから値を1つずつ受け取ることができます。

for (int i = 0; i < 5; i++) { scanf("%d", &data[i]); }

なお、データの入力は入力リダイレクションを使います。これも基礎プロIでやりましたよね。Sample Inputの内容を適当なファイル名のテキストファイルにし、例えば a.out < input.txt のようにします。本番の問題データもテキストファイルで与えられるので、同様に実行します。

プログラムを作っていこう

まず骨組みを作る

#include <stdio.h> int main() { return 0; }

これはCのプログラムで書くいつものやつ。

人数と科目数を読み取る

#include <stdio.h> int main() { int seito; int kamoku; for (;;) { scanf("%d %d", &seito, &kamoku); if (seito == 0 && kamoku == 0) break; } return 0; }

変数名は英語にしなくてもローマ字でいいや。無限ループにしておいて、"0 0"が来たらbreakで抜け出しています。

点数を読み取る

#include <stdio.h> int main() { int seito; int kamoku; for (;;) { scanf("%d %d", &seito, &kamoku); if (seito == 0 && kamoku == 0) break; int sum[1000] = {}; for (int i = 0; i < kamoku; i++) { for (int j = 0; j < seito; j++) { int score; scanf("%d", &score); sum[j] += score; } } } return 0; }

合計点だけ計算していけばよいのでsumという配列を作っています。配列の大きさですが、生徒数分で十分なので int sum[seito] = {};でもOK。問題文では生徒の人数は1000以下であるとしているので、この例では1000としています。現在のC言語では変数宣言はプログラムの途中でもできるので、ここで作っています。すると、新たなデータセットのたびにsumを作り直すことになり、値をリセットする必要がありません（まあ、配列を作り直しているので大した違いじゃないですが）。次の繰り返しのカウンタ変数や1つ分の値を読み込むための変数scoreでも同様にしています。変数の有効範囲を極力絞るというのが今風のプログラミングです（基礎プロIの資料で説明している書き方＝変数宣言は関数の冒頭にまとめる、は実は古いのですが、C言語は伝統的にそういうものだったということで）。sumの値をすべて0にしておくために = {}; としていることに注意。

カウンタ変数jの繰り返しで1行分のデータを1つずつ読み取って、各生徒の点数の合計値に加えています。このscanfの使い方は上述のとおり。

最高得点を探す

#include <stdio.h> int main() { int seito; int kamoku; for (;;) { scanf("%d %d", &seito, &kamoku); if (seito == 0 && kamoku == 0) break; int sum[1000] = {}; for (int i = 0; i < kamoku; i++) { for (int j = 0; j < seito; j++) { int score; scanf("%d", &score); sum[j] += score; } } int max = -1; for (int i = 0; i < seito; i++) { if (max < sum[i]) max = sum[i]; } printf("%d\n", max); } return 0; }

先ほどのプログラムで各生徒の合計点は求まっているので、あとは最大値を探す。maxの初期値は-1としていますが、点数は0以上1000以下であるとInputの説明で書かれているので、0以下の値であれば問題ありません。次のようにした方が無難ですが。

int max = sum[0]; for (int i = 1; i < seito; i++) { if (max < sum[i]) max = sum[i]; }

できあがったと思ったらテストする

以上でできあがったはずなので、コンパイルして間違いが無いか確かめ、コンパイルできたらテストデータでテストしましょう。Sample Inputで示されているデータをテキストファイルにコピペしてデータファイルを作り、Output for the Sample Inputの結果と同じになればOK、はい1問解けた!!

Inputの説明の値の範囲は何だったのか

Problem Aレベルではあまり意味がなかったりします。敢えて言えば、生徒の人数から配列の大きさの最大値を決めてもよいとか、最大値は負にはならないことが分かる程度ですが、これとて特に重要ではなかったりします。後の方の問題では計算量を見積もり、あまりに遅くなりそうならアルゴリズムを工夫しなければならない、といった使い方もしたりしますが、とにかくProblem Aでは気にするだけ無駄なのでさらっと読み飛ばしましょう。

2問目を解くために

過去の傾向では、文字を扱う問題が次に易しい定番問題になっているようです。C言語で挑戦する場合は、char型の扱い（データの表現形式、入出力、値の判定など）をマスターしておきましょう（基礎プロIIの内容です）。また、scanfで読み取るときに改行文字の扱いが厄介であることも知っておきましょう（ググれば解説が沢山出てきます）。Java言語等の文字列処理が豊富に用意されている言語を使うと楽勝だったりすることもありますが、その分覚えることが多かったり、標準入出力を扱うのが面倒だったり（Javaの場合）。