ABC185
https://gyazo.com/b71472b5270bf5ca1c9e21467bebad27
今回でABCは3回連続全問正解となりました
https://gyazo.com/61d08bf0000ee4058a1266ff1229539d
https://gyazo.com/486e32a283d62265b907410eadf2c1ae
A
テストしないで提出したら括弧が足りなくて構文エラー、簡単だと思って手抜きしすぎ、反省
code:python
print(min(list(map(int, input().split()))))
切断場所11個をL-1の可能な切断箇所から選ぶ組み合わせ
code:python
def main():
L = int(input())
print(comb(L - 1, 12 - 1))
公式解説によれば「答えが2^63未満とは言ったが、分子がそうだとは言ってないぞ」というタイプの罠だったようだ オーバーフロー罠 Python使いなので何も気にせず解けてしまった
可能な最大スタンプサイズより小さくしてもスコアが良いことはない
最大スタンプサイズを求めてスコアを計算
最大スタンプサイズは最小隙間サイズ
入力がソートされてるとは書いてないのでソートする(手元テストでマイナスになって気づいた)
隙間サイズを求めるのに前後に番兵を入れた
座標の差が2の時、隙間のサイズは1
求めるスコアは$ \sum_i \lceil D_i / k \rceil
code:python
def main():
N, M = map(int, input().split())
AS = list(map(int, input().split()))
AS.append(0)
AS.append(N + 1)
AS.sort()
DS = []
for i in range(M + 1):
if d > 1:
DS.append(d - 1)
if not DS:
print(0)
return
k = min(DS)
ret = 0
for d in DS:
ret += (d - 1) // k + 1
print(ret)
セグメント木を使うだけ
悩んだけど片方が残り0文字だと消すしかないことから残り文字数でDPしてみたら素直にO(NM)で解けた
考えたこと
N=1000なのでO(N^3)はダメで、O(N^2logN)やO(N^2)はOK
長い方からしか取らない？
そうとも言えなさそう
残り文字数が(x, 0)になったらあとはx文字消すだけ
このルールで確定してるところを図に描いたら素直な動的計画法が見えた
https://gyazo.com/b71472b5270bf5ca1c9e21467bebad27
code:python
def solve(N, M, AS, BS):
if M > N:
N, M = M, N
AS, BS = BS, AS
table = list(range(N + 1))
for m in range(1, M + 1):
for n in range(1, N + 1):
d = 0
else:
d = 1
prev + 1,
)
table = newtable