−目次

ユニークビジョンプログラミングコンテスト2024 秋（AtCoder Beginner Contest 372）F,G問題メモ
- F - Teleporting Takahashi 2
  - 問題文
  - 制約
  - 解法
- G - Ax + By < C
  - 問題文
  - 制約
  - 解法

ユニークビジョンプログラミングコンテスト2024 秋（AtCoder Beginner Contest 372）F,G問題メモ

ユニークビジョンプログラミングコンテスト2024 秋（AtCoder Beginner Contest 372）

F - Teleporting Takahashi 2

問題文

$N$ 頂点 $N+M$ 辺の単純有向グラフ $G$ があります。
- 頂点には $1$ から $N$ の番号が、辺には $1$ から $N+M$ までの番号がつけられています。
- 辺 $i$ $(1 \leq i \leq N)$ は頂点 $i$ から頂点 $i+1$ へ張られています。（ただし、頂点 $N+1$ は頂点 $1$ とみなします。）
- 辺 $N+i\ (1\leq i\leq M)$ は頂点 $X_i$ から頂点 $Y_i$ へ張られています。
高橋君は頂点 $1$ にいます。各頂点において、高橋君はその頂点から有向辺が張られている頂点に移動することができます。
高橋君がちょうど $K$ 回移動する方法が何通りあるかを求めてください。
- すなわち、長さ $K+1$ の整数列 $(v_0,v_1,\dots,v_K)$ であって、下記の $3$ つの条件をすべて満たすものの個数を求めてください。
  - $i=0,1,\dots,K$ について、 $1\leq v_i\leq N$
  - $v_0=1$
  - $i=1,2,\ldots,K$ について、頂点 $v_{i-1}$ から頂点 $v_i$ へ有向辺が張られている。
ただし、答えは非常に大きくなることがあるので、答えを $998244353$ で割った余りを出力してください。

制約

$2\leq N\leq 2\times 10^5$
$0\leq M\leq 50$
$1\leq K\leq 2\times 10^5$
$1\leq X_i,Y_i\leq N,X_i\neq Y_i$
$N+M$ 本の有向辺はすべて異なる
入力は全て整数

解法

辺は、 $1→2→3→...→N→1$ をぐるっと一周する辺と、 $M$ 本の特殊辺からなる。特殊辺はとても少ない。

グラフ $G$ から「特殊辺の端点になっていない、かつ①でない」頂点は縮約し、コスト付きのグラフ $H$ に変えてしまう。

これを             こうじゃ
(G)                (H)  1
    ①-→②          ①-→②
  ↗  \ /  ↘       ↑1\ /1｜
⑥     X     ③    2｜  X  ｜2
  ↖ ↙ ↘ ↙       ｜↙ ↘↓
    ⑤←-④          ⑤←-④
                        1

グラフ $H$ の頂点数は、多くとも $2M+1 \le 101$ 個である。
これなら、以下のDPをおこなえる。

$\mathrm{DP}[i,j]=$ ①を出発してコストがちょうど $i$ で頂点 $j$ にいるような経路の個数

状態数が $O(KM)$ 、遷移も $i$ ごとに $M$ 回なので $O(KM)$ で、十分小さい。

全て埋め終わったら、答えとなる箇所を足していく。
この時、 $G$ から縮約した頂点で終わる経路も足し合わせる必要がある。

例えば②の場合、以下の2つが答えに寄与する。

コスト $K$ で②に着く経路 $\mathrm{DP}[K,2]$
コスト $K$ で③に着く経路は、 $K-1$ で②に着く経路と1対1対応する。 $\mathrm{DP}[K-1,2]$

$H$ の頂点集合を $V_H$ 、 $V_H$ の頂点 $v$ に対し、時計回りで次の頂点までのコストを $C_v$ として、

$\displaystyle \sum_{v \in V_H}\sum_{k=0}^{\min(K,C_v-1)} \mathrm{DP}[K-k,v]$

が答えとなる。

Python3

G - Ax + By < C

問題文

長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N),C=(C_1,C_2,\ldots,C_N)$ が与えられます。
以下の条件を満たす正整数の組 $(x,y)$ の個数を求めてください。
- 全ての $1\le i\le N$ に対して $A_i\times x+B_i\times y \lt C_i$ が成立する。
なお、条件を満たす正整数の組の個数は有限個であることが証明できます。
$T$ 個のテストケースが与えられるので、それぞれに対して答えを求めてください。

制約

$1\le T\le 2\times 10^5$
$1\le N\le 2\times 10^5$
$1\le A_i,B_i,C_i\le 10^9$
全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下である
入力は全て整数

解法

条件は $y \lt \dfrac{-A_i x+C_i}{B_i}$ と言い換えられる。
制約から、傾きは負、切片は正であり、ゼロ除算の心配は無い。

このような直線群のどれよりも下にある、 $(x,y)$ が互いに正の格子点の個数を数えればよい。

y^
 |  ＼
 |~~--_x   \
 | ・ ・＼--\_
 | ・ ・  ＼ \~~--__
 | ・ ・ ・ ＼\
 | ・ ・ ・ ・ x
 | ・ ・ ・ ・  \＼
 | ・ ・ ・ ・ ・\
 +-----|-------|-------> x

