はじめに $O(K ^ \frac{2}{3} (\log \log K) ^ \frac{1}{3} + K ^ \frac{1}{2} \log N)$ 解法を解説します。 解法 過程を色々すっ飛ばすと、答えは式 $(1)$ で計算されることが分かります。ここで、$\varphi$ は オイラーの $\varphi$ 関数 です。 $$ \sum _…

問題 atcoder.jp 解法 期待値ではなく，スコアの総和を考えることにします．スコアの総和 $S$ が求まれば，答えは $\dfrac{ S } { ( A + B + C ) !}$ として容易に計算されます． まずは具体的な例を考えます． $a _ 1, a _ 2, b _ 1, b _ 2, a _ 3, b _ 3, …

前書き 想定解法より計算量が良かったというのと、$m\leq 10 ^ {18}$ とかでも解けたので。 問題 Problem - F - Codeforces 解法 (前半パートはかなり雑なので、公式解説を併せて読むことを推奨します) 作る列 $a$ に $A_{i,j}$ が含まれる場合を考える。こ…

ABC091 D - Two Sequences 問題 D - Two Sequences 概要 長さ $N$ の整数列 $A,B$ に対して $\displaystyle \bigoplus _{1\leq i,j\leq N} A _ i + B _ j$ を計算する問題。 解法 数列の要素は $2^{28}$ 未満なので、和は $32$ bit に収まる。$256$ bit に $…

問題 yukicoder.me 解法 $\displaystyle v = \min _ { i : \mathrm{even} } a _ i \gt \max _ { i : \mathrm{odd} } a _ i$ または $\displaystyle v = \min _ { i : \mathrm{odd} } a _ i \gt \max _ { i : \mathrm{even} } a _ i$ を満たす $v = p _ k$ を…

A - アトラクション 問題文の通りに判定する。 h, w = map(int, input().split()) a, b = map(int, input().split()) if a >= h and b <= w: print("Yes") else: print("No") B - 穴の開いた硬貨 全ての硬貨が互いに倍数・約数関係にあるので、大きい順に貪…

問題 atcoder.jp 解法 $$ f ( x , y ) : = \# \{ ( i , j ) : 1 \leq i \leq j \leq N , \; \gcd ( i , j ) = x , \; \gcd ( P _ i , P _ j ) = y \} $$ とおくと、$x\gt N$ または $y\gt N$ のとき $f(x,y)=0$ なので、答えは $(1)$ で表されます。 $$ \sum…

想定解とは異なる解法で通しました。計算量は想定解の方がよいです。 問題 AtCoder Grand Contest 044 C - Strange Dance 解法 $ i , j \in \{ 0 , \ldots , 3 ^ N - 1 \} $ に関して、$i$ と $j$ の下位 $k$ trit が等しいならば、$P_i$ と $P_j$ の下位 $k…

