第一回日本最強プログラマー学生選手権-予選- 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 - 種類数 β でも出ている。木のときと同じで辺を入れ替えられるので、まだ使っていない最も重い辺…

第一回日本最強プログラマー学生選手権-予選- C. Cell Inversion

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_c左から見ていき区間を開く閉じるという動きを組み合わせることで解集合を作れる。開く閉じるのどちらを行わなければならないかは今見ている文字と開いている区間の数の偶奇によって一通りに定…

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

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

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(…

Educational Codeforces Round 67 F. Expected Square Beauty

https://codeforces.com/contest/1187/problem/F \documentclass[margin=2mm]{standalone} \usepackage{amsmath,amssymb,bussproofs} \begin{document} %\begin{prooftree} \AxiomC{\(N^2\)} \UnaryInfC{\(E[N^2]\)} \AxiomC{\(\displaystyle \sum_{i} \Pr[x…

AtCoder Beginner Contest F. Small Products

https://atcoder.jp/contests/abc132/tasks/abc132_f We have \[ k \le \left\lfloor \frac{N}{i} \right\rfloor \iff i * k \le N \iff i \le \left\lfloor \frac{N}{k} \right\rfloor. \]\[ \underbrace{\left\lfloor \frac{N}{1} \right\rfloor, \left\lf…

Codeforces Round #567 (Div. 2) E2. A Story of One Country (Hard)

https://codeforces.com/contest/1181/problem/E2The solution is based on the following fact: T(n) = T(x) + T(n - x) + min(x, n - x) = O(n log n)Analysis: Looking at one specific element, when the element moves to the smaller group, it takes …

SRM 761 500pts. SortArray

From 0-1 sorting lemma, we have an algorithm. #include <bits/stdc++.h> using namespace std; struct SortArray { vector<int> verify(int N, vector<int> commands) { for (int i = 0; i < 1 << N; i++) { vector<int> a(N); for (int j = 0; j < N; j++) { a[j] = i >> j & 1; } for </int></int></int></bits/stdc++.h>…

diverta 2019 Programming Contest. E - Balanced Piles

https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_eWe shall explain O(NH) solution by dynamic programming. Suppose that the elements are lined up in ascending order. Consider this operation: choose the leftmost element, and inc…

Google Code Jam 2019 Round 3: Datacenter Duplex

Code Jam - Google’s Coding CompetitionsAdding the edges without making any cycles as many as possible, we finally obtain the answer if the answer exists. We don't have to consider the order of adding edges. It is easy to imagine why this h…

ABC129 E. Sum Equals Xor

https://atcoder.jp/contests/abc129/tasks/abc129_eI solved it by digit DP with ordering monoid. In this DP, we scan the digits from the lowest to the highest as maintaining (order, carry). Iwarete mireba a+b=(a^b)+2*(a&b) kizuku beki. #incl…

Codeforces Round #564 (Div. 1) E. Nauuo and ODT

https://codeforces.com/contest/1172/problem/EHL decomposition. https://codeforces.com/contest/1172/submission/55290873

Codeforces Round #230 (Div. 1) D. Three Arrays

https://codeforces.com/contest/392/problem/DLet \(f_A(k)\) be the minimum i such that \(A_i=k\). If there doesn't exist such a index, we define \(f_A(k) = \infty\). \(f_B(k)\) and \(f_C(k)\) are similarly defined. Then, we want to obtain t…

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>…