https://atcoder.jp/contests/abc141/tasks/abc141_fIf the number of ones on i-th bit is odd, 2^i is always added to the answer no matter how we classified them. Therefore, we can use an usual approach for finding lexicographically maximum. W…

https://codeforces.com/contest/1209/problem/FSuppose that we already understand the official editorial. Official solution is really simple but I didn't come up with this algorithm without reading it. Instead, I will explain another way to …

https://yukicoder.me/problems/no/879Struct generator is available on Github now. github.com The lazy information on LZ segtree usually has linearity. So, it can be expressed by a matrix. This time, we prepare a vector having (value, odd or…

https://codeforces.com/contest/1217/problem/FIt didn't take long to come up with a solution, but I couldn't remove bugs during a contest.I always make mistakes due to index variables name and loop range. To avoid them, I wrote a code which…

https://codeforces.com/contest/1214/problem/FIf we have to solve sequence version instead of a circular sequence, greedy solution will work. Specifically, we first sort both sequences according to its coordinate, then match elements having…

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_l?lang=jaSince $(x \bmod 10^K) = 0 \iff (x \bmod 2^K) = 0 \land (x \bmod 5^K) = 0$, we can use brute-force. I got TLE when using non-constexpr mod. #include <bits/stdc++.h> #define rep(i, n) for (int i </bits/stdc++.h>…

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_f Before explaining the solution, we first explain the four typical problems. These often appears in various counting problems. Problem 1 How many are there N non-negative integer…

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_eWe should calculate not the maximum spanning forest but the maximum pseudo forest. K - 種類数 β uses similar property. We know we can swap edges in any tree, and we can also swap…

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_cLooking at elements from left to right, we'll decide to open or close an interval. We can determine which operation we should do by the parity of the number of intervals currentl…

https://codeforces.com/contest/1207/problem/GI'm not good at string problems, but I have solved it luckily. First we construct the Aho-Corasick of the query strings. If N strings is produced by type 2 except the first string, we can direct…

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

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

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…

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…

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…

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 …

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…

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…

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…

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…

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

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…

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

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…

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…

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 …

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

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…

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…