Static Range Inversions Query

前置き judge.yosupo.jp を解いたのでメモ。前計算 $O(N\sqrt{N})$、クエリ $O(\sqrt N)$ で解きます。 問題 長さ $N$ の整数列 $A=(A _ 0, \ldots, A _ {N-1})$ が与えられる。以下のクエリを $Q$ 個処理せよ: l r : $A$ の連続部分列 $A _ l A _ {l+1} \cd…

第11回 アルゴリズム実技検定

114:52 で全完しました。 A うさぎは $\dfrac{X}{A} + C$ 秒、かめは $\dfrac{X}{B}$ 秒掛かるので分母を払って整数で比較。 B 連想配列に入れてカウント。 C $10 ^ 9$ より大きい値は $10 ^ 9 + 1$ に潰してもよいので、$\min(N ^ k, 10 ^ 9 + 1)$ を前から…

任意次元Fenwick Treeとその実装

$$ \gdef\defarrow{\overset{\text{def}}{\Longleftrightarrow}} $$ 注: 計算量解析が全体的に怪しいです。疑いながら読んでください(?) 問題 $D$ 次元空間の格子点 $\bm{x}\in \Z ^ D$ の重み $w(\bm{x})$ が全て $0$ で初期化されている。以下の種類のク…

AtCoder 橙/Codeforces IGMになりました

はじめに 両者とも人生最後の上方向の色変になる可能性があるので書きます。今まで色変記事は書いたことがなかったので、黄->橙というよりは今までにやったことを振り返る感じです。 うれしい! うれしい! 精進・コンテスト参加 全体 Solved (全体) AtCoder…

ICPC 国内予選 2022 参加記(Bu-Bu-Du-Ke)

suisen・otera・kenchoの3人でチーム「Bu-Bu-Du-Ke」として参加し、全体12位・学内3位の成績で国内予選を通過しました。自分とoteraさんにとっては最終年だったので、何とか突破出来て嬉しいです。 予選前 Heno Worldの権利が無ければ突破は基本的に出来るん…

第10回 アルゴリズム実技検定 バチャ録

83:42+2ペナで完走しました. A - 3枚のカード (5:03 (+5:03)) 格好付けて minmax_element で出力しようとしたら色々おかしくなって原因を探ったりしてたら 5 分掛かった (?) B - 花束 (6:00 (+0:57)) 赤と青でそれぞれ花束を作ると誤読して $\lfloor X/A \r…

仮想関数を回避するテク [C++]

(追記 2022/06/22 22:35) 本記事の内容は Curiously recurring template pattern (CRTP) と呼ばれるものらしいです.より正確な情報や関連する情報を得たい場合は "Curiously recurring template pattern" や "CRTP C++" などと調べると良さそうです. (追記…

模擬国内2017G へやわり!(Room Assignment)

前置き 解説の天才二項係数が理解できなかったので,形式的べき級数を用いた機械的(?)な解法の導出について書きます. 問題 onlinejudge.u-aizu.ac.jp 解法 $(i, a _ i)$ の辺を張った無向グラフ $G$ を考える.$G$ から多重辺を取り除いてできる新しいグラ…

矩形加算・矩形和取得クエリ

はじめに 次のような問題を考えましょう。 問題 (Rectangle Add Rectangle Sum) 整数 $x, y$ に対して、$2$ 次元平面上の矩形領域 $[x, x + 1) \times [y, y + 1)$ をマス $(x,y)$ とよぶ。初め、全てのマスの重みは $0$ である。整数 $x, y$ に対して、マス…

そらで書ける <Θ(N), Θ(log N)> Level Ancestor

次の問題を考えます. 問題 (Level Ancestor Problem) 頂点 $1$ を根とする $N$ 頂点の木 $T$ が与えられます. 頂点 $v$ と非負整数 $k$ に対して,$\mathrm{LA}(v, k)$ を頂点 $v$ から親方向への辺をちょうど $k$ 回辿って到達する頂点と定義します. 頂…

AtCoder Beginner Contest 245 Ex - Product Modulo 2

問題 atcoder.jp 解法 $M = \prod _ {t = 1} ^ l {p _ t} ^ {q _ t}$ と素因数分解されるとする.中国剰余定理より,各 $t = 1, \ldots, l$ に対して $$\prod _ {i = 1} ^ K A _ i ^ t \equiv N \pmod {{p _ t} ^ {q _ t}}$$ を満たす列 $\{ A _ i ^ t \} _ …

木上の等高線集約クエリ

(追記 2022/03/27 23:07) 変種 1, 1' に対する可逆性を仮定しない解法を教えて頂きました.詳細は以下の記事を参照してください. noshi91.hatenablog.com www.mathenachia.blog (追記終) 次のような問題を考えます. 問題 $N$ 頂点の木 $T$ が与えられる.$…

AtCoder Beginner Contest 162 E - Sum of gcd of Tuples (Hard)

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

ARC034 D - インフレゲーム

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

ECR114 F. Occurrences

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

SIMDで愚直解を通すチャレンジ

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 No.1827 最長部分スーパーリッチ門松列列

問題 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 Beginner Contest 230 G - GCD Permutation

問題 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

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

2018-2019 ACM-ICPC, Asia Dhaka Regional Contest G - Techland

問題 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,>…

Educational Codeforces Round 104 F - Ones

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

ICPC 2019-2020 North-Western Russia Regional Contest C - Cross-Stitch

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

AOJ No.2446 Enumeration

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

Tenka1 Programmer Contest F - ModularPowerEquation!!

問題リンク 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$ ならば $ …

第6回 ドワンゴからの挑戦状 予選 E - Span Covering の Θ(X^2((log X)^2+log N)+N) 解法

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

AtCoder Beginner Contest 213 H - Stroll

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

第一種スターリング数の末尾 k 項を計算する

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

下に凸な数列同士の (min, +) convolution

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

京セラプログラミングコンテスト2021(AtCoder Beginner Contest 200)

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