PAST2K
from 第二回 アルゴリズム実技検定
PAST2K
考えたこと
変更と削除を行うことで対応の取れた括弧にする問題
文字ごとに変換コストと削除コストが決まっている
N=3000
変換してから削除することにメリットはないので「何もしない、変換する、削除する」の三択
括弧をプラマイ1、削除を0とすれば「X番目までの和」をYとしてDPができそう
対応した括弧は、途中で負にならず、最後で0になる
値の範囲は0〜N
N^2なので間に合う
AC
pythondef solve(N, S, CS, DS):
INF = 9223372036854775807
table = [INF] * (N + 1) # table[N] is sentinel
table[0] = 0
for i in range(N):
new_table = [INF] * (N + 1)
if S[i] == "(":
d = 1
else:
d = -1
for j in range(N):
new_table[j] = min(
table[j - d], # no change
table[j + d] + CS[i], # change
table[j] + DS[i], # delete
)
table = new_table
return table[0]Related Pages
- →帰着する力×小さい制約の問題×nが8前後の制約×nが10~20前後の制約×n_が_30~40前後の制約×n_が_50前後の制約×n_が_300~500前後の制約×n_が_1000_前後の制約×小さな定数に注目×変数を一つ固定する×3つのものの真ん中を固定×行列の半分×xとyにわける×操作の不変量に注目×偶奇に注目×偶奇で場合わけ×操作の順番によらない×時間軸反転×元に戻せる操作×左右から累積積×等差数列の加算は差に注目×区間反転の合成はxor×grundy数×余事象を引く×k番目の数を二分探索×xorは繰り上がりのない足し算×xorは桁ごとに分割可能×45度回転×差の最小化は中央値×代表的なグラフで考察×木は二部グラフ×木の直径×最大化を二分探索で×選択肢が少ない方から貪欲×二次元座標を二部グラフにする×順序を有向グラフにする×凸関数の極値は三分探索×単調増加ならしゃくとり法×等比数列は剰余に注目×n進数は剰余に注目×括弧列は上り下り×競技プログラミングで解法を思いつくための典型的な考え方×keyence2020_d×abc152_f×agc026_c×arc060_a×joi2008ho_c×abc034d×abc138e×abc023d→
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×arc106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×Educational DP Contest×動的計画法×atcoder_library_practice_contest×atcoder_library×帰着する力×帰着訓練→
"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]