−目次

パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 251）G,Ex問題メモ
- G - Intersection of Polygons
  - 問題
  - 解法
- Ex - Fill Triangle
  - 問題
  - 例
  - 解法

パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 251）G,Ex問題メモ

パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 251）

G - Intersection of Polygons

問題

$xy$ 平面上に $N$ 頂点の凸多角形 $P$ があり、頂点座標は反時計回りに $(x_1,y_1),(x_2,y_2),...,(x_N,y_N)$
この $P$ を平行移動させた $M$ 個の多角形を考える
- $i$ 番目の多角形は、 $P$ を $x,y$ 軸方向にそれぞれ $u_i,v_i$ だけ移動させたもの
以下の $Q$ 個のクエリに答えよ
- 点 $(a_i,b_i)$ は、 $M$ 個の全ての多角形の内側にあるか？
$1 \le N \le 50$
$1 \le M,Q \le 2 \times 10^5$

解法

平行移動した頂点を全て $x$ 座標基準でソートして…とやっていって、共通部分の多角形を求めることはできるんだけど、頂点数は最悪 $O(NM)$ とかになって、 $Q$ 個のクエリで「その内側にあるか？」を1辺1辺見ていくと全体で $O(NMQ)$ となり無理。

何らかの前計算 $O(NM)$ 、クエリ $O(NQ)$ くらいが関の山と見積もれる。

点 $X$ が多角形の内側にあるか？は、多角形の頂点が反時計回りに並んでいるとすると、

「 $X$ が、 $(x_i,y_i)$ から $(x_{i+1},y_{i+1})$ へと結ぶ辺の左側に存在する」ということが、全ての辺に対して成り立つ

という方法で判定できる。

すると、元の多角形 $P$ のある1辺について考えると、そこから平行移動した辺は互いに平行なので（あたりまえ）、「一番厳しい辺」というのはクエリに依らず、1つに決まる。その方向視点で見たときに、一番左となる辺である。

P  ______
 ／      ↖  この辺の平行移動結果となるM本の辺のうち
 |_______／

         ↖  ↖  クエリの判定に用いるのは
     [↖] ↖↖   一番左であるこの辺だけでよい
          ↖     （クエリの点がこの辺より左なら、当然、他の辺よりも左）

なので、まずは前計算として $N$ 本の各辺で一番厳しい辺を洗い出す。

クエリでは、 $N$ 本の各“一番厳しい辺”より左にあるかをチェックすれば、判定できる。

判定には、3点を順番に与えたときに、その並びが「反時計回りか、一直線か、時計回りか」を正確に判定できるアルゴリズムを用いるとよい。

第7回　（臨時回）線分の交差判定再訪：Blogopolisから学ぶ計算幾何｜gihyo.jp … 技術評論社

Python3

        
          
          
              
              import sys
 
 
def ccw(ax, ay, bx, by, cx, cy):
    """
        C         :1
    A------>B  C  :0
        C         :-1
    """
    dx1 = bx - ax
    dy1 = by - ay
    dx2 = cx - ax
    dy2 = cy - ay
    if dy1 * dx2 > dy2 * dx1:
        return -1
    if dx1 * dy2 > dy1 * dx2:
        return 1
    if dx1 * dx2 < 0 or dy1 * dy2 < 0:
        return 1
    if dx1 * dx1 + dy1 * dy1 < dx2 * dx2 + dy2 * dy2:
        return -1
    return 0
 
 
input = sys.stdin.buffer.readline
 
n = int(input())
vertices = [tuple(map(int, input().split())) for _ in range(n)]
vertices.append(vertices[0])
m = int(input())
# slides = [tuple(map(int, input().split())) for _ in range(n)]
 
# n本の各辺につき、最も厳しい（内側に近い）多角形の線分を前計算
nearest = []
u, v = map(int, input().split())
for i in range(n):
    x1, y1 = vertices[i]
    x2, y2 = vertices[i + 1]
    x1 += u
    y1 += v
    x2 += u
    y2 += v
    nearest.append((x1, y1, x2, y2))
 
for _ in range(m - 1):
    u, v = map(int, input().split())
    for i in range(n):
        x1, y1 = vertices[i]
        x2, y2 = vertices[i + 1]
        x1 += u
        y1 += v
        x2 += u
        y2 += v
        cx1, cy1, cx2, cy2 = nearest[i]
        if ccw(cx1, cy1, cx2, cy2, x1, y1) == 1:
            nearest[i] = (x1, y1, x2, y2)
 
buf = []
q = int(input())
for _ in range(q):
    a, b = map(int, input().split())
    for i in range(n):
        x1, y1, x2, y2 = nearest[i]
        if ccw(x1, y1, x2, y2, a, b) < 0:
            buf.append('No')
            break
    else:
        buf.append('Yes')
 
print('\n'.join(buf))

            

        
      

Ex - Fill Triangle

問題

一辺 $N$ の正三角形状に数字が並んだものを考える
- 一番下の段は、ランレングス圧縮した状態 $P=((a_1,c_1),(a_2,c_2),...,(a_M,c_M))$ で与えられる
- それ以外の段は、直下2つの数字の和 $\mod{7}$ である
$K$ 段目の数字を列挙せよ
$1 \le N \le 10^9$
$1 \le ランレングス圧縮の要素数 M \le 200$
$1 \le K \le 5 \times 10^5$

例

N=6
P=( (3, 3), (2, 2), (1, 1) )

     2
    1 1
   2 6 2
  5 4 2 0
 6 6 5 4 3     ←②下から、直下2つの数字の和 mod 7 で埋めていく
3 3 3 2 2 1    ←①ここがPによって決まる

解法

性質

下の段の数字は、足し算を重ねて上に上っていく。
このとき、「何段上った先の何個左（右）にずれた箇所には、何回分、足されることになるか」（仮に影響値と呼ぶ）は決まっている。

