Irreversible operation -AtCoder AGC029 A-

問題概要

一列にオセロの石が並んでいます。これに対し、次の操作をします。

• 「黒 白」と並んでいるものを裏返し、「白 黒」にする

この操作は最大何回できますか
問題リンク: A - Irreversible operation

解説

「黒 白」と並んでいるものを裏返して「白 黒」にするのは、黒と白を入れ替えて黒を一つ右に動かすことと変わりません。
この操作は黒が全部右に寄り、白が全部左に寄るまで可能です（そうなっていない場合、「黒 白」と鳴っている部分が必ず存在するので）。
したがって、各'B'につき、右にいくつ動かせばいいかを数えればそれが答えとなります。また、各'W'につき左にいくつ動かせばいいかの和を答えても良いです。今は後者でいきます。

以下詳細です

• 答えをansとします。
• 'W'に出くわしたら、その左にあったBの数をansに加算します。
• printf("%ld\n", ans);

僕はBの移動距離をこのように数えました。
文字列の長さをN, その中に含まれる'B'の数をcntとしたとき、s[i]がk番目の'B'のなら、この'B’が移動する距離はN - (cnt - k) + iです。例を図に描いて数えると納得できると思います。

▶ソースコードを開く

long n;
std::string s;

int main(){
	std::cin >> s;
	n = s.length();
	long cnt = 0;
	for(int i = 0; i < n; i++){
		if(s[i] == 'B'){
			cnt++;
		}
	}
	long ans = 0;
	int k = 0;
	for(int i = 0; i < n; i++){
		if(s[i] == 'B'){
			ans += n-(cnt-k) - i;
			k++;
		}
	}
	printf("%ld\n", ans);
	return 0;
}

僕の迷走/反省

AGC029 A: 「黒を1つ右に動かす」のことをやたら複雑に書いて惑わしてきます、こういう問題はジャンル「国語」と呼びたい。

— えびま (@evima0) 2018年12月15日

初っ端から「僕の」ではない感想が入りましたが、僕はジャンル「国語」ができなかったので手元に入出力例の図を描いてみてはじめて「黒を右に動かすだけか」と気づきました。僕は頭の中で考察するのが苦手なので、いつも図にするようにしています。
それと、スッキリした実装ができなかったのがて痛かったです。これで数分は差がつきそうです。

黒の移動する距離の式には様々な考え方があると思います。A問題を1分30秒とかでACしてる人のソースコードはすんごいスマートです。
こういう「いくつ移動するか」とか「間にいくつあるか」とかは割と数をこなすと慣れる面もあると思います。僕は最近精進をしていないので図を描かないとわかりませんでした...