こんにちは、ほけきよです。
最近、競技プログラミングをはじめました。
結構ハマってて、とりあえず年内水色目指しています。 水色になったらドヤ顔でイキリブログ更新します😏
アルゴリズム系のお勉強を全くやったことなかったので、 今まで知らなかった or 意識しなかったアルゴリズムが使えるようになっていくのが、とても楽しいのです。 無料で道具を貰うことができるなんて、ほんと最高ですよね。
道具を持っていると使いたくなるのが性です。先日、そんな場面に遭遇して嬉しかったので書いておきます。
改札きっぷ問題
出張で改札を通る直前、ふと思いました。
ほけきよ君は、金沢に行く。切符の指定範囲内の改札での乗り換えでは、必ず当該切符を通さなければならない。全ての切符を通す改札はどこでしょう？
— ほけきよ (@hokekiyoo) May 29, 2019
→imos法っぽい！！
となりながら出張してる。 pic.twitter.com/yKV9gkHU5x
新幹線とか使うときに、大量のきっぷが払い出されますよね？その時の改札ごとに何枚のきっぷを入れれば良いんだ！？という問題です。
ちなみに、東京の改札は賢くて適当に全部入れたらよしなにしてくれるんですが、安城はそうはいきません。区間外のきっぷを入れると改札を通してくれません。ハードモードです。
いもす法
このような始点と端点が決まっていて、数を数える問題は、いもす法というのが効率がよく、常套手段となっています。
出入り口だけカウントすれば、中身は後処理でいけるという発想です。
図にするとこんな感じ。
そのまんまこの改札きっぷ問題に使えそうです！各区間で
としておいて、累積和(はじめから足し上げていく)を取るとそのときに必要なチケット数が出ます
解いた
実装はとても簡単です。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
今後もほどほどに精進していきます！ではではっ