AGC048
https://gyazo.com/ce6dff57ab5fe086ab68116bb814689f
Aを飛ばしてBをDPでサンプルACしたがそれではジャッジはTLE
難易度的には僕はAをちゃんと解くべきではあった
https://gyazo.com/6da41ff4d9ba41609484bc422229e4b7
考えたこと
ピンとこなかったので飛ばしてBへ
公式解説
どういう時にどういう値になるが具体的な値で考えるべきだった
Sがa以外の文字を含んでいる場合、それを先頭に持ってくることで条件を満たせる
a以外の最初の文字がk番目であれば、k-1回で先頭に持ってこれる
その文字がtより大きければk-2回で良い
文字列打ち切りの影響とか3文字目のcの影響とかが気になる
https://gyazo.com/f420b862d8e8992897072307e294b328
考えたこと
動的計画法DPで求められる
https://gyazo.com/115398bbb2f4da118bbdd41f6f46434d
これでサンプルケースには正解するが、提出するとTLE
辞書でメモ化再帰してたので配列に書き直す→RE
ここで気づいたのだが、Nが10^5なのでその上の範囲って10^10ぐらいある
頑張って一桁削ってもMemoryErrorになる
「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