改札にチケットを何枚入れれば良いのかを、いもす法で解いてみた

こんにちは、ほけきよです。

最近、競技プログラミングをはじめました。

atcoder.jp

結構ハマってて、とりあえず年内水色目指しています。 水色になったらドヤ顔でイキリブログ更新します😏

アルゴリズム系のお勉強を全くやったことなかったので、 今まで知らなかった or 意識しなかったアルゴリズムが使えるようになっていくのが、とても楽しいのです。 無料で道具を貰うことができるなんて、ほんと最高ですよね。

道具を持っていると使いたくなるのが性です。先日、そんな場面に遭遇して嬉しかったので書いておきます。

改札きっぷ問題

出張で改札を通る直前、ふと思いました。

ほけきよ君は、金沢に行く。切符の指定範囲内の改札での乗り換えでは、必ず当該切符を通さなければならない。全ての切符を通す改札はどこでしょう？
→imos法っぽい！！
となりながら出張してる。 pic.twitter.com/yKV9gkHU5x

— ほけきよ (@hokekiyoo) May 29, 2019

新幹線とか使うときに、大量のきっぷが払い出されますよね？その時の改札ごとに何枚のきっぷを入れれば良いんだ！？という問題です。

ちなみに、東京の改札は賢くて適当に全部入れたらよしなにしてくれるんですが、安城はそうはいきません。区間外のきっぷを入れると改札を通してくれません。ハードモードです。

いもす法

このような始点と端点が決まっていて、数を数える問題は、いもす法というのが効率がよく、常套手段となっています。

いもす法の解説

出入り口だけカウントすれば、中身は後処理でいけるという発想です。 図にするとこんな感じ。

いもす法とは

そのまんまこの改札きっぷ問題に使えそうです！各区間で

• 区間の始まり : +1
• 区間の出口過ぎたら : -1

としておいて、累積和(はじめから足し上げていく)を取るとそのときに必要なチケット数が出ます

解いた

実装はとても簡単です。pythonで実装してみました。

累積和の計算にはitertoolsに入っているaccumlateが便利です。一瞬で終わります。

from itertools import accumulate
As = ["安城","名古屋","米原","金沢"]
tickets = [(0,3),(1,2),(2,3)]
imos = [0]*5
for s,g in tickets:
    imos[s] += 1
    imos[g+1] -= 1
cum = list(accumulate(imos))
for num, A in zip(cum,As):
    print("{}\t{}".format(A,num))

これを出力すると...

安城    1
名古屋  2
米原    3
金沢    2

きちんとその場所場所で必要なきっぷ枚数が出ています！いもす法バンザイ！

まとめ

今回のは結構簡単な問題でしたが、こうやって、学んだことを普段の生活に活かせられると、勉強が楽しくなってきますね！

ちなみに、考えすぎると↓の人みたいに日常生活に支障をきたすこともあるので注意が必要ですね。

朝、絶対値の最小値取るような問題を解いた後の出勤中、コンビニで283円のお買い物に対し「3円のお釣りが最小だろう」などと思い280円しかお金を出さず、店員に「えっ…」みたいな顔されたので、自分、今週いっぱい有休とっていいすか？

— ほけきよ (@hokekiyoo) May 26, 2019

今後もほどほどに精進していきます！ではではっ