2015JOI本選1 鉄道旅行 解説

問題リンク

解説

まずは、どのような場合にICカードを買えばいいか考えましょう。 当たり前ですが、「買った方が安くなる場合」に買う方がよいです。 よって、それぞれの鉄道について、「買った方が安いか」を判定できればよい、ということになります。

この判定をするためには、それぞれの鉄道に何回乗るかを求める必要がありますが、愚直に数えていては間に合いません。

このような、「区間に数を加算する」というクエリがたくさんある場合、imos法というテクニックを使い、クエリを高速に処理することができます。 imos法については、こちらの記事を参照してください。

imos法をはじめとする累積和のテクニックは、レベルが上がっても頻出です。覚えておきましょう。