SMBCプログラミングコンテスト #2（AtCoder Beginner Contest 481）E,F問題メモ

SMBCプログラミングコンテスト #2（AtCoder Beginner Contest 481）

E - Most Brilliant Starry Sky

問題文

$xy$ 平面上に $N$ 個の星があります。$i$ 個目の星は、座標が $(X_i,Y_i)$ である点として表されます。
原点を通りどの星も通らない直線を $1$ 本引き、その直線によって分けられる二つの領域のうちどちらか一方の領域を選びます。
選んだ領域に含まれる星の個数としてありうる最大値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \le T \le 2 \times 10^5$
$1 \le N \le 2 \times 10^5$
全てのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
$-10^9 \le X_i,Y_i \le 10^9$
$(X_i,Y_i) \ne (0,0)$
$(X_i,Y_i) \ne (X_j, Y_j) ~ (i \ne j)$
どの相異なる $2$ 個の星についても、それらと原点が一直線上に並ぶことはない
入力される値はすべて整数

解法

偏角ソート。

直線の傾きを、$-\infty～\infty$ までぐり～んと回転させることを考える。

「$x \gt 0$」または「$x=0$ で $y \gt 0$」の点の個数を $p$、そうでない点の個数を $q$ とする。
傾きが $-\infty$ の時、一方は $p$ でもう一方が $q$ である。
$x=0$ 以外の点を $y/x$ でソートし、その順に点を見ていく。
- 見ている点が最初 $p$ 側の点だった場合、その傾きを境に点は $p$ から $q$ へ移る。$p-=1,q+=1$
- 見ている点が最初 $q$ 側の点だった場合、その傾きを境に点は $q$ から $p$ へ移る。$p+=1,q-=1$

この過程で、$p,q$ の値として出現した最大値が答えとなる。

ただし、今回の $-10^9 \le X_i,Y_i \le 10^9$ という制約だと、精度が足りず単なる $y/x$ のソートでは正しい値を保証できなくなる。（目安として、実数でのソートで正しさが保証されるのは $2^{26} \simeq 6.7 \times 10^7$）

Python なら、分子と分母を分けて持って cmp_to_key で比較するか、または Fraction を使うと正確にソートできる。
速度は落ちるが、今回のように単純に全体を1回ソートするだけなら問題ない。

Python3

from fractions import Fraction


def solve(n, points):
    pos = 0
    neg = 0
    pos_neg = []
    for x, y in points:
        if x == 0:
            if y > 0:
                pos += 1
            else:
                neg += 1
        elif x > 0:
            pos_neg.append((Fraction(y, x), 1))
            pos += 1
        else:
            pos_neg.append((Fraction(y, x), -1))
            neg += 1
    pos_neg.sort()

    ans = max(pos, neg)
    for _, diff in pos_neg:
        pos -= diff
        neg += diff
        ans = max(ans, pos, neg)
    return ans


t = int(input())
for _ in range(t):
    n = int(input())
    points = [list(map(int, input().split())) for _ in range(n)]
    ans = solve(n, points)
    print(ans)

F - Evil Shortest Path

問題文

$N$ 頂点 $M$ 辺の有向グラフが与えられます。
- $i$ 番目の辺は頂点 $A_i$ から頂点 $B_i$ へと向かう辺であり、この辺には $1$ 以上 $9$ 以下の数字 $C_i$ が書かれています。
辺の向きに従って移動するとき、通った辺に書かれた数字を通った順につなげて得られる整数を、その移動のスコアと呼びます。
- 例えば、通った辺に書かれた数字が順に $3,1,4$ であるとき、その移動のスコアは $314$ です。同じ頂点や辺を複数回通ってもかまいません。
$v=2,3,\ldots,N$ のそれぞれについて、頂点 $1$ から頂点 $v$ へ移動するときのスコアの最小値を $998244353$ で割ったあまりを求めてください。
ただし、入力として与えられる有向グラフは、頂点 $1$ から他のすべての頂点へ、辺の向きに従って移動できることが保証されます。

制約

$2 \le N \le 2\times 10^5$
$N-1 \le M \le 2\times 10^5$
$1 \le A_i,B_i \le N$
$1 \le C_i \le 9$
入力される値はすべて整数
頂点 $1$ から他のすべての頂点へ、辺の向きに従って移動できる

解法

$1→u$ のスコア最小値を $S(u)$ とすると、$1→u→v$ のような経路のスコア最小値は必ず $S(u)$ を接頭辞に持つ。
「$1→u$ の2番目以降のスコアが、実は $1→u→v$ では最適になる」ようなことはない。

よって、巨大な整数同士の比較コストを無視すれば、スコアをそのまま距離とした Dijkstra が使えはするのだが、、、

