2022-02-27

ARC136-F Flip Cells 別解

問題

atcoder.jp

概要は省略します。

求める答えを $S$ とします。終了状態としてあり得る $M = \prod_{i=1}^H \binom{W}{A_i}$ 個の状態を $\Psi_1, \ldots, \Psi_M$ とします。

終了条件を除いて操作したとき、はじめて $\Psi_i$ となるまでの回数の期待値を $E'_i$ とします。

終了したときに $\Psi_i$ となっている確率を $P_i$ とします。

終了するまでの回数の期待値のうち、 $\Psi_i$ で終わったときの寄与を $E_i$ とします。

$S = \sum E_i$ です。

$C_{ij}$ を $\Psi_i$ からはじめて $\Psi_j$ に初めてなるまでの操作回数の期待値とすると、

$\begin{align} E_i = E'_i - \sum _ {j \neq i} \left(P_j C _ {ji} + E_j \right) \end{align}$

が成り立ちます。両辺 $i$ について総和を取ると

$\begin{align} S = \sum E' _ i - (M-1)S - \sum _ {j \neq 1} C_{1j} \end{align}$

となります。ここで、対称性から $i$ によらず $\sum C _ {ij}$ が等しいことと $\sum P_i = 1$ を用いました。

$C, E'$ を求めるときに必要な情報は、終了状態と今いくつマスの状態が一致しているかのみなので、これは適当な DP を行うことで $O(N ^ 4)$ 程度で解くことができます。また、DP は畳み込みの形になっている上、dp[x][y][z] = (始状態のうち x 個が 1, 終状態のうち y 個が 1, 等しい箇所が z 個) は前計算のもと O(1) で求められるので、全体で $O(HW \log HW \log H)$ で求めることもできます。

2021-12-02

JOI 難易度 10 circuit - 電気回路の結線 (Circuit) 解説

問題概要 $\left( 0, \ldots, N - 1\right)$ の置換 $\sigma$ と正整数 $K$ が与えられる。置換 $\tau$ であって、 $\tau ^ K = \sigma$ を満たすものを一つ求めよ。

制約 - $N, K \le 10 ^ 5$

$N\sqrt{N}$ 解がこちらで説明されています。segtree.hatenablog.com

置換を有向グラフとして見るといくつかのサイクルに分解できることが知られている。置換 $\sigma$ が誘導する有向グラフを $G(\sigma)$ で表す。

$G(\sigma)$ において $x$ が属するサイクルの大きさを $C(\sigma, x)$ とおく。

性質 1 一番簡単な場合、 $G(\sigma)$ が一つのサイクルからなる場合を考える。( $C(\sigma, x) = N$ ) このとき、 $gcd(N, K) = 1$ が必要十分条件である。

prf

$\sigma(x) = x + 1 (\mod N)$ としても一般性を失わない。

十分性 $\mod N$ での $K$ の逆元を $inv(K)$ と書く。

$\tau(x)$ = $\tau(x) + inv(K) (\mod N)$ とすればよい。

必要性 $C(\tau ^ K, x) = \dfrac{C(\tau, x)}{\gcd(C(\tau, x), K)}$

より、 $C(\tau ^ K, x) \lt N$ がわかる。

性質 2 任意の $1 \le x \le N$ について、 $C(\sigma, x)$ = $C(\sigma, \tau(x))$ が成り立つ。

prf

$C(\tau ^ K, x) = \dfrac{C(\tau, x)}{\gcd(C(\tau, x), K)}$

と

$C(\tau, x) = C(\tau, \tau(x))$

を合わせることでわかる。

上の性質より、 $G(\tau)$ で同じサイクルに属する頂点は、 $G(\sigma)$ で属するサイクルのサイズが等しいことがわかる。これにより、頂点は $C(\sigma, x)$ が等しい頂点ごとに独立に考えることができる。

よって、 $\sigma$ はサイズ $L$ のサイクル $M$ 個からなるものとしてよい。

性質 3 $\gcd\left(\dfrac{K}{\gcd\left(K, M\right)}, L\right) = 1$ が必要十分条件である。

prf

$G(\sigma)$ のサイクルに $1, \ldots, M$ の番号をつける。

$\lambda$ : 置換に対し、 $id(\lambda, x)$ で $G(\lambda)$ において $x$ が属するサイクルの番号を表す。

$id(\tau, x)=id(\tau,\tau ^ K (x)) = id(\tau, \sigma (x))$ を複数回適用することで、

$id(\sigma, x) = id(\sigma, y) \Rightarrow id(\tau, x) = id(\tau, y)$ がわかる。

