Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306）G問題メモ

Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306）

ジャッジサーバくんにはヨーグルトと納豆を食べて頑張ってほしい。

G - Return to 1

問題

$N$ 頂点 $M$ 辺の有向グラフが与えられる
頂点1から出発して、ちょうど $10^{10^{100}}$ 回の移動後に頂点1にいることが可能か、判定せよ
$2 \le N \le 2 \times 10^5$
$1 \le M \le 2 \times 10^5$

解法

変なDijkstra。

移動回数が変な値だが、重要な要素は「2と5のみを素因数に含む」こと、かつめちゃ大きいので「2と5のみを素因数に含むような移動回数で1→1に移動さえできれば、それを繰り返せばいいだろう」ということ。

（たとえば、移動回数が100回みたいに少ないと、80回（素因数が2と5のみ）で1→1に移動できるルートがあったとしても、それを繰り返してちょうど100回にすることはできないが、今回はそういうのは心配しなくていいだろう、ということ）

2と5のみを素因数に含む数を「良い数」とする。

1から出発して1に戻ってくるような経路で、長さが良い数のものがあればそれでよし。
無くても、ある2つの経路のGCDが良い数なら、拡張ユークリッド互除法のようにして良い数の周回を作り出せる。

問題は、無限にある経路のGCDをどうやって調べるか、ということ。

差分のGCD

以降、頂点1に戻れないとややこしいので、グラフを「1から到達でき、1に戻れる頂点」のみにしておくとする。

以下の性質を利用する。

集合 $A=(a_1,a_2,...)$ の総GCDは、「$a_1$」と「$(a_1-a_i)$ の総GCD」のGCDと一致する

よって、各頂点に付き、差分で見る。
$a_1$ に相当するものを「最も短い 1→1経路の距離」とし、そこからの差分で考える。

まず、いったん最短経路探索で、各頂点への1からの最短距離 $d_i$ を求めておく。

$d_v=8$ である頂点 $v$ に、別ルートで距離68と98でもたどり着けるとする（差分60と90）。
残りを最短ルートで頂点1まで戻ることを考えると、1→1ルートにおいてもその差分はそのまま残る。
よって、何周かすることで $GCD(60,90)=30$ の調整が可能であることがわかる。
この場合、$v$ から次の頂点へは、距離を $d_v+GCD+1=39$ として探索を進めてよい。

つぎ、$v$ に距離128（差分120）でたどり着いたとする。
既に30単位での調整が可能であることはわかっており、$GCD(30,120)=30$ で更新はない。
その場合、この差分で $v$ 以降を探索しても、既に分かっている差分しか発生しないので次に探索を進めなくてよい。

つぎ、$v$ に83（差分75）でたどり着いたとする。
$GCD(30,75)=15$ となり、GCDに更新が発生する。
その場合、次の頂点への距離を $d_v+GCD+1=24$ として探索を続ける。

このようにして、いずれかの頂点でGCDが良い数になればOK。

ならない場合、同じ頂点が何度も探索されるのでTLEが気になる。
ただ、GCDはどんどん減っていく。
良い数でないGCDだと3の累乗が最も更新回数が多くなるが、頂点数が上限なので、$3^{11}=177147$ で、11回程度しか更新は発生しない。
（しかも別ルートで $3^{10},3^9,...$ を作らないといけないし、全ての頂点についてそれを成り立たせることも難しそうなので、実際はもっと少なく済むはず）

Dijkstraの $O((N+M) \log{N})$ に11程度の定数倍が付いても、十分通る。

Python3

from collections import deque
from heapq import heappop, heappush
from math import gcd


def bfs(n, links, s=0, INF=1 << 60):
    dists = [INF] * n
    q = deque()
    for u in links[s]:
        q.append(u)
        dists[u] = 1

    while q:
        u = q.popleft()
        rd = dists[u]
        for v in links[u]:
            if dists[v] == INF:
                dists[v] = rd + 1
                q.append(v)

    return dists


def solve(n, m, links, rev_links):
    INF = 1 << 60
    INF10 = 10 ** 18

    # 逆方向に探索して、0 に戻ってこれる頂点を計算
    rev_dists = bfs(n, rev_links)

    rd0 = rev_dists[0]
    if rd0 == INF:
        return False
    if INF10 % rd0 == 0:
        return True

    for i in range(n):
        links[i] = [j for j in links[i] if rev_dists[j] != INF]

    # 順方向で、0からの基準距離（最短距離）を計算
    dists = bfs(n, links)

    # 基準距離との差分のgcdを保持
    gcds = [-1] * n
    q = []
    for u in links[0]:
        gcds[u] = 0
        q.append((1, u))

    while q:
        d, u = heappop(q)
        nd = d + 1
        for v in links[u]:
            gv = gcds[v]
            if gv == -1:
                gcds[v] = 0
                heappush(q, (nd, v))
            else:
                ngv = gcd(gv, nd - dists[v])
                if gv != ngv:
                    if INF10 % ngv == 0:
                        return True
                    gcds[v] = ngv
                    heappush(q, (dists[v] + ngv, v))
    return False


t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    links = [[] for _ in range(n)]
    rev_links = [[] for _ in range(n)]
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        links[u].append(v)
        rev_links[v].append(u)

    ans = solve(n, m, links, rev_links)
    print('Yes' if ans else 'No')

目次

Toyota Programming Contest 2023#3（AtCoder Beginner Contest 306）G問題メモ

G - Return to 1

問題

解法

差分のGCD