プロクラシスト

今日の寄り道 明日の近道

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


スポンサーリンク

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

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

atcoder.jp

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

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

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

改札きっぷ問題

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

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

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

いもす法

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

いもす法の解説

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

f:id:imslotter:20190529113148p:plain
いもす法とは

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

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

解いた

実装はとても簡単です。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

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

まとめ

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

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

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

PROCRASIST