よって、ある正整数 $T$ が存在して、 $C(\tau, x) = TL$ と書ける。

今、この $x, T$ を固定する。

$\tau ^ {KL} (x) = x$ より、 $TL | KL \Leftrightarrow T|K$

また、 $\tau ^ {K} (x) = \sigma (x)$ と性質 1 より、 $gcd\left(K, T\right) = 1$ を満たす必要がある。

以上二つより $id(\sigma, \tau ^ T (x)) = id(\sigma, x)$

これは直感的にもわかりやすいです(L * T 個の長方形で、T 個進んだら元のグループに戻ってくるようにするしかない)。

相異なる $id(\sigma, x)$ に関する $T$ は総和が $M$ である。

これらを合わせて、主張を得る。

なので、アルゴリズムとしては

サイクルに分解する。
サイクルのサイズごとにまとめる
$gcd(K, M)$ を $T$ として、 $\sigma ^ T$ を $\sigma$ に取り換えてサイクルが一つの場合に帰着する。
性質 1 の証明のように構成する。

という流れで構成できます。計算量は $O(N)$ です。(gcd のパートはちょっと考えると消えることがわかります)

2021-11-05

ICPC2021国内予選参加記

f:id:no_imi:20211105222419p:plain

全体 2 位/学内 2 位でした！！去年落ちて悔しかったので今年は無事通過出来て良かったです。

折角なので本番中の動きについてメモっておきます。

本番前
- 作戦を説明。のいみが BC, jell が A, シャーペンに DEF を読んでもらうことに。
本番
- ページが繋がらない。キレる。去年もやってたやんこれ～～と言いながら F5 してたらつながったので B を読む。
B
- 問題文を読むと解けてたので書いた。しっかりと問題選択を忘れて missing problem! を出しつつ AC
C
- 読む。めちゃくちゃ読みづらいし読めても解法がわからない。
- 回転が怠いけどこれ形変わらないし実質根の取り換えだけだな。C だし実は自明な上界が達成可能？→すぐに嘘がわかる。
- 全方位か～？んなわけあるか！ｗ
- こうしてる間に A が通ったのと D が解けたのを聞く
D
- D のいみが実装した方が早いといわれパスを受け取る。
- 代わりに C を jell に考えてもらう。
- 話聞くとマジで DP 書くだけだったのですぐに AC。
再び C
- やっぱこれ全方位しかなくね？と言われる。
- ほかに解けてる問題もなかったので仕方ないから書きます！と言って書き始める。
- 構文解析パートでバグらせるも子の数が少ないのもあって木 DP パートが結構サボれたのでそこまで苦労せず AC。
EF
- 一旦落ち着いたので順位表を見る。→BD FA だし余裕の一位じゃん！
- E も F も多分解けてるといわれたが、F が嘘っぽいらしいので E を jell に書いてもらい F の聞き役に回る。
- 基本的にはあってそうだが、有向グラフに辺を貼って強連結にするパートがダルそう/嘘多そう
- 多種多様な嘘を生やしては撃墜を二人で繰り返しているうちに E が沼る。
- 2 ペナ出したところで手伝いに行く。コード読んでもよくわからない

のいみ「とりあえず #define int long long でもしてみたら？ｗ」

jell「うーん、流石に変わらんと思うんだけどなぁ」

jell「え、めちゃくちゃ変わったんだけど」

のいみ「草」 → 無事 AC

F
- その間に考えた F の解法の一つが正しそうなことをシャーペンに検証/証明してもらったので実装に取り掛かる。
- こういうのは証明ベースで考えた方がいいね(入次数0/出次数0がともに減るような操作だけしないといけない)
- 多種多様な罠、罠、罠、バグ、嘘に困らされる。
- 一応書きあがるがサンプルは i -> i がマッチングになってるやつしかなくて不安なのでチェッカーを書いて assert を入れる。
- 走らせる！→ assertion failed →マジで殺すぞ
- failed している小さいケースを出力させて検証を手伝ってもらってる途中でチェッカーが間違ってることが判明(は？)
- 直して投げると assert が通る
- そのまま投げると AC！チェッカー書かなければよかったじゃん…
GH
- 余った時間で GH を読む
- なんか G は木幅 2 っぽい→マジでそうじゃん→時間ないわバカ
- H は反転効きそうじゃね？式の形的に→マジで効くらしい→時間ないわバカ

というわけでコンテスト終了です。WF 目指してアジアも頑張ります！

追記

応援してくださった方ありがとうございました！あとでツイッターを見返したんですが、序盤と F 通したときに結構言及されてて嬉しかったです。

