Zenn
📚

AtCoder ABC185 個人的メモ

2020/12/13に公開
Python
競技プログラミング
AtCoder
tech

所感

abcd 26分 4完
緑復帰
やったぜ
今回は結構落ち着いて考察できた気もする
e以外はwaしてないし
abc185score

A - ABC Preparation

4つの内の最小値を出力すればおｋ

別にアンパックする必要なかった

a, b, c, d = map(int, input().split())

print(min(a, b, c, d))

B - Smartphone Addiction

小数見て「うっ」って思ったがよく考えたら別に関係なかった

問題文では，バッテリーが減るのは時刻n+0.5毎だが，n+1毎でも特に問題ないのでその様に考える
後は，外出の途中でバッテリーが0になること，バッテリーの充電には上限があること，最後のカフェから帰宅するまででもバッテリーを消耗すること，辺りを考慮してシミュレーションすればおｋ

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

vattery = N
now = 0
for i in range(M):
    arrived, leaved = move[i]
    vattery -= arrived - now
    if vattery <= 0:
        break
    vattery += leaved - arrived
    vattery = min(vattery, N)
    now = leaved

vattery -= T - move[-1][1]

if vattery > 0:
    print("Yes")
else:
    print("No")

C - Duodecim Ferra

Nを12個に分割する=N個の球の間に仕切りを11個入れる=N-1個の候補から11個選ぶ
なので{}_{N-1} C_{11}を求めればおｋ

組み合わせの計算は自作のライブラリ
この辺りを参考した

def combination(N: int, R: int, MOD: int = 1 << 65):
    if N - R < R:
        R = N - R
    if R == 0:
        return 1
    if R == 1:
        return N
    numerator = [N - R + r for r in range(1, R + 1)]  # 分子を昇順で列挙
    denominator = [r for r in range(1, R + 1)]  # 分母を昇順で列挙
    # 分母分子を約分
    for p in range(2, R + 1):
        pivot = denominator[p - 1]
        if pivot <= 1:
            continue
        offset = (N - R) % p
        for r in range(p - 1, R, p):
            numerator[r - offset] /= pivot
            denominator[r] /= pivot
    result = 1
    for n in numerator:
        if n <= 1:
            continue
        result *= int(n)
        result %= MOD
    return result


L = int(input())

print(combination(L - 1, 11))

D - Stamp

白が連続しているマスの長さを長さが短いものからB0，B1，・・・とする
スタンプの大きさは1度決めたら変えられない
操作回数を最小にするには，スタンプは大きい程良さそう
なので，最も短い白が連続するマスの長さB_0がスタンプの大きさになる
これ以上の大きさだとB_0を塗り替えられない
連続するマスの長さがスタンプの大きさで割り切れなくても，サンプル2のようにすることで白マスを塗りつぶせる
よって，B_0がスタンプの大きさとなる

後は，全てのBを求めて，それらを全てB_0で切り上げの割り算をして総和を取れば良い

Bを求める際，両端のマスに注意

N, M = map(int, input().split())
A = [0] + list(map(int, input().split())) + [N + 1]
M += 2

A.sort()
stamp_len = 10 ** 18
between = []
for i in range(1, M):
    res = A[i] - A[i - 1] - 1
    if res <= 0:
        continue
    stamp_len = min(stamp_len, res)
    between.append(res)

ans = 0
for B in between:
    ans += -(-B // stamp_len)

print(ans)

E - Sequence Matching

dp
dpなのは分かったけど，考察を詰め切れなかった
LCS

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
INF = 10 ** 18

N += 1
M += 1
# dp[i][j]はAがi文字目まで，Bがj文字目までの時の答え
dp = [[INF] * M for _ in range(N)]
dp[0][0] = 0
for i in range(N):
    for j in range(M):
        if i > 0:
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
        if j > 0:
            dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)
        if i > 0 and j > 0:
            if A[i - 1] != B[j - 1]:
                res = 1
            else:
                res = 0
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + res)

print(dp[-1][-1])

Discussion