1 3 3 1    最下段の[1]は、
 1 2 1     1つ上の段には 1 1
  1 1      2つ上の段には 1 2 1
  [1]      3つ上の段には 1 3 3 1
           ... 回分、足されることになる

逆に言うと、ある上の段にある数字は、そこから何段か下の個々の値に、個々の影響値を掛け合わせた和となっている。

（わかりやすくするため、mod7をせずに表記）

    23
   12 11      23は、一番下の段 3 3 3 2 を、
  6  6  5     それぞれの影響値 1 3 3 1 回ずつ足し合わせた数となっている
3  3  3  2    3*1 + 3*3 + 3*3 + 2*1 = 23

この、下段に掛け合わせる影響値の数列（上例での1 3 3 1）は、二項係数となる。
一番上を1として、影響力を計算していくと、ちょうどパスカルの三角形のようになることからわかる。

で、パスカルの三角形の素数modはちょっと面白い性質を持っていて、素数 $p$ ごとに、両端を除き0になる。

       1
      1 1
     1 2 1
    1 3 3 1
   1 4 6 4 1
  1 5 3 3 5 1
 1 6 1 6 1 6 1
1 0 0 0 0 0 0 1    mod7では、7段目(0-index)で両端以外0になる

二項係数 $\binom{p}{k} = \dfrac{p!}{(p-k)!k!}$ は、 $p$ が素数なら $k=0,p$ 以外で $p$ の倍数になることから言える。

これを $p$ ごとに縮約すると、縮約前と同じような並びが現れる。

              1
           ／   ＼        (6段省略)
          1 0...0 1
        ／ ＼   ／ ＼     (6段省略)
       1 0..0 2 0..0 1
     ／ ＼  ／ ＼  ／ ＼  (6段省略)
    1 0.0 3  0.0 3  0.0 1

なので、 $p^2$ 段目も、同じように端以外は0となる。同様に、 $p^3,p^4,...$ 段目も端以外0となる。

ずらして足し合わせる

上から $i$ 段目、左から $j$ 番目の数字を $B_{i,j}$ とする。

上記の性質を利用すれば、 $7^d$ 段上の数列というのは、今の段の $B_{i,j}$ を $7^d$ 個ずらして被る部分を足し合わせた数列ということになる。

$B_{i-7^d,j}=B_{i,j}+B_{i,j+7^d} \mod{7}$

10段目  0 1 2 3 4 5 6 0 1 2
  ↓
        0 1 2 3 4 5 6 0 1 2
                      0 1 2 3 4 5 6 0 1 2
                    ---------
 3段目                0 2 4

遡れる限り大きい $7$ のべき乗毎に、ずらして足し合わせる操作を繰り返すと答えとなる。

ランレングス圧縮を保ったまま行う必要があり、若干実装がややこしいが、頑張る。

計算量は、ずらして足し合わせる操作にランレングス圧縮の要素数だけかかり、それを最大 $66$ 回程度行うことになる。
（制約を考えると7のべき乗は $7^{10}～7^{0}$ を試せばよく、各べき乗で最大6回の操作が必要になる）

ランレングス圧縮の要素数は、はじめは $M \le 200$ であるものの、繰り返す毎に乗数的に増えていくので、あれ、やっぱり無理では？となるが、、、

一方で、終着点を考えると $K$ 要素以下になっているはずなので、増えっぱなしにはならず、どこかから減少に転じてくれることが想定される。

より詳しくは公式Editorialにあるが、 $7^x$ についてのループを回しているときのランレングス圧縮の長さは $\min(\dfrac{MN}{7^x},K+7^x)$ と評価できるので、これは $\sqrt{MN}+K$ 以下であることが説明できる。

解説 - パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 251）

Python3

細かな高速化（特にPython）として、ランレングス圧縮を行わなくてもメモリに乗るくらい1段の要素数が小さくなったら、展開した方が計算は速い。

        
          
          
              
              n, m, k = map(int, input().split())
nums = [tuple(map(int, input().split())) for _ in range(m)]
is_rle = True
 
d = 7 ** 10
 
while d > 0:
    while n - d >= k:
 
        if is_rle:
 
            i1 = 0
            a1, c1 = nums[0]
 
            r = d
            for i, (a, c) in enumerate(nums):
                if r < c:
                    i2 = i
                    a2 = a
                    c2 = c - r
                    break
                r -= c
 
            l = len(nums)
            new_nums = []
            is_all_one = True
 
            while i2 < l:
                if c1 == c2:
                    new_nums.append(((a1 + a2) % 7, c1))
                    if c1 > 1:
                        is_all_one = False
                    i1 += 1
                    i2 += 1
                    if i2 >= l:
                        break
                    a1, c1 = nums[i1]
                    a2, c2 = nums[i2]
                elif c1 < c2:
                    new_nums.append(((a1 + a2) % 7, c1))
                    if c1 > 1:
                        is_all_one = False
                    c2 -= c1
                    i1 += 1
                    a1, c1 = nums[i1]
                else:
                    new_nums.append(((a1 + a2) % 7, c2))
                    if c2 > 1:
                        is_all_one = False
                    c1 -= c2
                    i2 += 1
                    if i2 >= l:
                        break
                    a2, c2 = nums[i2]
 
            if is_all_one:
                nums = [a for a, c in new_nums]
                is_rle = False
            else:
                nums = new_nums
 
        else:
            nums = [(a1 + a2) % 7 for a1, a2 in zip(nums, nums[d:])]
 
        n -= d
 
    d //= 7
 
if is_rle:
    ans = []
    for a, c in nums:
        ans.extend([a] * c)
    print(*ans)
else:
    print(*nums)

            

        
      