ABC140-D - Face Produces Unhappiness
今日はこの問題を取り上げます。非常に考察が楽しかったです。
リンク
エンジニアとして生きていくにはこの問題のように物事をどう簡単なものに帰着させて行くかという思考も実装力に加えて大事な気もするので、こういう能力も伸ばして行きたいと思います。
考察
LとRの区切りの個数と幸福な人の数の関係が相関を持っていることに気づけばあとは簡単。サンプルを見ると
LLLLLRRRRR
はLRの区切りが1ですね。ここでこの状態の幸福な人の数は(10-1)-1=8となります。
全員が同じ方向を向いている時答えはn-1なのでそこから区切りの数を引いたものが答えになりますね。つまり元の状態から区切りを最小化すれば答えは最大になるとわかります。ではK回の試行でどこまで区切りを減らせるか考えると、例えば
LRRRL
のとき区切りは2です。ここでRを反転すればLLLLLになり区切りは0になります。つまり1回の操作で区切りを2つ減らせます。区切りの数は0未満にならないことに注意すると以下のような簡潔なコードで解くことができます。
#include <bits/stdc++.h> using namespace std; int main(){ int n,k; string s; cin>>n>>k>>s; int cnt=0; //区切りをカウント for (int i = 0; i < n-1; i++) { if(s[i]!=s[i+1]) cnt++; } cout<<n-1-max(0,(cnt-2*k))<<endl; return 0; }