Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

AOJ 2438 「YAML」

onlinejudge.u-aizu.ac.jp

問題

階層構造をもつオブジェクトを表現する、「YAML」という記法がある。

YAMLの形式に基づいたオブジェクトのデータが与えられるので、それをパースして指定されたプロパティを検索せよ。

今回与えられる入力は、BNF記法で以下のように表現できる。

yaml ::= mapping(0)
mapping(n) ::= mapping-item(n) | mapping-item(n) mapping(n)
mapping-item(n) ::= indent(n) key ':' ' ' string '\n'
                  | indent(n) key ':' '\n' mapping(m) (ただしm>n)

key    ::= [a-z0-9]+
string ::= [a-z0-9 ]+

indent(0)   ::= ""
indent(n+1) ::= ' ' indent(n)

制約

  • 検索するプロパティの深さ \leq 20
  • 入力に含まれる文字数 \leq 5 \times 10^4

考察

LL(1)なので気合で構文解析をする。ただ一気にやろうとすると面倒なので、大きく4段階に分けて実装した。

  1. 取得するプロパティをパース。
  2. 与えられた入力を(indent, key, body)の組へパース。
    • bodyを持たない(オブジェクトである)場合、bodyは空。
  3. 2で作ったデータをパースして、オブジェクトを構築する。
  4. プロパティを検索する。

この問題の核となるのはもちろん3である。


これは解説スライドから学んだことだが、パース関数の名前としてBNF記法で使われているものを使うと実装しやすい。構文解析では、脳死で与えられたBNF記法通りにパースするのが正解なのだろう。それが中々できないのだが。

解説スライドで参考資料に挙げられていたページがこちら

実装例

onlinejudge.u-aizu.ac.jp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// keyの列をパース
vector<string> get_keys() {
    string S;
    getline(cin, S);
    vector<string> ret;
    for (int i = 0; i < S.length(); ++i) {
        if (S[i] == '.') {
            ret.push_back("");
        } else {
            ret.back().push_back(S[i]);
        }
    }
    return ret;
}

// YAMLの各行の情報
struct Line {
    int n;  // spaceの数
    string key, body;
};
vector<Line> inputs;

// YAMLをLineの形式にパースしてinputsへ
void get_inputs() {
    string S;
    while (getline(cin, S)) {
        Line line;
        int itr = 0;

        // スペースを数える
        line.n = 0;
        while (S[itr] == ' ') {
            ++line.n;
            ++itr;
        }

        // keyを抽出
        while (S[itr] != ':') {
            line.key.push_back(S[itr]);
            ++itr;
        }
        itr += 2;  // :とspace

        while (itr < S.length()) {
            line.body.push_back(S[itr]);
            ++itr;
        }
        inputs.push_back(line);
    }
}


struct Obj {
    string key, body;
    vector<Obj> ch;
};

vector<Obj> mapping(int, int&);

Obj mapping_item(int n, int& itr) {
    Obj ret;
    ret.key = inputs[itr].key;
    ret.body = inputs[itr].body;
    ++itr;
    if (!ret.body.empty()) return ret;  // string

    ret.ch = mapping(inputs[itr].n, itr);  // object
    return ret;
}

vector<Obj> mapping(int n, int& itr) {
    vector<Obj> ret;
    while (itr < inputs.size() && inputs[itr].n == n) {
        ret.push_back(mapping_item(n, itr));
    }
    return ret;
}

int main() {
    vector<string> keys = get_keys();
    get_inputs();

    int itr = 0;
    vector<Obj> res = mapping(0, itr);

    string ans = "";
    for (auto k : keys) {
        bool found = false;
        for (auto obj : res) {
            if (obj.key == k) {
                // 1つ下へ潜る
                ans = obj.body;
                res = obj.ch;
                found = true;
                break;
            }
        }

        if (!found) {
            cout << "no such property" << endl;
            return 0;
        }
    }

    cout << (ans.empty() ? "object" : "string \"" + ans + "\"") << endl;
    return 0;
}

