ABC162お疲れ様でした。最近競技プログラミングのモチベが低くて全然精進してなかったらレートが溶けまくって辛いよう・・・・
stringの変数sの'7’ の文字数カウントをしたい場合はcount(ALL(s),'7')で利用できます。(ALLマクロ使用している前提ですが。)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a) (a).begin(),(a).end()
#define endl "\n"
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;
void solve() {
string N;
cin >> N;
string ans = count(ALL(N),'7') > 0 ? "Yes" : "No";
cout << ans << endl;
}
int main() {
solve();
return 0;
}
|
提出 #11934824 - AtCoder Beginner Contest 162
条件分岐して足して行きましょう。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a) (a).begin(),(a).end()
#define endl "\n"
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;
void solve() {
ll N;
cin >> N;
ll sum = 0;
FOR(i,1,N+1) {
bool cond1 = i%3 == 0;
bool cond2 = i%5 == 0;
if (cond1 || cond2) continue;
else sum+=i;
}
cout << sum << endl;
}
int main() {
solve();
return 0;
}
|
提出 #11934855 - AtCoder Beginner Contest 162
gcd(a,b,c)はgcd(gcd(a,b),c)と同値です。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a) (a).begin(),(a).end()
#define endl "\n"
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;
void solve() {
int K;
cin >> K;
ll sm = 0;
REP(am,K) {
REP(bm,K) {
REP(cm,K) {
auto a = am+1;
auto b = bm+1;
auto c = cm+1;
sm += gcd(gcd(a,b),c);
}
}
}
cout << sm << endl;
}
int main() {
solve();
return 0;
}
|
提出 #11934855 - AtCoder Beginner Contest 162
R,G,Bと書かれた袋があり、例えば、0文字目がRならRと書かれた袋に0を入れることとします。
入力を見て、インデックスをそれに対応する袋に入れます。
R,G,Bの袋から一個ずつ取り出します。取り出した後、昇順に並び替えると、
i,j,kを満たす組の条件の1つ($S_i \ne S_j$ かつ $S_i \ne S_k$ かつ $S_j \ne S_k$である。)を必ず満たします。
よって、$S_i \ne S_j$ かつ $S_i \ne S_k$ かつ $S_j \ne S_k$を満たす組から$j-i \ne k-j$でないものを引けばよいです。
$j-i \ne k-j$でないものは$ 2*j - i = k $を満たすのでそれを求めていけば間に合います。
私は、R,G,Bの袋に対してi,j,kを全パターン(6パターン)で割り当てて、求めていきました。
ちなみに数え上げをやるとどうやっても間に合わず、2TLEをば。。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a) (a).begin(),(a).end()
#define endl "\n"
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;
string S;
int N;
// pos
vector<set<int>> v;
// j - i \ne k-j を満たす数を負数として返す。
ll go() {
ll ans = 0;
for(const auto &i:v[0]) {
// find start
auto sj = upper_bound(ALL(v[1]),i);
for(auto j = sj; j != v[1].end(); j ++) {
int nk = 2*(*j) - i;
if ( *j < nk && v[2].count(nk) == 1) ans--;
}
}
return ans;
}
void solve() {
v.resize(3);
cin >> N;
cin >> S;
REP(i,N) {
if (S[i]== 'R') v[0].insert(i);
if (S[i]=='G') v[1].insert(i);
if (S[i]=='B') v[2].insert(i);
}
ll ans = v[0].size()*v[1].size()*v[2].size();
// iter_swapでi,j,kとR,G,Bの袋の割り当て方を全部だしている。
REP(i,3) {
ans += go();
iter_swap(v.begin()+1,v.begin()+2);
ans += go();
iter_swap(v.begin(),v.begin()+1);
}
cout << ans << endl;
}
int main() {
solve();
return 0;
}
|
提出 #11935231 - AtCoder Beginner Contest 162
これは無理だった。解説ACです。
まず、数えていくと$K^N$個あるので明らかに間に合わないです。そこで、違う方法でアプローチをかける必要があります。
ここで、$ 1 \leq K \leq 10^5 $ の条件から、 $ 1 \leq gcd(A_1,…,A_N) \leq K $ です。
$ gcd(A_1,…,A_N) = X$になるようなXを満たす$A_1,…,A_N$の組み合わせの数を求めていき、
最終的には(Xになる数列の組み合わせの数 * X)の和を求めます。
これなら$ gcd(A_1,…,A_N) = X$になるようなXを満たす$A_1,…,A_N$の組み合わせの数がlogで出せれば総計算量はそれにKを掛けたものなので
間に合いそうです。
それでは考えていきましょう。
まずは、$ gcd(A_1,…,A_N) = X$を満たす場合について考えると、以下の条件が成り立ちます。
最大公約数が$X$に等しい数列Aの個数を$f(X)$とすると、
$f(X) = floor(\frac{K}{X})^N - \sum_{2X \leq mX \leq K} f(mX)$
です。
漸化式を見れば、X,2X,3X,… において、大きい方からなら求められそうだということがわかります。
こちらの記事がとても分かりやすい。
競プロ参戦記 #78 Select Half | ABC 162 - Qiita
後はmod_intを使ってごにょごにょしつつ答えを出せばおｋ。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a) (a).begin(),(a).end()
#define endl "\n"
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template< int mod >
struct ModInt {
int x;
ModInt() : x(0) {}
ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
ModInt &operator+=(const ModInt &p) {
if((x += p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if((x += mod - p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = (int) (1LL * x * p.x % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const { return ModInt(-x); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt inverse() const {
int a = x, b = mod, u = 1, v = 0, t;
while(b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ModInt(u);
}
ModInt pow(int64_t n) const {
ModInt ret(1), mul(x);
while(n > 0) {
if(n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ModInt &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ModInt &a) {
int64_t t;
is >> t;
a = ModInt< mod >(t);
return (is);
}
static int get_mod() { return mod; }
};
using modint = ModInt< int(1e9)+7 >;
void solve() {
int N,K;
cin >>N >> K;
modint ans;
vector<modint > v(K+1,0);
REPR(i,K) {
if (i == 0) break;
modint d (K/i);
v[i] = d.pow(N);
auto ni = i * 2;
while ( ni <= K) {
v[i] -= v[ni];
ni += i;
}
modint m;
m = v[i] * i;
ans += m;
}
cout << ans << endl;
}
int main() {
solve();
return 0;
}
|
提出 #11938251 - AtCoder Beginner Contest 162
ひっさしぶりに頭動かした。水、青diffはかなり体力使うけど理解できると楽しいね。(おもすぎて中々気分が向かないが・・・)