プログラミング問題解法集
可能な限り簡潔にします。
CF679E
直接代入と修正のタイミングが正しいことがわかりますので、書き方について説明します。区間を良い数に変える操作を「加算」と呼びます。
既に区間代入が行われた区間にUpというマークを付けると、その区間とその子区間は1つの点と見なせます。そのため、修正の複雑さは単点修正と同じになります。
したがって、加算操作は次のように記述 ...
6月21日 23:23 投稿
主要アルゴリズムとデータ構造の実践: セグメントツリー、ハンガリー法、素因数分解Union-Find
競技プログラミング問題解決のヒント
競技プログラミングでは、時間計算量の制約をクリアするために効率的なアルゴリズムやデータ構造の理解が不可欠です。以下に、いくつかの実践的なアプローチとコード例を紹介します。
繰り返しの多いクエリに対する前計算（累積和）
多数のクエリに対して同じ計算を繰り返す場合、事前に結果を前計算しておくことで、各クエリの処理時 ...
6月21日 22:28 投稿
高度なアルゴリズム - バイナリインデックストリーとセグメントツリー
バイナリインデックストリー
単点更新、範囲照会が可能なデータ構造です。
典型的な問題として、数列の特定の位置を更新し、任意の区間の合計を求める操作が考えられます。
このデータ構造の核となるのがlowbit関数です。これは整数xに対して、xの最も右側にある1を含む部分を返す操作です。具体的にはx&-xと表現できます。
実装の基本となるのはtree配列です。各要素t ...
6月10日 23:11 投稿
木の連鎖分解（ヘビーライト分解）のまとめ
木の連鎖分解（ヘビーライト分解）のまとめ
基本概念
基本的な考え方
実装手順
ステップ1: 重い子、重い連鎖
ステップ2: dfn順序
ステップ3: 時間計算量の分析
コード実装
重い子の検出
連鎖分解
各種操作
LCAの計算：
パス更新：
パスクエリ：
推奨問題
基本概念
基本的な考え方
\qquad 木の連鎖分解、名前の通り、木データ構造に適用され ...
5月28日 14:42 投稿
SMU Summer 2024 Contest Round 6 問題解説
Many Formulas
問題概要
ある整数が与えられます。この整数の任意の桁と桁の間に + 記号を0個以上挿入することで式を形成し、形成可能なすべての式の合計値を計算します。
解法
1 ≤ |S| ≤ 10 であるため、全探索が現実的です。n桁の整数では、n-1箇所の隙間に加号を挿入するかどうかを決定できます。バイナリビットマスク用于枚举所有可能的加号插入位置。
実装
#include & ...
5月16日 16:51 投稿