読者です 読者をやめる 読者になる 読者になる

AtCoder ABC027 D - ロボット

問題

D: ロボット - AtCoder Beginner Contest 027 | AtCoder

部分点解法

部分点解法は動的計画法を用いた解法となる。

文字列を1文字ずつ辿る。'M' の時に「右に行く場合」と「左に行く場合」の2パターンで分木していく。すると以下のような木構造となる。

dp(i, j) := i番目操作した時、座標jにいる時に最大の幸福度

なぜ、このようにおけるのか。i番目まで操作した時、座標jいるパターンが複数ある時、その後の操作はどのパターンも同じとなる。 実際に以下の例では、同じ深さで同じ座標にいるパターンが複数存在することが分る。 よって一度その状態における最大の幸福度を計算しておけば、2回目同じ状態になった時には再度計算する必要はなく、メモした値を使用する。


ソースコード(DPによる解法)

満点解法

→ を選んだ時: Mごとに (自分より右にあるプラスの数) - (自分より右にあるマイナスの数)
← を選んだ時: Mごとに (自分より右にあるマイナスの数) - (自分より右にあるプラスの数)

を求めておく。 また、操作が終わった時には座標0にいなくてはならないので、「→」を選ぶ数と「←」を選ぶ数は等しい。 よって、「→」の行を昇順でソートし、Mの数の内、前半を「←」、後半を「→」を選択することで幸福度が最大となる。

また、ソートの部分はプライオリティキューを用いることでO(logN)で挿入可能。

「→」と「←」の2つの操作した場合の幸福度の増減をPairというクラスを作成し保持させる。プライオリティキューにはこのPairを入れていくので、Comparableを付与さて、compareToメソッドをオーバーライドし、「→」の操作での増減で値が比較されるようにする。

ソースコード(満点解法)