| 第９回日本情報オリンピック 予選５ |
|
|
2009年12月26日
情報オリンピック日本委員会
|
最短経路の個数を数える問題であるが，この問題では「交通規則」が存在するため，難しくなっている． しかし，問題を解くにあたっての考え方は，交通規則がない場合と同じである．
解法１
南北や東西の道の1ブロック分の区間を「辺」とよぶ．家を出てから「ある辺」に「ある状態」（次の交差点で曲がれる，または曲がれない）で到達するまでの場合の数を考える．この値は「辺」と「状態」の組ごとに様々であるが，次のようにして順次求めていくことが出来る．
辺 E に「次で曲がれない」状態で到達する場合の数を t[E][0]，「次で曲がれる」状態で到達する場合の数を t[E][1] と書くことにする．E の真後ろにある辺を B，E へ進入してくる B とは異なるもう一つの辺を S と書くことにすると，t[E][0] = t[S][1]，t[E][1] = t[B][0] + t[B][1] が成り立つ．これらの式を用いて，t の値を順に求めていくことが出来る．
最終的に求める場合の数は，交差点 (w,h) に西から進入する辺に「曲がれる」または「曲がれない」状態で到達する場合の数と， (w,h) に南から進入する辺に「曲がれる」または「曲がれない」状態で到達する場合の数，これら 4 つの値を合計した値となる．
ただし，この問題では場合の数を 100000 で割った値を答えることに注意しなければならない．また「上の解法で家から会社までの通勤経路の総数を求めた後に，最後に 100000 で割って答とする」のでは不十分である．なぜならば通勤経路の個数は非常に大きな値になる可能性があり，そのまま計算するとオーバーフローする場合があるためである（実際の入力データの中にも，通勤経路の総数が非常に大きな値となるデータが存在する）．そこで，上述の方法で t の値を求めていく際に，「 t の値を 100000 で割った余り」を代わりに求めていくようにすればよい．すなわち，上述の式で新たな t の値を計算する際に毎回 100000 で割った余りを代わりに代入するようにすればよい．
解法２
与えられた w,h に対して，家から会社までの通勤経路の個数を直接計算する方法がある．この解法では次の事実を用いる： 「和が n であるような 0 以上の整数 a1,a2,…,am の組の個数はn+m-1Cnである」．
さて，n を 0 以上の整数とする．かりにJOIさんの通勤経路が「家から東へ a1 ブロック進み，北へ b1 ブロック進み，東へ a2 ブロック進み，北へ b2 ブロック進み，……，北へ bn ブロック進み，東へ an+1 ブロック進み，会社に到達する」というものであったとしよう（各 ai, biは 1 以上とする）．このときa1+…+an+1 = w-1, b1+…+bn = h-1 である．また，二度続けて曲がれないという規則は，a2, a3, …, an ≧ 2, b2,…bn-1 ≧ 2 という条件と同値である．さて，このような条件をみたす通勤経路の個数は「これらの式をみたす a1,…,an+1 の組の個数」×「これらの式をみたす b1,…,bn の組の個数」である． ここで，a'1 = a1-1, a'i = ai-2 (2 ≦ i ≦ n), a'n+1 = an+1-1 とすると，「 a1,…,an+1 の組が上の式をみたすこと」と「 a'1,…,a'n+1 の和が w-1-2n となり，各a'iは 0 以上であること」が同値となる．したがって冒頭で述べた事実より，上の式をみたす a1,…,an+1 の組の個数は (w-1-2n)+(n+1)-1Cw-1-2n = w-n-1Cn である．同様にして，上の式をみたす b1,…,bn の組の個数が h-n-2Cn-1 であることもわかる．
よってJOIさんの通勤経路が最初に書いたような形のものである場合，通勤経路の個数は w-n-1Cn × h-n-2Cn-1 個である．実際には n はさまざまな値をとること，またさらにJOIさんの通勤経路には他の形のもの（たとえば最初に東に進み，最後に北に進むものなど）が存在することを考えると（いずれの場合における通勤経路の個数も今回の場合と同様にして求めることが出来る），求める通勤経路の総数は次の式となる：
二項係数はプログラムの最初ですべて計算し，配列に保存しておくとよい．ただし，オーバーフローを回避するために，二項係数の値を 100000 で割った余りを求めるようにする．そのためには，式 n-1Cm-1 + n-1Cm = nCm を用いるのがよいだろう．