反省

  • 流石に実装に時間をかけすぎた。
  • 脳死で解析できるようになりたい。

AOJ 2297 「Rectangular Stamps」

onlinejudge.u-aizu.ac.jp

問題

 N個の長方形をしたスタンプがあり、 i個目の大きさは H_i \times W_iである。

 4 \times 4の全てのマスが白いグリッドに、これらのスタンプを押していく。

  • インクの色はRGBの3種類。
  • スタンプにインクを付けて押すと、押された部分の色が全て更新される。
  • 同じスタンプを、色を変えて複数回使うことができる。
  • グリッドをはみ出るように押すことができる(はみ出た部分は無視される)。
  • 縦横を入れ替えて押すことはできない。

指定された模様を作るのに必要な、スタンプを押す回数の最小値を求めよ。

制約

  •  1 \leq N \leq 16
  •  1 \leq H_i, W_i \leq 4

考察

制約からして地道な全探索なのだが、中々上手い方法が思いつかなかった。特に「はみ出て押しても良い」という制約が厄介で、「左上のマスから順にスタンプを押していく」といった戦略が取れない。

そこで「スタンプを押す」という操作を「長方形領域の色を変える」と見ると、選べる長方形領域の数は結構少ない( 16^2未満)ので上の方針が使える。それでも盤面の状態数が 4^{16}であまりにも険しく、結局諦めた。

解説を読むと「各マスの状態を『色が一致しているか否か』で持てば状態数を 2^{16}に抑えられる」とあり、「天才か〜?」となった。のはいいのだが、この問題で難しいのは多分実装の方である。


グリッド全探索系の問題でよくあるように、この問題でもグリッドをbitパターンで持つ必要がある。しかしそうなると「選べる長方形領域」もbitパターンにする必要があり、これがまぁ面倒。

その後BFSをするのだが、無駄に探索の枝刈りをしようとしてバグらせた。結局シンプルに「全ての押し方について、全てのインクの色を試して遷移する」としたら上手く行ったが、とても疲れた......。

実装例

onlinejudge.u-aizu.ac.jp

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>

using namespace std;

const int INF = 1 << 30;

inline int enc(int x, int y) { return x + y * 4; }

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

    set<int> paint;  // 選べる長方形領域
    for (int i = 0; i < N; ++i) {
        int H, W;
        cin >> H >> W;

        // 左下を軸に全探索
        for (int lx = -3; lx <= 3; ++lx) {
            for (int ly = -3; ly <= 3; ++ly) {
                int pat = 0;
                for (int dx = 0; dx < H; ++dx) {
                    for (int dy = 0; dy < W; ++dy) {
                        int x = lx + dx, y = ly + dy;
                        if (x < 0 || 4 <= x || y < 0 || 4 <= y) continue;
                        pat |= (1 << enc(x, y));
                    }
                }
                paint.insert(pat);
            }
        }
    }

    vector<string> S(4);
    for (auto& s : S) cin >> s;

    // BFS
    queue<int> que;
    que.push((1 << 16) - 1);

    vector<int> dist(1 << 16, INF);
    dist[(1 << 16) - 1] = 0;

    while (!que.empty()) {
        int v = que.front();
        que.pop();

        // 長方形領域と色を全探索
        for (auto pat : paint) {
            for (char c : string("RGB")) {
                int sv = v;
                for (int x = 0; x < 4; ++x) {
                    for (int y = 0; y < 4; ++y) {
                        if ((pat >> enc(x, y)) & 1) {
                            sv &= ~(1 << enc(x, y));
                            sv |= (S[x][y] != c) << enc(x, y);
                            // 一度bitを消してから、「同じか否か」で書き換える
                            // 同じなら0とする
                        }
                    }
                }

                if (dist[sv] == INF) {
                    dist[sv] = dist[v] + 1;
                    que.push(sv);
                }
            }
        }
    }

    cout << dist[0] << endl;
    return 0;
}

