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