AtCoder Regular Contest 069 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; }