問題 D - Swap Permutation 解法 問題を少し変更して $\displaystyle \sum _ {i = 0} ^ {N - 1} |P _ i - P _ {i + 1}|$ の総和を求める問題を考えます。ここで、$P _ 0 = P _ N$ とします (つまり円環上で隣接している項の差分の絶対値の和)。 元の $P$ に…

前回のコンテスト で重くし過ぎたことを反省してやや軽めにしようと思っていたんですが、結局後ろが大変になってしまいました。 言い訳をさせて頂くと、テスター作業を依頼する前に設定していた難易度は☆1.5 - 2.0 - 2.5 - 3.0 - 3.0 - 3.5 - 3.5 - 4.0でし…

Many Factorials を準備したので宣伝を兼ねて。 $N! \bmod P$ ($P$ は固定された素数) をたくさんの非負整数 $N$ に対して評価する状況を考える。 $N$ の上限が小さい (例えば $N \leq 10 ^ 7$ が保証される) 場合 $N$ の上限を $M $ とする。 予め $N! \bmo…

未証明要素を多分に含む怪しい解法で通してしまった 問題 atcoder.jp 解法 ちょうど $n$ 回の操作で終了する確率を $f _ n$ とする。$f _ n$ を直接計算するのは難しいので、終了条件を無視して $n$ 回の操作を行った後に終了条件を満たしている確率 $g _ n$…

問題 atcoder.jp 解法 数列 $X$ を数える代わりに整数列 $D = (D _ 1, \ldots, D _ {N + 1})$ を $D _ 1 \coloneqq X _ 1,\ D _ i \coloneqq X _ i - A _ {i - 1} X _ {i - 1}\ (i \geq 2)$ と定めて $D$ を数える。 $D$ が次の条件をすべて満たすことが、$X…

問題 atcoder.jp 解法 雑ですが画像だけで伝わってほしい。 問題文の $H,W$ からそれぞれ $1$ ずつ引いて縦の移動回数がちょうど $H$ 回、横の移動回数がちょうど $W$ 回になるよう調整しています。 画像中の「非交差」という表現は不適切かもしれなくて、正…

$\mathrm{mod}\ M (\lt 2 ^ {31})$ 上で様々な計算を行うことを考える。このとき、よくある状況として、たくさんの $0\leq a,b\lt M $ なる整数組 $(a,b)$ に対して $a \star b \bmod M\ (\star\in\lbrace +,-,\times\rbrace)$ を計算することになる。 $\sta…

#define rep(i, n) for (int i = 0; i < n; ++i) 例えば rep(i, k & 1) とすると for (int i = 0; (i < k) & 1; ++i) と等価であるため、意図しない動作を引き起こします: [C++] gcc HEAD 14.0.0 20230712 (experimental) - Wandbox これを避けるには #defin…

問題 D - Yet Another ABC String 解法 包除原理により数える。 $0\leq i \leq A+B+C-3$ に対して条件 $P _ i$ を「$S _ iS _ {i + 1}S _ {i + 2}$ で条件に違反する」と定める。$X\subseteq \lbrace 0,1,\ldots, A+B+C-3\rbrace$ に対して、全ての $i\in X$…

自分用。随時加筆予定。 ドキュメント www.unicode.org 特に気を付けるべきこと 空白 (以降 ␣ で表す) の有無によってしばしば挙動が変わる 左: n(n+1)/2␣ / 右: n␣(n+1)/2␣ 意味的にまとまりがある部分は空白を開けずに書くと概ね意図通りに組版されるよう…

問題 F - Wine Thief 解法 数列は 0-indexed とする。 $\displaystyle \mathcal{B} _ {i, p} = \left\lbrace (B _ 0, \ldots, B _ {i - 1}) \in \lbrace 0, 1\rbrace ^ i \mid B _ j + B _ {j + 1} \neq 2 \ (\forall j\in\lbrace 0,1,\ldots, i-2\rbrace) \…

65:09 で完走しました。 解説は公式解説があるので、感想を書きます。 C - 偏ったサイコロ $$\mathsf{dp}(i, j) \coloneqq 1 \text{ 個目から } i \text{ 個目までの出目の和がちょうど } j \text{ である確率}$$ として dp を書いたけど、想定解は出目の全…

$\gdef\all#1{\lbrack #1\rbrack}$ $\gdef\powall#1{2 ^ {\all{#1}}}$ $\gdef\set#1{\lbrace#1\rbrace}$ $\gdef\F{\mathcal{F}}$ 追記 本記事の内容に関してより統一的な見方をしていそうな記事を教えて頂きました。 https://codeforces.com/blog/entry/9218…

AtCoder Beginner Contest 219 G - Propagation 問題 https://atcoder.jp/contests/abc219/tasks/abc219_g 解説 https://atcoder.jp/contests/abc219/editorial/2670 コメント (折り畳み) クエリ平方分割による解法の説明です。 AtCoder Beginner Contest 23…

問題 https://yukicoder.me/problems/no/1922 解法 として一般性を失いません。 回の操作を行ったとして、値 が 回目の操作で に属したなら 、 に属したなら とします。 操作前の値 の位置を 、 回の操作後の値 の位置を とします。 また、各 に対して、 を …

問題 judge.yosupo.jp 動機 Bostan-Mori のアルゴリズムで $\displaystyle \lbrack x ^ N \rbrack \dfrac{P}{Q}$ を高速に計算できると知っていても Kth term of Linearly Recurrent Sequence を解くにはややギャップがあると思ったので、書きました。新規性…

昨年組んでいただいたゆきのんさんが引退されたので、kenchoくんに入ってもらってsuisen, otera, kenchoの 3 人でチーム「Bu-Bu-Du-Ke」として ICPC 2022 Yokohama Regional に参加しました。昨年はアジア予選に進出することは叶わず、今年に関しても国内予…

$$ \gdef\V{\mathcal{V}} \gdef\set#1{\lbrace #1 \rbrace} \gdef\card#1{\vert #1 \vert} \gdef\sqbrack#1{\lbrack #1 \rbrack} \gdef\induced#1#2{#1\sqbrack{#2}} $$ これは 帰ってきた AOJ-ICPC Advent Calendar 2022 - Adventar 15日目の記事です。 202…

前置き 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…

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

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

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

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

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

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

前置き 解説の天才二項係数が理解できなかったので，形式的べき級数を用いた機械的(?)な解法の導出について書きます． 問題 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$ に対して、マス…

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

問題 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$ が与えられる．$…