反省

  • 見返したらそこまで実装長くなかった(あるある)。
  • 賢く全探索をしていきたい。

AOJ 2222 「Alien's Counting」

onlinejudge.u-aizu.ac.jp

問題

※ 強い言い換えをしているので、原文を読みたい方は上のリンクをご参照ください。

 N頂点 M辺の有向グラフが与えられる。このグラフの各頂点に黒か白を塗りたいが、以下の制約を満たさなければならない

  • 各辺 uvについて、 uが黒なら vも黒でなくてはならない。

このような塗り方の総数を求めよ。

制約

  •  1 \leq N, M \leq 1,000
  • 各頂点の出自数は高々1である

考察

制約が地味に重要で、出自数が高々1であるような有向グラフは「根がサイクルであるような有向森」になる。

サイクルは同じ色に塗るしかないので、1つの頂点に縮約できる。 つまり強連結成分分解をしたグラフ上でこの問題は考えて良く、こうすると完全に根付き森になる。

では具体的にパターン数を考える。まず非連結な頂点間には特に制約もないので、各木について答えを求めてそれらを掛け合わせればよい。

木の塗り方について、根に着目すると以下の2つが考えられる。

  • 根が白の場合。
    • 木全体は白でなくてはならないので1通り。
  • 根が黒の場合。
    • 他の頂点には特に制約はないので、1段低い部分木の塗り方の総積になる。

後者は単純なDFSで求められるので終わり。

ちなみに、後半パートはEDPC-V - Subtreeの部分問題とほぼ同型だったりする(根を白で塗るケースがないだけ)。

実装例

onlinejudge.u-aizu.ac.jp

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

using lint = long long;
using Graph = std::vector<std::vector<int>>;

using namespace std;

struct StronglyConnectedComponents {
    Graph graph, rgraph;
    vector<bool> visited;
    vector<int> order;

    // id[v] = 頂点vはgroups[id[v]]に属する
    vector<int> id;
    vector<vector<int>> groups;

    void revinit() {
        rgraph = Graph(graph.size());
        for (int v = 0; v < graph.size(); ++v) {
            for (int sv : graph[v]) {
                rgraph[sv].push_back(v);
            }
        }
    }

    void dfs(int v) {
        if (visited[v]) return;
        visited[v] = true;
        for (int sv : graph[v]) dfs(sv);
        order.push_back(v);
    }

    void rdfs(int v) {
        if (id[v] >= 0) return;
        id[v] = groups.size() - 1;
        groups.back().push_back(v);
        for (int sv : rgraph[v]) rdfs(sv);
    }

    explicit StronglyConnectedComponents(const Graph& g)
        : graph(g), visited(graph.size(), false), id(graph.size(), -1) {
        revinit();

        for (int v = 0; v < graph.size(); ++v) dfs(v);
        reverse(order.begin(), order.end());

        for (int v : order) {
            if (id[v] < 0) {
                groups.push_back(vector<int>());
                rdfs(v);
            }
        }
    }
};


const lint MOD = 1e9 + 7;

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

    Graph graph(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        graph[v].push_back(u);
        // 後でDFSしやすいように逆向きに辺を張る
    }

    StronglyConnectedComponents scc(graph);
    int V = scc.groups.size();

    // 縮約したグラフ(根付き森)を作成
    vector<int> in(V, 0);  // 入次数(根の判定に使う)
    Graph ngraph(V);
    for (int v = 0; v < N; ++v) {
        for (int sv : graph[v]) {
            if (scc.id[v] == scc.id[sv]) continue;
            ngraph[scc.id[v]].push_back(scc.id[sv]);
            ++in[scc.id[sv]];
        }
    }

    function<lint(int, int)> dfs = [&](int v, int r) {
        lint ret = 1;  // vを黒く塗る場合
        for (int sv : ngraph[v]) {
            if (sv == r) continue;
            (ret *= dfs(sv, v)) %= MOD;
        }

        // vを白く塗る場合を追加
        return (ret + 1) % MOD;
    };

    lint ans = 1;
    for (int v = 0; v < V; ++v) {
        if (in[v] == 0) (ans *= dfs(v, -1)) %= MOD;
    }

    cout << ans << endl;
    return 0;
}

