2021-01-02

JOI 本選 2007 D - 最悪の記者 (AOJ 0519, 難易度 7)

トポロジカルソートせよ、という問題！

問題へのリンク

問題概要

頂点数 $N$ 、辺数 $M$ の DAG (閉路のない単純有向グラフ) が与えられる。

このグラフのトポロジカルソート順を一つ求めよ。また、トポロジカルソート順が唯一かどうかを判定せよ。

制約

$1 \le N \le 5000$
$1 \le M \le 10^{5}$

考えたこと

まずトポロジカルソート自体は次の記事に書いた！

DFS でやるやつ

qiita.com

BFS でやるやつ

qiita.com

一意性の方をちょっと考えてみよう！

トポロジカルソートが一意となる条件とは

まずトポロジカルソートとは、下図のように、各頂点を辺の向きに沿うように一列に並べることである。

上の並び替え方は一意ではない。下図のような並び替え方もできる。

一般に、トポロジカルソート順 $v_{1}, v_{2}, \dots, v_{N}$ において、ある連続する 2 要素 $v_{i}, v_{i+1}$ の間に辺がないとき、その 2 要素を入れ替えることができてしまう！！！！！

逆に、すべての連続する 2 要素 $v_{i}, v_{i+1}$ の間に辺があるとき、順序が一意に確定する！！！！！！

よって、解法としては以下のとおり。

トポロジカルソート順を 1 つ求める
その順序に沿って辺がすべてあるかどうかを判定する

計算量は $O(N+M)$ 。

コード 1 (DFS バージョン)

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using Graph = vector<vector<int>>;

int main() {
    int N, M;
    cin >> N >> M;
    Graph G(N);
    set<pint> edges;
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(v);
        edges.insert(pint(u, v));
    }

    // ord: 実際に並び替えられた順序
    vector<int> ord, seen(N, false);
    auto dfs = [&](auto self, int v) -> void {
        seen[v] = true;
        for (auto nv: G[v]) if (!seen[nv]) self(self, nv);
        ord.push_back(v);
    };
    for (int v = 0; v < N; ++v) if (!seen[v]) dfs(dfs, v);
    reverse(ord.begin(), ord.end());

    // 出力
    bool unique = true;
    for (int i = 0; i+1 < ord.size(); ++i) {
        if (!edges.count(pint(ord[i], ord[i+1]))) unique = false;
    }
    for (auto v: ord) cout << v+1 << endl;
    cout << (unique ? 0 : 1) << endl;
}

コード 2 (BFS バージョン)

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using Graph = vector<vector<int>>;

int main() {
    int N, M;
    cin >> N >> M;
    Graph G(N);
    vector<int> deg(N, 0); // 出次数
    set<pint> edges;
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[v].push_back(u); // 逆向きに辺を張っておく
        deg[u]++;
        edges.insert(pint(u, v));
    }

    // 出次数が 0 の頂点から後退解析していく
    vector<int> ord, finished(N, false);
    queue<int> que;
    for (int v = 0; v < N; ++v) if (deg[v] == 0) que.push(v);
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        finished[v] = true;
        ord.push_back(v);
        for (auto nv: G[v]) {
            if (finished[nv]) continue;
            deg[nv]--;
            if (deg[nv] == 0) que.push(nv);
        }
    }
    reverse(ord.begin(), ord.end());

    // 出力
    bool unique = true;
    for (int i = 0; i+1 < ord.size(); ++i) {
        if (!edges.count(pint(ord[i], ord[i+1]))) unique = false;
    }
    for (auto v: ord) cout << v+1 << endl;
    cout << (unique ? 0 : 1) << endl;
}

2020-12-30

AtCoder ABC 170 D - Not Divisible (緑色, 400 点)

AtCoder AtCoder400点 ABC-D 緑色diff 調和級数制約:数値が10^6以下バケット数列数学(整数問題) 集計処理

数列をヒストグラム化することで解決できるタイプの問題！特に今回みたいに、数値の値も $10^{6}$ 以下と小さい場合はすごくそれっぽい！

問題へのリンク

問題概要

長さが $N$ の正の整数からなる数列 $A_{1}, \dots, A_{N}$ が与えられる。以下の条件を満たす $i$ の個数を求めよ。

$j \neq i$ なる任意の $j$ に対して、 $A_{i}$ は $A_{j}$ の倍数ではない

制約

$1 \le N \le 2 \times 10^{5}$
$1 \le A_{i} \le 10^{6}$

考えたこと

数列 $A$ を次のような配列に変換して考えるのは、割とよくやっても良さそうな気がする。

