第一回日本最強プログラマー学生選手権-予選- F - Candy Retribution

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_f解き方を書く前によくある数え上げの問題を四つ取り上げておく。いずれも問題を解くときによく現れるものである。 問題 1 となる非負整数 $x_1,\ldots,x_N$ は何通りあるか。これはよくある重…

第一回日本最強プログラマー学生選手権-予選- E - Card Collector

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_e最大全域森ではなく最大なもりを求めればいい。答えの形がなもりグラフになるようなものは K - 種類数 β でも出ている。木のときと同じで辺を入れ替えられるので、まだ使っていない最も重い辺…

Educational Codeforces Round 71 (Rated for Div. 2) G. Indie Album

https://codeforces.com/contest/1207/problem/G文字列は苦手だけど運よく解けた。クエリ側の文字列集合に対してエイホコラシック法を使う。まずＮ個の文字列が最初を除いてタイプ２のみで作られているとすると エイホコラシック法をそのまま使って解ける。…

CF 581 Div2. E. Natasha, Sasha and the Prefix Sums

https://codeforces.com/contest/1204/problem/EI just wanted to draw figures. #include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); i++) #define repr(i, n) for (int i = (n) - 1; i >= 0; i--) using namespace std; using ll = long long; constexp</bits/stdc++.h>…

ABC 138 screencast

https://atcoder.jp/contests/abc138/taskshttps://drive.google.com/file/d/15FST30n57Kb4yDPkUfNV4E4XR8qL8XLN/viewProblem C We should use items in ascending order because the first item thrown into the bin is finally multiplied by 1/2**(N-1). …

CF 579 Div. 3 F Complete the Projects

Problem - F2 - CodeforcesI wonder why my solutions passes. My solution is quite different from the official solution. We assume that the optimal solution forms like this. In the following figure, elements are sorted in descending order acc…

CF 578 Div 2 E. Compress Words

https://codeforces.com/contest/1200/problem/EThe array used in KMP algorithm is useful to compute the length of common string. Someone may think this algorithm is squared time, but we don't have to treat whole string, so it works in linear…

ABC 137 screencast

F - Polynomial Constructiondrive.google.comProblem C: I forget a hashtable whenever I use C++. C++'s hashtable is really dangerous because it doesn't use randomness.Problem D: Considering reversed time, the items we can choose increases. T…

ABC 136 F. Enclosed Points

https://atcoder.jp/contests/abc136/tasks/abc136_fI solved problems with F# because I don't want to use C++. Although I prefer to OCaml, I gave up it due to 64bit integers. I use verbose F# because in off-side rule we can't restore indents …

ABC134 F. Permutation Oddness

F - Permutation OddnessAny permutation can be represented as a permutation. For example, [0,8,3,6,9,7,2,5,1,4] can be drawn as the following graph.The oddness is the sum of the number of edges across over the lines. Let us consider doing D…

SRM763 1000pts ProductAndProduct

The answer is $[x^M] \frac{1}{{}_N \mathrm{H}_M}\prod_{i=1}^{N} \left( C_i + (C_i+1)x + (C_i+2)x^2 + \cdots \right).$We already know$1+x+x^2+\cdots = \frac{1}{1-x}.$\begin{align} x+2x^2 + 3x^3 + \cdots &= x \frac{d}{dx} (1+x+x^2+\c…

AtCoder Grand Contest 035. B. Even Degrees

https://atcoder.jp/contests/agc035/tasks/agc035_bWe can restated the problem as follows. There are people on vertices with odd degree. When we swap the direction of the edge, the human on the end-points moves on the edge. If both endpoints…

Codeforces Round #573 (Div. 1) D. Tokitsukaze and Strange Rectangle

https://codeforces.com/contest/1190/problem/DIf there is a point on the boundary of the rectangle, strictly speaking, this point is not contained in the rectangle, but we can consider it is contained in. The reason why we can include it by…

Codeforces #573 (Div. 1) C. Tokitsukaze and Duel

https://codeforces.com/contest/1190/problem/CWe can return the same state by doing the same action. If we will be defeated, we should give them the same state. Therefore, this game will not end.However, we cannot imitate the first action. …

AtCoder Beginner Contest 133 F Colorful Tree

atcoder.jpThere are several solutions. If we may use wavelet matrix, this task becomes very easy. This method works in the online version, that is, we can reply the answer efficiently if we can't know the next query before do the previous …

Codeforces Round #572 (Div. 1) B. Count Pairs

https://codeforces.com/contest/1188/problem/B\begin{align} & (x+y)(x^2+y^2)=k \\ \iff & x^3 + x^2 y + x y^2 + y^3 = k \\ \iff & \frac{x^4-y^4}{x-y}=k \\ \iff & x^4 - kx=y^4 - ky \end{align} My first approach is to solving cubic equation. I…

Codeforces Round #572 (Div. 1) C. Array Beauty

https://codeforces.com/contest/1188/problem/CSuppose that the array is already sorted. Let f(x) be the number of subarrays such that any difference between adjacent elements is greater than or equal to x. We then have the answer as f(1)+f(…

AGC034 F - RNG and XOR

https://atcoder.jp/contests/agc034/tasks/agc034_fLet a and b be arrays with 2^n elements. a*b denotes the xor convolution of a and b.Let x=[x[0], x[1], ... , x[2^n-1]] be the answer and p=[p[0],...,p[2^n-1]] be the probability that i-th el…

ABC127 F - Absolute Minima

https://atcoder.jp/contests/abc127/tasks/abc127_fMaintain the first smallest half of a[i] and the second smallest half of a[i], call them L and R respectively. Then, the answer is sum(R)-sum(L) if L and R have the same number of elements.T…

Codeforces #559 (Div. 1) A. The Party and Sweets

https://codeforces.com/contest/1158/problem/AI didn't know the iterator has operator[] *1. I found this when I read his solution. #include <vector> #include <cassert> using namespace std; int main() { vector<int> a{1,2,3,4,5}; assert(a.begin()[0] == 1); assert(</int></cassert></vector>…