反省

  • SCC分解を書くのはダルいのでなんとか回避できないかと思ったが、無駄な足掻きだった。
  • 自分のライブラリの使い方に慣れねば。

AOJ 2306 「Rabbit Party」

onlinejudge.u-aizu.ac.jp

問題

 N頂点 M辺の重み付き無向グラフが与えられる。頂点集合を1つ取ったとき、そのスコアを以下のように定義する。

  • 頂点集合からなる誘導部分グラフを取る。
  • 各頂点について、接続している辺の重みの最小値を求める。
    • 辺が張られていないような頂点間にも、重み0の辺が張られているとみなす。
  • それらの合計をスコアとする。

スコアの最大値を求めよ。

制約

  •  1 \leq N, M \leq 100
  • 重みは 10^6以下

考察

最初「重みが大きい方から追加していくだけか?」と思ったが、追加したい辺と一緒に無駄な辺もついてくるので無理。愚直全探索は論外として、DPにしても頂点集合保持する必要あるし無理だな〜と思いながら何も進まなかった。

解説を読むと「実はクリークの最適解が常にあります」とあってびっくり。「最小値0でも重みが大きい辺と接続してれば仕事するだろ」と思ったが、よくよく考えたらそんなことはなかった。

これで考えるべきはクリークだけになり、クリークの辺数が M以下であることから頂点数 14以下の集合に絞ることができる。しかしこれを全列挙していると {}_{100} C_{14}というオーダーになって、とてもじゃないが間に合わない。

そこで、クリークの頂点数 dを固定してしまう。このクリークに属する頂点の次数は d - 1以上でなくてはならないので、それらにだけ着目する。次数の総和は 2M以下なので、これを満たす頂点の数は \frac{2M}{d-1}となる。この部分集合を全列挙したときの計算量は

 \displaystyle \sum_{d = 2}^{14} {}_{\frac{2M}{d - 1}} C_{d} \leq 17,116,333

でなんとか間に合う(Wolfram alphaの計算結果)。

素数 dの部分集合の全列挙は「bool配列に対してnext_permutaionを使う」ことで実現できることを別の問題で学んだので、これを実装して終わり。

実装例

onlinejudge.u-aizu.ac.jp

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

using namespace std;

const int INF = 1 << 30;

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

    vector<int> deg(N, 0);                           // 次数
    vector<vector<int>> cost(N, vector<int>(N, 0));  // 隣接行列
    for (int i = 0; i < M; ++i) {
        int u, v, f;
        cin >> u >> v >> f;
        --u, --v;
        cost[u][v] = cost[v][u] = f;
        ++deg[u], ++deg[v];
    }

    int ans = 0;
    for (int d = 2; d * (d - 1) / 2 <= M; ++d) {
        // 頂点数dのクリークを全列挙
        vector<int> vs;
        for (int v = 0; v < N; ++v) {
            if (deg[v] >= d - 1) vs.push_back(v);
        }

        int K = vs.size();
        if (K < d) continue;

        vector<bool> pat(K, false);
        for (int i = 0; i < d; ++i) pat[K - i - 1] = true;

        // 要素数dの部分集合をnext_permutationで全列挙
        do {
            int sum = 0;
            for (int i = 0; i < K; ++i) {
                if (!pat[i]) continue;

                int mi = INF;
                for (int j = 0; j < K; ++j) {
                    if (i == j || !pat[j]) continue;
                    mi = min(mi, cost[vs[i]][vs[j]]);
                }
                sum += mi;
            }
            ans = max(ans, sum);
        } while (next_permutation(pat.begin(), pat.end()));
    }

    cout << ans << endl;
    return 0;
}

