Codeforces #630

https://codeforces.com/contest/1332 A Exercising Walk xとyは独立に考えてよい。どんな移動方法であっても最終位置は同じである。隣接する2マスをジグザグ動くことで、始点から終点へ一直線に移動することができる。これがもっとも無駄のない動きであ…

AtCoder Beginner Contest 159 感想

https://atcoder.jp/contests/abc159F 問題。$F_i=1+x^{A_i}$ とする。多項式 $G_i$ を次のように定める。\begin{align} G_i = (F_i) + (F_i \times F_{i-1}) + (F_i \times F_{i-1} \times F_{i-2}) + \cdots + (F_i \times \cdots \times F_1) = \sum_{j=1…

AtCoder Beginner Contest 156 F - Modularness

見てすぐに苦手な問題だと理解したけど、結果としては思いつけたし良かった。https://atcoder.jp/contests/abc156/tasks/abc156_fまず D の各項を M で割ったあまりに置き換える。ただし割り切れた場合は 0 ではなく M としておく。このようにしても答えは変…

AtCoder Beginner Contest 155 F. Perils in Parallel

F - Perils in Parallel以下は公式解説とほとんど同じですが、捉え方がすこしだけ異なります。スイッチのオフとオンをそれぞれ0と1とします。ある範囲のスイッチを切り替えるというのは、法を2としてある範囲に1を足すことに言い換えられます。ある範囲…

yukicoder No.980 Fibonacci Convolution Hard

https://yukicoder.me/problems/no/980もとの数列の母関数を二乗したものが 2000000 項目までわかればよい。もとの数列の母関数が分数の形で書けるので、二乗しても分数の形で書ける。分子と分母が求まったら、分数の形から無限和の形に書き換えればよい。こ…

AtCoder Beginner Contest 152 F. Tree and Constraints

F - Tree and Constraints条件が一つだけの場合を考えてみます。つまりある頂点からある頂点の道の上に黒辺が少なくとも一つある、という条件のもとでの数え上げを考えます。全体から条件を満たさないものを引くことを考えると解けます。条件が二つある場合…

Educational Codeforces Round 80 A から E

A. Deadline x と d/(x+1) が近いほど値が小さくなりそうなので d の正の平方根の前後を 100000 くらいを探したんだけど、これやるなら 1 から 1000000 を全探索で良かった。 B. Yet Another Meme Problem b の桁数を L だと仮定する。そうすると与えられた…

AtCoder Beginner Contest 151

Tasks - AtCoder Beginner Contest 151 A 言語を間違えてしまい 1WA。char 型に一を足すと int 型になることを考えてなくて 1WA。インクリメントなら壊れません。 B N 掛ける M 引く総和をそのまま出力して 1WA。点数に上下限があることにきづいて修正しまし…

第六回ドワンゴからの挑戦状 C Cookie Distribution

Xi, j を i 番目の人が j 日にクッキーをもらうときに一となる確率変数とすると、うれしさは (X1,1 + ... + X1, K) × ... × (XN, 1 + ... + XN, K) とあらわせる。これを展開したときの項をひとつ固定してみると次の図のようになる。対称性があるので左下か…

AtCoder Beginner Contest 150 D. Semi Common Multiple

https://atcoder.jp/contests/abc150/tasks/abc150_d初項 $A_i / 2$、公差 $A_i$ の等差数列が $N$ 個ある。これらの共通部分を求め、そのうち 1 以上 M 以下のものがいくつあるか求めればよい。ふたつの等差数列の共通部分はまったく存在しないかふたたび等…

AtCoder Beginner Contest 150 E. Change a Little Bit

https://atcoder.jp/contests/abc150/tasks/abc150_eC を降順に整列しても答えは変わらない。費用は、「すべての S と T に対して「すべての位置 k に対して S と T が異なるなら $C_k$ 掛ける何かを足す」」であるが、「すべての位置 k に対して「すべての …

Codeforces 614 Div. 2 A から F

A ありうる最も左の点と右の点がわかれば、その間の点はすべてありうるので植木算。自分は気づかなかったが、要素数足す一が答え。 B 連続部分列の和の最大値は動的計画法で求められる。この問題では列全体が答えにならないようにしなければならない。そこで…

Codeforces Hello 2020

https://codeforces.com/contest/1284Problem A. Since this system is similar to 十干十二支, so I immediately understood this problem. Maybe, the two are the same.Problem B. "The sequence is ascent" is the same as "the sequence is not non-inc…

yukicoder No.950 行列累乗

https://yukicoder.me/problems/no/950だいぶ手間取った。対角化は頭にちらついてはいたけど経験上、行列の成分が任意のときにこれをやると沼にはまるので避けた。結果として避けてよかったのかな。たぶんどっちを選ぶかは好みの問題な気がする。行列でなく…

