AtCoder Beginner Contest 183

4完だったがB問題に解くのにすごく時間がかかってしまった。

atcoder.jp

目次

B - Billiards

X軸への入射角と反射角が必ず等しくなるとき、スタートの座標(Sx,Sy)からゴールの座標(Gx,Gy)にたどり着くにはX軸のどの部分にボールがぶつかればよいか。

答えのX軸の座標をxとすると、 Sy/(x-Sx) = Gy/(Gx-x)になるので、これを式変形すると、x = (Sy*Gx + Gy*Sx) / (Gy+Sy)となるのでこれを実装すればよい。(これに気づくのにすごく時間がかかった...)

SX, SY, GX, GY = list(map(int,input().split()))
print((SY*GX + GY*SX) / (GY+SY))

同じように式変形する問題 atcoder.jp

C - Travel

N個(2<=N<=8)の都市があって、ある都市からある都市への移動時間が与えられる。 都市１から出発して全ての都市を通って、最後に都市１に戻る場合の移動時間の合計がちょうどKになるものはいくつあるか。

都市が3つの場合は
1 - 2 - 3 - 1
1 - 3 - 2 - 1
の二通りの移動の仕方がある。 都市は最大8個しかないので都市の並び方を全て列挙して試してみる。(順列全列挙)

import itertools
 
N, K = list(map(int, input().split()))
 
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))
 
ans = 0
t = list(range(N))[1:]
for p in list(itertools.permutations(t, len(t))):
    pp = [0] + list(p) + [0]
    dist = 0
    for src, dst in zip(pp[0:], pp[1:]):
        dist += arr[src][dst]
    if dist == K:
        ans += 1
print(ans)

D - Water Heater

給湯器は毎分Wリットルお湯を供給できる。 N人の人が時刻SからTまでの間(時刻Tは含まない)、お湯を毎分Pリットル使う。 全ての人にお湯を供給することは可能か。

ある時刻でもっともお湯が使われる量を求めて、それがWリットル以下であれば供給可能。 こういうときはいもす法が使える。

imoz.jp

いもす法
1 開始時刻に使用するお湯の量を足す。終了時刻に引く。
2 これをN人分あらかじめ行っておき、累積和を計算する。
3 累積和の結果がその区間で使用するお湯の量となる。

この場合最大で使用されるお湯の量は11リットルになる。

N, W = list(map(int, input().split()))
MAX = (2 * 10**5) + 1

arr = [0] * MAX
for n in range(N):
    s, t, p = list(map(int, input().split()))
    arr[s] += p
    arr[t] -= p

for i in range(1, MAX):
    arr[i] += arr[i - 1]

print(['No','Yes'][max(arr) <= W])

いもす法を使う他の問題
atcoder.jp