2021-12-05

区間係数付き加算・一点係数更新・一点和取得ができるデータ構造

はじめに

累積和高速化型貰うDPの添字に苦しめられたことはありませんか？私はあります。

なんと、貰う配る変換をしなくても、配るDPのまま高速化できるデータ構造があります。その名も Shuz* 木！（勝手に名付けた）

といっても非直感的なので係数セグ木と呼ぶことにします。

というわけで今回は係数セグ木の概要を書いていきます。

係数セグ木

概要

大きさ $2^n$ の配列と係数列に対し、区間係数付き加算・一点係数更新・一点和取得を $O(n)$ で行うデータ構造。

要件

$(M, +)$ はアーベル群
$R$ は環
$\times$ はスカラー乗法
$(M, +, R, \times)$ は左加群
$0 \in M$ は $M$ の $+$ の単位元
$-x \in M$ は $x \in M$ の逆元
$1 \in R$ は $R$ の $\times$ の単位元

インターフェース

$\rm initialize()$ : $a_0 \gets 0, a_1 \gets 0, \ldots, a_{{2^n-1}} \gets 0, b_0 \gets 1, b_1 \gets 1, \ldots, b_{{2^n-1}} \gets 1$
$\rm distribute(l, r, x)$ : $a_l \gets a_l + b_l \times x, a_{{l+1}} \gets a_{{l+1}} + b_{{l+1}} \times x, \ldots, a_{{r-1}} \gets a_{{r-1}} + b_{{r-1}} \times x$
$\rm update(x, y)$ : $a_x \gets b_x \times y$
$\rm get(x)$ : $a_x$ を返す。
$\rm change(x, y)$ : $b_x \gets y$

内部実装

らて木あるいは双対セグメント木を 1 つと、係数を保持する配列 1 つを持つ。係数が変更されるたびに和を取り出す。

実装例

github.com

終わりに

これで、ABC230-F も直感的に、バグらせずに書ける！うれしい！（解答例）

2021-12-02

計算量解析

問題

void f(unsigned int x, unsigned int y, unsigned int z) {
    if (!x || !y || !z) return;
    f(x / 2, y, z), f(x, y / 2, z), f(x, y, z / 2);
}

この関数の計算量を解析せよ。

▽正解（クリックして展開）

2021-12-01

乱数による開区間の生成

たくさんの空でない開区間を乱数で生成したいとき、l = rand([0, N - 1]), r = rand([l + 1, N]) としていないだろうか？これでは分布に偏りが生じてしまう。例えば、 $[0, x)$ の出現確率は $[N - 1, N)$ の出現確率の $\frac{{1}}{{N}}$ になってしまう。これを避けるには、

l = rand([0, N])
r = rand([0, N - 1])
if (l <= r) r++
else swap(l, r)

とすればよい。

2021-01-27

View内に重要なデータを置いておくのは危ないという話

概要

NavigationLinkで, 例えばpresentationMode.wrappedValue.dismiss()をした直後にタスキルすると親Viewが初期化される. 他にもいくつかのタイミングでNavigationViewに限らずViewが初期化され, .onAppear()も同時に呼ばれるので, Viewにデータを保存しておくのはよくない.

2021-01-23

【SwiftUI】[LayoutConstraints] (NavigationView) の対処法

TL;DR

NavigationView {
}

の下に

    .navigationViewStyle(StackNavigationViewStyle())

を追加しましょう.

経緯

タイトル付きで NavigationView 使うと発生して邪魔. iPad に localize していたら解決法がわかった.

急募

[LayoutConstraints] (ActionSheet) の対処法がわからない...

2020-09-07

AGC031 Reversi

atcoder.jp

なんか同じ考え方の人が全然いないので書きます

${\rm DP}[今何色で被覆しているか]$ とすれば, 遷移は高々「被覆を開始する」「被覆を終了する」だけになるので, disjointに気をつけてDPして終わりです

int main() {
    int N;
    cin >> N;
    int A[N];
    rep(i, N) cin >> A[i];
    mint DP[200001] = {};
    DP[0] = 1;
    rep(i, N) if (i == N - 1 or A[i] != A[i + 1]) {
        mint a = DP[0], b = DP[A[i]];
        DP[A[i]] += a;
        DP[0] += b;
    }
    cout << DP[0] << endl;
}

2020-08-25

greedy証明典型テク

まえがき

このように、直感に頼った未証明のGreedyは危険です。

概要

状態に対してコストが定まるような状況を考える.

コストが最小になるための状態の必要十分条件を $B$ とする.

このとき, 以下のいずれかを仮定できるなら, 条件 $A$ を $B$ の必要条件に代るものとして考えることができる.

任意の状態から, (必要なら状態を変化させて) コストを増加させずに条件 $A$ を満たすようにできる
任意の $B$ を満たす状態から, (必要なら状態を変化させて) コストを変化させずに条件 $A$ を満たすようにできる

TODO

マトロイド系貪欲証明

コスト比較系貪欲証明

Shuz*'s Blog

事象の性質を考察する