結果

問題 No.2692 How Many Times Reached?
ユーザー GEX777GEX777
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

/**
* @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> //ACL
using 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,3Mod
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÷bMOD
ll DivisionMod(ll a, ll b, ll MOD)
{
return (a * intPowMod(b, MOD - 2, MOD)) % MOD;
}
// C(n, r)Mod, 3Conbination
ll 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;
else
return 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->false
bool 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;
}
// Eratosthenestable使
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; // parent
dat[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; // parent
data[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-Find
struct 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
else
return 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 rank
if (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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0