最終ケースだけ尋常じゃなく遅いのは、next_permutationが線形時間であることが原因らしい。他の人々の提出を見たら、ほとんど枝刈りDFSをしていてかつ実行時間が十分短かった。

反省

  • まぁ想定解だし実行時間は許して欲しい。
  • クリークでいけるところまでは最低限気づきたかった。

AOJ 2425 「全探索お姉さんの休日」

onlinejudge.u-aizu.ac.jp

問題

あなたと全探索お姉さんは正六角形が敷き詰められた空間のマス (sx, sy)にいる。ここから毎分隣接するマスへの移動を繰り返すことで、マス (gx, gy)に行きたい。

ただし障害物が置かれているマス、 x座標の絶対値が lxより大きい、または y座標の絶対値が lyより大きいマスには入れない。

さらに厄介なことに、お姉さんは毎分座標と時刻に基づいて適当な方向に移動するように指示する。目的地に着くまでにお姉さんの指示を無視する回数を最小化せよ。

制約

  • 障害物は 1,000個以下
  •  0 \lt lx, ly \leq 1,000

考察

座標の指定方法が気持ち悪いため、 x座標の偶奇で隣接するマスの相対位置が変わっていることに注意。

まずBFSが思いつくが、お姉さんの指示が時間に依存しているため時刻も状態として持つ必要がある。お姉さんの指示は時刻を6で割った値にしか依存しないため、これと座標を組にすると状態数を 2lx \cdot 2ly \cdot 6 = 24 lx \cdot lyに抑えられる。

後はBFSだが、お姉さんの指示に従った場合距離は増えないため普通のBFSは無理。Dijkstraでもいいのだが、ここでは01-BFSを実装した。

01-BFSは「距離が増加しない場合はdequeの先頭に突っ込む」以外はBFSと全く同じ、と思っていた時期が僕にもありましたDijkstraと同様に再探索を防ぐ機構が必要なので注意。

実装例

onlinejudge.u-aizu.ac.jp

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <deque>
#include <tuple>

using namespace std;

using lint = long long;
using ldouble = long double;

const int INF = 1 << 30;

const int dx[7] = {0, 1, 1, 0, -1, -1, 0};
const int dy[2][7] = {{1, 0, -1, -1, -1, 0, 0}, {1, 1, 0, -1, 0, 1, 0}};

