arimattiの競プロ精進日記

競プロ問題の解法を記録していきます

ABC174 D - Alter Altar を解いてみた

問題リンク

atcoder.jp

問題概要

左から右に  N 個の石が並んでいる。左から i 番目の石の色は  c_ i で与えられ、 c_ i が 'R' のとき赤、'W' のとき白である。
以下の二種の操作を任意の順に何度でも行うことができる。

  • 石を 2 個選び (隣り合っていなくてもよい)、それらを入れ替える。
  • 石を 1 個選び、その石の色を変える (赤なら白に、白なら赤に)。

赤い石の左隣に置かれた白い石がない状態にするために必要な最小の操作回数を求めよ。

制約

 2 \leq K \leq 2 \times 10 ^ 5

ポイント

  • 満たすべき最終状態は、ある位置を境に左側には赤石が並び、右側には白石が並ぶ。
  • 石の入れ替えは石の色変えの上位互換(な気がする)。
  • 左から赤の個数分をみて、その中で白の個数が入れ替えすべき回数。

f:id:arimatti:20210609125827p:plain

感想

直感的にこうだろうって感じです。入れ替えだけで最小回数にできることをちゃんと説明しようとすると難しそうです。

コード

#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;

int main() {
  int n;
  string s;
  cin >> n >> s;
  int cnt_R = 0;
  rep(i, n) if (s[i] == 'R') cnt_R++;
  int ans = 0;
  rep(i, cnt_R) if (s[i] == 'W') ans++;
  cout << ans << endl;
  return 0;
}