ABC185
今回でABCは3回連続全問正解となりました
A
テストしないで提出したら括弧が足りなくて構文エラー、簡単だと思って手抜きしすぎ、反省
pythonprint(min(list(map(int, input().split()))))切断場所11個をL-1の可能な切断箇所から選ぶ組み合わせ
pythondef main():
L = int(input())
print(comb(L - 1, 12 - 1))公式解説によれば「答えが2^63未満とは言ったが、分子がそうだとは言ってないぞ」というタイプの罠だったようだ オーバーフロー罠
Python使いなので何も気にせず解けてしまった
可能な最大スタンプサイズより小さくしてもスコアが良いことはない
最大スタンプサイズを求めてスコアを計算
最大スタンプサイズは最小隙間サイズ
入力がソートされてるとは書いてないのでソートする(手元テストでマイナスになって気づいた)
隙間サイズを求めるのに前後に番兵を入れた
座標の差が2の時、隙間のサイズは1
求めるスコアは\sum_i \lceil D_i / k \rceil
pythondef 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):
d = AS[i + 1] - AS[i]
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文字消すだけ
このルールで確定してるところを図に描いたら素直な動的計画法が見えた
pythondef 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):
newtable = [0] * (N + 1)
prev = newtable[0] = m
for n in range(1, N + 1):
if AS[-n] == BS[-m]:
d = 0
else:
d = 1
prev = newtable[n] = min(
prev + 1,
table[n - 1] + d,
table[n] + 1
)
table = newtable
return table[-1]
Twitterを見てるとLongest Common Substringの話をしてる人が多い
関連: 編集距離
Related Pages
- →数え上げ×degwer×状態をまとめる×dpは全探索の高速化×arc059f×codefestival_2016_final_f×aoj2439×探索順の変更×大きい順に並べる×aoj2333×順列は挿入dp×bit_dp×区間は終点でソート×条件の言い換え×操作は多いが産物は少ない×agc013d×線形和への分解×演算順序の変更×ビット演算を桁ごとに分解×部分群×操作が可逆で全域→部分群×ラグランジュの定理×再帰的定義→dp×arc037d×桁dp×aoj0570×累積和×フェニック木×高速フーリエ変換×ntt×高速ゼータ変換×and_と_add_の畳み込み×二分累乗×agc013e×行列木定理×全域木の個数×lgv公式×非交叉経路の個数×小さい確率を無視する×二項係数の公式×経路数×45度回転×xとyにわける×カタラン数×包除原理×agc005d×約数系包除×arc064f→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]