https://codeforces.com/contest/1111/problem/DWe first find the generating function of whole elements.\begin{align} (1+x^\bigcirc)(1+x^\bigcirc) \cdots (1+x^\bigcirc) \end{align}Dividing $(1+x^\bigcirc)^{-1}$, we obtain the answer. #include <stdio.h></stdio.h>…

https://codeforces.com/contest/1101/problem/F The following solution is faster than mine. It is based on the fact that the prefix maximum doesn't change at most O(log N) times. https://codeforces.com/blog/entry/64438?#comment-483640There i…

https://atcoder.jp/contests/dp/tasks/dp_zIt is convex hull trick. There are two ways to understrand CHT, the one is using lines, another is using points.We are given N points (a[i], b[i]) on the a-b plain. And then given $x$, please find t…

https://codeforces.com/contest/1097/problem/FA[k] denote the number of multiples of k included in the multiset A. Then the following holds.\[(A \cup B)[i]=A[i]+B[i]\]\[(A \times B)[i]=A[i] \times B[i]\]Clearly, $A \cup B$. Conversely, $a$ …

https://codeforces.com/contest/1091/problem/DThe sum is N(N+1)/2 is equivalent to the sequence is a permutation. For N=10, we have two permutations AAAABBBBBB CCCCDDDDDDWhen BBBBBBCCCC is a permutation, BBBBBB is not sorted in descending o…

https://www.codechef.com/LTIME67A/problems/BESTPATHThe distance array D[i] is filled with zero. Then start Bellman-ford, finally D[i] stores the shortest distance between a certain vertex and vertex i. If there are no negative cycles, we c…

https://atcoder.jp/contests/caddi2018/tasks/caddi2018_bWe can solve this problem ad-hoc. This problem is the special case of the ooooo. if there are at least one game is the game first player wins, the first player also wins in this game.

https://yukicoder.me/problems/no/772The centroid gives the answer. So we should compute centroid quickly and calculate the sum of distances between the centroid and the marked vertices.Looking at a edge, we obtain two trees by removing the…

https://yukicoder.me/problems/no/770The first terms of A[i] can be written asA[1] = B[1] A[2] = max ( min ( B[1] , N - 1 ) , B[2] ) A[3] = max ( min ( B[1] , N - 2 ) , min ( B[2] , N - 1 ) , B[3] ).In general,A[i] = max ( min ( B[1] , N - …

https://codeforces.com/contest/1083/problem/EIf we may use 128bit integers, this problem will be easier than the original one. The most difficult task is the comparison of two rational numbers with large digits. There exists a sophisticate…

UPD: November 11, 2018I believe this property always holds, but I haven't shown the correctness yet. For small n, we can check the correctness partially: https://ideone.com/ljg1Ul. Perhaps, the Dirichlet convolution and the Möbius inversio…

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/BI found an interesting solution. Most of the solutions use a linked list, but it is based on another property. The operation LxR->RxL is similar to LR->RL. LR->RL is we…

https://jag2018summer-day2.contest.atcoder.jp/tasks/jag2018summer_day2_dIt's very interesting. The key property is a queue can be simulated by two stacks. Each push query, you can compute new values of dp in O(mod). Pop query is trivial, j…

Official editorial: https://discuss.codechef.com/tags/sept18/ BSHUFFLE I don't know why this is correct. https://ideone.com/p8tq79 TABGAME View the win-loss table diagonally and alternately. You can realize that the values almost unchange …

http://codeforces.com/contest/1002I had never study quantum computing. I acquired all the knowledge of quantum computing from only a official tutorial. I mean I am not an expert, so this article is unreliable.Write a quantum program | Micr…

A 問題 i 番目と i+1 番目の間をいくつのボールが通過するかを計算できると、それをそのまま。 B 問題 丁度にする必要はなくて、適当に辻褄をあわせることができる、というのが重要な考察。 (i,j) を使う、というのを n×n グリッドの (i,j) の位置に駒を置く…