①--1→○--2→○→...→○--3→○→...○--5→○--6--,
 `--1→○--2→○→...→○--4→○→...○--5→○--6→②
 |-------ほぼ一緒------|  ↑  |-----ほぼ一緒------|
                       僅かに違う

こんな時、①→②は上と下とどちらの経路がいいのか比較できない。スコアをそのまま持ったらTLE or MLE になるし、modを取ったら大小は失われる。

スコアをベースとして考える。 ①を根として、それぞれから1～9の辺が生えるTrieをイメージする。

                ①
    1↙     2↙....8↘     9↘
   ○       ○       ○       ○
 ↙↓↘   ↙↓↘   ↙↓↘   ↙↓↘
○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○

これらの辺・頂点は、元のグラフと区別して「Trie上の辺」「Trie上の頂点」と呼ぶことにする。

グラフ上の辺とコストが同じ辺を Trie でたどった時、 $1→v$ までのあり得る経路スコア（＝辿り着くTrie上の頂点）は複数あるが、その内「Trie上で最も上の階層、階層が同じなら最も左の頂点」が、$v$ のスコアの最小値を表すことになる。

よって、Trie上の幅優先探索（同じ頂点からは、末尾に付けた数字が小さい方がキューに先に入る）順に従うと、巨大な数値を直接扱わなくても、$v$ が初めて訪れたTrie上の頂点が、$v$ のスコアの最小値であると保証される。

$v$ のスコアの最小値を表すTrie上の頂点を $t$ とする。異なるグラフ上の頂点 $u_1,u_2,...,u_k$ が、同じ $t$ となることもありえる。

$t$ が同じとなるような $u_1,...,u_k$ はまとめて処理する。つまり、単なる幅優先探索なら、

×: 頂点優先
$u=u_1,u_2,...,u_k$ の順に、
- $c=1,2,...,9$ の順に、
  - 辺コスト $c$ の辺 $u→v$ に対し、$v$ が未訪問なら、$v$ のスコア $S(v)$ を $10S(u)+c$ で確定する

としてしまうが、これだと $u_2→v$ の辺に $u_1→v$ よりよいコスト $c$ があっても、見つけることができない。

○: コスト優先
$c=1,2,...,9$ の順に、
- $u=u_1,u_2,...,u_k$ の順に、
  - 辺コスト $c$ の辺 $u→v$ に対し、$v$ が未訪問なら、$v$ のスコア $S(v)$ を $10S(u)+c$ で確定する

とすると、上手くいく。

Python3

最短距離に使われない辺を最初に除いたりしていて（本来は不要）、効率の良いコードではない。

from collections import deque, defaultdict


def solve(n, m, edges):
    links = [defaultdict(lambda: 10) for _ in range(n)]
    for a, b, c in edges:
        a -= 1
        b -= 1
        links[a][b] = min(links[a][b], c)
    INF = 1 << 60
    dists = [INF] * n
    dists[0] = 0
    predecessors = [[] for _ in range(n)]
    q = deque([0])
    while q:
        u = q.popleft()
        dv = dists[u] + 1
        for v, c in links[u].items():
            if dists[v] > dv:
                dists[v] = dv
                predecessors[v] = [(u, c)]
                q.append(v)
            elif dists[v] == dv:
                predecessors[v].append((u, c))
    links2 = [defaultdict(list) for _ in range(n)]
    for v in range(n):
        for u, c in predecessors[v]:
            links2[u][c].append(v)
    groups = [-1] * n
    groups[0] = 0
    mapping = {0: [0]}
    gid = 1
    links3 = [[] for _ in range(n)]
    q = deque([0])
    while q:
        gu = q.popleft()
        for c in range(1, 10):
            nxt = set()
            for u in mapping[gu]:
                if c in links2[u]:
                    vvv = links2[u][c]
                    nxt.update(vvv)
            nxt = [v for v in nxt if groups[v] == -1]
            if len(nxt) == 0:
                continue
            links3[gu].append((c, gid))
            mapping[gid] = nxt
            for v in nxt:
                groups[v] = gid
            q.append(gid)
            gid += 1

    n3 = gid

    best = [-1] * n3
    best[0] = 0
    MOD = 998244353

    q = deque([0])
    while q:
        u = q.popleft()
        for c, v in links3[u]:
            if best[v] != -1:
                continue
            best[v] = (best[u] * 10 + c) % MOD
            q.append(v)

    ans = [0] * n
    for i in range(n3):
        for u in mapping[i]:
            ans[u] = best[i]

    return ans[1:]


n, m = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, edges)
print('\n'.join(map(str, ans)))

目次

SMBCプログラミングコンテスト #2（AtCoder Beginner Contest 481）E,F問題メモ

E - Most Brilliant Starry Sky

問題文

制約

解法

F - Evil Shortest Path

問題文

制約

解法