## Search

-  Programming   -  Competitive Programming   -  AtCoder   -  ABC   -  AtCoder Beginner Contest 190

# AtCoder Beginner Contest 190

AtCoder Beginner Contest 190 solutions

## Solutions

### Problem A

Score : 100points

#### Problem Statement

Takahashi and Aoki will play a game against each other.
Initially, Takahashi and Aoki have A and B candies, respectively.
They will alternately do the operation below. Takahashi goes first if C=0, and Aoki goes first if C=1

• Eat one of the candies he has.

The person who first becomes unable to do the operation loses. Which person will win?

#### Constraints

• All values in input are integers.
• 0≤A,B≤100
• C∈{0,1}

### Solution

When A > B, Takahashi will always win the game.
When A = B and C = 0, Takahashi will lose, because Takahashi goes first.
When A = B and C = 1, Takahashi will win, because Aoki goes first.
When A < B, Takahashi will always lose the game.

#include <bits/stdc++.h>
using namespace std;

void solve(long long A, long long B, long long C){
if(A > B){
printf("Takahashi\n");
}else if(A == B && C == 0){
printf("Aoki\n");
}else if(A == B && C == 1){
printf("Takahashi\n");
}else{
printf("Aoki\n");
}
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
long long A;
scanf("%lld",&A);
long long B;
scanf("%lld",&B);
long long C;
scanf("%lld",&C);
solve(A, B, C);
return 0;
}


### Problem B

Score : 200points

#### Problem Statement

Takahashi, the magician, is fighting with a monster.
He can use N spells.
The i-th spell takes Xi seconds to cast and has a power Yi.
However, the monster is strong enough to avoid taking damage from spells taking S or more seconds to cast and spells with powers D

or less.
Also, there is nothing other than spells that can do damage to the monster.
Can Takahashi do damage to the monster?

#### Constraints

• All values in input are integers.
• 1≤N≤100
• 1≤N≤100
• 1≤Xi≤109
• 1≤Yi≤109
• 1≤S≤109
• 1≤D≤109

### Solution

Takahashi can damage to the monster, if and only if there is at least one spell, which takes less than S seconds to cast with powers more than D.

#include <bits/stdc++.h>
using namespace std;

const string YES = "Yes";
const string NO = "No";

void solve(long long N, long long S, long long D, std::vector<long long> X, std::vector<long long> Y){
long long ans = 0;
for(int i = 0; i < N; ++i){
if(X[i] < S && Y[i] > D) ans++;
}
if(ans) printf("Yes\n");
else printf("No\n");
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
long long N;
scanf("%lld",&N);
long long S;
scanf("%lld",&S);
long long D;
scanf("%lld",&D);
std::vector<long long> X(N);
std::vector<long long> Y(N);
for(int i = 0 ; i < N ; i++){
scanf("%lld",&X[i]);
scanf("%lld",&Y[i]);
}
solve(N, S, D, std::move(X), std::move(Y));
return 0;
}


### Problem C

Score : 300

points

#### Problem Statement

We have N dishes numbered 1,2,…,N and M conditions numbered 1,2,…,M.
Condition i is satisfied when both Dish Ai and Dish Bi have (one or more) balls on them.
There are K people numbered 1,2,…,K. Person i will put a ball on Dish Ci or Dish Di

.
At most how many conditions will be satisfied?

#### Constraints

• All values in input are integers.
• 2≤N≤100
• 1≤M≤100
• 1≤Ai<Bi≤N
• 1≤K≤16
• 1≤Ci<Di≤N

### Solution

This problem is typical Brute Force Search problem.
The number of all possible states are
$$2^K$$
, because Ki‘s people can chose Ci or Di.
You can simulate these states by using bit.
After Calculating the number of satisfied conditions on each state, the maximum among them is the answer.

#include <bits/stdc++.h>
using namespace std;

void solve(long long N, long long M, std::vector<long long> A, std::vector<long long> B, long long K, std::vector<long long> C, std::vector<long long> D){
long long  rec = 0;
for(int i = 0; i < (1 << K); ++i){
long long ans = 0;
set<long long> q;
q.clear();
for(int j = 0; j < K; ++j){
if(i & (1 << j)){
q.insert(C[j]);
}else q.insert(D[j]);
}
for(int j = 0; j < M; ++j){
if(q.count(A[j]) && q.count(B[j])){
ans++;
}
}
rec = max(ans, rec);
}
printf("%lld\n", rec);
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
long long N;
scanf("%lld",&N);
long long M;
scanf("%lld",&M);
std::vector<long long> A(M);
std::vector<long long> B(M);
for(int i = 0 ; i < M ; i++){
scanf("%lld",&A[i]);
scanf("%lld",&B[i]);
}
long long K;
scanf("%lld",&K);
std::vector<long long> C(K);
std::vector<long long> D(K);
for(int i = 0 ; i < K ; i++){
scanf("%lld",&C[i]);
scanf("%lld",&D[i]);
}
solve(N, M, std::move(A), std::move(B), K, std::move(C), std::move(D));
return 0;
}


### Problem D

Score : 400

points

#### Problem Statement

How many arithmetic progressions consisting of integers with a common difference of 1 have a sum of N?

#### Constraints

• 1≤N≤1012
• N is an integer.

### Solution

