ykmakuのブログ

競技プログラミングをがんばるブログ

AtCoder Regular Contest 069 D - Menagerie

  • 問題

D - Menagerie

  • 解法

最初の2人の動物の種類が決まれば、3番目以降の動物の種類は順番に決まっていく、ということに気がつけば後は実装するだけ。
最初の2人の動物の種類の組合せは4通りなので、全部試してそれぞれ条件に矛盾しないかどうかを調べる。
ここでいう条件とは、動物の種類を決めていったときに1番目の動物とn+1番目の動物が同じであることと、1番目の動物の両隣が文字列と矛盾しないかどうかである。

  • 感想

最初は

ans[0] = true,ans[1] = true;
 
	for(int i = 1; i < n; i++){
		if(s[i] == 'o'){
			if(ans[i]) ans[i+1] = ans[i-1];
			else ans[i+1] = !ans[i-1];
		}else{
			if(ans[i]) ans[i+1] = !ans[i-1];
			else ans[i+1] = ans[i-1];
		}
	}
if(check()){
		for(int i = 0; i < n; i++){
			if(ans[i]) cout << 'S';
			else cout << "W";
		}printf("\n");
		return 0;
	}

を4回コピペしていました。
こういうときにスッとbitの形のループ?(下のコード)で書けるようになりたい。
あんまりbitの操作を使わないので積極的に使って慣れていきたい。

  • コード
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int n;
string s;
vector<bool> ans; // true = S, false = W

bool check(){
	bool zero = (ans[0] == ans[n]);
	bool ss = true;
	if(s[0] == 'o'){
		if(ans[0]){
			if(ans[n-1] != ans[1]) ss = false;
		}else{
			if(ans[n-1] == ans[1]) ss = false;
		}
	}else{
		if(ans[0]){
			if(ans[n-1] == ans[1]) ss = false;
		}else{
			if(ans[n-1] != ans[1]) ss = false;
		}
	}

	return (zero&&ss);
}

void circle(bool x,bool y){
	ans[0] = x,ans[1] = y;

	for(int i = 1; i < n; i++){
		if(s[i] == 'o'){
			if(ans[i]) ans[i+1] = ans[i-1];
			else ans[i+1] = !ans[i-1];
		}else{
			if(ans[i]) ans[i+1] = !ans[i-1];
			else ans[i+1] = ans[i-1];
		}
	}
}

int main()
{
	cin >> n >> s;
	ans.resize(n+1);

	for(int i = 0; i < (1<<2); i++){
		circle(1&(i>>0),1&(i>>1));
		if(check()){
			for(int i = 0; i < n; i++){
				if(ans[i]) cout << 'S';
				else cout << "W";
			}cout << endl;
		return 0;
		}
	}
	cout << -1 << endl;

	return 0;
}