1.問題

2.この記事を書こうと思った理由

問題の結論から述べると、開始時刻を $L := \text{lcm}(P_{1}, P_{2}, ..., P_{N-1})$ で割った余りで分類したらよいです。要するに、$0, 1, ..., L-1$ それぞれについて、その値を出発時刻とした場合の、移動の所要時間を求められたらよいです。確かに周期は $\text{lcm}(P_{1}, P_{2}, ..., P_{N-1})$ になりそうだな～という感じはしますが、きちんと説明するとなると個人的に難しく感じましたし、公式解説を読んでみても、分かりやすく説明しているというより正当性の証明という感じで理解が難しかったので、自分の中で咀嚼し、理解した過程を残そうと思い、備忘録としてこの記事を書きました。

3. 思考の流れ

時刻とありますが、一旦開始から到着にかかる時間 $T$ だけを考えます。$T = バスまたは徒歩による移動時間 + 待ち時間$ です。前者は一定であるため、後者の待ち時間について考えてみましょう。

バス停 $i$ では（時刻 $t_{i}$ に到着したとして）、待ち時間（厳密には、バス停 $i$ に到着してから次のバスが来るまでの時間）を $W_{i}$ とすると、$W_{i} = (P_{i}-r) \text{%} P_{i}$（ただし、$r=t_{i}\text{%}P_{i}$）となります。よって、バス停 $i$ における待ち時間は $r$ のみによって決定することが分かりました。これは全てのバス停について言えることなので、$T$ にも（出発時刻による）周期性があるはず、という予測が立ちます。ここまでは当たり前のことを述べただけで、次からが本題です。
まず、$i=1$ について考えます。出発時刻を $L$ だけ遅らせた場合を考えます（なぜかというと、$L$ だけ遅らせたときの $T$ の値が $L$ だけ遅らせなかった場合のそれと一致した場合、待ち時間は $L$ の周期があると言えるからです。）。到着時刻は $t_{1}'=t_{1}+L$ だから、待ち時間は $W_{1}'
=(P_{1}-t_{1}'\text{%}P_{1})\text{%}P_{1}
=(P_{1}-(t_{1}+L)\text{%}P_{1})\text{%}P_{1}$ となります。$W_{1}=W_{1}'$、つまり $(P_{1}-t_{1}\text{%}P_{1})\text{%}P_{1}=(P_{1}-(t_{1}+L)\text{%}P_{1})\text{%}P_{1}$ が成り立つための必要十分条件は、$L\text{%}P_{1}=0$ ということが分かりました。この条件が満たされているとき、（当たり前ですが）$i=1$ のときの待ち時間は、出発時刻を $L$ 遅らせる前と全く変わりません。よって、$i=2$ における到着時刻は、単に $L$ を足しただけの $t_{2}+L$ になります。$i=1$ の時と全く同様の議論から、$W_{2}=W_{2}'$ となるための必要十分条件は $L\text{%}P_{2}=0$ となります。

これを繰り返していくと、全ての $i$ で待ち時間が変わらないための必要十分条件は $L\text{%}P_{1}=0 \ かつ \ L\text{%}P_{2}=0 \ かつ \ ... かつ \ L\text{%}P_{N-1}=0$、すなわち（$P_{1},P_{2},...,P_{N-1}$ のいずれでも割り切ることができる最小の自然数であるから）$L=\text{lcm}(P_{1},P_{2},...,P_{N-1})$ となります。以上の説明が、周期を導出する流れとなります。

4.終わりに

読んでいただきありがとうございました。誤りや説明が足りない部分などがあれば教えていただけると幸いです。