競技プログラミング 日記 python

つよつよエンジニアもすなる競技プログラミングといふものをよわよわエンジニアもしてみむとてするなり。

AtCoder Beginner Contest 183

• A - ReLU

入力が負の値なら0を、正の値ならそのあたりを返す関数を実装する。

N = int(input())

def ReLU(x):
   if x > 0:
       return x
   else:
       return 0
       
print(ReLU(N))

• B - Billiards

x軸に跳ね返してビリヤードを行う。受験でよくある問題なので懐かしい。目的の場所をx軸対象に移動させた地点にめがけて弾を打つ。その際のx軸との交点が答えとなる。
相似を考えて内分点を計算すると良い感じな気がした

sx, sy, gx, gy = map(int, input().split())

print(float((gy * sx + sy * gx) / (sy + gy)))

• C - Travel

N個の都市があり、すべての都市に一度ずつ訪れる場合時間がちょうどKになる経路は何個あるか

Nがたかだか8なので、経路の組み合わせは8!通り程度。全探索で問題なさそう。

組み合わせをすべて書き出すのは、pythonなら itertools を使うと簡単に書ける

0 1 10 100
1 0 20 200
10 20 0 300
100 200 300 0

のような行列をinputで受け取るのは、各列を配列に変換したものを行分回せばいいので

code.py

N, K = map(int, input().split())

matrix = [input().split() for _ in range(N)]
print(*matrix, sep='\n')

output.py

['0', '1', '10', '100']
['1', '0', '20', '200']
['10', '20', '0', '300']
['100', '200', '300', '0']

回答はこんな感じ。もっとうまく書ける気がする

import itertools

N, K = map(int, input().split())

matrix = [list(map(int, input().split())) for _ in range(N)]
ans =0
# 1からスタートして1に変えるので、1を外した順列組み合わせを求めたのち、都市1を挿入する（index は 0）
for v in itertools.permutations(range(1, N)):
    total_time = 0
    keiro = list(v)
    keiro.append(0)
    keiro.insert(0, 0)
    for i in range(len(keiro) -1):
        total_time += matrix[keiro[i]][keiro[i+1]]
    if total_time == K:
        ans += 1
print(ans)

• D - Water Heater

時間の長さ分の配列を用意、人に対してループしながら利用時間帯に利用時間を足していく。Wを超える時間があればアウト。

と思って実装したがTLE

max_time = 2 * 10 ** 5
t = [0 for _ in range(max_time)]

n, w = map(int, input().split())
ans = 'Yes'
for i in range(n):
    start, end, usage = map(int, input().split())
    for j in range(start, end): #endは含めないのでこれでOK
        t[j] += usage
        if t[j] > w:
            ans = 'No'
            break
print(ans)

制約を見落としていた…NもTも2 * 10 ** 5 オーダーだった

判定する必要があるのは、スタートとエンドのタイミングのみなので、それぞれの人に対してそのタイミングでの要素を見ればよさそう、という所までは行けたがその後が思いつかず、、

解説を見ると「いもす法」というものがあるらしい

これを使うと時間内に解くことができた！

max_time = 2 * 10 ** 5 + 1
t = [0 for _ in range(max_time)]

n, w = map(int, input().split())
ans = 'Yes'
for i in range(n):
    start, end, usage = map(int, input().split())
    # いもす法を使う。入出のタイミングを記録
    t[start] += usage
    t[end] -= usage

for i in range(1, len(t)):
    t[i] += t[i-1]

if max(t) > w:
    print('No')
else:
    print(ans)