結果
問題 | No.2692 How Many Times Reached? |
ユーザー |
|
提出日時 | 2024-03-22 22:38:52 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 16,180 bytes |
コンパイル時間 | 1,942 ms |
コンパイル使用メモリ | 155,132 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-30 12:03:50 |
合計ジャッジ時間 | 3,084 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 |
ソースコード
/*** @file template.cpp* @brief 競技プログラミングのデッキ* @author Gex777* @date update:2024/03/10*/#include <algorithm>#include <bitset>#include <cassert>#include <climits>#include <cmath>#include <complex>#include <deque>#include <iomanip>#include <iostream>#include <list>#include <map>#include <queue>#include <set>#include <sstream>#include <string>#include <unordered_map>#include <unordered_set>#include <valarray>#include <vector>#include <functional>// #include <atcoder/all> //ACLusing namespace std;// using namespace atcoder;// 独自型定義using ll = long long;using ull = unsigned long long;using vi = vector<int>;using vvi = vector<vi>;using vll = vector<ll>;using vvll = vector<vll>;using vvvll = vector<vvll>;using vs = vector<string>;using vc = vector<char>;using vvc = vector<vc>;using vb = vector<bool>;using vvb = vector<vb>;using vd = vector<double>;using vvd = vector<vd>;using ld = long double;using pii = pair<int, int>;using pll = pair<ll, ll>;// マクロの宣言#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), e.rend()// 定数宣言constexpr double PI = 3.141592653589793;constexpr ll MOD998 = 998244353;constexpr ll MOD107 = 1000000007;/*****************************************************************ここから下は自作ライブラリ******************************************************************/// コンテナの中身を表示, 1行で出力をする, debug用template <typename T>void printv(T &a){for (const auto &x : a){cout << x << " ";}puts("");return;}// コンテナの中身を表示, 二次元配列用template <typename T>void printvv(T &a){for (const auto &x : a){printv(x);}}// コンテナの中身を表示, pair型template <typename T>void print_vpair(const T &a){for (const auto &x : a){cout << "(" << x.first << ", " << x.second << "), ";}puts("");return;}template <class T>inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}template <class T>inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}// コンテナの中身を表示, 改行して出力をする, debug用template <typename T>void println(T &a){for (const auto &x : a){cout << x << endl;}return;}// 1~Nまでの総和を求めるll sum_from_1_to_N(ll N){if (N < 1LL){return 0;}if ((N & 1) == 0) // even{return N / 2 * (N + 1);}else // odd{return (N + 1) / 2 * N;}}// A+1~Nまでの総和を求めるll sum_from_A_to_B(ll A, ll B){return sum_from_1_to_N(B) - sum_from_1_to_N(A);}// a^bを求める, 繰り返し2乗法を用いる,3番目の引数はModを取る場合に設定ll intPowMod(ll a, ll b, const ll MOD = LLONG_MAX){ll ans = 1;ll A = a;while (b > 0){int n = b % 2;b /= 2;if (n == 1){ans *= A % MOD;ans %= MOD;}A = ((A % MOD) * (A % MOD)) % MOD;}return ans;}ld arg_to_rad(ld arg) { return (arg * PI / 180.0); }ld rad_to_arg(ld rad) { return rad * 180.0 / PI; }// C(n, m)を求めるll combination(const ll n, const ll m){assert(n >= m); // n>=mは保証されるll up = 1;ll down = 1;for (int i = n; i > n - m; i--){up *= i;}for (int i = m; i >= 2; i--){down *= i;}return up / down;}// 動的計画法で前処理,O(N**2)vvll combination_table(const int MAX_N = 50){vvll com = vvll(MAX_N + 1, vll(MAX_N + 1, 0)); // 前計算の結果を保存com[0][0] = 1;for (int i = 1; i <= MAX_N; ++i){com[i][0] = 1;for (int j = 1; j <= MAX_N; j++){com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]);}}return com;}// a÷bをMODで割ったあまりを返す関数ll DivisionMod(ll a, ll b, ll MOD){return (a * intPowMod(b, MOD - 2, MOD)) % MOD;}// C(n, r)をModで割った余りを返す関数, 3番めの引数を入れないと通常のConbinationll combinationMod(ll n, ll r, ll MOD = LLONG_MAX){// 分子upを求めるll up = 1;for (ll i = n - r + 1; i <= n; ++i){up = (up * i) % MOD;}// 分母downを求めるll down = 1;for (ll i = 1; i <= r; ++i)down = (down * i) % MOD;return DivisionMod(up, down, MOD);}// a,bの最大公約数を求める, A>=B>=0の時, 計算量O(logB)long long GCD(long long a, long long b){if (b == 0)return a;elsereturn GCD(b, a % b);}// 拡張ユークリッドの互助法, 返り値: a と b の最大公約数// ax + by = gcd(a, b) を満たす (x, y) が格納されるlong long extGCD(long long a, long long b, long long &x, long long &y){if (b == 0){x = 1;y = 0;return a;}long long d = extGCD(b, a % b, y, x);y -= a / b * x;return d;}// 最小公倍数ll LCM(ll a, ll b) { return a * b / GCD(a, b); }// 素数判定, P->true, not_P->falsebool check_Prime(ll N){if (N == 2)return true;if (N == 1 || (N & 1) == 0)return false;for (ll i = 3; i <= sqrt(N); i += 2){if (N % i == 0)return false;}return true;}// 素因数分解,key:素数, value:指数のmap<ll,ll>を返すmap<ll, ll> prime_factorize(ll number){if (number == 1){return {{1LL, 1LL}};}map<ll, ll> table;for (ll i = 2; i * i <= number; ++i){while (number % i == 0){table[i]++;number /= i;}}if (number != 1LL){table[number]++;}return table;}// Eratosthenesのtableを使った素因数分解vector<pii> prime_factorize(ll number, const vi &IsPrime){if (number == 1){return {{1, 1}};}vector<pii> factor;while (number != 1){int cnt = 0;int f = IsPrime[number];while (IsPrime[number] == f){number /= IsPrime[number];++cnt;}factor.push_back({f, cnt});}return factor;}/* エラストステネス and 高速素因数分解prime->IsPrime[i]=i; not prime ->最小の素因数高速素因数分解をするのにはprime_factorize(ll num, ll table)を使う */vi Eratosthenes(size_t max_number){vi IsPrime(max_number + 1);// tableの初期化for (int i = 1; i < IsPrime.size(); ++i){IsPrime[i] = i;}for (int i = 2; i <= sqrt(max_number); ++i){for (int j = i; j <= max_number; j += i){if (IsPrime[j] == j){IsPrime[j] = i;}}}return IsPrime;}// O(N)でNの階乗を求めるll factorial(const ll N){ll ans = 1;for (ll i = 1; i <= N; ++i){ans *= i;}return ans;}// Run Length Encoding, ランレングス圧縮template <typename T>vector<pair<T, int>> RLE(const vector<T> &A){vector<pair<T, int>> rle;rle.push_back({A.front(), 1});for (int i = 1; i < A.size(); ++i){if (rle.back().first == A[i]){rle.back().second++;}else{rle.push_back({A[i], 1});}}return rle;}vector<pair<char, int>> RLE(const string &S){vector<pair<char, int>> rle;rle.push_back({S.front(), 1});for (int i = 1; i < S.size(); ++i){if (rle.back().first == S[i]){rle.back().second++;}else{rle.push_back({S[i], 1});}}return rle;}void DEBUG_INDICATE(){static int cnt = 0;cout << "-----DEBUG:" << cnt++ << "------" << endl;return;}// 正方行列の回転を行うライブラリtemplate <typename T>struct ROTATE{static vector<vector<T>> clockwise(const vector<vector<T>> &X){assert(X.size() == X[0].size());const int N = X.size();vector<vector<T>> Y(N, vector<T>(N));for (int i = 0; i < N; ++i)for (int j = 0; j < N; ++j)Y[j][N - 1 - i] = X[i][j];return Y;}static vector<vector<T>> anticlockwise(const vector<vector<T>> &X){assert(X.size() == X[0].size());const int N = X.size();vector<vector<T>> Y(N, vector<T>(N));for (int i = 0; i < N; ++i)for (int j = N - 1; 0 <= j; --j)Y[N - 1 - j][i] = X[i][j];return Y;}};/* RMQ:[0,n-1] について、区間ごとの最小値を管理する構造体update(i,x): i 番目の要素を x に更新。O(log(n))query(a,b): [a,b) での最小の要素を取得。O(log(n))*/template <typename T>struct RangeMinimumQuery{const T INF = numeric_limits<T>::max();int n; // 葉の数vector<T> dat; // 完全二分木の配列RangeMinimumQuery(int n_) : n(), dat(n_ * 4, INF){ // 葉の数は 2^x の形int x = 1;while (n_ > x){x *= 2;}n = x;}void update(int i, T x){i += n - 1;dat[i] = x;while (i > 0){i = (i - 1) / 2; // parentdat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2]);}}// the minimum element of [a,b)T query(int a, int b) { return query_sub(a, b, 0, 0, n); }T query_sub(int a, int b, int k, int l, int r){if (r <= a || b <= l){return INF;}else if (a <= l && r <= b){return dat[k];}else{T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);return min(vl, vr);}}};// 1次元累積和のためのクラスtemplate <typename T>struct CSUM1D{vector<T> csum;// 1次元累積和にするコンストラクタCSUM1D(const vector<T> &_csum){const size_t N = _csum.size();csum = vll(N + 1, 0);for (int i = 0; i < N; ++i)csum[i + 1] = csum[i] + _csum[i];}// 区間[L,R]の合計値(閉区間)T get(const int L, const int R){const size_t N = csum.size();assert(1 <= L && L <= R && R <= N);return csum[R] - csum[L - 1];}};// 二次元累積和のためのクラスtemplate <typename T>struct CSUM2D{vector<vector<T>> csum;// 二次元累積和にするコンストラクタCSUM2D(const vector<vector<T>> &_csum){const int N = _csum.size();const int M = _csum[0].size();csum = vector<vector<T>>(N + 1, vector<T>(M + 1, 0));for (int i = 1; i <= N; ++i)for (int j = 1; j <= M; ++j)csum[i][j] = _csum[i - 1][j - 1];for (int i = 0; i <= N; ++i)for (int j = 0; j < M; ++j)csum[i][j + 1] = csum[i][j] + csum[i][j + 1];for (int j = 0; j <= M; ++j)for (int i = 0; i < N; ++i)csum[i + 1][j] = csum[i][j] + csum[i + 1][j];}//(i1,j1)を左上,(i2,j2)を右下とする長方形領域の合計値(閉区間)T get(const int i1, const int j1, const int i2, const int j2){assert(i1 <= i2 && j1 <= j2);assert(1 <= i1 && i1 < csum.size() && 1 <= j1 && j1 < csum[0].size());assert(1 <= i2 && i2 < csum.size() && 1 <= j2 && j2 < csum[0].size());T s4 = csum[i2][j2];T s1 = csum[i1 - 1][j1 - 1];T s2 = csum[i1 - 1][j2];T s3 = csum[i2][j1 - 1];return s4 - s3 - s2 + s1;}};/*** @brief 要素数N,二項演算op, 初期値INFを指定するセグ木* update(i,x): i 番目の要素を x に更新。O(log(n))* query(a,b): [a,b) での最小の要素を取得。O(log(n))*/template <typename T>struct SegTree{T INF; // 初期値int N; // 葉の数vector<T> data; // 完全二分木の配列function<T(T, T)> op; // 二項演算SegTree(int _N, const function<T(T, T)> _op, const T _INF) : N(), data(_N * 4, _INF), op(_op), INF(_INF){ // 葉の数は 2^x の形int x = 1;while (_N > x){x *= 2;}N = x;}void update(int i, T x){i += N - 1;data[i] = x;while (i > 0){i = (i - 1) / 2; // parentdata[i] = op(data[i * 2 + 1], data[i * 2 + 2]);}}// the minimum element of [a,b)T query(int a, int b) { return query_sub(a, b, 0, 0, N); }T query_sub(int a, int b, int k, int l, int r){if (r <= a || b <= l){return INF;}else if (a <= l && r <= b){return data[k];}else{T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);return op(vl, vr);}}// 添字でアクセスT operator[](int i){return data[i + N - 1];}};// Union-Findstruct UnionFind{vector<int> par, rank, siz;// 構造体の初期化UnionFind(int n) : par(n, -1), rank(n, 0), siz(n, 1) {}// 根を求めるint root(int x){if (par[x] == -1)return x; // x が根の場合は x を返すelsereturn par[x] = root(par[x]); // 経路圧縮}// x と y が同じグループに属するか (= 根が一致するか)bool issame(int x, int y) { return root(x) == root(y); }// x を含むグループと y を含むグループを併合するbool unite(int x, int y){int rx = root(x), ry = root(y); // x 側と y 側の根を取得するif (rx == ry)return false; // すでに同じグループのときは何もしない// union by rankif (rank[rx] < rank[ry])swap(rx, ry); // ry 側の rank が小さくなるようにするpar[ry] = rx; // ry を rx の子とするif (rank[rx] == rank[ry])rank[rx]++; // rx 側の rank を調整するsiz[rx] += siz[ry]; // rx 側の siz を調整するreturn true;}// x を含む根付き木のサイズを求めるint size(int x) { return siz[root(x)]; }};/**********************************************************ライブラリ終わり*****************************************************************/int main(){int N;cin >> N;vs S(N);int ans = 0;for (auto &s : S){cin >> s;int cnt = 0;bool is_ok = true;for (auto &ch : s){cnt += ch == 'A';is_ok = ch == 'B' ? false : is_ok;}ans += cnt == N - 1 && is_ok;}// printvv(S);// cout << "ans=" << ans << endl;for (int j = 0; j < N; ++j){int cnt = 0;bool is_ok = true;for (int i = 0; i < N; ++i){cnt += S[i][j] == 'A';is_ok = S[i][j] == 'B' ? false : is_ok;}ans += cnt == N - 1 && is_ok;}// cout << "ans=" << ans << endl;int cnt1 = 0;int cnt2 = 0;bool is_ok1 = true;bool is_ok2 = true;for (int i = 0; i < N; ++i){cnt1 += S[i][i] == 'A';is_ok1 = S[i][i] == 'B' ? false : is_ok1;cnt2 += S[i][N - i - 1] == 'A';is_ok2 = S[i][N-1-i] == 'B' ? false : is_ok2;}ans += cnt1 == N - 1 && is_ok1;ans += cnt2 == N - 1 && is_ok2;// cout << "cnt1=" << cnt1 << endl;// cout << "cnt2=" << cnt2 << endl;cout << ans << endl;}