新人女子プログラマの書いたコードを直すだけの簡単なお仕事です! ←やってみた(Python)〜Part3〜
画像の出典: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
相変わらず入力値の受け取りが汚いが、目を瞑る。
めんどいので動作確認用の入力値もそのまま。
結果
画像の出典:paiza
https://paiza.jp/poh/ec-campaign
オールクリア!
画像の出典:paiza
https://paiza.jp/poh/ec-campaign
kaeroukaさん、凄いコードですねっ!!私にはこんな効率のいいコード書けませんっ!
かわいい。
彼女にはちゃんと仕様を読むプログラマーになっていただきたいところです(しみじみ
実行速度だが、Case3で5秒弱かかっている。
最速の人が0.09秒とか鬼畜の所業。
ここまでのチューニングはわりと普通なやり方だと思うんだけど、これ以降はどうすんのかねぇ。
いい結果が出たらまた記事にしよう。
過去の記事
新人女子プログラマの書いたコードを直すだけの簡単なお仕事です! ←やってみた(Python) - Tips
新人女子プログラマの書いたコードを直すだけの簡単なお仕事です! ←やってみた(Python)〜Part2〜 - Tips