num[v] ← 数列 $A$ の中に $v$ が何個あるか

このように変換したとき、サイズ $N$ に関する問題から、サイズ $V$ に関する問題へと変わる ( $V$ を登場する最大値とする)。このように変換してあげた方が解きやすいことも多い。

さて、今回の問題を解くにあたっては、エラトステネスの篩と同じような方法でやると良さそう。こんな感じ。

int V = 1000000;
vector<bool> ok(V, true);
for (int d = 1; d < MAX; ++d) {
     if (v[d] == 0) continue;
     if (v[d] > 1) v[d] = 0;
  
     // d の倍数を除去していく
     for (int e = d * 2; e < MAX; e += d) v[e] = 0;
}

これは一見すると $O(V^{2})$ かかるように見えるかもしれない。しかしちゃんと解析すると $O(V \log V)$ になっているのだ。計算時間をよりちゃんと書くと

$\frac{V}{1} + \frac{V}{2} + \dots + \frac{V}{V}$

という風になる。二番目の for 文は $d$ の倍数のみを走るので、大体 $\frac{V}{i}$ くらいの範囲を動くことになるのだ。一方

$1 + \frac{1}{2} + \frac{1}{3} + \dots = O(\log N)$

となることが知られている ( $\frac{1}{x}$ の積分が $\log x$ であることから来る)。よって、上述の処理の計算量は $O(V \log V)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

const int MAX = 2100000;

int main() {
    int N;
    cin >> N;
    vector<long long> v(MAX, 0);
    for (int i = 0; i < N; ++i) {
        long long a;
        cin >> a;
        v[a]++;
    }
    for (int d = 1; d < MAX; ++d) {
        if (v[d] == 0) continue;
        if (v[d] > 1) v[d] = 0;
        for (int e = d * 2; e < MAX; e += d) v[e] = 0;
    }
    long long res = 0;
    for (int d = 1; d < MAX; ++d) res += v[d];
    cout << res << endl;
}

2020-12-29

AtCoder ABC 137 D - Summer Vacation (水色, 400 点)

AtCoder AtCoder400点 ABC-D 水色diff Greedy priority_queue データ構造 Greedy:端から順に決まっていく後ろから解く探索順序を工夫して解く最適化テク:解を変形していく(最適性を失わずに) マトロイド勤怠を題材とした問題

これは難しい！！！　誘惑されそうな嘘解法がたくさんある！！

問題へのリンク

問題概要

$N$ 件の日雇いアルバイトがあります。 $i$ 件目の日雇いアルバイトを請けて働くと、その $A_{i}$ 日後に報酬 $B_i$ が得られます。

あなたは、これらの中から 1 日に 1 件まで選んで請け、働くことができます。ただし、請けたことのある日雇いアルバイトは選べません。

今日から $M$ 日後まで ( $M$ 日後を含む) に得られる報酬の合計の最大値を求めてください。

なお、日雇いアルバイトは今日から請けて働くことができます。

制約

$1 \le N, M \le 10^{5}$
$1 \le A_i \le 10^{5}$
$1 \le B_i \le 10^{4}$

考えたこと

一見すると自然に思えてしまう嘘解法がたくさんある！！

たとえば、「報酬が多いアルバイトから順にやる」という Greedy に対しては、 $M = 2$ , $(A, B) = (1, 5), (2, 1)$ の場合が反例となる。

ほかにも、「報酬を受け取れるまでの期間が長いアルバイトから順にやる (先に終わらせておきたい)」という Greedy に対しても、 $M = 2$ , $(A, B) = (1, 5), (1, 5), (2, 1)$ の場合が反例となる。

うまい探索順序を見出す

手の付け所が難しい問題だと思う。このような問題では、探索順序を適切に定めることが重要かなと。

さて、この問題では、最終日の方から考えていくとうまくいく。まず、締め切り前日である $M-1$ 日目に選べるアルバイトはそもそも「 $A_{i} = 1$ であるもの」しかないのだ。こういう「ここにしか入れられない」というものから順に考えていくのは有効だ。というわけで、次のことが言える。

「まず $M-1$ 日目には、 $A_{i} = 1$ であるアルバイトのうち、 $B_{i}$ が最も大きいアルバイト ( $p$ とする) を入れてしまってよい」

このように言えることの証明は、いつも通りの議論でできる。つまり、アルバイト $p$ なしの解が得られているときに、その解を悪化させることなく $p$ を挿入することができる or 入れ替えることができるのだ。

$M-1, M-2, \dots, 0$ 日目と遡る

