2020-10-20

DPを納得したい

競プロ

DPというのは不思議で、ただ適当に配列をループで回しているだけに見えても難しい問題を解決してくれていたりします。
実際に解決できているのだから、間違っていることはないのでしょうが、直感的に正しいとはとても思えません。

最近、DPは効率のいい全探索なのかなと思うようになりました。
何があっても、その状態のときに変わらない答えを持つような問題に分割し、それぞれを解く。
この、「何があっても、その状態のときに変わらない答えを持つ」とは、例えばメモ化再帰なら自分自身を呼び出しているところなどです。
この時に、自分自身の呼び出しをロジックとしてではなく、抽象的なAとBのときにCとなる値、として、その値は常に正しいものと仮定してみます。

その値が正しいなら、現在の値も正しい。
たどっていくと、DPは自明な状態に遷移します。
この自明な状態については例えば0などといった値を当てはめてやることで、正しい値とすることができます。
これにより、自明な状態の値によって計算される値、さらにそれを使って計算される値もすべて正しくなります。

数学的帰納法ってやつですかね？

2020-10-18

全域木と最小全域木

競プロ

全域木とは

あるグラフがあったとき、そのグラフの全ての頂点といくつかの辺を使って作られた新たなグラフが連結で閉路を持たないとき、新たなグラフを元のグラフの全域木という。

最小全域木

辺がコストを持つとき、コストの総和が最小の全域木を最小全域木という。

アルゴリズムとしてクラスカル法などがある。

2020-10-15

ABC140 C Maximal Value

競プロ

問題リンク

考察

数列 $A$ の和を最大化したいので、できるだけ全ての $A_i$ を $B_i, B_{i-1}$ に近づけたい。
$A_N = B_{N-1}$ として問題なさそう。
$A_i (1 \leq i \leq N-1)$ については $A_{i+1}$ が $B_i$ を上回らないのなら $A_i = B_i$
$A_{i+1}$ が $B_i$ を上回るのなら $A_{i+1} = A_i = B_i$ とすると辻褄を合わせたまま最大化できそう。
こんな感じで数列 $B$ を後ろから見て行って数列 $A$ を決定していく。

思ったこと

灰diffなのに難しくない？

2020-10-12

コードの折り畳み

Vim

範囲を選択して zf で折り畳み作成
折り畳み内で zo で展開、 zc で再度折り畳み
zdで折り畳みの削除
zO で折り畳みを削除して展開

2020-10-07

C++テンプレートのメモ

C++

struct reporter {
    reporter() {
        cout << "construct" << endl;
    }
    ~reporter() {
        cout << "destruct" << endl;
    }
    reporter(const reporter &) {
        cout << "copy" << endl;
    }
    reporter(reporter &&) {
        cout << "move" << endl;
    }
    reporter &operator =(const reporter &) {
        cout << "copy" << endl;
        return *this;
    }
    reporter &operator =(reporter &&) {
        cout << "move" << endl;
        return *this;
    }
};

using type = reporter;

template <typename T>
void f1(T) {
    cout << "f1(T)" << endl;
    cout << "type       \t" << is_same_v<T, type> << endl;
    cout << "type &     \t" << is_same_v<T, type &> << endl;
    cout << "type &&    \t" << is_same_v<T, type &&> << endl;
    cout << "type *     \t" << is_same_v<T, type *> << endl;
    cout << "type[1]    \t" << is_same_v<T, type[1]> << endl;
    cout << "type(&)[1] \t" << is_same_v<T, type(&)[1]> << endl;
    cout << "type(&&)[1]\t" << is_same_v<T, type(&&)[1]> << endl;
    cout << endl;
}
template <typename T>
void f2(T&) {
    cout << "f2(T&)" << endl;
    cout << "type       \t" << is_same_v<T, type> << endl;
    cout << "type &     \t" << is_same_v<T, type &> << endl;
    cout << "type &&    \t" << is_same_v<T, type &&> << endl;
    cout << "type *     \t" << is_same_v<T, type *> << endl;
    cout << "type[1]    \t" << is_same_v<T, type[1]> << endl;
    cout << "type(&)[1] \t" << is_same_v<T, type(&)[1]> << endl;
    cout << "type(&&)[1]\t" << is_same_v<T, type(&&)[1]> << endl;
    cout << endl;
}
template <typename T>
void f3(T&&) {
    cout << "f3(T&&)" << endl;
    cout << "type       \t" << is_same_v<T, type> << endl;
    cout << "type &     \t" << is_same_v<T, type &> << endl;
    cout << "type &&    \t" << is_same_v<T, type &&> << endl;
    cout << "type *     \t" << is_same_v<T, type *> << endl;
    cout << "type[1]    \t" << is_same_v<T, type[1]> << endl;
    cout << "type(&)[1] \t" << is_same_v<T, type(&)[1]> << endl;
    cout << "type(&&)[1]\t" << is_same_v<T, type(&&)[1]> << endl;
    cout << endl;
}

