Tips

IT技術系Tips

新人女子プログラマの書いたコードを直すだけの簡単なお仕事です! ←やってみた(Python)〜Part3〜

f:id:kaerouka:20131213081901p:plain
画像の出典:paiza
https://paiza.jp/poh/ec-campaign

前回の続き

100点になった。

二分探索(bisect)使った。

ソース

# -*- coding:utf-8 -*-
import sys, bisect


#prices = ["4 3","8000","4000","9000","6000","3000","14000","10000"] #=>0, 14000, 10000
#prices = ["5 2", "4000", "3000", "1000", "2000", "5000", "10000", "3000"] #=>9000, 3000
#prices = ["4 1","1000","3000","7000","8000","10000"] #=>10000
#prices = ["10 2", "4311", "89", "2836", "9904760", "12435", "8437", "345", "4356", "43287", "9648", "8999", "43222"] #=>8782, 22083
prices = [x.rstrip() for x in sys.stdin]

N, D = [int(x) for x in prices[0].split(' ')]
m_s = [int(x) for x in prices[N+1:]]
prices = [int(x) for x in prices[1: D * -1]]
prices.sort()

for n in xrange(D):
    result = 0
    m = m_s[n]
    current_prices = [x for x in prices if x + prices[0] <= m]
    current_len = len(current_prices)
    for i, x in enumerate(current_prices[:-1]):
        # 二分探索
        j = bisect.bisect_left(current_prices, m-x, i+1)

        # j < current_len → m-xがmax(current_prices)を超えると、範囲外のindexが返されるため、その対処
        # current_pricesはソート済みなので、current_prices[i]はcurrent_prices[i-1]より必ず大きいため
        # 前回までの値(result値)との比較は必要ない。
        if j < current_len and current_prices[i] + current_prices[j] == m:
            result = m
            break
        # 一つ上のif文の条件を満たさず、j == i+1を満たす場合、current_prices[i] + current_prices[j] <= mを満たさなかったと判断
        elif j == i+1:
            continue
        else:
            # 1つ前。
            j -= 1
            total = current_prices[i] + current_prices[j]
            if result < total <= m:
                result = total
                if result == m:
                    break

    print result

相変わらず入力値の受け取りが汚いが、目を瞑る。
めんどいので動作確認用の入力値もそのまま。

結果

f:id:kaerouka:20131216015643p:plain
画像の出典:paiza
https://paiza.jp/poh/ec-campaign

オールクリア!

f:id:kaerouka:20131216015754p:plain
画像の出典:paiza
https://paiza.jp/poh/ec-campaign

kaeroukaさん、凄いコードですねっ!!私にはこんな効率のいいコード書けませんっ!

かわいい。
彼女にはちゃんと仕様を読むプログラマーになっていただきたいところです(しみじみ



実行速度だが、Case3で5秒弱かかっている。
最速の人が0.09秒とか鬼畜の所業。

ここまでのチューニングはわりと普通なやり方だと思うんだけど、これ以降はどうすんのかねぇ。
いい結果が出たらまた記事にしよう。


過去の記事
新人女子プログラマの書いたコードを直すだけの簡単なお仕事です! ←やってみた(Python) - Tips
新人女子プログラマの書いたコードを直すだけの簡単なお仕事です! ←やってみた(Python)〜Part2〜 - Tips