AtCoder ABC027 D - ロボット
問題
D: ロボット - AtCoder Beginner Contest 027 | AtCoder
部分点解法
部分点解法は動的計画法を用いた解法となる。
文字列を１文字ずつ辿る。'M' の時に「右に行く場合」と「左に行く場合」の２パターンで分木していく。すると以下のような木構造となる。
dp(i, j) := i番目操作した時、座標jにいる時に最大の幸福度
なぜ、このようにおけるのか。i番目まで操作した時、座標jいるパターンが複数ある時、その後の操作はどのパターンも同じとなる。 実際に以下の例では、同じ深さで同じ座標にいるパターンが複数存在することが分る。 よって一度その状態における最大の幸福度を計算しておけば、２回目同じ状態になった時には再度計算する必要はなく、メモした値を使用する。
ソースコード(DPによる解法)
満点解法
→ を選んだ時: Mごとに (自分より右にあるプラスの数) - (自分より右にあるマイナスの数)
← を選んだ時: Mごとに (自分より右にあるマイナスの数) - (自分より右にあるプラスの数)
を求めておく。 また、操作が終わった時には座標0にいなくてはならないので、「→」を選ぶ数と「←」を選ぶ数は等しい。 よって、「→」の行を昇順でソートし、Mの数の内、前半を「←」、後半を「→」を選択することで幸福度が最大となる。
また、ソートの部分はプライオリティキューを用いることでO(logN)で挿入可能。
「→」と「←」の２つの操作した場合の幸福度の増減をPairというクラスを作成し保持させる。プライオリティキューにはこのPairを入れていくので、Comparableを付与さて、compareToメソッドをオーバーライドし、「→」の操作での増減で値が比較されるようにする。
