競プロって何ですか？

13. 線形探索法って何ですか？

「ダメだ、1問しか解けなかったー」

　私は机に突っ伏した。1問解けたことは嬉しいが、「1問しか解けなかった」と考えると悔しい。2問目も解けそうな問題ではあったのだ。しかし、どうやっても解けなかった。

「私は3完だったぜ」

　早希が大きく伸びをしながら言った。

「3完いいなあー」

「いいだろ」

「玲奈は？」

「……4完」

　特に嬉しそうでもない無表情の玲奈がそう呟く。

「4完かー。二人ともすごいなあ。なんでそんなに解けるの？　私だけ置いてきぼりだ」

　1完の私と、3完の早希と4完の玲奈では天と地ほどの差があるだろう。やはりこの二人は頭が良い。それに加えて玲奈はもともとプログラミングの経験者だ。早希は学年トップの成績だし。私だけ何者でもない。

「どこで躓いたの？」

　一仕事終えたような顔をした枝刈先輩が尋ねてくる。さっきまでパソコンで何か作業をしていたようだ。

「この問題なんですけど……」

「どれどれ」

　枝刈先輩が身を乗り出して私のパソコンの画面をのぞき込んだ。

◇◇◇◇◇◇

太郎君はN個の整数A_0, A_1, ……, A_N-1を持っています。N個の整数の最大値を求めてください。

制約

1 <= N <= 10^5

0 <= A_i <= 10^9

入力

N

A_0, A_1, ……, A_N-1

出力

N個の整数の最大値を出力せよ。

◇◇◇◇◇◇

「これのどこが分からないの？」

　枝刈先輩が首をかしげる。

「……どうやったら最大値が求められるのか分からないんです」

　私は率直に答えた。

「なるほどね。じゃあ線形探索法について教えてあげよう」

「線形探索法？　何ですか、それは？」

「簡単に言うとデータを前から順番に見ていく探索方法ね。今回の問題だったらA_iの値を前から順番に見ていって最大値を探すのよ」

　そう言われて私は考える。

「うーん、言われてみればそうなんですけど、それをどうやってプログラムに書けばいいのか分かりません……」

「それじゃあ私が書いてあげる」

　そう言ってから枝刈先輩がホワイトボードにコードをすらすらと書いていく。いつの間に我が部活にホワイトボードなんてあったのだろうか。どうせ早希がパソコン部から持ってきたのだろうけど、と私は予想する。そしてその予想は当たっていることだろう。

　枝刈先輩がコードを書き終えてこちらを向いた。

「どう？　理解できそう？」

「頑張ってみます」

　私はホワイトボードに書かれたコードを見ながら、自分でもキーボードを叩いてプログラムを書く。なるほど、少し理解できた気がした。

　サンプルケースを試してみると、ちゃんと答えが一致した。そのまま提出ボタンを押す。すると数秒の後、ページが切り替わって「AC」が表示された。

「解けました！　ありがとうございます、先輩！」

「おめでとう。詩織は本番でも2問解けたら良さそうだね。早希は3問、玲奈は4問」

「そうですね」

　私がそう答えると、早希が続けて言った。

「先輩、他に覚えておいたほうがいいやつとかないの？」

「他に？　いっぱいあるけど」

「教えて！」

　枝刈先輩は少し考えてから口を開いた。

「まずはソートだね。ソートっていうのはデータを並び替えること。ソートにもいろいろな種類があるけど、とりあえずはC++の標準で用意されているsortを使うといいよ」

　そう言ってから枝刈先輩はホワイトボードにコードを書き始める。

◆◆◆◆◆◆

#include <bits/stdc++.h>

using namespace std;

int main() {

　vector<int> v = {2, 7, 1, 10, 5};

　// 昇順にソート

　sort(v.begin(), v.end()); // 1,2,5,7,10

　// 降順にソート

　sort(v.begin(), v.end(), greater<int>{}); // 10,7,5,2,1

}

◆◆◆◆◆◆

「書き方としてはこんな感じだな」

「おお、勉強になります」

　私は勉強用のノートにコードを書き写した。そんなアナログな勉強方法でいいのかと思われるかもしれないが、結局のところ手で書いたほうが覚えやすいのだ。私は何でもノートに書き写す。これまでそうやって生きてきた。

「ソートはよく使うから覚えておいて損はない、それどころか覚えていないと厳しいかもしれない」

　枝刈先輩の話を早希と玲奈も頷きながら聞いている。

「それから他には――」

　そのとき5時を告げるチャイムが鳴った。下校の時間だ。

「もうこんな時間か」

「今日はもう終わりですね。残念です」

　私はそう言ってから立ち上がる。ずっと座っていたから体が固まっている。大きく伸びをして体をほぐした。

「じゃあ続きはまた明日ということで。私は一度ゲーム研究部の部室に寄っていくから先行くわね」

　枝刈先輩は何か用事があるらしく、荷物をまとめると急いで部室を出ていった。

「詩織、玲奈、帰ろうぜ」

　早希がカバンを持って部室を出ていく。その後ろを玲奈がついていく。

「ちょっと待って」

　私もパソコンの電源を落とすと部室を後にした。

　家に帰ったら今日の復習をしよう。

◆◆◆つづく◆◆◆