以下の2段階の手順で解ける。

ConvexHullTrick の要領で、最小を取り得る直線と、そいつが最小となる区間を計算
各区間に対し、FloorSum で答えを求める

やることは少し高度な典型の素直な組合せだが、注意すべき点が諸々あり、バグらせやすい。

傾きや切片が有理数となるので、分子と分母で保持するなどして誤差を防ぐ。
格子点のうち、 $x=0$ または $y=0$ となる点や、直線上の点は含んではいけない。
- 特に直線上の点について、素直なFloorSumは含んだ結果が求まるので、除く必要がある。
単純にConvexHullTrickを適用した結果は、 $y \lt 0$ となる範囲でしか最小とならない直線も含む。
- 途中で次の直線との交点が $y \le 0$ になる直線になったらそこで打ち切る。
- FloorSumも、最後の直線は「次の直線」ではなく「 $x$ 軸」との交点までの区間で求める。

Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

from functools import cmp_to_key
from math import gcd
 
 
def floor_sum(n, m, a, b):
    """
    i = 0..n-1 につき、(ai + b) // m の和を計算する
 
    https://rsk0315.hatenablog.com/entry/2020/12/13/231307
    """
    if n <= 0:
        return 0
 
    result = 0
    if a < 0:
        # a±m は45度の ◢ or ◥ の分の足し引きで調整できる。
        a2 = a % m
        result -= n * (n - 1) // 2 * ((a2 - a) // m)
        a = a2
    if b < 0:
        # b±m は n×m の矩形の足し引きで調整できる。
        b2 = b % m
        result -= n * ((b2 - b) // m)
        b = b2
 
    while n:
        if a >= m:
            d, a = divmod(a, m)
            result += n * (n - 1) // 2 * d
        if b >= m:
            d, b = divmod(b, m)
            result += n * d
        d, mod = divmod(a * (n - 1) + b, m)
        result += d
        n = d
        m, a = a, m
        b = mod
    return result
 
 
def count_grid_points_on_line(a, b, c, l, r):
    """ y=(-a/b)x+(c/b) が通る格子点の、l<=x<r の範囲での個数 """
    g = gcd(a, b)
    if c % g != 0:
        return 0
    a //= g
    b //= g
    c //= g
    x0 = c * pow(a, -1, b) % b
    return (r - x0 - 1) // b - (l - x0 - 1) // b
 
 
def solve(n, lines):
    def cmp_func(abc1, abc2):
        l = -abc1[0] * abc2[1]
        r = -abc1[1] * abc2[0]
        if l == r:
            return 0
        if l < r:
            return -1
        else:
            return 1
 
    # 傾きが同じやつがあるとCHTでちょっと面倒なので、切片が一番下のやつのみ残す
    use_lines = {}
    for a, b, c in lines:
        g = gcd(a, b)
        key = (a // g, b // g)
        if key in use_lines:
            a1, b1, c1 = use_lines[key]
            if b * c1 > b1 * c:
                use_lines[key] = (a, b, c)
        else:
            use_lines[key] = (a, b, c)
    lines = sorted(use_lines.values(), key=cmp_to_key(cmp_func), reverse=True)
    # ConvexHullTrick
    INF = 1 << 30
    stack = [(-INF * INF, 1, -INF, -INF)]  # (a, b, c, d) -> 傾き -a/b, 切片 c/b の直線が、現状 x >= d 以降で最小
    for a, b, c in lines:
        while True:
            a0, b0, c0, d0 = stack[-1]
            # (a,b,c) が、x=d0 で (a0,b0,c0) より下なら、(a0,b0,c0) は意味が無い
            if -a * b0 * d0 + c * b0 <= -a0 * b * d0 + c0 * b:
                stack.pop()
            else:
                cb = c0 * b - c * b0
                ab = a0 * b - a * b0
                if cb < 0:
                    cb *= -1
                    ab *= -1
                d1 = (cb - 1) // ab + 1
                stack.append((a, b, c, d1))
                break
    # 最後の直線の分を余裕を持って追加。
    stack.append((0, 0, 0, 1 << 60))
    # 格子点の個数を floor_sum で数える
    ans = 0
    for i in range(1, len(stack) - 1):
        a, b, c, d0 = stack[i]
        _, _, _, d1 = stack[i + 1]
        # 直線の開始点の時点で y<=0 なら以降は不要
        if -a * d0 + c <= 0:
            break
        # x軸をまたぐ場合は、x軸との交点まで（次のループでbreak）
        d1 = min(d1, (c - 1) // a + 1)
        ans += floor_sum(d1, b, -a, c) - floor_sum(d0, b, -a, c)
        # 直線の上にある格子点を除く
        ans -= count_grid_points_on_line(a, b, c, d0, d1)
    return ans
 
 
t = int(input())
buf = []
for _ in range(t):
    n = int(input())
    lines = [tuple(map(int, input().split())) for _ in range(n)]
    ans = solve(n, lines)
    buf.append(ans)
 
print('\n'.join(map(str, buf)))