Google APAC university test 2017 round AのC問題Jane's flower shopに挑戦する.
この問題は,いろいろ書いてあるが結局は
である.
$r$が一意に定まるように入力$C_0, C_1, C_2, \dots, C_M$は用意されているようだ.
また,出力は一般に無限小数が想定されるので,絶対(あるいは相対)誤差$10^{-9}$で出力しろとある.
入力と,それに対する正しい出力の例は
である.
例の1つ目は$f(r) = -200 \cdot (1 + r)^2 + 100 \cdot (1 + r)^{1} + 100 \cdot (1 + r)^0 = 0$を解けば良い. 一応式変形すると$f(r) = -200 \cdot (1 + r)^2 + 100 \cdot (1 + r)^{1} + 100 \cdot (1 + r)^0 = -2(1 + r)^2 + (1 + r)^{1} + (1 + r)^0 = -2(1 + 2 r + r^2) + 1 + r + 1 = - 2 r^2 - 3 r = r (- 2 r - 3)$である. よって$r = 0$のみが$-1 < r < 1$における$f(r) = 0$の解となる.
例の2つ目と3つ目は,手計算で解を求めるのはきついので,以下にグラフをプロットして直感的に捉えるまでとする.
def total_cash(M, C, r): # 上記の関数f(r)に相当する.
cash = 0
rate = 1
for i in range(M, 0, -1):
cash += C[i] * rate
rate *= 1 + r
cash -= C[0] * rate
return cash
# このコードはプロット用なので気にしなくて良い.
import numpy as np
import matplotlib.pyplot as plt
def draw_f(f, M, C, title):
R = np.linspace(-1, 1, 100)
F = f(M, C, R)
plt.title(title)
plt.xlabel('$r$')
plt.ylabel('$f(r)$')
plt.plot(R, F)
plt.plot(R, np.array([0 for i in range(len(R))]))
return
# このコードはプロット用なので気にしなくて良い.
%matplotlib inline
plt.figure(figsize=(16,4))
plt.subplot(1, 3, 1)
draw_f(total_cash, M=2, C=[200,100,100], title='Sample 1')
plt.subplot(1, 3, 2)
draw_f(total_cash, M=3, C=[10000,3000,4000,5000], title='Sample 2')
plt.subplot(1, 3, 3)
draw_f(total_cash, M=5, C=[3000,100,100,100,100,100], title='Sample 3')
plt.tight_layout()
Sampleの3つ目は非常に微妙な感じだが,$r = -0.4$くらいで$r$軸と交わっていると見て取れないこともない.
Small datasetは$M \le 2$なので,二次方程式の解の公式を使うだけでも解けそうである.
しかし,Large datasetは$M \le 100$なので,方程式を直接解く方法は使えない.
ここでも役に立ちそうなのは「2分探索」である. 方程式を直接解くのは難しいが,$r$に数値を代入して方程式を満たすか否か判定するのは簡単である.
以下に方針を示す.
この方針に従って,$f(r)$を計算する関数をtotal_cash,それを用いて2分探索する関数をsolveとして以下に定義する.
def solve(M, C):
upper_bound = 1.0
lower_bound = - 1.0
while upper_bound - lower_bound > 10 ** -10: # 上界と下界の差が10^-10以下になるまで繰り返す.
middle = (lower_bound + upper_bound) / 2
if total_cash(M, C, upper_bound) * total_cash(M, C, middle) > 0:
upper_bound = middle
else:
lower_bound = middle
return upper_bound
ここで定義した関数solveでは,前に計算した$f(r)$を再度計算しているので若干無駄があるが,細かいことは気にしないことにする.
実際にサンプルの入力を与えて,出力を確かめてみる.
solve(M = 2, C = [200, 100, 100])
5.820766091346741e-11
solve(M = 3, C = [10000, 3000, 4000, 5000])
0.08896339469356462
solve(M = 5, C = [3000, 100, 100, 100, 100, 100])
-0.40179074881598353
良さそうである.
続けて,先程の関数solveを用いて,入力のファイルを読み込み,出力のファイルを書き出す関数answerを以下に定義する.
def answer(input_file_name, output_file_name):
input_file = open(input_file_name)
output_file = open(output_file_name, 'w')
T = int(input_file.readline())
for case_number in range(1, T + 1):
M = int(input_file.readline())
C = list(map(int, input_file.readline().split()))
# mapの出力のままだとリストと同様に扱えない場合があるので,組込み関数listでリストにする.
output_file.write('Case #{0}: {1:10.9}\n'.format(case_number, solve(M, C)))
# 有効数字を指定したフォーマット出力の書き方は上記の通り{x:y.z}で
# 「メソッドformatのx番目の引数を,有効数字y桁で,そのうち小数部分はz桁」という意味になる.
input_file.close()
output_file.close()
return
Small datasetの入力ファイルをC-small-practice.in,large datasetの入力ファイルをC-large-practice.inとして以下を実行してみる.
answer('C-small-practice.in', 'C-small-practice.out')
answer('C-large-practice.in', 'C-large-practice.out')
ファイル'C-small-practice.out','C-large-practice.out'のいずれも正しく出力される.