yukicoder No.940 ワープ ε=ε=ε=ε=ε=│;p>д<│

https://yukicoder.me/problems/no/940いくつかの組合せ問題は多項式によって解くことができます。これがどういうことか、簡単な例を取り上げて説明します。サイコロを二個振ったとき目の和が k となる場合の数を求める問題を考えましょう。いきなりですが次…

AtCoder Beginner Contest 144 F - Fork in the Road

https://atcoder.jp/contests/abc144/tasks/abc144_f問題文には書いていないが制約に書いてある $s_i 動的計画法によって期待値を求められる。それは以下の式によって得られる。\begin{align} E_i = \frac{1}{|N(i)|} \sum_{ j \in N(i)} (E_j + 1) \end{ali…

AtCoder Beginner Contest 144 E - Gluttony

https://atcoder.jp/contests/abc144/tasks/abc144_e積の最大値を $x$ 以下にできるかどうかを二分探索する。$F_i$ は降順に並んでいるものと仮定する。このとき各 $F_i$ と対となる値は $\lfloor x/F_i \rfloor$ 以下になるはずである。よって$A$ を自由に…

AtCoder Beginner Contest 144 D - Water Bottle

https://atcoder.jp/contests/abc144/tasks/abc144_dまず水をなみなみ入れておいてそれを傾けていったとき水の量がちょうど $X$ になる角度を求めればいい。どこまで傾ければいいかは二分探索によって求められる。二分探索するには傾けた角度に対してどのく…

AtCoder Beginner Contest 143 E Travel by Car

https://atcoder.jp/contests/abc143/tasks/abc143_eBecause I hear that O((n + m) log n) Dijkstra is slow, I tried that too. That's indeed slow. I hear that fibonacci heap is faster than binary heap, so I tried that too. That's indeed fast. B…

October Challenge 2019: Faulty System

Official Editorial https://discuss.codechef.com/t/cnnct2-editorial/40191Please consider this problem: Please construct two trees on each graph so that the number of edges which appears in both trees as many as possible. This problem is the…

October Challenge 2019 Queries on Matrix

Official Editorial : https://discuss.codechef.com/t/jiit-editorial/39300My solution is really complicated. As far as viewing other people's solutions, more simple solution exists.We can consider the row and the col independently, so it is …

Yosupo Judge : Exp of Formal Power Series

https://judge.yosupo.jp/problem/exp_of_formal_power_seriesI implemented the algorithm to compute exp(f(x)) by divide and conquer described in https://arxiv.org/abs/1807.11597. To improve performance, I did the following. Precalculate the F…

Codeforces #589 E. Another Filling the Grid

https://codeforces.com/contest/1228/problem/EI used inclusion-exclusion principle. Let R_i be the event that the minimum of i-th row is not 1, and C_i is similarly defined. Then the answer is can be written as\begin{align} | \overline{R_1}…

CF 588 C. Konrad and Company Evaluation

https://codeforces.com/contest/1229/problem/CStraight forward solution runs in O(Q sqrt(N)). Let's prove this fact by potential analysis. We define the potential of this problem as the sum of the degrees of the vertices whose in-degree is …

CF #588 D. Wojtek and Card Tricks

https://codeforces.com/contest/1229/problem/DConsider this problem : How many permutations can be represented by the product of P[L] ... P[R]? In other words, please find the order of the group generated by P[L] ... P[R]. Then, this answer…

AGC038 B - Sorting a Segment

https://atcoder.jp/contests/agc038/tasks/agc038_bRolling hash is useful in this problem. For example, we are given 2013754689 and K=4, then suppose that we are now looking at 20[1375]4689. In this case, we write "1", "3", "5", "7" on the s…

AGC 038 C - LCMs

https://atcoder.jp/contests/agc038/tasks/agc038_cBefore solving this task, solve this problem.\begin{align} f_k = \sum_{\mathrm{gcd}(i, j)=k} a_i b_j. \end{align}We can find this from the following by inclusion-exclusion principle.\begin{a…

AGC 038 D - Unique Path

https://atcoder.jp/contests/agc038/tasks/agc038_dType 0 has transitivity, that is for all a, b, c, if there is exactly one path between a and b and there is exactly one path between b and c, then there is exactly one path between a and c. …

Educational Codeforces 73 E. Game With String

https://codeforces.com/contest/1221/standingsFirst, if there is a segment whose length x is B Second, if there are two or more segments whose length x is 2B, the second player always wins. The optimal movement of the second player is to ma…

ABC141 E. Who Says a Pun?

https://atcoder.jp/contests/abc141/tasks/abc141_eThere exists the way to find LCS (longest common prefix) using DP. LCS, LCP and edit distance are typical problems of string DP. Since the ant book describes only LCS, LCS may be not well kn…