異端開発室

コードのマクロ定義とフレームワークの約束 #include <bits/stdc++.h> using namespace std; #define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr); #define ENDL '\n' #define RANGE(_x, _y) (_x).begin(), (_x).end() #define LOOP(_i, _s, _e) for (int _i = _s; _i < _e; ++_i) typedef long long ll; const int MAXN = 200010; signed main() { ...

差分配列差分配列は、区間更新や多次元の範囲操作に効率的に対処するために使用されます。 一維差分 一連の値を変更する際、差分配列を使用して効率よく計算できます。 #include <iostream> using namespace std; int main() { int n, m; cin >> n; int a[n + 2], diff[n + 2]; for (int i = 1; i > a[i]; diff[i] = a[i] - a[i - 1]; ...

P2671 [NOIP2015 初級者部門] 和の計算 この問題では、xとzの色が同じで偶奇が一致する条件を満たす要素の組み合わせで和を計算する必要がある。単純なO(n²)の解法では時間制限に間に合わないため、色と偶奇で分類する方法を採用。 色ごとに偶数・奇数グループを分けて集計し、各グループ内で次の式を適用： ans += 要素番号 × (該当色グループ内の要素数 - 1) × 値 + 要素 ...

時間管理 7:40 から 8:40 まで、対拍と乱数生成の準備を行い、問題を読み込み、T1 を開始しました。40分で初回の提出を完了し、対拍で小さな誤りを見つけたため修正して再提出しました。 8:40 から 10:20 まで、T2 の解決に取り組みました。以前の模擬試験の T2 と類似点がありましたが、直接的な解法が見つからなかったため、まずは暴力解法を考えました。しかし、n ≤ 6 ...

可能な限り簡潔にします。 CF679E 直接代入と修正のタイミングが正しいことがわかりますので、書き方について説明します。区間を良い数に変える操作を「加算」と呼びます。 既に区間代入が行われた区間にUpというマークを付けると、その区間とその子区間は1つの点と見なせます。そのため、修正の複雑さは単点修正と同じになります。 したがって、加算操作は次のように記述 ...

競技プログラミング問題解決のヒント 競技プログラミングでは、時間計算量の制約をクリアするために効率的なアルゴリズムやデータ構造の理解が不可欠です。以下に、いくつかの実践的なアプローチとコード例を紹介します。 繰り返しの多いクエリに対する前計算（累積和） 多数のクエリに対して同じ計算を繰り返す場合、事前に結果を前計算しておくことで、各クエリの処理時 ...

バイナリインデックストリー 単点更新、範囲照会が可能なデータ構造です。 典型的な問題として、数列の特定の位置を更新し、任意の区間の合計を求める操作が考えられます。 このデータ構造の核となるのがlowbit関数です。これは整数xに対して、xの最も右側にある1を含む部分を返す操作です。具体的にはx&-xと表現できます。 実装の基本となるのはtree配列です。各要素t ...

木の連鎖分解（ヘビーライト分解）のまとめ 基本概念 基本的な考え方 実装手順 ステップ1: 重い子、重い連鎖 ステップ2: dfn順序 ステップ3: 時間計算量の分析 コード実装 重い子の検出 連鎖分解 各種操作 LCAの計算： パス更新： パスクエリ： 推奨問題 基本概念 基本的な考え方 \qquad 木の連鎖分解、名前の通り、木データ構造に適用され ...

Many Formulas 問題概要 ある整数が与えられます。この整数の任意の桁と桁の間に + 記号を0個以上挿入することで式を形成し、形成可能なすべての式の合計値を計算します。 解法 1 ≤ |S| ≤ 10 であるため、全探索が現実的です。n桁の整数では、n-1箇所の隙間に加号を挿入するかどうかを決定できます。バイナリビットマスク用于枚举所有可能的加号插入位置。 実装 #include & ...