プロローグ
「う〜ん、わかんないなあ......。」
私は駅前の案内地図とにらめっこをしていた。といっても、道に迷っているわけではない。この街は道路が碁盤の目のように走っていて、基本的に方角さえ把握していれば道に迷うことはないのだ。目的地の市役所は、今いる交差点から東に向かって5つ目の交差点で左に曲がり、北に向かって5つめの交差点にある。
では私は一体何に悩んでいるのか。それは目的地に向かうルートの数が何通りあるかという問題だ。
もちろん、ある程度の制約がなければ、ルートの数に上限が無くなってしまうので、いくつかの条件はつけてある。
1. 道路の上のみを移動する。
2. 各交差点を通る回数は高々1回である。
3. 現在地と目的地を含む最小の長方形領域から出ない（境界上はOK）。
「地図を見た感じ、この制約を満たしたまま、xy平面上で隣接する格子点同士のみ行き来可能として、原点から(5,5)まで移動できるルートの数を答えれば良いっぽい......無理では......？」
そんなことを考えている私は傍から見ると、道に迷った観光客に見えるのだろう。この1時間で5人に「道案内をしましょうか......？」と声をかけられている。ただ、声をかけてくれた親切な人達も、私が悩んでいる内容を聞くと、苦笑いを浮かべて立ち去ってしまった。
「なにやってんだろ、もう行こ......。」
意気消沈してトボトボと歩きだす。
「あの、ちょっと良いですか？」
声のする方に振り返ると、そこには背の高い男性がいた。帽子を深く被っているせいで顔は見えないけど、おそらく外国の人だろう。
「はい、なんでしょうか？」
「盗み聞きするつもりはなかったんだけど、さっきの会話が聞こえてしまってね、君の疑問に答えようと思うんだ。といっても、"現状では効率よく数え上げる手段が発見されておらず、全てのルートを重複無く数えるしか方法がない" というしょうもない答えしか出せないんだけどね。」
「ええっ！？5×5とはいえ、それってかなり大変ですよね！？！？」
「ああ、そうだね。実際に全てを数えてみると 1,262,816 通りになることが知られているのだけど、もう手で数えるのは厳しいね。」
「そうなんですね。私はできもしないことに一時間も悩んで、時間を無駄にしてしまったのですね......。」
「一時間も悩んでいたのかい！？時間を無駄にしてしまったと思うことなんて無いよ。むしろ、その考え続けた時間は君の才能さ。誇るといいよ。」
「はあ、ありがとうございます。」
「君は何かの組合せの数とかを数えるのが好きかい？」
「ええ、人並みには好きだと思います......。学校の勉強はからっきしですが、何かを数えるのだけは昔から好きでした。」
「やっぱりね。君には素質があるよ。"競技プログラミング"というのをやってみると良い。きっと楽しいから。」
「プログラミングですか？学校の授業でふぉーとらん？ってやつを使ってやったことがありますけど、あんまり楽しいと思えませんでした......。」
「それは題材が君に向いていなかっただけさ。それに、競技プログラミングはプログラミングという名前が付いてはいるけれど、決してプログラミングだけの能力を競うものじゃない。むしろ、思考力や発想力を問うような問題が多い。それこそ、何かの組合せの数を数える問題とかね。組合せを数える力を全世界の強豪たちと競えるんだ、しかも、君は強い方になれるだろう。見たところ君は高校生のようだが、最近では全国大会も開かれている。君なら優勝も夢ではないかもしれない。」
「そうなんですか。そうやって言われると、なんだか面白そうに思えてきました......！競技プログラミング、やってみようと思います！」
「それは良かった。君という才能に出会えた今日に、心から感謝するよ。」
「ありがとうございます。最後に、あなたの名前を聞いても良いですか？」
「名乗るほどの者でもないよ。ただの"旅人"さ。そうだ、最後に1問だけ、問題をだそう。君が考えていたルートのうち、最短経路に絞ると何通りになるかな？君が競技プログラミングを続けていれば、きっといつかまた会うだろう。その時に答えを聞かせてくれ。」
これが私、吉田萌花と競技プログラミングとの出会いだった。