次に $M-2$ 日目を考える。まったく同様にして、

残っているアルバイトのうち
$A_{i} \le 2$ であるアルバイトであって
$B_{i}$ が最大のもの

を入れてしまってよいということがいえる。以降これを繰り返すと、次の解法が導かれる。

$i = M-1, M-2, \dots, 0$ に対して

残っているアルバイトのうち
$A_{i} \le M - i$ であるアルバイトであって
$B_{i}$ が最大のもの

を $i$ 日目に入れていく。ただし存在しない場合にはスキップする。

データ構造を用いて高速化

以上の解法は、単純に実装すると $O(N^{2})$ の計算量となるので高速化が必要だ。ここではヒープとよばれるデータ構造を用いて高速化する。ヒープは次のことができる。

ヒープに要素 $v$ を挿入する ( $O(\log N)$ )
ヒープに含まれる要素のうち、最大値を取得する ( $O(1)$ )
ヒープに含まれる要素のうち、最大のものを削除する ( $O(\log N)$

ヒープは、C++ では priority_queue、Python3 では heapq が使える。ヒープを活用することで、計算量は $O((M + N) \log N)$ となる。　

コード

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    // AtoB[i] := A が i であるような B の集まり
    vector<vector<int>> AtoB(M+1);
    for (int i = 0; i < N; ++i) {
        int A, B;
        cin >> A >> B;
        if (A > M) continue;
        AtoB[A].push_back(B);
    }

    long long result = 0;
    priority_queue<long long> que;
    for (int i = M-1; i >= 0; --i) {
        for (auto B : AtoB[M-i]) que.push(B);
        if (que.empty()) continue;
        result += que.top(); // キューの最大値を足す
        que.pop(); // キューの最大要素を削除
    }
    cout << result << endl;
}

2020-12-29

AtCoder ABC 136 D - Gathering Children (茶色, 400 点)

AtCoder AtCoder400点 ABC-D 茶色diff テク:区間ごとに分割するランレングス圧縮 >< 収束性に着目するパリティ周期性に着目する各kに対してダブリング操作後の結果を求める問題

「大体こういう感じ」というところまではすぐに見えるけど、細かいところを詰めるのが大変な問題かもしれない。

問題へのリンク

問題概要

$N$ マスがあって、各マスには "L" または "R" が書かれている (左端は "R" で右端は "L" であることが保証される)。また初期状態では各マスに 1 人ずつ子どもがいる。今から以下の操作を $10^{100}$ 回実施する。

すべての子どもについて、現在自分のいるマスの文字が "L" の場合は左に移動し、"R" の場合は右に移動する

$10^{100}$ 回実施後の、各マスの人数を求めよ。

制約

$2 \le N \le 10^{5}$

考えたこと (解法 (1))

こういう問題は、一瞬「ん！？」となるので、手を動かしてみると見えてくる。たとえば

RRRRRRLLLLLRRRRRRLLLLLL

という感じだと、結果は

0 0 0 0 0 5 6 0 0 0 0 0 0 0 0 0 6 6 0 0 0 0 0

となる。見てわかるのは「十分長い回数の移動を行うと、R と L の変わり目のところに皆集まる」ということだった。そして、上のような文字列は

RRRRRRLLLLL | RRRRRRLLLLLL

というふうに分割できる。つまり、"R...RL...L" という形をしたものだけを考えればよいことがわかる。

"R...RL...L" について

残る問題は、"R" が $A$ 個、"L" が $B$ 個あるときに、"RL" の変わり目にどのように集まるかを求めることだ。最終的に左の "R" 側に集まる子どもを "o" で表し、"L" 側に集まる子どもを "x" で表すことにすると、下のようになる。

R R R R R R | L L L L L L L
x o x o x o | x o x o x o x

整理すると、

"R" 側では "o" になるのは $(A+1)/2$ 個 (残りが "x")
"L" 側では "x" になるのは $(B+1)/2$ 個 (残りが "o")

となる。

コード

ランレングス圧縮に書き慣れていると実装しやすいかなと思う。計算量は $O(N)$ となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S;
    cin >> S;
    int N = S.size();

    // ランレングス圧縮
    vector<int> res(N, 0);
    vector<int> div({0}); // 変わり目をメモ
    for (int i = 0; i < S.size();) {
        int j = i;
        while (j < N && S[j] == S[i]) ++j;
        div.push_back(j);

        // R と L の個数から、集計
        if (S[i] == 'L') {
            int A = div[div.size()-2] - div[div.size()-3];
            int B = div[div.size()-1] - div[div.size()-2];
            res[i-1] = (A+1)/2 + B/2;
            res[i] = A/2 + (B+1)/2;
        }

        // 更新
        i = j;
    }
    for (int i = 0; i < res.size(); ++i) cout << res[i] << " ";
    cout << endl;
}

