AtCoder Grand Contest 048 - AtCoder
- Aを飛ばしてBをDPでサンプルACしたがそれではジャッジはTLE
- 難易度的には僕はAをちゃんと解くべきではあった
- 考えたこと
- ピンとこなかったので飛ばしてBへ
- 公式解説
- どういう時にどういう値になるが具体的な値で考えるべきだった
- Sがa以外の文字を含んでいる場合、それを先頭に持ってくることで条件を満たせる
- a以外の最初の文字がk番目であれば、k-1回で先頭に持ってこれる
- その文字がtより大きければk-2回で良い
- 文字列打ち切りの影響とか3文字目のcの影響とかが気になる
- 未AC
- 考えたこと
- 動的計画法DPで求められる
- これでサンプルケースには正解するが、提出するとTLE
- 辞書でメモ化再帰してたので配列に書き直す→RE
- ここで気づいたのだが、Nが10^5なのでその上の範囲って10^10ぐらいある
- 頑張って一桁削ってもMemoryErrorになる
- なおAtCoderのPythonでMemoryErrorを出すとREになる
- 「DPでやっても間に合わない」と気づくべきだった
- 公式解説
- 開き括弧と閉じ括弧の偶奇が異なる
- これ今回に限らず対応した括弧列の時に成り立つ
- 逆に偶奇の個数が等しければ良い括弧列であることも示せる
- どこがAの括弧かさえ決まればスコアは決まるので、全ての括弧列について最大スコアを求める必要はない
- これをDPで求めてしまったから僕はTLE になったのだ
- これでもまだ多すぎる
- すべてAにして、一部をBにする
- B-Aの大きい方から選べば良い
- 偶奇の個数が一致することから、それぞれソートして上位k個を取れば良い。kは0以上N/2以下を動く
- ソートが前処理の1回だけなのでO(N log N)
- 関連話題
-
B: O(n)
-
長さ N の数列 A 長さ M の数列 B
max[k]{A と B から k 個ずつ選んだ和}これを O(N + M) で解きます -
A を一旦全て選んでしまうと、A から N-k 個戻して B から k 個選んで最大化
-
→ -A と B を並べて top N
-
-
- 未AC
- 開き括弧と閉じ括弧の偶奇が異なる
