AtCoder Beginner Contest 169 解説

https://atcoder.jp/contests/abc169 C問題 decimalを使えば10進数の小数計算は(28桁まで)誤差なしにできる。使い方を忘れてたので調べた。 from decimal import * A, B = map(Decimal, input().split()) print(int(A * B)) D問題 p,p^2,p^3,...の順に使う…

Codeforces Div.1 #641

https://codeforces.com/contest/1349/myABCの3AC10WA。頭が悪かった。 A問題 素因数ごとに分けてよくて、入力は$1,p,p^2,p^3,\ldots$だけで構成されていると思っていい。このときの答えは最小から二番目の値になる。 B問題 ややこしい解法になった。Kの隣に…

AtCoder Beginner Contest 167 解説

https://atcoder.jp/contests/abc167/tasks36位。AからDはpythonで提出。EFはC++。 A問題 startswithという接頭辞になっているかどうか判定する関数があるのでそれを使った。 def ZZ(): return list(map(int, input().split())) def Z(): return int(input()…

AtCoder Beginner Contest 165 解説

https://atcoder.jp/contests/abc165ABCの存在を忘れてて遅刻した。108位。EがWAで最初のWAは偶奇によるバグでそれはすぐ直せたんだけど、二つ目のWAに手間取った。原因は出力のしすぎだったんだけど、Mが最大のケースでデバッグしてたせいでバグに気付くの…

AtCoder Beginner Contest 164 感想

https://atcoder.jp/contests/abc164/tasks15位。 D問題 前から見ても後ろから見ても解けることは知ってて、考察の難しさも変わらない。前からやると逆元が必要で、後ろからやると逆元が要らないので後ろからやる。 E問題 頂点と銀貨枚数の組を状態としてダ…

AtCoder Beginner Contest 162 感想

https://atcoder.jp/contests/abc16228位。F問題で2、3個飛ばしするDP書いたらバグっちゃった。A,B,Cはいうことなし。Dはj-i≠k-jがなければ(赤の数)×(緑の数)×(青の数)で求まるので、そこからj-i=k-jであるものを引けばいい。E問題は約数包除(?)で…

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 155 F. Perils in Parallel

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

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。点数に上下限があることにきづいて修正しまし…

AtCoder Beginner Contest 150 D. Semi Common Multiple

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

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…

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…

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…