解法 (2)：ダブリング

今回の問題に限らず、 $K$ 回操作後の結果を "思考停止で" 求められる方法として、ダブリングがある。まず次のデータは簡単に求められる。

next[0][v] ← マス $v$ から 1 ステップで行くマス ("L" なら $v-1$ 、"R" なら $v+1$ )

ここで添字の 0 は、ダブリングの 0 ステップ目であることを意味している。これを用いると、次のようなデータが求められる。

next[1][v] ← マス $v$ から $2^{1} = 2$ ステップで行くマス

具体的には next[1][v] = next[0][next[0][v]] と求められる。つまり「1 ステップで行くマスからさらに 1 ステップで行くマス」というわけだ。さらにこれを用いると

next[2][v] = next[1][next[1][v]] ← マス $v$ から $2^{2} = 4$ ステップで行くマス

が求められる。つまり「2 ステップで行くマスからさらに 2 ステップで行くマス」というわけだ。以下同様に、 $i = 0, 1, 2, \dots$ に対して

next[i+1][v] = next[i][next[i][v]]

とすることで、 $2^{0}, 2^{1}, 2^{2}, \dots$ ステップ先のマスが求められる。これを上手に組合せることで、 $K$ ステップ先のマスを求めることもできる！！！

$K = 10^{100}$ とするわけにはいかないけど、たとえば $k = 2N$ くらいで OK。十分大きい偶数なら OK。計算量は $O(N \log N)$ になる。

コード

#include <bits/stdc++.h>
using namespace std;

const int MAX = 20;
int main() {
    string S;
    cin >> S;
    int N = S.size();

    vector<vector<int>> next(MAX, vector<int>(N));
    for (int i = 0; i < N; ++i) {
        if (S[i] == 'L') next[0][i] = i-1;
        else next[0][i] = i+1;
    }
    for (int d = 0; d+1 < MAX; ++d) {
        for (int i = 0; i < N; ++i) next[d+1][i] = next[d][next[d][i]];
    }

    vector<int> res(N, 0);
    int K = N*2;
    for (int v = 0; v < N; ++v) {
        int nv = v;
        for (int d = 0; d < MAX; ++d) {
            if (K & (1<<d)) nv = next[d][nv];
        }
        res[nv]++;
    }
    for (int v = 0; v < N; ++v) cout << res[v] << " ";
    cout << endl;
}

2020-12-29

JOI 二次予選 2021 E - スパイ 2 (難易度 10)

JOI JOI予選・二次予選 JOI難易度10 AtCoder AOJ 3-SAT 後退解析 queue 応用的な探索葉から考える制約条件:2-SAT 論理パズルグラフどれか1つ求める SAT

面白かった。

問題へのリンク

問題概要

$N$ 人がいて、それぞれ「スパイ」か「非スパイ」かのどちらかである。 $N$ 人のうち、何人かについてはスパイかどうかが予めわかっている ( $T_{1}, \dots, T_{N}$ で与えられる)。

$M$ 個の証言がある。各証言は人 $A_{i}$ が証言者によってなされ、「人 $B_{i}$ はスパイである」かつ「人 $C_{i}$ はスパイではない」というものである。

$A_{i}$ がスパイである場合は、「人 $B_{i}$ はスパイである」かつ「人 $C_{i}$ はスパイではない」のうちの少なくとも一方は虚偽の情報である。 $A_{i}$ がスパイでない場合は、証言の真偽は不明である。

これらの情報が整合するように、 $N$ 人それぞれが「スパイ」か「非スパイ」であるかどうかを特定せよ。解なしである場合は -1 を出力せよ。

制約

$1 \le N, M \le 3 \times 10^{5}$

考えたこと

見た感じ SAT っぽいと思った。つまり

$\lnot A_{i} \lor \lnot B_{i} \lor C_{i}$

を一つの closure とした 3-SAT になる。ただしいくつかのリテラルについてはすでに真偽が割り当てられているという状態だ。3-SAT になるので、一瞬解けない気持ちになった (3-SAT は一般には NP-Hard で解けない)。

まずは、真偽値が確定するところを確定させてしまうことを考えた。たとえば、closure の 3 個のリテラルのうち、2 個が確定していたら

その closure がすでに True になる
残りの 1 個のリテラルの真偽が確定する