int main() {
    cout << "type" << endl;
    type v;
    f1(v);
    f2(v);
    f3(v);

    cout << "type &" << endl;
    type &r1 = v;
    f1(r1);
    f2(r1);
    f3(r1);

    cout << "type &&" << endl;
    type &&r2 = type();
    f1(r2);
    f2(r2);
    f3(r2);

    cout << "type *" << endl;
    type *p = nullptr;
    f1(p);
    f2(p);
    f3(p);

    cout << "type[]" << endl;
    type a[1];
    f1(a);
    f2(a);
    f3(a);
}

type
construct
copy
f1(T)
type        1
type &      0
type &&     0
type *      0
type[1]     0
type(&)[1]  0
type(&&)[1] 0

destruct
f2(T&)
type        1
type &      0
type &&     0
type *      0
type[1]     0
type(&)[1]  0
type(&&)[1] 0

f3(T&&)
type        0
type &      1
type &&     0
type *      0
type[1]     0
type(&)[1]  0
type(&&)[1] 0

type &
copy
f1(T)
type        1
type &      0
type &&     0
type *      0
type[1]     0
type(&)[1]  0
type(&&)[1] 0

destruct
f2(T&)
type        1
type &      0
type &&     0
type *      0
type[1]     0
type(&)[1]  0
type(&&)[1] 0

f3(T&&)
type        0
type &      1
type &&     0
type *      0
type[1]     0
type(&)[1]  0
type(&&)[1] 0

type &&
construct
copy
f1(T)
type        1
type &      0
type &&     0
type *      0
type[1]     0
type(&)[1]  0
type(&&)[1] 0

destruct
f2(T&)
type        1
type &      0
type &&     0
type *      0
type[1]     0
type(&)[1]  0
type(&&)[1] 0

f3(T&&)
type        0
type &      1
type &&     0
type *      0
type[1]     0
type(&)[1]  0
type(&&)[1] 0

type *
f1(T)
type        0
type &      0
type &&     0
type *      1
type[1]     0
type(&)[1]  0
type(&&)[1] 0

f2(T&)
type        0
type &      0
type &&     0
type *      1
type[1]     0
type(&)[1]  0
type(&&)[1] 0

f3(T&&)
type        0
type &      0
type &&     0
type *      0
type[1]     0
type(&)[1]  0
type(&&)[1] 0

type[]
construct
f1(T)
type        0
type &      0
type &&     0
type *      1
type[1]     0
type(&)[1]  0
type(&&)[1] 0

f2(T&)
type        0
type &      0
type &&     0
type *      0
type[1]     1
type(&)[1]  0
type(&&)[1] 0

f3(T&&)
type        0
type &      0
type &&     0
type *      0
type[1]     0
type(&)[1]  1
type(&&)[1] 0

destruct
destruct
destruct

2020-10-05

sqrt(N)の素因数分解

競プロ

コード

vector<uint64_t> prime_factor(uint64_t n) {
    vector<array<uint64_t, 2>> ret;
    for (uint64_t i = 2; i * i <= n; ++i) {
        if (n % i) continue;
        uint64_t cnt = 0;
        while (n % i == 0) {
            n /= i;
            ++cnt;
        }
        ret.push_back({ i, cnt });
    }
    if (n != 1) ret.push_back({ n, 1 });
    return ret;
}

解説のようなもの

for (uint64_t i = 2; i * i <= n; ++i)

まず、ある整数 $N$ が合成数の時からなず $\sqrt{N}$ 以下に約数が存在します。
$i \leq \sqrt{N} = i \times i \leq N$ です。
このfor文では最小の素数である2から、調べる必要のある最大の約数までを探索します。( $\sqrt{N}$ 以降は対称性により必要ありません)

if (n % i) continue;

ここでは素数以外、またはnの約数に存在しない素数をはじいています。
このif文を通過するiはすべて素数です。なぜでしょうか？

まず、ある合成数 $N$ の素因数はすべて $N$ 未満です。
iが合成数の時、iで割り切れる $N$ はiの素因数をすべて持たなければなりません。
しかしながら、 $N$ はiより小さい素数をすべて取り除かれています。

uint64_t cnt = 0;

素数iが $N$ の中にいくつ存在するかを保持しておくための変数です。

while (n % i == 0) {

$N$ をiで割り切れることができる限りループします。

n /= i; ++cnt;

$N$ から素因数iを1つ取り除き、カウント値を1つ増加させます。

ret.push_back({ i, cnt });

素因数iがcnt個存在したことを戻り値用配列に保持させます。

if (n != 1) ret.push_back({ n, 1 });

最後に残った $N$ が素数の時、 $N$ を戻り値用配列に追加します。

2020-09-26

JOI 難易度5 factorial

競プロ

問題リンク

まず、 $N$ を素因数分解し $N={P_1}^a \times {P_2}^b \times \dots$ で考えてみます。( $P$ はそれぞれ素数)

この時 $N$ で割り切ることのできる最小の $M!$ とは $M \leq max(P_1a,P_2b, \dots)$ です。
これは $(Pa)!$ が必ず素因数として $P$ を $a$ 個以上もつためであり、 $P_1a \leq P_2b$ ならば、 $(P_2b)!$ は $(P_1a)!$ を内包します。( $P_1$ と $P_2$ は互いに異なる素数なので、 $max(P_1a,P_2b)! \div N$ は必ず割り切れます)