int main() {
    int sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;

    int N;
    cin >> N;
    vector<int> ox(N), oy(N);
    for (int i = 0; i < N; ++i) {
        cin >> ox[i] >> oy[i];
    }

    int lx, ly;
    cin >> lx >> ly;

    // 全体をlx, lyだけずらして非負整数座標にする
    sx += lx, sy += ly, gx += lx, gy += ly;
    int H = lx * 2, W = ly * 2;
    vector<vector<bool>> obj(H + 1, vector<bool>(W + 1, false));
    for (int i = 0; i < N; ++i) {
        obj[ox[i] + lx][oy[i] + ly] = true;
    }

    // お姉さんの指示に逆らった回数 with 時刻
    vector<vector<vector<int>>> dist(H + 1, vector<vector<int>>(W + 1, vector<int>(6, INF)));
    dist[sx][sy][0] = 0;

    deque<tuple<int, int, int, int>> que;
    que.emplace_front(sx, sy, 0, 0);

    // 01-BFS
    while (!que.empty()) {
        int x, y, t, d;
        tie(x, y, t, d) = que.front();
        que.pop_front();

        // Dijkstraと同じくこのfilterが必要なので注意
        if (d > dist[x][y][t]) continue;

        int dir = abs((x - lx) * (y - ly) * t) % 6;  // お姉さんの指示
        int nt = (t + 1) % 6;

        for (int i = 0; i < 7; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[abs(x - lx) % 2][i];

            if (nx < 0 || H < nx || ny < 0 || W < ny ||
                obj[nx][ny] || dist[nx][ny][nt] <= dist[x][y][t] + (i != dir)) continue;

            if (i == dir) {
                // 指示に従うなら距離は増えない
                dist[nx][ny][nt] = dist[x][y][t];
                que.emplace_front(nx, ny, nt, dist[nx][ny][nt]);
            } else {
                dist[nx][ny][nt] = dist[x][y][t] + 1;
                que.emplace_back(nx, ny, nt, dist[nx][ny][nt]);
            }
        }
    }

    int ans = INF;
    for (int t = 0; t < 6; ++t) {
        ans = min(ans, dist[gx][gy][t]);
    }
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

反省

  • 01-BFSに関する知見が得られた。
    • 解説見たらDijstra法でお気持ちになった。

AOJ 2742 「選挙活動」

onlinejudge.u-aizu.ac.jp

問題

平面上に、 M個の多角形状の障害物と N人の有権者がいる。平面上の適当な位置に立つことで、障害物に遮られることなく見える有権者の数を最大化せよ。

厳密には、あなたと有権者を結ぶ線分で、全ての障害物と交差しないものの数を最大化せよ。ただし多角形の頂点と線分の接触は交差と見なさないものとする。

制約

  •  1 \leq N \leq 5
  •  1 \leq M \leq 10
  • 各障害物の頂点数は 15以下
  • 各点の座標の絶対値は 20以下
  • その他相対位置に関する制約(問題ページを参照のこと)

考察

 qを固定して、線分 p qが全ての障害物と交差しないような pの領域を考えると、これは多角形の頂点と qを結ぶ直線で仕切られることが分かる。

ここから点の候補を「多角形の頂点と候補者を結ぶ直線」上、さらに言えばそれらの直線の交点のみに絞ることができる。このような点の数は (5 \cdot 15 \cdot 10)^2 = 5.6 \times 10^5個くらい(意外と多い)なので、判定が十分高速に行えれば間に合う。

後は多角形と線分の交差判定ができればいい。まず「線分と交差する多角形の辺があればアウト」なのは明らかだろう。これで大半のケースはカバーできるのだが、以下のように線分が多角形の頂点とのみ交差するケースは扱えない。

f:id:misteer:20190521044224p:plain

しかし制約をよく読むと「多角形の頂点または有権者のいる場所の座標のうち3点が同一直線状に存在することはない」とあるので、上のようなケースは存在しない。よってこれで十分判定ができる。

実装例

onlinejudge.u-aizu.ac.jp

#include <iostream>
#include <vector>
#include <complex>

using Real = long double;
using Point = std::complex<Real>;
using Segment = std::pair<Point, Point>;
using Polygon = std::vector<Point>;

bool operator<(const Point& a, const Point& b) {
    return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
}

std::istream& operator>>(std::istream& is, Point& p) {
    Real x, y;
    is >> x >> y;
    p = Point(x, y);
    return is;
}

const Real EPS = 1e-10;
const Point origin(0, 0);

// 宇宙船演算子
inline int compare(Real a, Real b) {
    if (std::abs(a - b) < EPS) return 0;
    return a - b > 0 ? 1 : -1;
}

inline Real dist(Point a, Point b) {
    return std::abs(a - b);
}

inline Real length(Segment s) {
    return dist(s.first, s.second);
}

// inner product
inline Real dot(Point x, Point y) {
    return std::real(std::conj(x) * (y));
}

// outer product
inline Real cross(Point x, Point y) {
    return std::imag(std::conj(x) * (y));
}

// lに対するpの位置
// 0: on segment
// 1: counter clockwise  -1: clockwise
// 2: online front       -2: online back
int side(Segment s, Point p) {
    Real c = cross(s.second - s.first, p - s.first);
    if (compare(c, 0) != 0) return compare(c, 0);

    Real d = dot(s.second - s.first, p - s.first);
    if (compare(d, 0) < 0) return -2;

    return (compare(length(Segment(s.first, p)), length(s)) > 0 ? 2 : 0);
}

// 平行判定
inline bool isparallel(Segment s1, Segment s2) {
    return compare(cross(s1.second - s1.first, s2.second - s2.first), 0) == 0;
}

// 線分の交差判定
// bound: 線分の端点を含むか
inline bool intersect(Segment s1, Segment s2, bool bound) {
    return (side(s1, s2.first) * side(s1, s2.second) < bound) &&
           (side(s2, s1.first) * side(s2, s1.second) < bound);
}

// 線分の交点
Point intersection(Segment s1, Segment s2) {
    Real c1 = cross(s2.second - s2.first, s1.second - s1.first);
    Real c2 = cross(s2.second - s2.first, s1.first - s2.first);
    return s1.first + (s1.second - s1.first) * (-c2 / c1);
}


using namespace std;

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

    vector<Polygon> gs(N);
    for (auto& g : gs) {
        int L;
        cin >> L;
        g.resize(L);
        for (auto& p : g) cin >> p;
    }

    vector<Point> people(M);
    for (auto& p : people) cin >> p;

    // 有権者と障害物の頂点を結ぶ直線を列挙
    vector<Segment> segs;
    for (auto p : people) {
        for (auto& g : gs) {
            for (auto q : g) {
                segs.emplace_back(p, q);
            }
        }
    }

    // 上で列挙した直線同士の交点を列挙
    vector<Point> stand;
    for (int i = 0; i < segs.size(); ++i) {
        for (int j = i + 1; j < segs.size(); ++j) {
            if (!isparallel(segs[i], segs[j])) {
                stand.push_back(intersection(segs[i], segs[j]));
            }
        }
    }

    int ans = 0;
    for (auto p : stand) {
        int cnt = 0;

        for (auto q : people) {
            Segment s(p, q);
            bool judge = true;
            for (auto& g : gs) {
                for (int i = 0; i < g.size(); ++i) {
                    // 多角形の辺と線分が端点を除いて交差するか?
                    if (intersect(s, Segment(g[i], g[(i + 1) % g.size()]), false)) judge = false;
                }
            }
            if (judge) ++cnt;
        }

        ans = max(ans, cnt);
    }

    cout << ans << endl;
    return 0;
}

