ABC185

1 min read読了の目安(約1600字

リンク

https://atcoder.jp/contests/abc185/tasks

A問題

print(min(map(int, input().split())))

ワンライナーでかけた。

B問題

n, m, t = map(int, input().split())
now = 0
strage = n
frag = True
for _ in range(m):
    a, b = map(int, input().split())
    strage -= a - now
    if(strage <= 0):
        frag = False
    strage = min(strage + b - a, n)
    now = b
strage -= t - now
if(strage <= 0):
    frag = False
if(frag):
    print("Yes")
else:
    print("No")

M \leq 1000なのでとりあえずO(M)で考えられる。B問題は割と愚直に考えていい問題が多い。各カフェによったときとラストで0以下になってないかチェック

C問題

from scipy.special import comb
print(int(comb(int(input())-1, 11, exact=True)))

仕切りがあるタイプの組み合わせ問題なので{}_{L-12} \mathrm{H} _{11}で良い。scipy.special.combはexactがないと大きな数値を計算する時(64bitオーバー?)オーバーフローしてしまうことに注意

D問題

n, m = map(int, input().split())
a = list(map(int, input().split()))
if(m == 0):
    print(1)
else:
    a.sort()
    a.insert(0, 0)
    dis = []
    ans = 0
    for i in range(m):
        dis.append(a[i+1]-a[i] - 1)
    dis.append(n - a[m])
    d = [x for x in dis if x != 0]
    if(len(d) == 0):
        print(0)
    else:
        ex = min(d)
        for i in range(m+1):
            ans += -(-1*dis[i] // ex)
        print(ans)

はじめに与えられたリストをソートし、最初に0, 最後にn+1を代入する。そうすることによってm+1個の「間隔」を導出できる。間隔の最小値がハンコの大きさであり、それが0ならばすべて赤マスであると同値。そうでなかったら各間隔(m+1個)に対してその間隔を最小値で割った商を繰り上げたものの総和が答えとなる。赤マスがなかったば場合は1が答え。

E問題(わからなかった)

参考リンク

https://youtu.be/a3J9AMZjCqw
https://note.com/momomo0214/n/ne00c1582703d#cVm7w

考え方

xの操作...数列の先頭から1つずつ消していって何回消えたかをカウント
yの操作...a, bの各先頭の文字が一致していたらカウントせずに消す、それ以外は1つカウントして2つけす(大抵の場合、yを増やしたほうが得$

文字列操作系DP下手くそすぎるので知識面含めて勉強が必要だなあと強く思いました