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

いろはちゃんコンテスト Day 1

I - リスのお仕事 Let us consider a graph whose vertices are (vertex ID, The cost used at last). If there exists a vertex having a lot of kinds of costs, it is difficult to update the distance efficiently. To perform efficiently, we prepare…

Codeforces Round #551 (Div. 2) F. Serval and Bonus Problem

https://codeforces.com/contest/1153/problem/FWithout loss of generality, we assume \(L=1\). The probability that x is covered by a single interval is \(2x(1-x)\). Let \(f(x)=2x(1-x)\), then the expectation of the length covered by exactly …

GCJ 2019 Round 1A

Pylons If we properly take some k, (i,j) -> ((i+k)%H,j+1) -> ((i+2k)%H,j+2) -> ... is a path satisfying the given conditions. I don't have any proof, but at least under this constraints, it is correct. In addition, (H,W)=(4,4) doesn't work…

Codeforces Global Round 2 H - Triples

https://codeforces.com/contest/1119/problem/H Preliminaries Hadamard transform of 3bits is almost the same as Fourier transform of 2*2*2. A polynomial of x,y,z can be represented as 8 coefficients of 1,x,y,z,xy,xz,yz,xyz. Hadamard transfor…

GCJ Qualification Round 2019

D Using binary representation, we can determine the missing numbers. Someone may think 10 bits are necessary, but 5 bits are sufficient. 4 bits are also ok?For simplicity, we explain the solution for small cases. We send the following 10 s…

yukicoder 3046 yukicoderの過去問

https://yukicoder.me/problems/no/3046(First solution) M denote the maximum value of A. Then, the answer is\[ [x^{M - 1}] (x^{M + K - 1} \bmod (x^{M}-x^{M - a_1}-\cdots - x^{M-a_N})). \]https://yukicoder.me/submissions/334973(Second solutio…

Codeforces Round #549 (Div. 1) C. U2

Draw parabolas satisfying the given condition. Then, an envelope appears *1.This is similar to the convex hull. Actually, Graham scan *2 also works in this case. There is another solution using the the convex hull of (x[i],y[i]-x[i]*x[i]).…

エクサウィザーズ2019 D Modulo Operations

https://atcoder.jp/contests/exawizards2019/tasksDynamic programming. Look at the elements in ascending order.Let dp[i][j] be the answer of the sub problem replacing a[0],...,a[N-1] with a[0],...,a[i-1] and replacing X with j. Suppose a[0] …

Codeforces #548 (Div. 2) D. Steps to One

题目链接 https://codeforces.com/contest/1139/problem/Df(k) 表示 a[1],...,a[k] 的最大公约数不是 1 的概率。然后答案是 1+f(1)+f(2)+f(3)+...。a[1],...,a[n] 的最大公约数是 1 和 a[1],...,a[k] 不能被 2,3,4,... 整除等价。所以由容斥原理可以计算 f(k…

yukicoder no. 803 Very Limited Xor Subset

https://yukicoder.me/problems/no/803Once we realize this problem is related to a system of linear equations, this problem has been almost solved. All we have to do is to find the number of solutions of the given linear system.Let u be a so…

yukicoder 802 だいたい等差数列

https://yukicoder.me/problems/no/802Let us find the number of \(x_1, \ldots, x_N\) such that \(x_1 + \cdots + x_N \le M\) and \( x_1 \ge 0\), \(0 \le x_i \le D_2-D_1 \) for \(2\le i \le N\). The generating function can be written as\begin{…

AtCoder Grand Contest 031 D: A Sequence of Permutations

https://atcoder.jp/contests/agc031/tasks/agc031_dThis article is almost the same as the official editorial. I just want to write English and Chinese (A month has passed since I started learning Chinese. If you cannot read my Chinese, I'm s…

Codeforces Round #546 (Div. 2) E. Nastya Hasn't Written a Legend

https://codeforces.com/contest/1136/problem/EIf we have a segment tree which can perform the following operations, we can directly solve this problem.1. For $l \le i \le r$, $A_i \gets \max(A_i, x)$ 2. For $l \le i \le r$, $A_i \gets A_i +…