反省

  • 点の候補を有限に絞るのは本質的な方針っぽい。
  • 今回の制約がない場合の交差判定は難しそうだが持っておきたい。

AOJ 2741 「インビジブル」

onlinejudge.u-aizu.ac.jp

問題

AさんとBさんがそれぞれ N枚、 M枚のカードの山を使ってゲームを行う。各プレイヤーは自分と相手のカードの山の中身を把握している。

カードには「得点カード」と「妨害カード」があり、得点カードには正の整数が書かれている。また、場には「山場」というカードを出す場所がある。

ゲームはAさんから始まるターン制で、ターンが来たプレイヤーは「カードを出す」か「パス」のどちらかの操作を行う。

  • 「カードを出す」を選んだ場合、自分のカードの山で一番上のカードを山場の上に置く。
    • ただし自分のカードの山が空の場合はこの操作は選べない。
  • 「パス」を選んだ場合、以下のようにして山場のカードが精算される。
    • 山場にあるカードで、自分が出した得点カードに書かれた値がスコアに加算される。
      • ただし山場に相手の妨害カードがある場合、一番上の妨害カードより上にある得点カードしか加算されない。
    • その後、山場のカードは全て取り除かれる。

山場が空の状態で2回連続でパスが行われた場合、ゲームは終了する。

各プレイヤーが自分のスコアと相手のスコアの差を最大化するとき、最終的なAさんのスコアとBさんのスコアの差を求めよ。

制約

  •  1 \leq N, M \leq 50
  • 得点カードに書かれている値は 1以上 10^6以下

考察

やることは至ってシンプルで、「Min-Max法」を実装すればいい。つまりシミュレーションである。

愚直に実装するとTLEなので、DPによって効率化を行う必要がある。持つべき状態は以下の6つ。

  • Aさんのカードのうち、場に出ていてかつ「有効」なもので、一番下にあるカードのindex。
  • Aさんのカードのうち、場に出ていて一番上にあるカードのindex。
  • Bさんも同様。
  • 今どっちのターンか。
  • 山場が空になってから、何回連続でパスされたか。

