いかにもよくわからない操作問題なので、難しいことは考えずに探索に走るべきな雰囲気

問題概要

正の整数 $x$ に対し、 $r(x)$ で $x$ を 10 進表記してできる文字列を反転したものを 10 進表記に持つ整数を表す。

正の整数 $N, M$ が与えられる。 $1 \le x \le N, 1 \le y \le M$ なる整数の組 $(x, y)$ であって、 $(x, y)$ から始めることで以下の一連の操作を無限に繰り返すことができるものの個数を求めよ

$x, y$ のいずれかが 0 なら、終了する
$x$ < $y$ なら $x$ を $r(x)$ で、そうでないなら $y$ を $r(y)$ で置き換える
上の操作後、 $x$ < $y$ となっていれば $y$ を $y−x$ で、そうでなければ $x$ を $x−y$ で置き換える

制約

$1 \le M, N \le 999$

考えたこと

割とよくわからない操作。。。
だけど、グラフは

頂点数が少ない、 $O(MN)$ 程度

という感じのグラフ。こういうグラフを一般的に扱ってもよさそうなくらいには、問題特有の構造が特に見つけられなさそう。。。

有向グラフ (今回は特に「出次数が 1」のグラフだがその構造も特に使わない) において「閉路の構成員となりうる頂点」をすべて数え上げる問題ということになる。

それは後退解析のようなやり方がバッチリはまる。すなわち、

シンク (出次数が 0 の頂点) から出発して次々とシンクを切り落とす
そうすることで新たなシンクができてくるので、それも全部落とす

という風にして行って、新たなシンクがなくなるまで繰り返す。queue を使う。

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

int rev(int x) {
    long long res = 0;
    while (x > 0) { res *= 10; res += x % 10; x /= 10; }
    return res;
}

vector<vector<int> > G;
int main() {
    const int MAX = 1000;
    int N, M; cin >> N >> M;
    int V = MAX * MAX;
    G.assign(V, vector<int>());

    // グラフは逆向きに枝を張る、そのグラフにおいて deg は入次数を表す
    vector<int> deg(V, 0);
    for (int x = 1; x < MAX; ++x) {
        for (int y = 1; y < MAX; ++y) {
            int nx = x, ny = y;
            if (x < y) nx = rev(x);
            else ny = rev(y);
            if (nx < ny) ny -= nx;
            else nx -= ny;

            int from = x * MAX + y;
            int to = nx * MAX + ny;
            G[to].push_back(from);
            deg[from]++;
        }
    }

    // 後退解析
    queue<int> que;
    vector<int> seen(V, 0);
    for (int v = 0; v < V; ++v) if (deg[v] == 0) que.push(v);
    while (!que.empty()) {
        auto v = que.front(); que.pop();
        seen[v] = true;
        for (auto nv : G[v]) {
            if (seen[nv]) continue;
            --deg[nv];
            if (deg[nv] == 0) que.push(nv);
        }
    }

    // 答え
    int res = 0;
    for (int x = 1; x <= N; ++x) {
        for (int y = 1; y <= M; ++y) {
            int id = x * MAX + y;
            if (!seen[id]) ++res;
        }
    }
    cout << res << endl;
}

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

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

MUJIN 2018 D - うほょじご (400 点)

問題概要

制約

考えたこと