Chef 側の解説がまだ出てないので、それ読んで思うものがあったら更新します。CHEFAT: この制約なら SIMD O(n^2) 通る。そうは言っても 2 ケースほど TLE になってしまったので、平方分割＋遅延評価で平均的に速くなるようにした。 多くの提出は $\log(1-x)=…

PSHTRG Q=1 で考えてみよう。これは，数列をソートして最大 3 つを見る，それで駄目なら次の 3 つを見るというのを繰り返すことで求められる。この繰り返しが O(log max a) 回しか起きないことに気がつくと，50th max 程度まで保持するセグメント木があれば…

https://arc091.contest.atcoder.jp/tasks/arc091_dK を固定して Grundy 数 g(n) を考える。実験すると g(Kn)=n であることに気づける。g(Kn)=n ということは，その直前 n 個を見ると 0..n-1 の順列になっている。これに気がつくと漸化式が見える。 実験から…

最近いろんな作業を Rust で書いてるんですが、Rust やってると Haskell が書きたくなってくる。664はまだです。 661 ハローキティはりんご3個分 import Control.Monad main = getLine >> getContents >>= mapM_ (putStrLn . solve . read) . lines solve n …

問題概要 n × n のグリッドが与えられる。スタート地点は (sx,sy) でゴール地点は (gx,gy) である。ユークリッド距離が d 以上の点に移動できる。移動回数の最小値を求めよ。ただし到達不可能な場合は -1 を出力せよ。 誤解法 四隅だけ使えばよく，到達でき…

https://beta.atcoder.jp/contests/arc089/tasks/arc089_bこの解説では、座標を（横,縦）で表している。$(x,y)$ が黒であることと $(x \bmod 2K, y \bmod 2K)$ が黒であることは同値である。 $(x,y)$ が白であることと $(x+K,y)$ が黒であることは同値である…

重心を求めるコードが間違っていたので修正しました（sz[v] >= x / 2ではなくsz[v] > x / 2が正しい）。計算量に影響はないです。2018-01-22 21:25http://codeforces.com/contest/914/problem/E重心分解による分割統治法で解く。重心を c としたとき、回文パ…

AND, OR, XOR 畳み込みを使う。ANDは分割統治、ORは高速ゼータ変換と高速メビウス変換、XORは高速アダマール変換を使うことで処理できる。n=2^17 としたとき、ANDがO(n log n)、ORがO(n log^2 n)、XORがO(n log n)になっている。OR も O(n log n) で行けるの…

http://codeforces.com/problemset/problem/916/ELC-tree は根を変更するクエリと lca を求めるクエリを捌ける。ET-tree は辺の追加・削除と連結成分全体に x を一様加算するというクエリが捌ける。これらを組み合わせることで容易に解くことができる。 #inc…

http://codeforces.com/problemset/problem/916/D誤読さえしなければ解法は自明。永続multiset と永続配列があれば良い。永続multisetは使いまわせそうな形で再実装した。内部的には LLRBtree を用いている。 ポインタ型が64bitというのが厄介で、nodeにポイ…

A問題 端に追いやられたら負けである。よって相手に近寄るように移動するのが最適行動になる。この戦略を実際にシミュレートすることで答えが得られる。 main = do [n, a, b] <- map read . words <$> getLine putStrLn $ turnA n a b turnA :: Int -> Int -…

http://codeforces.com/contest/908/problem/G 解法 上の桁から決めていく桁 DP により解くことができる。ソート済み整数はレピュニット数*1 の和で表せるという性質が役に立つ。たとえば 1122244 という整数の場合 1122244 1111111 11111 11 11という表現が…

E: Smuggling Marbles - AtCoder Regular Contest 086 | AtCoder 解法 縮約解について説明する。よく考えるとマージテク解と本質的に同じ。深さが等しい頂点をまとめて計算できるのは自明だと思いたい。普通にやると$O(depth\times n)$ だが、各深さごとに木…

Rust で書き直したのだが Rust で提出できなかった。そういえばクロージャの再帰ってできるんだろうか。グラフを引数に渡すのくどい。パスを交差させる必要はなくて、互いに素なものだけ考慮すれば良い。これは適当な木DPで解ける――具体的には、状態を(dp0: …