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

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 コのグループがある のふたつ。…

Lunar New Year and a Recursive Sequence

https://codeforces.com/contest/1106/problem/Fリサンタイスウについて かく。ホウ 7 では 3 のベキをならべると $[1,3,3^2,3^3,3^4,3^5]=[1,3,2,6,4,5]$ になるけど 1,2,3,4,5,6 が すべて あらわれている。こういうかずは ゲンシコンだとかセイセイゲンだ…

Connecting Cities

https://atcoder.jp/contests/keyence2019/tasks/keyence2019_eブルーフカで やった。こういう もっとも おもいエッジだけなら わかる みたいなのは ブルーフカが うまくいきやすいかも。ブルーフカについて かくまえに MST でよくつかうセイシツに ふれよう…

Educational Codeforces Round 58 G (Zero XOR Subset)-less

https://codeforces.com/contest/1101/problem/Gみためからして ランクだから ランクをもとめればいい。ルイセキワをとると それぞれのセグメントは S[i1] , S[i1] xor S[i2] , S[i2] xor S[i3] , ... という あたいになる。これらをつかって つくれるあたい…

Educational Codeforces Round 58 F Trucks and Cities

https://codeforces.com/contest/1101/problem/F したのコメントの やりかたのホウが はやそうだ。サイダイチが かわるカイスウのキタイチが O(log N) であることを うまくいかしていて すごい。https://codeforces.com/blog/entry/64438?#comment-483640こ…

Educational DP Contest J Sushi

https://atcoder.jp/contests/dp/tasks/dp_jときかたは おいといて つぎの モンダイを かんがえてみよう。1,2,3,...,N の ますが まっすぐに ならんでいる。あなたは はじめに ます 1 にいる。コインをなげて おもてがでたら ひとつすすんで うらがでたら ひ…

Educational DP Contest Z Flog 3

https://atcoder.jp/contests/dp/tasks/dp_zconvex hull trick だね。CHT は チョクセンで かんがえる やりかたもあるけど テンでも できる。$a$-$b$ ヘイメンに N コのテン $(a_i,b_i)$ がある。$x$ があたえられるから $a_i x + b_i$ が もっとも おおきく…

Codeforces Hello 2019 F. Alex and a TV Show

https://codeforces.com/contest/1097/problem/Fマルチセット $A$ のなかに $k$ のバイスウが いくつあるかを $A[k]$ とかくことにする。このとき\[(A \cup B)[i]=A[i]+B[i]\]\[(A \times B)[i]=A[i] \times B[i]\]がなりたつ。$A \cup B$ はあきらかだけど …

Good Bye 2018 D New Year and the Permutation Concatenation

https://codeforces.com/contest/1091/problem/Dワが N(N+1)/2 というのは そのレツが ジュンレツであることと おなじ。(いいかえなくても おなじような はなしの ながれになる) N=10 で たとえば ふたつのジュンレツが つぎのように ならんでるとする。 AAA…

December Lunchtime 2018 Find Best Path

https://www.codechef.com/LTIME67A/problems/BESTPATHキョリのハイレツ D[i] をゼロでうめておいてから ベルマンフォードをすると D[i] には あるノードから i への サイタンキョリがはいる。もしネガティブサイクルがないのなら これでよい。ベルマンフォ…

CADDi D Harlequin

https://atcoder.jp/contests/caddi2018/tasks/caddi2018_bこのモンダイは ふかいことを かんがえなくても とけるけど イッパンのばあいでも とけるんだよね。よくかんがえると あきらかだから キづいてるひとも いそう。どういうことかというと センテヒッ…

yukicoder 772 Dynamic Distance Sum

https://yukicoder.me/problems/no/772こたえがジュウシンなのは すぐわかるとおもう。ジュウシンを サクサクもとめて ジュウシンから しるしのついた テンへの キョリの ソウワをもとめられれば いいのね。あるヘンをみたとき そのヘンをきると ふたつの き…

yukicoder 770 Median Sequence

https://yukicoder.me/problems/no/770A[i] のはじめをいいかえるとA[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] )となる。イッパンにはつぎのようになる。A[i] = max ( min (…

CF #526 Div.1 E: The Fair Nut and Rectangles

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…

Compute exp and log of formal Dirichlet series in O(n log^2 n) time

Maybe this already exists and some of them are unreliable. The exponential of a formal Dirichlet series can be written as\begin{align} \exp\left( \frac{a_2}{2^s} + \frac{a_3}{3^s} + \frac{a_4}{4^s} + \cdots \right) = \exp\left( \frac{a_2}{…

Codeforces #519 F. Make It One

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…

Exponential Function Evaluation

This article shows an implementation of the exponential of a formal power series. This runs in O(n log n) time. I compute the nth term of the partition function for benchmark.https://ideone.com/m1LAWr [1] is a standard reference of formal …

Analysis of path halving for DSU

Consider the following implementation of DSU. This approach is shown in [1, 2]. int find(int x) { while (p[p[x]] != p[x]) x = p[x] = p[p[x]]; return p[x]; } void link(int x, int y) { p[find(x)] = find(y); } Surprisingly, both find and link…

Find the nth partition number mod p in O(n log n)

This algorithm comes from a study of subset sum [1]. exp, log, recip are described in [2]. The generating function of partition number is \[ (1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^3+x^6+\cdots)\cdots. \]The logarithm of this function is\[ …

Regarding linear time implementation of shakutori

I introduced this problem before: https://pekempey.hatenablog.com/entry/2018/09/18/085432This technique can be applied to shakutori (also known as two pointers or sliding window). Its implementation is a little complicated but it might be …

RMQ using BIT

An implementation of this document: https://ioinformatics.org/journal/v9_2015_39_44.pdfUpdate O(log n), query O(log n). Update is slightly slower than segtree based RMQ, but query is slightly faster. I have written it once before, but it i…

Pivots

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…

Knapsack and Queries

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…

September Challenge 2018

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 …

digit dp

digit dp について書く。ここでは $n$ 以下の自然数の総数を求める問題を扱う。明らかに答えは $n+1$ だけど、見方を変えて解いてみれば、digit dp の本質がみえると思って書いてみた。$n=31415$ として樹形図で列挙すると次のようになる。最も下のノードた…

Microsoft Q# Coding Contest - Summer 2018

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…

Euler tour tree implementation using a circular skip list

I implemented an euler tour tree using a skip list. Typically, a skip list is used as dictionary structures. However this skip list is merely used as a doubly linked list which can be joined and split fast, and can determine whether given …