早稲田大学プログラミングコンテスト F. RPG

https://atcoder.jp/contests/wupc2019/tasks/wupc2019_fThe solution is easy for us, so I do not explain it here. Instead, I shall explain how to reduce the vertex cover problem to the minimum st cut problem. This technique is also known as K…

Educational Codeforces Round 61 B. Discounts

https://codeforces.com/contest/1132/problem/BI was going to solve all the problems by Rust. But, I lost the motivation due to TLE in the problem B. I rewrite the I/O after the contest, then my solution becomes faster than the C++'s one. I'…

Codeforces Round #545 C. Museums Tour

https://codeforces.com/contest/1137/problem/C We do not need to use GCD or something. We prepare the graph with N×D vertices and do SCC on it. Then, we can do dynamic programming on the contracted graph. The total time complexity is O(ND),…

Codeforces Round #545 (Div. 1) B. Camp Schedule

Problem Link: https://codeforces.com/contest/1137/problem/BThere are a lot of ways to solve this problem. For example, we can use Z-algorithm, rolling hash and suffix array (suffix array might be too slow for this constraints). This proble…

Educational Codeforces Round 61 E. Knapsack

https://codeforces.com/contest/1132/problem/EUsing a technique like digit-dp, this problem can be reduced to the 0-1 problem. I define the table dp[2000][1 My implementation is a little noisy. https://codeforces.com/contest/1132/submission…

Microsoft Q# coding contest winter 2019

https://codeforces.com/contest/1116I solved 11 problems. The remaining two problems are difficult for me. B1 Let us create a function which converts |000> to the first state, say f. We only have to apply (Adjoint f) to the given state. We …

Microsoft Q# Winter 2019 warmup

This article is written for my future self. The following explanation isn't clear.Official solutions are here https://assets.codeforces.com/rounds/1115/warmup-editorial.pdf. Some of them use useful functions, especially G2 and U3. I’ll rev…

日経 G Greatest Journey

An optimal move is like this.Fix the start vertex r. The red route is better than the orange one. In general, if the maximum weight of the edges on the r-v path is greater than the weight of the edge between v and parent(v), then v is unne…

日経 F Flights

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_f The orange course is shorter than the black one. The orange course is shorter than the black one. Therefore, points on the orange area are unnecessary after this move. P…

Codeforces Round #539 B. Sasha and One More Name

I explain the bonus problem described in the official editorial.The following code runs in O(n). If A+B and B+A are both palindromes and A+B ≠ B+A, then A+AR and B+BR can be expressed by the repetition of a palindrome. (see the below figur…

Codeforces Round #539 D. Sasha and Interesting Fact from Graph Theory

This problem requires advanced knowledge. Fix the number of nodes laid on ab path, say k. Removing the edges on ab path, k connected components appear. The number of labeled forest with n vertices with r connected components (however, 1,2,…

CF#538 F. Please, another Queries on Array?

https://codeforces.com/contest/1114/problem/FMy solution is the fastest on Feb 16, 2019. The discrete logarithm is one of the keys for speed. (This approach is based on deja-vu's solution.)https://codeforces.com/contest/1114/submission/499…

CF#538 E. Arithmetic Progression

問題 https://codeforces.com/contest/1114/problem/E 解説 https://codeforces.com/blog/entry/65136 初項 a[0] は わかる。0 から n-1 の乱数 r[0],...,r[29] を つくって d=gcd(a[r[0]] - a[0], a[r[1]] - a[0], ... , a[r[29]] - a[0]) をもとめると 高…

CF#537 | Destroy the Colony

https://codeforces.com/contest/1111/problem/Dならびは あとであたえればいいから ただのナップサック。ならびを おぼえたままでも DP できるけど テイスウバイでしんだから えだがりして とおした。でも ナップサックのホウが ラクだね。ハイレツをつかい…

CF#537 | Tree

https://codeforces.com/contest/1111/problem/Eねに ちかいノードから グループをきめていく。ノードたちを ねからの とおさで ならびかえて そのならびで DP する。ジョウタイは はじめの i コのノードのグループをきめた j コのグループがある のふたつ。…