2 乗の木 DP は O(N^2) になる

タイトルが小泉進次郎すぎる

概要

$dp[i][j]$ のうち、$0\leq j\leq |\mathrm{children}(i)|$ に定義されて、子から遷移していくタイプの木 DP では、計算量が $O(N^2)$ になる（常識）

$N$ 個の頂点をマージしていく形に帰着できる。サイズ $S_l$ と $S_r$ のグループをマージするときには $S_lS_r$ の計算量がかかる。 これを、グループ内の頂点どうしに辺を張る、と解釈すれば、最終的には完全グラフができるので、辺数 $=$ ならし計算量は $O(N^2)$。

競プロ典型 90 問 040 - Get More Money 解説

準備やりました。

問題リンク(Twitter/原案) 問題リンク(AtCoder)

解説

「家 A に入る前に家 B に入らなくてはならない」という条件がたくさんあるので、燃やす埋める問題です。 最大流問題を解けばよいです。

サンプルコード

#include <cfloat>
#include <climits>
#include <iostream>
#include <queue>

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define REP(i, n) for (int i = 1; i <= int(n); i++)

using lint = long long;
using IP = std::pair<int, int>;

constexpr int INF = INT_MAX / 2;
constexpr lint LINF = LLONG_MAX / 2;

class Dinic {
    class edge {
      public:
        int to;
        lint cap;
        int rev, id;
    };
    int N, idx = 0;
    std::vector<std::vector<edge>> vec;
    std::vector<int> iter, level;
    bool bfs(int s, int t) {
        level.assign(N, -1);
        level[s] = 0;
        std::queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int node = que.front();
            que.pop();
            for (const auto& i : vec[node]) {
                if (i.cap > 0 && level[i.to] == -1) {
                    level[i.to] = level[node] + 1;
                    que.push(i.to);
                }
            }
        }
        return level[t] != -1;
    }
    lint dfs(int node, int t, lint f) {
        if (node == t) return f;
        for (int& i = iter[node]; i < vec[node].size(); i++) {
            edge& e = vec[node][i];
            if (e.cap > 0 && level[node] < level[e.to]) {
                lint d = dfs(e.to, t, std::min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    vec[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
 
  public:
    Dinic(int n) : N(n) {
        vec.resize(N);
        level.resize(N);
        iter.resize(N);
    }
    void add_edge(int from, int to, lint cap) {
        vec[from].push_back({to, cap, (int)vec[to].size(), -1});
        vec[to].push_back({from, 0, (int)vec[from].size() - 1, idx++});
    }
    lint max_flow(int s, int t) {
        lint res = 0;
        while (true) {
            bfs(s, t);
            if (level[t] < 0) return res;
            iter.assign(N, 0);
            lint f;
            while ((f = dfs(s, t, LINF)) > 0) res += f;
        }
    }
};

int N, W;
int main() {
    std::cin >> N >> W;
    Dinic D(N + 2);
    int sum = 0;
    rep(i, N) {
        int A;
        std::cin >> A;
        D.add_edge(0, i + 1, A);
        sum += A;
    }
    REP(i, N) D.add_edge(i, N + 1, W);
    rep(i, N) {
        int k;
        std::cin >> k;
        rep(j, k) {
            int c;
            std::cin >> c;
            D.add_edge(c, i + 1, INF);
        }
    }
    std::cout << sum - D.max_flow(0, N + 1) << std::endl;
    return 0;
}

競プロ典型 90 問 026 - Independent Set on a Tree 解説

準備やりました。

問題リンク(Twitter/原案) 問題リンク(AtCoder)

解説

木は二部グラフなので、大きい方から $\frac{N}{2}$ 個取れば良いです。

サンプルコード

#include <algorithm>
#include <iostream>
#include <vector>

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define REP(i, n) for (int i = 1; i <= int(n); i++)

template <class F>
inline constexpr decltype(auto) lambda_fix(F&& f) {
    return [f = std::forward<F>(f)](auto&&... args) {
        return f(f, std::forward<decltype(args)>(args)...);
    };
}
template <class T>
constexpr void printArray(const std::vector<T>& vec, char split = ' ') {
    rep(i, vec.size()) {
        std::cout << vec[i];
        std::cout << (i == (int)vec.size() - 1 ? '\n' : split);
    }
}
int N;
std::vector<int> vec[100010], ans;
int flag[100010];
int main() {
    std::cin >> N;
    rep(i, N - 1) {
        int A, B;
        std::cin >> A >> B;
        vec[A].emplace_back(B);
        vec[B].emplace_back(A);
    }
    lambda_fix([&](auto self, int node, bool f) -> void {
        flag[node] = f + 1;
        for (int i : vec[node]) {
            if (!flag[i]) self(self, i, !f);
        }
    })(1, false);
    if (std::count(flag + 1, flag + N + 1, 1) >= N / 2) {
        REP(i, N) {
            if (flag[i] == 1) ans.emplace_back(i);
            if (ans.size() == N / 2) break;
        }
        printArray(ans);
    } else {
        REP(i, N) {
            if (flag[i] == 2) ans.emplace_back(i);
            if (ans.size() == N / 2) break;
        }
        printArray(ans);
    }
    return 0;
}

俺ガイル聖地巡礼レポ

「kaage精進録」に精進のしょの字もない記事を載せるのは初めてな気がする。 ここで「しょの字もない」と「しの字もない」どちらにするべきかで5分くらい悩んだのは置いておこう。 さて、昨日俺ガイルの聖地巡礼に行ってきたので、なんか書こうと思う。

なお、聖地巡礼は完全に初心者で当初のプランも穴だらけだが、回る順番に関してはもし聖地巡礼することがあったら参考になると思う。

きっかけ

一昨日、海浜幕張に行った。唐突に俺ガイルの聖地巡礼をしたいおきもちになったので、明くる日に出かけることにした。

当初の計画

※当初の計画のため、無理があったりミスがあったりします

海浜幕張（千葉村への出発シーン、ゆきのんの家、川なんとかさんのバイト先、小町受験の後のサンマルク） → 美浜大橋（2期OP、平塚先生のドライブ） → 稲毛海浜公園（合同プロム会場、当て馬プロム写真撮影） → 稲毛海岸駅周辺（総武高校、学校近くの公園、コミュニティーセンター、マリンピア、花火大会の待ち合わせ、3期11話告白シーン） → 千葉みなと駅（花火大会） → 千葉ポートパーク（花火大会） → 千葉駅（八幡・葉山・折本・仲町のデート、3期OP） → 西船橋駅（これはただの乗り換え） → 葛西臨海公園駅、葛西臨海公園（2期ラストから3期へ）

告白シーンと2期ラストを最後に持ってきて、いい感じのプランにしたつもりだった。 12:00 に海浜幕張に着いて昼食をとった後移動を始める予定で、そこからにかかる時間は一切考慮していない。

当日

当日 1:30 くらいまでこのプランを組んで、カットを集めて、適当に当日出発した。

ところで、当日の朝、南船橋のららぽーとも聖地のひとつであることに気がつき（←？？？）、南船橋から回り始めることにした。

南船橋のららぽーとには、3期4話で八幡と由比ヶ浜が訪れている。 ららぽーとにはマッ缶自販機を見に行っただけで、残りは隣の IKEA で済ませているが、この IKEA のモデルは立川店らしい（なんで？？）ので、ららぽーとだけ見に行った。

1期の6話でもこのららぽーとは登場しているようだが、作画が雑すぎてカットに含まれそうな場所は見つけられず、時間も押していたので撤退した。

海浜幕張に着いたのはちょうど 12:00 ごろ。 とりあえずサイゼで昼を済ませて、（八幡は2期4話で葉山たちとデートに出かけた際、夕食にサイゼを提案してドン引きされているが、無視！）写真を撮りに向かった。

どうでも良いが、平塚先生のレンタカーと同じ色の車が通過する瞬間に写真を撮ったのは天才だと思う。 この後、ゆきのんの家に向かったが、アニメと違って、道路に面したエントランスはなかった。 一応実在のマンションなので住所は伏せるお約束のようだが、海浜幕張の駅に着いた時点で丸見えで場所がバレバレなので、わざわざ伏せる必要ないだろこれと思った。行ってみたら一瞬で見つかると思う。 ここで、3期2話での八幡と陽乃さんの帰り道をリサーチしていなかったので全然写真が撮れなかった。反省。

ここで、海浜幕張のサンマルクとホテルニューオークラを撮るのを忘れたまま、美浜大橋まで進んだ。 途中の巨大歩道橋の上からいい感じの写真が撮れた。

この辺は道がシンプルなので迷いこそしなかったが、いくぶん風が強かった。 美浜大橋の上に来たタイミングで風がピークを迎えた。風速 20m は超えていたんじゃないかと思う。

この美浜大橋の上では、2期 OP で陽乃さんが黄昏れたり、2期8話で八幡が平塚先生に連れてこられて話をしたりする。 ところが、マジで風が強かったのでそれどころではなかった。平塚先生の心に沁みる台詞が聞こえないレベル。 適当に写真だけ撮った。

もう少し進んで検見川の浜を歩くと、合同プロムの会場が見えてくる。ブリオッシュドーレというらしい。

検見川の浜を出て、水門の横の橋を渡ったくらいのタイミングで、今回最大の事件が発生した。

雨が降ってきたのである。

用意が悪すぎることに定評があるぼくは、当然傘など持っているはずがなく、近くのローソンに駆け込んだが、傘は売り切れ、仕方なく600円のレインコートを買った。 この時雨は弱かったので、稲毛海岸駅あたりまで耐えるという選択肢もあったが、この後かなり雨が降ってきたので、マジでここで買ってよかったと思う。

雨風があまりにも強かった影響で、砂浜には少しだけ出て戻ったので、海老名さんや由比ヶ浜、三浦たちのように浜ではしゃぐ暇はなかった。 ここからは雨が降ったり止んだりして、その度にレインコートを着脱していて、わざわざ書くと話にならないため、レインコートの話はしない。数えてないけどなんやかんや5回くらい着た気がするな… このあとは、千葉市花の美術館を一瞬見てから浜を出た。

浜を出ると、すぐのところに千葉市立稲毛高校がある。総武高校のモデルである。校門に差し掛かる前に、まず見えてきたテニスコートにただならぬ感動を覚える。いやこれ戸塚彩加いるでしょ絶対。緑色のジャージを着てテニスをしている戸塚彩加の姿がありありと目に浮かぶ。もしかしたら、八幡と葉山たちがテニス勝負をしているシーンかもしれない。

この海岸沿いの風の強さこそが、1巻での八幡の勝利の伏線だった。 小さな伏線回収に感動しつつ道を進むと、作中で複数回登場する、学校近くの小さな公園、中高浜公園が登場する。 人がいたので、適当に距離をとって撮影した。

ここでは、3期6話でいろはすと、8話で葉山と、9話で由比ヶ浜と、八幡が時間を過ごす。 いろはすにプロムの理由を聞く八幡も、葉山に「男の意地」と嘯く八幡も、想いを伝えようとする由比ヶ浜と約束する八幡も、この公園にいた。全然写真が撮れなかったのがかなり悔やまれる。

公園を出て、稲毛海岸駅に向かった。駅前のマリンピアを撮って、千葉みなと駅に向かう。京葉線で一駅である。

このタイミングで、今回の旅で最も重要といっても過言ではないことがひとつある。

八幡が雪乃に告白する陸橋に行けていない。

行けていないことに気づいてはいたのだが、陸橋が思ったより駅から遠く、時間の問題で諦めて千葉みなとに向かった。ここで陸橋に行かなかったことがあとで効いてくる。

さて、千葉みなと駅に着くと、とりあえず駅の写真を撮りたかったが、駅の看板がリニューアルされていて、花火大会のシーンとはどうも違和感が目立った。緑色の JR 東日本のシンプルな看板がいちばんなんだけどな…

ここから、花火大会で八幡と由比ヶ浜が訪れた千葉ポートパークに向かった。 途中の郵便局前の交差点は、八幡が由比ヶ浜に帰宅を提案した、あの場所である。

千葉ポートタワーの前まで行ったが、花火が上がっているわけでもなし、屋台が並んでいるわけでもなしと聖地要素がさすがになかったので、撤退した。

ここで引き返して、千葉都市モノレールで千葉駅に向かった。千葉駅には、葉山と折本たちとの待ち合わせ場所、3期OPのモノレール出現場所などがあるはずなのだが、複雑すぎて全然見つからなかった。折本たちが買い物をしていろはすとエンカウントした千葉 PARCO は閉館したらしい。悲しい。とりあえず千葉駅の写真だけ撮った。

さて、千葉駅を出て葛西臨海公園に向かう予定だったが、俺ガイルの一大クライマックスである、陸橋での告白シーンを逃すわけにはいかない。ということで、隣のJR稲毛駅で下車し、陸橋まで向かうことにした。

稲毛駅西口を出ると、そこそこの量の雨が降っていた。歩けないほどではなかったので進んでいったが、陸橋まで残り半分のあたりで、歩くどころではない "ガチの" 大雨が降ってきた。やむなく歩道橋の下で5分ほど待機して、雨が落ち着いたタイミングで急いで陸橋まで向かった。陸橋に着いたタイミングでも豪雨が降り注いでいた。

陸橋を下りると、車道の下に造られた歩道には、そこにだけぽっかりと穴が空いたように雨が降っておらず、傘を閉じて歩道に進んだ。 信じがたい絶景が広がっていた。 豪雨が降りながらも陽射しの降り注ぐ空に、大きな二重の虹がかかっていたのである。 あの日、八幡が雪乃とともに眺めた景色にかかった虹は、どうしようもなく特別なものに思われた。

陸橋を離れる頃には嘘のように雨は止んだ。時刻は18時を過ぎたあたりであった。 葛西臨海公園に行くことも考えたが、日の入りは18時半前だったから、2期のラストシーン、日没とともに話を切り出す奉仕部3人のシーンが撮れない。これは流石にもったいなかったので、京成稲毛駅まで歩いて、そこからは帰ることにした。

総括

一日で、しかも風が強い日に回り切るのは無理のあるスケジュールだった。次行く暇があれば、海浜幕張と千葉で撮り残しを回収しつつ、葛西臨海公園に行ければいいかなと思う。（でも中高浜公園で全然写真が撮れなかったのは最悪だったので、もう一回行きたいみも、ある）

AGC045-B 01 Unbalanced 解説

問題リンク

面白かった

解説

累積和みたいなことを考えると、上矢印と下矢印をつなげて、縦幅をなるべく小さくする、みたいに読める。 すなわち、初期位置を $0$ とすると、'0' が出てきたら位置に $-1$、'1' が出てきたら位置に $1$ を加算していって、その過程での最大値と最小値の差を最小化する問題に帰着できる。

このとき、初期位置を適当な非負整数に決めると、「位置が $[0, N]$ に収まるような $N$ のうち最小のもの」が答えとなる。 よって、$N$ を決め打ちして実現可能性が判定できれば、二分探索によってこの問題が解ける。

これをベースにして、次の DP を考える。

• $dp[i][j]=i$ 番目まで見て、現在の位置が $j$ であることがありうるかの bool 値

この DP は更新に $O(|S|^2)$ （工夫すると $(|S|\log|S|)$ に落ちる？）かかるので、このままだと解けない。 ここで、遷移をよく眺めると、次の事実が得られる。

• $dp[i][j]$ が true であるような $j$ が複数存在するうちは、このような $j$ は必ず連続してひとつの区間に固まって現れる。
• 初めてこのような $j$ がひとつになったタイミングから先、このような $j$ は、あるひとつの区間のうちで parity が一定な場所に必ず、そしてそのような場所のみに現れる。

これを考えると、$j$ を唯一の区間として管理できて、DP の遷移が $O(1)$ になる。 よって、$O(|S|\log|S|)$ でこの問題が解けた。

競プロ典型 90 問 017 - Crossing Segments 解説

準備やりました．

問題リンク(Twitter/原案) 問題リンク(AtCoder/OJ)

これも QCFium 法が通ったので，制約が上がりました．

解説

小課題は略

円環の問題だが，実は好きなところで切って考えられる． 互いに被覆し合わない，重なる区間の組の数が数えたい．これは，次のようにして数えられる．

• 区間を終点順でソートする．
• 配列の $l_i$ 番目にある値を答えに加算し，$[l_i+1,r_i-1]$ の要素に $1$ を加算する．
• これを全ての区間に対して順に行い，最後に答えを出力する．

区間加算一点取得のクエリは，一点加算区間取得クエリの双対問題として，Binary Indexed Tree(Fenwick Tree) を使うことで高速に実現できる．計算量は，$O(N+M(\log N+\log M))$ となる．

競プロ典型 90 問 007 - CP Classes 解説

準備やりました．

問題リンク(Twitter/原案) 問題リンク(AtCoder/OJ)

QCFium 法が通ったので制約が上がりました．

解説

$A_i$ をソートして，$B_j$ の前後にある数との差の小さい方を取れば良いです． $B_j$ の $A$ の中での位置は，二分探索によって求められるので，全体の計算量は $O((N+M)\log N)$ になります．

サンプルコード

#include <iostream>
#include <algorithm>
constexpr int INF = 1000000000;
int N, Q, A[300010];
int main() {
    std::cin >> N;
    for (int i = 0; i < N; i++) std::cin >> A[i];
    std::sort(A, A + N);
    std::cin >> Q;
    for (int i = 0; i < Q; i++) {
        int B;
        std::cin >> B;
        int ans = INF;
        auto p = std::upper_bound(A, A + N, B);
        if (p != A + N) ans = std::min(ans, *p - B);
        if (p != A) ans = std::min(ans, B - *std::prev(p));
        std::cout << ans << std::endl;
    }
    return 0;
}