必要なメモリ量は 4N^2M^2となり、生配列を静的領域に確保すれば100MB程度になって一応足りる(ちなみにvectorで取ったら死んだ)。

実装もそこまで複雑ではないのだが、中々ひどいミスを連発したので以下にまとめておく。

  • 山場にあるカードのindexが閉区間だったり半開区間だったりで混乱させる。
  • 「妨害カードは自分の得点カードも無効化する」と誤読。
  • スコアの差分は負にもなりうるのに、DP配列を -1で初期化。
  • 終了条件の「山場が空になってから」を読み飛ばし、パスが2連続で起きたら終了すると誤読

本当に冷静になるべきだった。誤読についてはじっくり問題文を読む時間を設けるべき。

実装例

onlinejudge.u-aizu.ac.jp

#include <iostream>
#include <vector>

using namespace std;

using lint = long long;
using ldouble = long double;

const int INF = 1 << 30;

int N, M;
vector<int> A, B;
int dp[51][51][51][51][2][2];

// 1がスタックに積んでいるのが[l1, r1)
// 2がスタックに積んでいるのが[l2, r2)
// 今t+1のターン
// p : スタックが空になってからパスしたか
int rec(int l1, int l2, int r1, int r2, int t, int p) {
    int& ret = dp[l1][l2][r1][r2][t][p];
    if (ret > -INF) return ret;

    if (t == 0) {  // スコアを最大化
        // パスする場合
        if (p == 1) {
            ret = 0;  // ゲーム終了
        } else {
            int score = 0;
            for (int i = l1; i < r1; ++i) score += A[i];
            for (int j = l2; j < r2; ++j) score -= B[j];
            bool empty = (l1 == r1) && (l2 == r2);  // スタックが空か
            ret = score + rec(r1, r2, r1, r2, 1 - t, empty);
        }

        // カードを出す場合
        if (r1 < N) {
            if (A[r1] == 0) {
                // 「相手の」カードを全部消す
                ret = max(ret, rec(l1, r2, r1 + 1, r2, 1 - t, 0));
            } else {
                ret = max(ret, rec(l1, l2, r1 + 1, r2, 1 - t, 0));
            }
        }

    } else {  // スコアを最小化
        if (p == 1) {
            ret = 0;
        } else {
            int score = 0;
            for (int i = l1; i < r1; ++i) score += A[i];
            for (int j = l2; j < r2; ++j) score -= B[j];
            bool empty = (l1 == r1) && (l2 == r2);
            ret = score + rec(r1, r2, r1, r2, 1 - t, empty);
        }

        if (r2 < M) {
            if (B[r2] == 0) {
                ret = min(ret, rec(r1, l2, r1, r2 + 1, 1 - t, 0));
            } else {
                ret = min(ret, rec(l1, l2, r1, r2 + 1, 1 - t, 0));
            }
        }
    }
    return ret;
}

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

    A.resize(N);
    for (auto& a : A) {
        cin >> a;
        if (a < 0) a = 0;
        // 区間和を求める上で都合が悪いので、妨害カードを0にする
    }
    B.resize(M);
    for (auto& b : B) {
        cin >> b;
        if (b < 0) b = 0;
    }

    fill(dp[0][0][0][0][0], dp[51][0][0][0][0], -INF);
    cout << rec(0, 0, 0, 0, 0, 0) << endl;
    return 0;
}

最初は累積和で精算を O(1)で実装していたのだが、ループを回しても間に合った。実際に取りうる状態数は見た目より少ないっぽい。

反省

  • 上に書いた通り盛大にやらかしたので、この反省を噛み締めていきたい。
  • 計算量が際どくても実装が楽なやつを選ぶべきなのか、これが分からない。
  • 区間とindexはちゃんと意識しよう。