Considering the arithmetic progressions, A = [A0, ….., Ak] with common difference of 1.
The sum of A (we define sum of A as S) is
$$S = \frac{(A_0+A_k)(A_k-A_0+1)}{2}$$
As A0 + Ak > 0 and Ak - A0 + 1> 0, we can calculate all of the pair of (A0 + Ak, Ak – A0 + 1).
The order of calculating the pair is
$$O(\sqrt(N))$$
When the parity of the pair is same, it does not satisfy the condition.

#include <bits/stdc++.h>
using namespace std;

void solve(long long N){
long long ans = 0;
while(N%2 == 0){
N /= 2;
}
for(long long i = 1; i <= sqrt(N); ++i){
if(N%i == 0) ans+=2;
}
if(((long long)sqrt(N) * (long long)sqrt(N)) == N) ans--;
printf("%lld\n", 2*ans);
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
long long N;
scanf("%lld",&N);
solve(N);
return 0;
}


### Problem E

#### Problem Statement

There are N kinds of magical gems, numbered 1,2,…,N, distributed in the AtCoder Kingdom.
Takahashi is trying to make an ornament by arranging gems in a row.
For some pairs of gems, we can put the two gems next to each other; for other pairs, we cannot. We have M pairs for which the two gems can be adjacent: (Gem A1, Gem B1), (Gem A2, Gem B2), , (Gem AM, Gem BM). For the other pairs, the two gems cannot be adjacent. (Order does not matter in these pairs.)
Determine whether it is possible to form a sequence of gems that has one or more gems of each of the kinds C1,C2,…,CK

. If the answer is yes, find the minimum number of stones needed to form such a sequence.

#### Constraints

• All values in input are integers.
• 1≤N≤105
• 1≤Ai<Bi≤N
• If i≠j, (Ai,Bi)≠(Aj,Bj).
• 1≤K≤17
• 1≤C1<C2<⋯<CK≤N

### Solution

This problem is typical of Shortest Hamiltonian problems and DP.
As K is really small integer, it is possible to simulate all of the combination of C’s subsets.
We define S as a subset of C.
dp[S][i] :- The smallest value of the length of S, whose pass ends on vertex i
All we want to know is the minimum value of dp[C][i].
Firstly , you have to calculate all pass of each pair of C.
It is possible to calculate in (O(KM)).
Secondly, you can simulate all the possible C’s subsets by using bit, and restore the value in DP.
dp[S][i] = min(dp[S\i][j]+dist(i,j), dp[S][i])
You can achieve the answer by searching the minimum value of dp[C][i].

#include <bits/stdc++.h>
using namespace std;

static const int INF = 1e9;

void solve(int N, int M, vector<int> A, vector<int> B, int K, vector<int> C){
vector<vector<int>> dp((1 << K), vector<int> (K, INF));
vector<vector<int>> cnt(K, vector<int>(K));
vector<vector<int>> g(N);

for(int i = 0; i < M; ++i){
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}

for(int i = 0; i < K; ++i){
vector<int> d(N, -1);
d[C[i]] = 0;
queue<int> q;
q.push(C[i]);
while(!q.empty()){
int f = q.front();
q.pop();
for(int w:g[f]){
if(d[w] == -1){
d[w] = d[f] + 1;
q.push(w);
}
}
}
for(int j = 0; j < K; ++j) cnt[i][j] = d[C[j]];
}

for(int i = 0; i < K; ++i){
dp[1 << i][i] = 1;
}

for(int i = 1; i < (1 << K); ++i){
for(int j = 0; j < K; ++j){
if(dp[i][j] != INF){
for(int l = 0; l < K; ++l){
if(!(i >> l & 1)){
if(cnt[j][l] != -1){
int m = i + (1 << l);
dp[m][l] = min(dp[m][l], dp[i][j] + cnt[j][l]);
}
}
}
}
}
}
int ans = INF;
for(int i = 0; i < K; ++i){
ans = min(ans, dp[(1 << K) - 1][i]);
}
if(ans == INF) puts("-1");
else cout << ans << endl;
}
// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
cin.tie(0);
ios_base::sync_with_stdio(false);
int N, M;
cin >> N >> M;
vector<int> A(M), B(M);
for(int i = 0; i < M; ++i) {
cin >> A[i] >> B[i];
A[i]--, B[i]--;
}
int K;
cin >> K;
vector<int> C(K);
for(int i = 0; i < K; ++i){
cin >> C[i];
C[i]--;
}
solve(N,M,A,B,K,C);
return 0;
}


### Problem F

#### Problem Statement

Given is a sequence A=[a0,a1,a2,…,aN−1] that is a permutation of 0,1,2,…,N−1.
For each k=0,1,2,…,N−1, find the inversion number of the sequence B=[b0,b1,b2,…,bN−1] defined as bi=ai+kmodN

. What is inversion number? The inversion number of a sequence A=[a0,a1,a2,…,aN−1] is the number of pairs of indices (i,j) such that i<j and ai>aj.

#### Constraints

• All values in input are integers.
• 2≤N≤3×105
• a0,a1,a2,…,aN−1 is a permutation of 0,1,2,…,N−1.

### Solution

First, we want to calculate the inversion number of the initial state.
It is not difficult to calculate all of the pairs of indices (i,j) such that i<j and ai>aj.
But this brute-force search’s estimate order is O(N2)(≈$$9\times{10}^{10}$$), we have to think about another approaches.
We can use Fenwick Tree, for calculating the number of such pairs.
Fencick Tree allows us to calculate inversion number in O( $$N\log{N}$$ )

AtCoder