AtCoder ABC185 個人的メモ

公開:2020/12/13
更新:2020/12/14
4 min読了の目安(約3700字TECH技術記事

所感

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

A - ABC Preparation

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

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

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

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

B - Smartphone Addiction

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

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

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}を求めればおk

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

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])