AtCoder Beginner Contest 142
Updated:
- Review: 2020-06-05
Source codes
Solutions
A - Odds of Oddness
Just calculate by for-loop.
Or let $M = (N + 1) / 2$. Then flush $M / N$, casting them into double.
B - Roller Coaster
Just calculate by for-loop, too.
C - Go to School
Solution #1
We use vector<tuple<int, int>> V;. We insert $(A _ i, i)$ into $V$ and sort it.
Solution #2
Assume $0$-indexed.
Let $X[i]$ be the $i$-th person who came to the school. Then, it holds that $X[A _ i - 1] = i$. Flush $X$ in the ascending order.
D - Disjoint Set of Common Divisors
Let $M = \mathrm{lcm}(A, B)$. Count the prime factors by your library.
ll A, B;
cin >> A >> B;
Sieve sieve;
auto V{sieve.factor(gcd(A, B))};
cout << V.size() + 1 << endl;
E - Get Everything
Solution
This is done by bit-DP.
Definition
For $c \in \mathcal{P}(N)$, we define $DP[c]$ as follows.
$DP[c] = $ the minimum cost to buy a set of keys that enable us to unlock all the box $b \in c$.
Answer
Flush $DP[2 ^ N - 1]$ if it is not $\infty$, otherwise flush -1.
Initial State
$DP[0] = 0$, otherwise $\infty$.
Transition
For all $(a, k)$, for all $j \in \mathcal{P}(N)$, we execute the following. \[ DP[j \cup k] \gets \min(DP[j \cup k], DP[j] + a). \]
F - Pure
If $M = 0$, the answer is -1. Hereinafter we assume that $M \geq 1$.
Observation
Suppose there exists an induced subgraph $G’$ of $G$ whose in-degree and out-degree of every vertex are both $1$. How is the structure of $G’$? We can easily see that it is a simple cycle and its disjoint union.
However, many algorithm that determines whether the graph has a cycle or not do not detect a simple cycle. If the answer is yes, they just tell us there is a cycle. In this problem, $O(N ^ 2 + M ^ 2)$-solution is allowed.
My solution
We focus on the fact that the smallest cycle must be a simple cycle. We determine the smallest cycle by brute-force method.
Fix an edge $(A, B)$. We use BFS from $B$ to $A$ to search for the shortest path. If we find a cycle combining the path and the edge, this is a possibility of the smallest cycle. We execute this process for all $(A, B)$. The solution works in $O(M (N + M))$-time.
Others
Review 2020-06-05:
A - sample: 3, tle: 2.000, time: 03:17, from_submit: 46:11
B - sample: 3, tle: 2.000, time: 01:24, from_submit: 44:46
C - sample: 3, tle: 2.000, time: 02:37, from_submit: 42:10
D - sample: 3, tle: 2.000, time: 05:54, from_submit: 36:16
E - sample: 3, tle: 2.000, time: 12:11, from_submit: 24:05
F - sample: 3, tle: 2.000, time: 24:05, from_submit: 00:00