AtCoderBeginnerContest183復習＆まとめ

AtCoder ABC183

2020-11-15(日)に行われたAtCoderBeginnerContest183の問題をA問題から順に考察も踏まえてまとめたものとなります．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説

A問題　ReLU

問題文
ReLU関数は以下のように定義されます。

整数$x$が与えられるので$ReLU(x)$を求めてください。

活性化関数で馴染みのReLU関数．

abc183a.py

x = int(input())
if x >= 0:
    print(x)
else:
    print(0)

B問題　Billiards

問題文
高橋君は$2$次元平面上でビリヤードをしています。$x$軸は壁になっており、球をぶつけると入射角と反射角が等しくなるように球が跳ね返されます。
いま高橋君の球が$(S_x,S_y)$にあります。ある座標を狙って球を撞くと、球はその座標へ向かって直線的に転がっていきます。
$x$軸で球をちょうど$1$回反射させたのち、$(G_x,G_y)$を通過させるためには、$x$軸のどこを狙えば良いでしょうか？

制約が$0 < S_y, G_y \leq 10^6$だったので，解説同様に$G_y$を負にして，直線の式と$x$軸の交点として解きました．

$x = S_x - S_y × (G_x - S_x) ÷ (G_y - S_y)$

abc183b.py

s_x, s_y, g_x, g_y = map(int, input().split())
g_y = -g_y
print(s_x - s_y * (g_x - s_x) / (g_y - s_y))

C問題　Travel

問題文
$N$個の都市があります。都市$i$から都市$j$へ移動するには$T_{i,j}$の時間がかかります。
都市$1$を出発し、全ての都市をちょうど$1$度ずつ訪問してから都市$1$に戻るような経路のうち、移動時間の合計がちょうど$K$になるようなものはいくつありますか？

制約が$2\leq N \leq 8$と小さいので，全探索しても実行時間制限内に解くことができましたが，最初問題見たときには，$1\to 2\to 3\to 4\to 1$の経路と$1\to 4\to 3\to 2\to 1$の経路は，$T_{i,j}=T_{j,i}$の制約から移動時間の合計が一緒になるから，計算量減らせるとか，再帰関数とか使ったら，計算量減らせるかもとか考えていたので，けっこう解き始めるのに時間とられてしまいました．

abc183c.py

import itertools
import numpy as np
n, k = map(int, input().split())
matrix = np.zeros((n, n), dtype=int) 
for i in range(n):
    x_list = list(map(int, input().split()))
    for j in range(n):
        matrix[i, j] = x_list[j]
no_list = range(1, n)
count = 0
for temp_list in itertools.permutations(no_list):
    no = 0
    total = 0
    for next_no in temp_list:
        total += matrix[no, next_no]
        no = next_no
    total += matrix[no, 0]
    if total == k:
        count += 1
print(count)

D問題　Water Heater

問題文
給湯器が$1$つあり、毎分$W$リットルのお湯を供給することができます。
$N$人の人がいます。$i$番目の人は時刻$S_i$から$T_i$までの間 (時刻$T_i$ちょうどを除く)、この湯沸かし器で沸かしたお湯を毎分$P_i$リットル使おうと計画しています。お湯はすぐ冷めてしまうので、溜めておくことはできません。
すべての人に計画通りにお湯を供給することはできますか？

なぜかコンテスト中はdictで解いていますが，listでも同じように解けます．
そもそも，増やすと減らすで別々に管理する必要もないので，無駄が多く反省．

abc183d.py

n, w = map(int, input().split())
start_dict = {}
end_dict = {}
for i in range(n):
    s, t, p = map(int, input().split())
    if s in start_dict:
        start_dict[s] += p
    else:
        start_dict[s] = p
    if t in end_dict:
        end_dict[t] += p
    else:
        end_dict[t] = p
now = 0
flag = 1
for i in range(2 * 100000):
    if i in start_dict:
        now += start_dict[i]
    if i in end_dict:
        now -= end_dict[i]
    if now > w:
        flag = 0
        break
if flag == 1:
    print("Yes")
else:
    print("No")

解説を参考に手直ししたコード．

abc183d.py

n, w = map(int, input().split())
a_list = [0] * 200001
for i in range(n):
    s, t, p = map(int, input().split())
    a_list[s] += p
    a_list[t] -= p
for i in range(1, 200001):
    a_list[i] += a_list[i - 1]
if max(a_list) > w:
    print("No")
else:
    print("Yes")

E問題は，'TLE'から抜け出せず終わってしまいました．
時間があるときに追記できたらと思います．

最後まで読んでいただきありがとうございました．