2021-07-12

WSL スタック領域不足解決法

-Wl,--stack=256000000 みたいなオプションをつけるのではうまくいかなかったんですが、

#pragma comment(linker, "/stack:256000000")

をコードの先頭につけるとなんかうまくいきます。

2021-05-06

AGC017-F ZigZag

https://atcoder.jp/contests/agc017/tasks/agc017_f

$M \times \dfrac{N - 2}{4} \times 2 ^ {N-1}$ で解きます。

左に曲がったら 0, 右に曲がったら 1 として折れ線を 2 進数に変換します。隣りあった折れ線に対応する整数について、01 の列の累積和を取ったものが、どの index についても右の方が大きいことが必要十分です。

今、右側の折れ線を固定し、一個左の折れ線としてあり得るものはどんなものなのかを観察します。右の折れ線に対応する 2 進数に 1 が登場する回数を $s$ 回とします。左側で登場できる 1 の個数は明らかに $s$ 回以下です。左側で登場する 1 の個数を $t \le s$ 回とするとき、右側の 1 は前から $t$ 個のみを考慮すればいいことがわかります。

実は、左側で $i$ 個目の 1 が登場する index を $l_i$ , 右側を同様に $r_i$ と書くと、任意の $i$ について、 $l_i \ge r_i$ が必要十分、と書けます。

今、個数が固定されているので遷移の際 1 番右の 1, 次の 1, $\ldots$ とより後ろの 1 から順に高速ゼータ変換っぽく遷移させることでこれらは一気に遷移させることができます。

遷移するためには "10" の順番で並んでいる必要があるので、このような遷移の起きる場所は合計で $(N-2)2 ^ {N-3}$ 箇所です。

結論として、

一番右の 1 を消す方向に遷移させる
より右の 1 から、1 個ずつ右に動かしていく

の順で遷移させることで、すべての遷移をカバーできます。提出コード

2021-05-05

2018-2019 ACM-ICPC, Asia Seoul Regional Contest I 問題

かなり面白かった + 解説が韓国語しかないということで簡潔に解法をメモっておきます。

概要

木 $G$ がある。 $G$ で距離 $2$ の点の組に辺を張ったグラフ $G ^ 2$ が与えられる。 $G$ を 1 つ復元、またはそのような $G$ がないことを言え。

制約

$N \le10 ^ 5$
$M\le10 ^ 6$

かなり取っ掛かりがつきにくくて迷走した。

$G$ での次数を「真次数」、 $G ^ 2$ での次数を単に「次数」という。次数は、 $G$ での隣接頂点の真次数の和になる。

ある頂点 $u$ を取り、 $u$ の $G ^ 2$ での隣接頂点の誘導部分グラフを考える。 $u$ 自身は含めないことに注意。

この誘導グラフの形を観察すると、中心に完全グラフがあり、その完全グラフの各頂点にこれまた完全グラフがくっついている形になっていることがわかる。中心の完全グラフが、 $u$ の $G$ での隣接頂点になっている。

誘導グラフが完全グラフ一つのみからなったり、二つのみからなったりする場合もあるが、結局はすべての極大完全グラフの頂点を含むような完全グラフの頂点が、 $u$ の隣接頂点である。これは、二重頂点連結成分分解をして関節点全部を含むような二重頂点連結成分を探せばよい。(実は完全グラフ 2 個の場合はどちらを取っても OK！)

$(u, v)$ という辺があったことがわかったとする。 $v$ の $G ^ 2$ での隣接頂点のうち、 $u$ の $G ^ 2$ での隣接頂点であり $u$ の $G$ での隣接頂点でない頂点集合が、 $v$ の $G$ での隣接頂点である。以下それを再帰的にやればよい。

提出コード

感想

難しくて面白いかなりいい問題だった。一つの頂点に着目したときに完全グラフが～みたいなのは自然にたどり着く発想ではあったが、それ自身を除くという発想がなかなか出てこなかったし出てきても試そうとしていなかった。解法ガチャを回すうちにたどり着ける考察では明らかにあるので時間を短縮できるように頑張りたい、一個一個の解法候補を詰める速度を早くするのがいいのかなあ

2021-05-02

区間を管理する構造体

区間と値を管理する構造体、名付けて Interval Manager を書いてみました。特殊なアルゴリズムは特に使っていませんが、よく出てくる操作かつバグらせやすいと思い書いてみました。

機能

$get(k)$

$[k, k + 1)$ の値を返す。

$update(l, r, x)$

