AtCoder Beginner Contest 190

Problem A

実行時間制限: 2 sec / メモリ制限: 1024 MB

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.

Problem B

実行時間制限: 2 sec / メモリ制限: 1024 MB

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≤10⁹
• 1≤Yi≤10⁹
• 1≤S≤10⁹
• 1≤D≤10⁹

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

実行時間制限: 2 sec / メモリ制限: 1024 MB

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
[latex] 2^K [/latex]
, because K_i‘s people can chose C_i or D_i.
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.

Problem D

実行時間制限: 2 sec / メモリ制限: 1024 MB

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≤10¹²
• N is an integer.

Solution

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

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].

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×10⁵
• a0,a1,a2,…,aN−1 is a permutation of 0,1,2,…,N−1.