問題 PDF の G です。 頂点番号が 1-indexed で振られた $N$ 頂点の木が与えられる。また、map<int, set<int>> M が空で初期化されている。以下のクエリを処理せよ; 1 X L R: M[X] = { L, L + 1, ..., R } とする。 2 X: M.erase(X) とする。 3 x k v_1 ... v_k: $\min \{ </int,>…

問題 リンク 正整数 $n$ が与えられる。$1$ や $11$、$111$ などの $1$ のみからなる数の加減算によって $n$ を作る (例: $24=11+11+1+1, 102=111-11+1+1$)。式中に現れる $1$ の個数の最小値を求めよ。 解法 $\displaystyle \underbrace {11 \cdots 1} _ { …

前置き 公式解説がロシア語なので、自分の解法を書き留めておきます。 問題 ここ 解法 裏面の縫い目の個数は決まっている (表面の縫い目の個数よりちょうど $1$ だけ少ない) ので、裏面のすべての縫い目の長さを $1$ に出来るならば、明らかにそれが最適。実…

問題概要 リンク先 を見てください 解法 制約的に、bit DP をしたい。 $$ \begin{aligned} \mathrm{dp}(S) :=\; & 1 \text{ 以上 } M \text{ 以下の整数 } x \text{ であって、}\\ &\text{ある } i\in S \text{ が存在して } A_i \text{ が } x \text{ を割…

問題リンク atcoder.jp 問題概要 正整数 $ A, M $ が与えられるので、 $$ A ^ x \equiv x \pmod M $$ を満たす $2\times 10 ^ {18}$ 以下の正整数 $x$ を一つ求めよ。 制約 $1\leq A\leq 10 ^ 9$ $1\leq M\leq 10 ^ 9$ 解法 Step 1. $\gcd(A,M)=1$ ならば $ …

(追記 2022/04/29) : 計算量を に改善できたので、追記しました。 問題 atcoder.jp 解法 包除原理の適用を考える。具体的には、 とおき、非負整数 に対して集合 を で定め、 により答えを求める。 の例 なので、 に対して および の値が分かれば として計算…

前置き 公式解説とは異なる 解法を説明します。 問題リンク atcoder.jp 解法 まず、形式的冪級数 を次のように定めます。 また、 に対して形式的冪級数 を次のように定めます。 このとき、 と の間に次の関係式が成り立ちます。 ここで、 は畳み込み演算です…

こどふぉブログ https://codeforces.com/blog/entry/47764 の最後で紹介されているテクニックです．第一種スターリング数 を全ての に対して で計算できます． 解説 以下， とおきます． とすると，任意の非負整数 に対して が成り立つのでダブリング的に を…

より制約を弱くして一方のみが下に凸だとした場合も SMAWK Algorithm を使えば畳み込む数列の長さの和に対して線形時間で求まるんですが，両方ともが下に凸という制約を課した場合はかなり簡単に，かつ定数倍もかなり軽いアルゴリズムで求まることが分かった…

A - Century 答えは ． 実装 (Python) print((int(input()) - 1) // 100 + 1) B - 200th ABC-200 毎回愚直に操作してよい．多くの言語は % 演算子で剰余を取ることが出来る． 実装 N, K = map(int, input().split()) for _ in range(K): if N % 200: N = N *…

だめだめのだめだめでした，残念． A - UFO襲来 各添え字 に対して愚直にチェックする．100 点だけど実質的に for 文が必要でびっくりした． 実装 (Python) Python だと部分文字列の切り出しが簡単． S = input() T = "ZONe" ans = 0 for i in range(len(S) …

177:09 で完走．自己最速なので嬉しい． A - POSTal Code 正規表現が楽？ 実装 (Python) import re if re.compile(r'[0-9]{3}-[0-9]{4}').match(input()): print('Yes') else: print('No') B - PASTal Code o の位置を探すのが楽だと思う． 実装 (Python) X …

(D 以外全部を解くのにかかった時間) < (D を解くのにかかった時間) になってしまった... A - Square Inequality YNeos を書こうとして頭と手が止まった．普通に書いた方がはやいね... A, B, C = map(int, input().split()) print("YNeos"[A ** 2 + B ** 2 >…

n 番煎じだと思いますが，既存の説明で私はあまりよく理解できていなかったので刺さる人がいればいいなと思って書きました． 問題 整数 , が与えられる． と の最大公約数 と を満たす整数 , を求めよ． 再帰解法 を で割ったときの商と余りをそれぞれ , と…

A-E は Python，F は Java． A - Rotate Python が楽． S = input() print(S[1:] + S[0]) B - Visibility を中心にして，4 方向それぞれに対して壁にぶつかるまで進む． を重複してカウントしないように注意． あんまりきれいに実装できなかった． H, W, X, …

面白い解法で解けたので (流石に既出かもしれない) 解法 これだけです．何をしているかというと，数列の後ろから順番に同じ場所を 回ずつ連続して選択しています． 順列 を読まなくても解けるのが個人的に面白いと思った部分です． N = int(input()) print(N…

初めて Python と Java の二刀流で参加した．A-E は Python で解いて，F は TL の関係で Java で解いた． A - Difference Max 一瞬場合分け問題かと思ったけど，冷静になると が最適で，答えは ．これはどっちの言語でもそんなに変わらなさそう． _, b = map…

editorial では最後のパートを DP で解いているが，組み合わせ的に処理すると定数倍の軽い で解くことが出来る． 集合 を昇順にソートしてできる列を とする．さらに， の長さを ， とする． 結論から言えば，順列 を作ることが出来るための必要十分条件は以…

橙 perf 域から外れてしまった． A - Health M Death H % M == 0 ? "Yes" : "No" B - Many Oranges 個数 を決め打って，実現可能かどうかを考える． 個のみかんの重さとしてあり得る最小値 は で，最大値 は である．従って， が実現可能であるための必要条…

A から D までは良かったのに，その後グダりまくってしまった． A - I Scream 読解に少し時間が掛かった． if (a + b >= 15 && b >= 8) { pw.println(1); } else if (a + b >= 10 && b >= 3) { pw.println(2); } else if (a + b >= 3) { pw.println(3); } el…

editorial で紹介されている解法は だが，別解として と の 2 通りで解けたので ( の制約だとあまり差は出なさそう)． 問題 atcoder.jp 解法 基本的な考え方は，初めに訪れる焼肉店 を降順に動かしながら差分を計算するというもの． 焼肉店 で終了する場合の…

めちゃくちゃ計算した．こんなんどうやったら時間内に解けるんだろう？ クエリの読み替えが本質だったっぽくて，これに気付くことが出来ればあるいは...？みたいな感じかもしれない．ただ，今の自分では厳しい... 問題 atcoder.jp 解法 以降，操作対象の数列…