区間 $[l,r)$ を $x$ に更新する。

$update(l, r, x, add, del)$

区間 $[l, r)$ を $x$ に更新する。区間と値の組 $([l, r), x)$ を消去する度、 $del(l,r,x)$ を呼び出す。追加する場合も同様に $add$ を呼ぶ。

これを使って PAST-M を解いてみた例がこちらです。

実装例を以下に載せておくのでよかったら使ってみてください！(バグってたらごめんなさい)

5/4 追記 : ちょっとバグ？っていたので変えました 2022/2/15 追記 : 一部高速化と仕様変更しました

// S : 持つデータの型 T : 範囲の型
template <class S, class T = int> struct IntervalManager {
    struct node {
        T l, r;
        S x;
        node(const T &l, const T &r, const S &x) : l(l), r(r), x(x) {}
        constexpr bool operator<(const node &rhs) const {
            if(l != rhs.l) return l < rhs.l;
            return r < rhs.r;
        }
    };
    const S unit;
    set<node> s;
    IntervalManager(const S &u = S()) : unit(u) {}
    IntervalManager(const vector<T> &a) {
        vector<node> setter;
        for(int l = 0; l < a.size(); l++) {
            int r = l;
            for(; r < a.size() and a[l] == a[r]; r++) {}
            setter.emplace_back(l, r, a[l]);
            l = r - 1;
        }
        s = set<node>(all(setter));
    }

    // x を含んだセグメントのイテレータを返す
    typename set<node>::iterator getIt(const T &x) {
        auto it = s.upper_bound(node(x, numeric_limits<T>::max(), 0));
        if(it == begin(s)) return end(s);
        it = prev(it);
        if(it->l <= x and x < it->r) return it;
        return end(s);
    }

    // x を含んだセグメントの情報を持ってくる
    node getSeg(const T &x) {
        auto it = getIt(x);
        if(it != end(s)) return *it;
        return node(x, x + 1, unit);
    }

    // x 以上をはじめて含むセグメントの iterator が帰ってくる
    typename set<node>::iterator nextIt(const T &x) {
        auto it = s.upper_bound(node(x, numeric_limits<T>::max(), 0));
        if(it == begin(s)) return it;
        return prev(it);
    }

    // x に設定されてる値を取得
    S get(const T &x) {
        auto it = getIt(x);
        if(it != end(s)) return it->x;
        return unit;
    }

    S operator[](T k) const { return get(k); }

    // [l, r) := x を set するときに消える区間加える区間ごとに関数を呼び出す
    // ただし、内包, 結合される [L, r) := x の区間も一旦消す
    template <typename ADD, typename DEL> void update(T l, T r, const S &x, const ADD &add, const DEL &del) {
        auto it = s.lower_bound(node{l, 0, x});
        while(it != end(s) and it->l <= r) {
            if(it->l == r) {
                if(it->x == x) {
                    del(r, it->r, x);
                    r = it->r, it = s.erase(it);
                }
                break;
            }
            if(it->r <= r) {
                del(it->l, it->r, it->x);
                it = s.erase(it);
            } else {
                if(it->x == x) {
                    r = it->r;
                    del(it->l, it->r, it->x);
                    it = s.erase(it);
                } else {
                    del(it->l, r, it->x);
                    node n = *it;
                    it = s.erase(it);
                    it = s.emplace_hint(it, r, n.r, n.x);
                }
            }
        }

        if(it != begin(s)) {
            it = prev(it);
            if(it->r == l) {
                if(it->x == x) {
                    del(it->l, it->r, it->x);
                    l = it->l;
                    it = s.erase(it);
                }
            } else if(l < it->r) {
                if(it->x == x) {
                    del(it->l, it->r, it->x);
                    l = min(l, it->l);
                    r = max(r, it->r);
                    it = s.erase(it);
                } else {
                    if(r < it->r) {
                        it = s.emplace_hint(next(it), r, it->r, it->x);
                        it = prev(it);
                    }
                    del(l, min(r, it->r), it->x);
                    node n = *it;
                    it = s.erase(it);
                    it = s.emplace_hint(it, n.l, l, n.x);
                }
            }
        }
        if(it != end(s)) it = next(it);
        add(l, r, x);
        s.emplace_hint(it, l, r, x);
    }

    void update(T l, T r, const S &x) {
        update(
            l, r, x, [](T, T, S) {}, [](T, T, S) {});
    }

    void show() {
        for(auto e : s) {
            cerr << "("
                 << "[" << e.l << ", " << e.r << "): " << e.x << ") ";
        }
        cerr << endl;
    }
};