0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

[AtCoder] ABC 174 D - Alter Altar

Posted at

さらっと読んだところ、左側に白い石を全部寄せて、右側に赤い石を寄せればよいはずです。
あとはどういう条件で2つの操作をするかです。
自分はまずひとつ目の操作、

石を2個選び (隣り合っていなくてもよい)、それらを入れ替える。

だけを考えることにしました。
左端から石の色を調べていって白い石を探します。
同様に右端から調べていって赤い石を探します。
両方見つけたら上記の入れ替え操作をします。
そうやって左右の探索インデックスが交差するまで調べて入れ替えを繰り返します。
もう片方の操作である、

石を1個選び、その石の色を変える (赤なら白に、白なら赤に)。

をどう使えばいいのかわからなかったので、とりあえずこれで提出して試してみました。
そしたらACとなってしまいました。
操作が2種類ある意味は。。。
解説を見ようとしたらないし、わからないままです。
解けたからよしとしましょう。
言語はC++(GCC 9.2.1)でAtCoderのコードテストで確認しています。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, L, R, answer = 0, white = -1, red = -1;
  string C;
  cin >> N;
  cin >> C;
  L = 0;
  R = C.size() - 1;
  while (L < R) {
    if (C[L] == 'W') white = L;
    if (C[R] == 'R') red = R;
    if (white >= 0) {
      if (red >= 0) {
        swap(C[white], C[red]);
        white = -1;
        red = -1;
        answer++;
      } else {
        R--;
      }
    } else {
      L++;
      if (red == -1) R--;
    }
  }
  cout << answer << endl;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?