CF Round #304 Div.2 E. Soldier and Traveling
Codeforces Round #304 Div.2 E. Soldier and Traveling
フローで解けることを知っていながら解いたが、解説無しでACしたのでよし。
n個の街があって、m個の道によって連結である。各街には兵士がa[i]人かいて、彼らは今いる街にとどまってもよいし、1個だけ道を使って別の街に移動しても良い。このとき、各街について、定められた兵士の数b[i]人にすることができるかを答え、できるならその移動の仕方を答える、という問題。
まず、「ある点Pに兵士がx人いて、それをy人に変える」という状況を考えるために、点Sと点Tを別で用意し、SからPに容量x, PからTに容量yの辺を張る、ということをとりあえず考えてみた。そして、点Pと点Qが繋がっているという状況をどう作るかを考えてみると、単純に容量a[P]、a[Q]でつなぐ、という解法を思いついたが、それでは兵士が何回も移動できることになってしまうのでダメだった。そこで、Pから移動できる人数は合計でa[P]である、ということに注目すると、まずPの中継点P'に容量a[P]の辺を張って、そこから各Qに対して容量INFの辺を張ることで、その点から流れるフローの大きさの合計がもともといた人数以下におさえることができる。そしてうまくいった。
あとで他の人の解説を見ると、辺の張り方が少し違っていたが、本質的には同じことをしていた。
#include "bits/stdc++.h" using namespace std; struct edge { int to, cap, rev; }; bool used[101010]; vector<edge> g[101010]; static const int INF = 0x3f3f3f3f; void add_edge(int from, int to, int cap) { g[from].push_back((edge) { to, cap, (int)g[to].size() }); g[to].push_back((edge) { from, 0, (int)g[from].size() - 1 }); } int dfs(int v, int t, int f) { if (v == t) return f; used[v] = true; for (int i = 0; i < g[v].size(); i ++) { edge& e = g[v][i]; if (!used[e.to] && e.cap > 0) { int d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; g[e.to][e.rev].cap += d; return d; } } } return 0; } int MaxFlow(int s, int t) { int flow = 0; while (true) { memset(used, false, sizeof(used)); int f = dfs(s, t, INF); if (f == 0) return flow; flow += f; } } int main() { int n, m; cin >> n >> m; vector<int> a(n), b(n); int sum1 = 0, sum2 = 0; for (int i = 0; i < n; i ++) { cin >> a[i]; sum1 += a[i]; } for (int i = 0; i < n; i ++) { cin >> b[i]; sum2 += b[i]; } if (sum1 != sum2) { //総人数は増減しないので異なるとダメ cout << "NO" << endl; return 0; } int s = 2 * n, t = 2 * n + 1; for (int i = 0; i < n; i ++) { add_edge(s, i, a[i]); add_edge(i, t, b[i]); add_edge(i, i + n, a[i]); //中継点にa[i]を張っておく } for (int i = 0; i < m; i ++) { int x, y; cin >> x >> y; x --, y --; add_edge(x + n, y, INF); //中継点から目的の点に張る add_edge(y + n, x, INF); } if (MaxFlow(s, t) != sum1) { //全部流せていないとダメ cout << "NO" << endl; return 0; } cout << "YES" << endl; vector<vector<int>> ans(n, vector<int> (n)); for (int i = 0; i < n; i ++) { for (int j = 0; j < n; j ++) { if (i == j) { for (auto e : g[i]) { if (e.to == i + n) { ans[i][j] = e.cap; //中継点に向かって流さなかった分（まだ流せる分）がそこにとどまる人数 } } } else { bool found = false; for (auto e : g[i + n]) { if (e.to >= n) continue; if (e.to == j) { found = true; ans[i][j] = g[e.to][e.rev].cap; //流した分は、逆辺の容量と等しい break; } } if (!found) ans[i][j] = 0; } } } for (int i = 0; i < n; i ++) { for (int j = 0; j < n; j ++) { cout << ans[i][j] << (j == n - 1 ? '\n' : ' '); } } return 0; }
Atcoder ABC #029 D. 1
Atcoder ABC #029 D. 1
D: 1 - AtCoder Beginner Contest 029 | AtCoder
1からnまでの数字を全て書いた時、1が何回現れるかを求める問題。例えばn=15なら8と答える。
部分点のn <= 999のときは、とりあえず愚直に数えるだけなので、あとで満点解法のデバッグができるようにてきとうに書いておいた。さて、n<=10^9のときは当然間に合わないので、考察する。ある桁に1が現れる数の個数ではなく、１そのものの個数を求めるので、各桁について、その桁の数を１に固定したときに作ることができる数の総数を独立に求めればよい。まず各桁について、その数字が２以上９以下だったときの処理は意外と簡単であることに気付く。例えば、n=2185だとして、10の位の8に注目しているとする。 これを1に書き換える操作を考えると、〇〇1○という数字であって、2185以下のものを数えれば、この位置が1であるものはすべて網羅することができる。このとき、最初の２つの数字は、00から21のすべてを動き、8は1より大きいので残りの1桁は自由に選んで構わない。よって、この場合、(21 + 1) * 10 = 220と求めることができる。注目している数が1のときは、例えば上の例でいうと、最初の左の数は、0または1にしたときは下2桁は自由に選んで良い。2にしたときは、下2桁は86種類とりうるので、2 * 100 + 86と求められる。0のときも同じように考える。先頭と末尾は注意して処理する必要がある(11などをうまく処理できるように）。
#include "bits/stdc++.h" using namespace std; int main() { int i, j; string s; cin >> s; int n = s.size(); int ans = 0; for (i = 0; i < n; i ++) { if (s[i] == '0' || s[i] == '1') { if (i != 0) { string first = s.substr(0, i); int res = stoi(first); for (j = 0; j < n - i - 1; j ++) res *= 10; ans += res; } if (s[i] == '1') { if (i != n - 1) { string last = s.substr(i + 1, n - i - 1); ans += stoi(last); } ans ++; } } else { if (i != 0) { string first = s.substr(0, i); int res = stoi(first) + 1; for (j = 0; j < n - i - 1; j ++) res *= 10; ans += res; } else { int res = 1; for (j = 0; j < n - 1; j ++) res *= 10; ans += res; } } } cout << ans << endl; return 0; }
なんか桁DPとかいうものを使って解くのがいいらしいけど、それが何かはまだ知らない。
Atcoder ARC #010 D. 情報伝播
Atcoder ARC #010 D. 情報伝播
D: 情報伝播 - AtCoder Regular Contest 010 | AtCoder
n人の青木くんとm人のスパイが平面上にいて、青木くんは、自分を中心とする任意の半径をもつ円の内部に情報を拡散できる。スパイに情報がもれないように、青木くん全員に情報を行き渡らせるために直接情報を伝えなければならない青木くんの最小人数を求める問題。各青木くんについて、最も近い距離にいるスパイまでの距離を持たせて、その範囲にいる他の青木くんに向かって有向グラフを張ると考えるのが自然である。そのあとは、強連結成分分解をして、トポロジカルソート順の小さいものからdfsをして、その途切れる回数を求めれば良い。
#include "bits/stdc++.h" using namespace std; double dis(int x, int y, int s, int t) { return sqrt((double)(x - s) * (double)(x - s) + (double)(y - t) * (double)(y - t)); }; int V; vector<int> g[101010]; vector<int> rg[101010]; vector<int> order; bool used[101010]; int cmp[101010]; void add_edge(int from, int to) { g[from].push_back(to); rg[to].push_back(from); } void dfs(int v) { used[v] = true; for (auto i : g[v]) if (!used[i]) dfs(i); order.push_back(v); } void rdfs(int v, int k) { used[v] = true; cmp[v] = k; for (auto i : rg[v]) if (!used[i]) rdfs(i, k); } int StronglyConnectedComponent() { memset(used, 0, sizeof(used)); order.clear(); for (int i = 0; i < V; i ++) if (!used[i]) dfs(i); memset(used, 0, sizeof(used)); int k = 0; for (int i = order.size() - 1; i >= 0; i --) if (!used[order[i]]) rdfs(order[i], k ++); return k; } int main() { int i, j; int n, x, y; cin >> n; V = n; vector<pair<int, int>> f;//person for (i = 0; i < n; i ++) { cin >> x >> y; f.emplace_back(x, y); } int m; cin >> m; if (m == 0) { cout << 1 << endl; return 0; } vector<pair<int, int>> s;//spy for (i = 0; i < m; i ++) { cin >> x >> y; s.emplace_back(x, y); } vector<pair<pair<int, int>, int>> fs;//combined for (i = 0; i < n; i ++) fs.emplace_back(f[i], 1); for (i = 0; i < m; i ++) fs.emplace_back(s[i], 0); sort(fs.begin(), fs.end());//すべてをx座標の小さい順に並べる int fp = 0; vector<double> dist(n);//各青木くんの、一番近いスパイまでの距離 for (i = 0; i < fs.size(); i ++) { if (fs[i].second == 0) continue; double d = 100000000000.0; int front = i; int back = i; while (d > (fs[front].first.first - fs[i].first.first)) { front ++; if (front > fs.size() - 1) break; if (fs[front].second == 1) continue; d = min(d, dis(fs[front].first.first, fs[front].first.second, fs[i].first.first, fs[i].first.second)); } while (d > (fs[i].first.first - fs[back].first.first)) { back --; if (back < 0) break; if (fs[back].second == 1) continue; d = min(d, dis(fs[back].first.first, fs[back].first.second, fs[i].first.first, fs[i].first.second)); } dist[fp ++] = d; } //これ以降、スパイは考えなくて良い sort(f.begin(), f.end()); for (i = 0; i < n; i ++) { int front = i; int back = i; while (dist[i] > (double)(f[front].first - f[i].first)) { front ++; if (front > f.size() - 1) break; double d = dis(f[front].first, f[front].second, f[i].first, f[i].second); if (d < dist[i]) { add_edge(i, front); } } while (dist[i] > (double)(f[i].first - f[back].first)) { back --; if (back < 0) break; double d = dis(f[back].first, f[back].second, f[i].first, f[i].second); if (d < dist[i]) { add_edge(i, back); } } } StronglyConnectedComponent(); vector<pair<int, int>> jun; for (i = 0; i < n; i ++) jun.emplace_back(cmp[i], i); sort(jun.begin(), jun.end()); for (i = 0; i < n; i ++) used[i] = false; int ans = 0; for (i = 0; i < n; i++) { if (!used[jun[i].second]) { dfs(jun[i].second); ans ++; } } cout << ans << endl; return 0; }
実装するだけ
ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) D. The Door Problem
ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) D. The Door Problem
2SATの問題。
ドアがn個あって、それぞれのドアはそれぞれちょうど2個の異なるスイッチによって操作でき、スイッチは動かすと状態が反転する。1と0からなる最初の状態と、各ドアとスイッチの関係が与えられるので、すべての状態を1にできるかを判定する問題。スイッチに関する2SATが思いつき、あるドアを操作するためのスイッチは2個と決まっているので、各ドアについて、どのスイッチが対応しているかのペアについて、グラフを作る。
i番目のスイッチを押さない <=> x[i] = true
とし、あるドアに対するスイッチをi, j番目とすると、最初の状態が1ならば、2回または0回操作をしなければならないので、x[i] => x[j], not x[i] => not x[j]、そしてこれらの逆、を辺として繋ぐ。最初の状態が0ならば、1回の操作をしなければならないので、x[i] => not x[j], not x[i] => x[j]、これらの逆、を繋ぐ。あとはトポロジカルソートを見て終わり。アリ本のように一旦論理和をとるやり方は、意味わかるけれど、直感的に書けなくてわかりにくいと思った。
#include "bits/stdc++.h" using namespace std; #define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++) int V; vector<int> g[1010101]; vector<int> rg[1010101]; vector<int> order; bool used[1010101]; int cmp[1010101]; void add_edge(int from, int to) { g[from].push_back(to); rg[to].push_back(from); } void dfs(int v) { used[v] = true; for (auto i : g[v]) if (!used[i]) dfs(i); order.push_back(v); } void rdfs(int v, int k) { used[v] = true; cmp[v] = k; for (auto i : rg[v]) if (!used[i]) rdfs(i, k); } int StronglyConnectedComponent() { memset(used, 0, sizeof(used)); order.clear(); for (int i = 0; i < V; i ++) if (!used[i]) dfs(i); memset(used, 0, sizeof(used)); int k = 0; for (int i = order.size() - 1; i >= 0; i --) if (!used[order[i]]) rdfs(order[i], k ++); return k; } signed main() { int n, m; cin >> n >> m; V = 2 * m; vector<int> state(n); bool f = true; rep(i, n) cin >> state[i]; vector<int> B[101010]; rep(i, m) { int q; cin >> q; while (q --) { int a; cin >> a; a --; B[a].push_back(i); // a番目のドアはこのi番目のスイッチで操作できる } } rep(i, n) { int a = B[i][0]; //2個だけpush_backされていることが保証されている int b = B[i][1]; if (state[i] == 1) { add_edge(a, b); add_edge(b, a); add_edge(a + m, b + m); add_edge(b + m, a + m); } else { add_edge(a, b + m); add_edge(b + m, a); add_edge(a + m, b); add_edge(b, a + m); } } StronglyConnectedComponent(); rep(i, m) if (cmp[i] == cmp[i + m]) { cout << "NO" << endl; return 0; } cout << "YES" << endl; return 0; }
Atcoder ARC #006 D. アルファベット探し
Atcoder ARC #006 D. アルファベット探し
D: アルファベット探し - AtCoder Regular Contest 006 | AtCoder
ある決められた図形A, B, Cの非負整数倍拡大図形が90度毎の回転を許していくつか描かれているので、A, B, Cがそれぞれ何個ずつ含まれているかを数える問題。仮に、拡大されたものが現れないとするならば、それぞれの図形が含むマスの数をカウントするだけで、どの図形だったのかは判断できそうである（それぞれA=12, B=16, C=11なので）。どれも少なくとも８方向のいずれかで繋がっているので、これは典型的な幅優先探索で書ける。さて、実際には拡大されたものがあって、例えばAの4倍拡大とBの3倍拡大のいずれもが48個とカウントされてしまって区別できなくなってしまう。そこで、倍率を計算しておくことにする。左上から右に探索をしているので、一番最初に見つかったマスは、拡大された「１つの点」の左上に位置している。よって、ratio = 1から正方形の探索をしてみて、すべて'o'マスならratioを増やしてさらに探索をするということを繰り返せば、その正方形が構成できなくなったときのratioが倍率とわかる（めんどくさいのでふつうに実装した）。そして最後にカウントをratio * ratioで割れば、結局12, 16, 11のいずれかになるはずなので、これで判定可能になる。
#include "bits/stdc++.h" using namespace std; #define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++) static const int dx[] = { 1, -1, 0, }, dy[] = { 0, 1, -1 }; //8方向の探索用 signed main() { int H, W; cin >> H >> W; vector<string> c(H); rep(i, H) cin >> c[i]; bool used[1010][1010] = { 0 }; int ansA = 0, ansB = 0, ansC = 0; rep(i, H) rep(j, W) { if (used[i][j]) continue; used[i][j] = true; if (c[i][j] == '.') continue; int ratio = 1; bool f = true; while (f) { rep(y, ratio) rep(x, ratio) if (c[i + y][j + x] == '.') f = false; //c[i][j]からみてy, xだけ探索してチェック if (f) ratio ++; } ratio --; int cnt = 0; queue<pair<int, int>> q; q.push(make_pair(i, j)); while (!q.empty()) { pair<int, int> s = q.front(); q.pop(); cnt ++; int y = s.first; int x = s.second; rep(ddx, 3) rep(ddy, 3) { //8方向すべて探索 int ny = y + dy[ddy]; int nx = x + dy[ddx]; if (!used[ny][nx] && c[ny][nx] =='o') { used[ny][nx] = true; q.push(make_pair(ny, nx)); } } } int detect = cnt / (ratio * ratio); if (detect == 12) ansA ++; if (detect == 16) ansB ++; if (detect == 11) ansC ++; } cout << ansA << ' ' << ansB << ' ' << ansC << endl; return 0; }
余計な図形が入っていないことが保証されていたので易しかった。
追記：他の方のコードを見てみると、yminとymaxを保持するやり方を見つけた。これで倍率が一意に定まる程度に大体の大きさがわかるというわけだって。よく考えたらそりゃそうだった。
Atcoder ARC #004 D. 表現の自由 ( Freedom of expression )
Atcoder ARC #004 D. 表現の自由 ( Freedom of expression )
D: 表現の自由 ( Freedom of expression ) - AtCoder Regular Contest 004 | AtCoder
整数nをm個の整数の積で表す方法の数を求める問題。
真っ先に考えたのは、負の数をどう処理するかであった。とりあえず数値は無視して、全体の符号について考えてみる。例えば、全体の符号を正にしたいとすると各符号はどうなるだろうか？実はm個のうちm - 1個はどちらの符号になっていても構わないことがわかる。なぜなら、最後の1個の符号をm - 1個の積の符号と同じにすれば、全体の符号は正になるからである。逆にそれによってすべての正負のパターンを網羅できることもいえるはずである。また、(-n, m)=(n, m)であることも示せるので、結局すべて正として考えてよく、最後に2のm - 1乗をかけてやればよいことになる。すべて正とすると、あとはm個の箱を用意して、nの素因数たちを分配していくとよい。重複を許してすべての素因数を分配すればよいので、これをm個の箱から、重複を許して(素因数の数)個の箱を選ぶ、と読み替えて、積をとっていくだけでよいことになる。つまり、ライブラリをペタリとはりつけるだけでよいことになる。
#include "bits/stdc++.h" using namespace std; #define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++) static const int MOD = 1000000007; #define int long long long long inv(long long x) { long long y = 1; while (y % x) y += MOD; return y / x; } long long nCr(long long n, long long r) { if (n < r) return 0; if (n - r < r) r = n - r; long long ret = 1; rep(i, r) { ret = ret * n % MOD; n --; ret = ret * inv(i + 1) % MOD; } return ret; } long long nHr(long long n, long long r) { return nCr(n + r - 1, r); } signed main() { int n, m; cin >> n >> m; n = n < 0 ? -n : n; //nが負ならば正にする int ans = 1; for (int i = 2; i * i <= n; i ++) if (n % i == 0) { int cnt = 0; while (n % i == 0) { n /= i; cnt ++; } ans = ans * nHr(m, cnt) % MOD;//m個の箱にcnt個のある素因数を分配する方法の数をかける } if (n > 1) ans = ans * nHr(m, 1) % MOD; rep(i, m - 1) ans = ans * 2 % MOD; //2のm - 1乗をかける cout << ans << endl; return 0; }
Atcoder ARC #002 D. ボードゲーム
D: ボードゲーム - AtCoder Regular Contest 002 | AtCoder
２時間ほどかかったが自力で通したので、個人的にはARCのD（F）にしてはぬるめの考察問題だったと思う。
ボード上の２種類のコマ'o'と'x'の状態が与えられる。'o'は右に、'x'は左に向かって１歩ずつ進める。進行方向に異なるコマがあれば、それを踏み潰せる。'o'からスタートし、理想的に動いたとき、向かっている方向の端っこに先についた方が勝ちであるとき、どちらが勝つかを判定する問題。
まずサンプルケースを見ると気づくことだが、進行方向に相手のコマがないコマが存在すれば、それらの端までの距離を比較するだけで答えが出る。そうでない場合は、すべてのコマが左に'o'のみ、右に'x'のみというペアに分けられ、これらは独立に考えて良い。少し考察すると、自分のターンで動かせるところが、「o'スペース'x'」の部分だけになったときは負ける、ということがわかる。よって、できる限りこの状況に到るまでの自分にとっての余裕のようなものを最大化し、相手にとっての余裕のようなものを最小化するような動きをとればよい。さらに考察すると、動かすべきコマは、向かい合うコマのそれぞれの後ろのコマの個数の和が最も大きいものであることがわかる。なぜならば、中央のコマを動かすことで自分にとっての余裕はその後ろのコマの数だけ進むスペースを作ることができ、さらに相手が進む距離を１少なくできるので、相手にとって増やせたであろう余裕度の増加を阻止できるからである。この和を余裕度とよぶことにし、各ペアについて、余裕度がどれくらい生まれるかをカウントし、最後に比較すると答えがわかる。O(HW)。余裕度の計算はすでに解いていたC: ウサギ跳び - AtCoder Regular Contest 041 | AtCoderと似た発想だったので、すぐに実装できた。
#include "bits/stdc++.h" using namespace std; #define OUT(x) cout << #x << " = " << x << endl #define rep(i, n) for (int (i) = 0; (i) < (int)(n); (i)++) #define rer(i, l, r) for (int (i) = (int)(l); (i) <= (int)(r); (i)++) #define reu(i, l, r) for (int (i) = (int)(l); (i) < (int)(r); (i)++) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() template<typename T> void pv(T a, T b) { for (T i = a; i != b; i ++) cout << *i << " "; cout << endl; } template<typename T, typename U> inline void amin(T &x, U y) { if (y < x) x = y; } template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; } int in() { int x; scanf("%d", &x); return x; } long long lin() { long long x; scanf("%lld", &x); return x; } static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; #define int long long signed main() { int H, W; cin >> H >> W; vector<string> c(H); rep(i, H) cin >> c[i]; int od = INFL, xd = INFL; rep(i, H) { rep(j, W) { if (c[i][j] == 'x') { //最初に'x'がある場合は向かい合うコマがないことを意味する amin(xd, j); break; } if (c[i][j] == 'o') break; } reverse(all(c[i])); //reverseして同様に'o'も考える rep(j, W) { if(c[i][j] == 'o') { amin(od, j); break; } if (c[i][j] == 'x') break; } reverse(all(c[i])); //元に戻す } if (od != INFL || xd != INFL) { //どちらかが向き合ってないコマをもっていれば、答えが出る if (od <= xd) cout << 'o' << endl; else cout << 'x' << endl; return 0; } vector<pair<int, pair<vector<int>, vector<int>>>> P; //各ペアを格納する。<コマの総数から各コマの先頭の数(=2)を引いた数, <'o'のある座標, 'x'のある座標>>で一つのペアにする vector<int> opoint; vector<int> xpoint; rep(i, H) { rep(j, W) { if (c[i][j] == '.') continue; if (c[i][j] == 'o') { if (!xpoint.empty()) { reverse(all(opoint)); //'o'については、中央からみて左にindexが増加するようにしておくとわかりやすい P.push_back(make_pair(opoint.size() + xpoint.size() - 2, make_pair(opoint, xpoint))); opoint.clear(); xpoint.clear(); } opoint.push_back(j); } else { xpoint.push_back(j); } } } reverse(all(opoint)); if (!xpoint.empty()) P.push_back(make_pair(opoint.size() + xpoint.size() - 2, make_pair(opoint, xpoint))); sort(rall(P)); //余裕度（？）で降順にソートして大きいものからコマを進める bool oturn = true; //最初'o'からはじめる int ocnt = 0, xcnt = 0; //余裕度 for (auto i : P) { int l = i.second.first.front(); //'o'の先頭のコマ int r = i.second.second.front(); //'x'の先頭のコマ int d = r - l; //先頭のコマ同士の間にあるマスの数＋１ d --; //mid - 1に'o'がきて、mid + 1に'x'がくるようにmid（スペースになるマスの位置）をつくる if (d & 1) { //奇数個のマスがあるときは、ターンは変わらない int mid = (l + r) / 2; reu(j, 1, i.second.first.size()) ocnt += (mid - 1) - i.second.first[j] - j; reu(j, 1, i.second.second.size()) xcnt += i.second.second[j] - (mid + 1) - j; } else { //偶数個のときはターンが必ず変わる上に、どちらのターンから始まるかによって、先頭のコマの到達位置も変わるので注意 if (oturn) { int mid = (l + r + 1) / 2; reu(j, 1, i.second.first.size()) ocnt += (mid - 1) - i.second.first[j] - j; reu(j, 1, i.second.second.size()) xcnt += i.second.second[j] - (mid + 1) - j; } else { int mid = (l + r) / 2; reu(j, 1, i.second.first.size()) ocnt += (mid - 1) - i.second.first[j] - j; reu(j, 1, i.second.second.size()) xcnt += i.second.second[j] - (mid + 1) - j; } oturn ^= 1; } } if (oturn) { //余裕度を使って動かし始めるときにどちらのターンかで最終的な答えを出す cout << (ocnt > xcnt ? 'o' : 'x') << endl; } else { cout << (ocnt < xcnt ? 'x' : 'o') << endl; } return 0; }
