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,...の順に使う…
https://codeforces.com/contest/1349/myABCの3AC10WA。頭が悪かった。 A問題 素因数ごとに分けてよくて、入力は$1,p,p^2,p^3,\ldots$だけで構成されていると思っていい。このときの答えは最小から二番目の値になる。 B問題 ややこしい解法になった。Kの隣に…
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()…
https://atcoder.jp/contests/abc165ABCの存在を忘れてて遅刻した。108位。EがWAで最初のWAは偶奇によるバグでそれはすぐ直せたんだけど、二つ目のWAに手間取った。原因は出力のしすぎだったんだけど、Mが最大のケースでデバッグしてたせいでバグに気付くの…
https://atcoder.jp/contests/abc164/tasks15位。 D問題 前から見ても後ろから見ても解けることは知ってて、考察の難しさも変わらない。前からやると逆元が必要で、後ろからやると逆元が要らないので後ろからやる。 E問題 頂点と銀貨枚数の組を状態としてダ…
https://atcoder.jp/contests/abc16228位。F問題で2、3個飛ばしするDP書いたらバグっちゃった。A,B,Cはいうことなし。Dはj-i≠k-jがなければ（赤の数）×（緑の数）×（青の数）で求まるので、そこからj-i=k-jであるものを引けばいい。E問題は約数包除（？）で…
https://codeforces.com/contest/1332 A Exercising Walk ｘとｙは独立に考えてよい。どんな移動方法であっても最終位置は同じである。隣接する２マスをジグザグ動くことで、始点から終点へ一直線に移動することができる。これがもっとも無駄のない動きであ…
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…
F - Perils in Parallel以下は公式解説とほとんど同じですが、捉え方がすこしだけ異なります。スイッチのオフとオンをそれぞれ０と１とします。ある範囲のスイッチを切り替えるというのは、法を２としてある範囲に１を足すことに言い換えられます。ある範囲…
F - Tree and Constraints条件が一つだけの場合を考えてみます。つまりある頂点からある頂点の道の上に黒辺が少なくとも一つある、という条件のもとでの数え上げを考えます。全体から条件を満たさないものを引くことを考えると解けます。条件が二つある場合…
A. Deadline x と d/(x+1) が近いほど値が小さくなりそうなので d の正の平方根の前後を 100000 くらいを探したんだけど、これやるなら 1 から 1000000 を全探索で良かった。 B. Yet Another Meme Problem b の桁数を L だと仮定する。そうすると与えられた…
Tasks - AtCoder Beginner Contest 151 A 言語を間違えてしまい 1WA。char 型に一を足すと int 型になることを考えてなくて 1WA。インクリメントなら壊れません。 B N 掛ける M 引く総和をそのまま出力して 1WA。点数に上下限があることにきづいて修正しまし…
https://atcoder.jp/contests/abc150/tasks/abc150_d初項 $A_i / 2$、公差 $A_i$ の等差数列が $N$ 個ある。これらの共通部分を求め、そのうち 1 以上 M 以下のものがいくつあるか求めればよい。ふたつの等差数列の共通部分はまったく存在しないかふたたび等…
A ありうる最も左の点と右の点がわかれば、その間の点はすべてありうるので植木算。自分は気づかなかったが、要素数足す一が答え。 B 連続部分列の和の最大値は動的計画法で求められる。この問題では列全体が答えにならないようにしなければならない。そこで…
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…
https://yukicoder.me/problems/no/950だいぶ手間取った。対角化は頭にちらついてはいたけど経験上、行列の成分が任意のときにこれをやると沼にはまるので避けた。結果として避けてよかったのかな。たぶんどっちを選ぶかは好みの問題な気がする。行列でなく…
https://yukicoder.me/problems/no/940いくつかの組合せ問題は多項式によって解くことができます。これがどういうことか、簡単な例を取り上げて説明します。サイコロを二個振ったとき目の和が k となる場合の数を求める問題を考えましょう。いきなりですが次…
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…
https://atcoder.jp/contests/abc144/tasks/abc144_e積の最大値を $x$ 以下にできるかどうかを二分探索する。$F_i$ は降順に並んでいるものと仮定する。このとき各 $F_i$ と対となる値は $\lfloor x/F_i \rfloor$ 以下になるはずである。よって$A$ を自由に…
https://atcoder.jp/contests/abc144/tasks/abc144_dまず水をなみなみ入れておいてそれを傾けていったとき水の量がちょうど $X$ になる角度を求めればいい。どこまで傾ければいいかは二分探索によって求められる。二分探索するには傾けた角度に対してどのく…
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…
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…
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 …
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…
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}…
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 …
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…
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…
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…
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…
