結果
問題 | No.43 野球の試合 |
ユーザー | troro_kelp |
提出日時 | 2019-01-06 01:34:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 2,535 bytes |
コンパイル時間 | 1,881 ms |
コンパイル使用メモリ | 107,200 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-23 23:40:23 |
合計ジャッジ時間 | 1,652 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 |
ソースコード
#include <stdio.h> #include <iostream> #include <string> #include <vector> #include <set> #include <cmath> #include <stack> #include <algorithm> #include <iomanip> #include <map> #include <queue> #include <functional> #include <numeric> #include <chrono> #include <cstdlib> using ll = long long; using namespace std; const ll MOD = 1e9 + 7; #define REP(i, n) for (int(i) = 0; (i) < (n); ++(i)) #define repi(i, a, b) for (int i = int(a); i < int(b); ++i) // bool operator<(const pair<int, int> &a, const pair<int, int> &b) // { // if (a.first == b.first) // return a.second < b.second; // return a.first < b.first; // }; /*unsigned int xor128(void) { static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123; unsigned int t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } unsigned int xor128rnd(unsigned int m) { return xor128() % m; }*/ /*bool operator<(const pair<int, int> &a, const pair<int, int> &b) { if (a.first == b.first) { return a.second < b.second; } return a.first < b.first; }*/ int ans = 1000000; int N; vector<string> v; void dfs(int a, int b) { // for (int i = 0; i < N; ++i) // { // for (int j = 0; j < N; ++j) // { // cout << v[i][j]; // } // cout << endl; // } // cout << endl; if (a == N) { vector<int> vec(N); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (v[i][j] == 'o') vec[i]++; } } //cout << endl; int t = vec[0]; sort(vec.begin(), vec.end()); vec.erase(unique(vec.begin(), vec.end()), vec.end()); for (int i = 0; i < (int)vec.size(); ++i) { if (vec[i] == t) { ans = min(ans, (int)vec.size() - i); break; } } return; } if (b == N) { dfs(a + 1, 0); return; } if (v[a][b] != '-') { dfs(a, b + 1); return; } v[a][b] = 'o'; v[b][a] = 'x'; dfs(a, b + 1); v[a][b] = 'x'; v[b][a] = 'o'; dfs(a, b + 1); v[a][b] = v[b][a] = '-'; } int main(void) { cin.tie(0); ios::sync_with_stdio(false); cin >> N; for (int i = 0; i < N; ++i) { string s; cin >> s; v.push_back(s); } dfs(0, 0); cout << ans << endl; return 0; }