AtCoder Beginner Contest 183 参戦記

ABC183A - ReLU

1分で突破. 書くだけ.

x = int(input())

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

追記: 普段は max(x, 0) って書いてるなって思った.

x = int(input())

print(max(x, 0))

ABC183B - Billiards

5分半で突破. こういう数学的なのがつらい…….

Sx, Sy, Gx, Gy = map(int, input().split())

print(Sx + (Gx - Sx) * Sy / (Sy + Gy))

ABC183C - Travel

5分半で突破. N≤8 なので全部パターンやってみれば OK. といいつつ、itertools.permutations が無いと解ける気がしない…….

from itertools import permutations

N, K = map(int, input().split())
T = [list(map(int, input().split())) for _ in range(N)]

result = 0
for p in permutations(range(1, N)):
    i = 0
    t = 0
    for x in p:
        t += T[i][x]
        i = x
    t += T[i][0]
    if t == K:
        result += 1
print(result)

ABC183D - Water Heater

5分で突破. imos 法一発.

from itertools import accumulate

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

t = [0] * (2 * 10 ** 5 + 1)

for _ in range(N):
    S, T, P = map(int, input().split())
    t[S] += P
    t[T] -= P

if all(x <= W for x in accumulate(t)):
    print('Yes')
else:
    print('No')

追記: まあ、imos 法を使わなくても簡単に解けるよね.

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

t = {}
for _ in range(N):
    S, T, P = map(int, input().split())
    t.setdefault(S, 0)
    t[S] += P
    t.setdefault(T, 0)
    t[T] -= P

c = 0
for k in sorted(t):
    c += t[k]
    if c <= W:
        continue
    print('No')
    break
else:
    print('Yes')

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

a = []
for _ in range(N):
    S, T, P = map(int, input().split())
    a.append((S, P))
    a.append((T, -P))

a.sort()
b = []
prev = -1
c = 0
for t, p in a:
    if prev != t:
        b.append(c)
    prev = t
    c += p
b.append(c)

if max(b) <= W:
    print('Yes')
else:
    print('No')

ABC183E - Queen on Grid

突破できず. 配列の添字の式がぱっと分からなくて仮に入れておいたのを直し漏れてあとちょっとのところで AC を漏らした. 仮に入れずにコンパイルエラーになるようにしておけばよかった、失敗.

結果を書き込む2次元配列だけで計算できるかと考えてみたが、ナイーブにやると O(HW(H+W)) になってしまうから駄目だし、SegmentTree を使って緩和しようにも一番近い石のある位置が O(1) で分からないと計算量は減らないしということで、結局左、上、左上方向のアキュムレータが一つづつ必要だという結論になった. 後はラスタスキャンで結果配列にそこへの移動する方法の通り数を埋めていけば良い.

よくよく考えると、結果配列は要らなかった. 以下、PyPy で通るコード.

m = 1000000007

H, W = map(int, input().split())
S = [input() for _ in range(H)]

au = [0] * W             # 上方向のアキュムレータ
aul = [0] * (H + W - 1)  # 左上方向のアキュムレータ
for h in range(H):
    al = 0               # 左方向のアキュムレータ
    for w in range(W):
        n = h - w + (W - 1)
        if h == 0 and w == 0:
            al = 1
            au[w] = 1
            aul[n] = 1
        elif S[h][w] == '#':
            al = 0
            au[w] = 0
            aul[n] = 0
        else:
            t = al + au[w] + aul[n]
            al += t
            al %= m
            au[w] += t
            au[w] %= m
            aul[n] += t
            aul[n] %= m
print(t % m)

ABC183F - Confluence

突破できず. 合流処理は Union Find だよなあと一目で思うが、クラスごとの人数の集計は素直にハッシュテーブルでやっても TLE しないんだなと.

from sys import setrecursionlimit, stdin


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


def merge(a, b):
    if len(a) < len(b):
        a, b = b, a
    for k in b:
        if k in a:
            a[k] += b[k]
        else:
            a[k] = b[k]
    return a


setrecursionlimit(10 ** 6)
readline = stdin.readline

N, Q = map(int, readline().split())
C = list(map(lambda x: int(x) - 1, readline().split()))

parent = [-1] * N
breakdown = [{C[i]: 1} for i in range(N)]
result = []
for _ in range(Q):
    Query = list(map(int, readline().split()))
    if Query[0] == 1:
        a, b = Query[1] - 1, Query[2] - 1
        i = find(parent, a)
        j = find(parent, b)
        if i == j:
            continue
        unite(parent, a, b)
        breakdown[find(parent, a)] = merge(breakdown[i], breakdown[j])
    elif Query[0] == 2:
        x, y = Query[1] - 1, Query[2] - 1
        b = breakdown[find(parent, x)]
        if y in b:
            result.append(b[y])
        else:
            result.append(0)
print(*result, sep='\n')