のどちらかになる (リテラルのうち 3 個が確定していて False の場合は解なし確定)。そしてリテラルの真偽が新たに確定すれば、他の closure によって新たに別のリテラルの真偽が確定したりする。

このような連鎖的な状況を扱うためには、queue を用いた後退解析と相性がいい。queue を用いた後退解析で解ける問題の代表例は「グラフの閉路検出」である。具体的には葉を queue に push して、queue から頂点を取り出して除去して、それによって新たに葉が生じたらまた queue に push して...というのを繰り返すアルゴリズムだ。問題例は以下。

drken1215.hatenablog.com

そして queue が空になったときには、「すでに矛盾が生じている」 or 「各節のリテラルの個数が 3 個以下の SAT が残る」という状態になる。この最後に残った SAT をどう解いたらよいか？

実は、この最後に残った SAT には、ある特異的な性質があることがわかってきた。それは、どの節にもからなず $\lnot X$ という形をしたリテラルがあるということだ。なぜなら、もとの 3-SAT は

「どの closure も $\lnot$ のついていないリテラルはただ 1 個だけ」

という性質を満たしている。よって、もし後退解析後に $\lnot X$ という形をしたリテラルを含まない closure があると仮定すると、そのような closure ではすでに「矛盾が生じる」or「True が確定する」or「 $\lnot$ のついていないリテラルの真偽は確定する」という状態になっているはずなのだ。

以上から、queue を用いた後退解析後には、どの closure にも $\lnot$ のついたリテラルがあることがわかった。よって、この時点で真偽の確定していないリテラルはすべて False にすれば、すべての closure を True にすることができる！！！

コード

後退解析を素朴に実装すれば、計算量は $O(N + M)$ となる。

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> T(N), A(M), B(M), C(M);
    for (int i = 0; i < N; ++i) cin >> T[i];
    for (int i = 0; i < M; ++i) cin >> A[i] >> B[i] >> C[i], --A[i], --B[i], --C[i];

    auto solve = [&]() -> bool {
        vector<vector<int>> where(N);
        vector<int> isok(M, false);
        queue<int> que;

        // リテラルを処理
        auto treat_closure = [&](int i) -> bool {
            int a = A[i], b = B[i], c = C[i];
            
            // すでに矛盾があったらダメ
            if (T[a] == 1 && T[b] == 1 && T[c] == 2) return false;

            // すでに確定 or 残りのリテラルが確定
            if (T[a] == 2 || T[b] == 2 || T[c] == 1) isok[i] = true;
            else {
                if (T[b] == 1 && T[c] == 2) T[a] = 2, que.push(a), isok[i] = true;
                if (T[c] == 2 && T[a] == 1) T[b] = 2, que.push(b), isok[i] = true;
                if (T[a] == 1 && T[b] == 1) T[c] = 1, que.push(c), isok[i] = true;
            }
            return true;
        };
        
        for (int i = 0; i < M; ++i) {
            // 節 i を処理
            if (!treat_closure(i)) return false;

            // 各リテラルをもつ節を格納
            if (!isok[i]) {
                where[A[i]].push_back(i);
                where[B[i]].push_back(i);
                where[C[i]].push_back(i);
            }
        }

        // 後退解析
        while (!que.empty()) {
            auto x = que.front();
            que.pop();
            for (auto id: where[x]) if (!treat_closure(id)) return false;
        }

        // 残りのリテラルはすべて false でよい (すべての節に not リテラルがあるため)
        for (int i = 0; i < N; ++i) if (T[i] == 3) T[i] = 2;
        return true;
    };
    
    if (!solve()) cout << -1 << endl;
    else for (int i = 0; i < N; ++i) cout << T[i] << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 本選 2007 D - 最悪の記者 (AOJ 0519, 難易度 7)

問題概要

制約

考えたこと

トポロジカルソートが一意となる条件とは

コード 1 (DFS バージョン)

コード 2 (BFS バージョン)

AtCoder ABC 170 D - Not Divisible (緑色, 400 点)

問題概要

制約

考えたこと

コード

AtCoder ABC 137 D - Summer Vacation (水色, 400 点)

問題概要

制約

考えたこと

うまい探索順序を見出す

$M-1, M-2, \dots, 0$ 日目と遡る

データ構造を用いて高速化

コード

AtCoder ABC 136 D - Gathering Children (茶色, 400 点)

問題概要

制約

考えたこと (解法 (1))

"R...RL...L" について

コード

解法 (2)：ダブリング

コード

JOI 二次予選 2021 E - スパイ 2 (難易度 10)

問題概要

制約

考えたこと

コード