AtCoder Beginner Contest 206（Sponsored by Panasonic）E,F問題メモ

AtCoder Beginner Contest 206（Sponsored by Panasonic）

E - Divide Both

やたらユーザー解説が充実してるね。解説書きたい欲が刺激される問題なんだろうか。

• ともに $L$ 以上 $R$ 以下の整数のペア $(x,y)$ で、以下の条件を全て満たすものの個数を求めよ
• 条件
  • $g=GCD(x,y)$ として、
    • $g \neq 1$
    • $\frac{x}{g} \neq 1$
    • $\frac{y}{g} \neq 1$
• $1 \le L,R \le 10^6$

いろいろな解法がある。

まず、GCDが1にならないペアの個数を求める。これで1つめの条件をクリアするものが全て揃う。
その後、2,3番目の条件に違反するものを除けば答えとなる。
一度に全条件を考える必要は無く、分けて考えられることに気付くと、幾分かスッキリする。

GCDが「ちょうどある値 $g$」になる $(x,y)$ の組は直接的に求めにくいが、 「$g$ の倍数」になる組の個数なら簡単に求められる。

• $C_g=$（$L$ 以上 $R$ 以下の $g$ の倍数の個数）=（$R$ 以下の $g$ の倍数の個数）-（$L$ 未満の $g$ の倍数の個数）

とすると、$C_g=\left \lfloor \dfrac{R}{g} \right \rfloor - \left \lfloor \dfrac{L-1}{g} \right \rfloor$ となり、 $C_g$ 個から2つ選べばよいので $C_g^2$ 通りの組ができる。

L, R = 5, 15
g = 3

L以上R以下のgの倍数: 6  9 12 15  →  ペアは16通り

この内、GCDが「ちょうど $g$ 」以外である組のGCDは $2g,3g,...$ であるはずなので、 「ちょうど $2g$」「ちょうど $3g$」……の組の個数を先に求めておいて 全て除けば「ちょうど $g$」の個数が求まる。

g = 15 :  (15, 15)
g = 12 :  (12, 12)
g = 9  :  ( 9,  9)
g = 6  :  ( 6,  6), ( 6, 12), (12,  6)

ちょうど 3 になるのは、16 - 6 = 10 ペア

現在の $g$ を求めるには、$2g,3g,...$ など自身より大きい場合の数が先に求まっていて欲しいので、 $g$ は大きい方から決定するのがポイント。

$g \ge 2$ の全ペア数の総和が「GCDが1にならないペア数」となる。

計算量は $O(R \log{R})$ となる。

2,3番目の条件は、言い換えると「$x$ が $y$ の倍数」「$y$ が $x$ の倍数」という関係である。

片方の数 $L \le k \le R$ を固定し、 $R$ 以下で $k$ の倍数となる相方が何個取れるかを求めていけば、 その総和が2,3番目の条件に違反するものとなる。

その個数は、$2\dfrac{R}{k}-1$ となる。
「$x$ が $k$ の場合」「$y$ が $k$ の場合」で各 $\dfrac{R}{k}$ 個ずつあるが、 ともに $k$ である $(k,k)$ を重複して数えているので1つ除く、という計算になる。

Python3

def solve(l, r):
    if r < 4:
        return 0
    if l < 4:
        l = 4

    ans = 0
    max_g = r // 2
    patterns = [0] * (max_g + 1)

    for g in range(max_g, 1, -1):
        rg = r // g
        lg = (l - 1) // g
        c = rg - lg
        tmp = c * (c - 1)
        for h in range(g * 2, max_g + 1, g):
            tmp -= patterns[h]
        patterns[g] = tmp
        ans += tmp - (0 if l > g else (c - 1) * 2)

    return ans


l, r = map(int, input().split())
ans = solve(l, r)
print(ans)

F - Interval Game 2

• $[L_i,R_i)$ で表される $N$ 個の半開区間がある
• 先手Aliceと後手Bobがゲームをする
• ゲームのルール
  • 自分の手番が来たら、これまで選ばれたどれとも重ならない半開区間を1つ選ぶ
  • 自分の手番で操作できなくなった方が負け
• 必勝がどちらか求めよ
• $1 \le N \le 100$
• $1 \le L_i \lt R_i \le 100$

Grundy数。

Grundy数は、Nim（石取りゲーム）の解法に使えるのが代表的な例ではあるが、 「最初から山が複数個ある状態で個々の山のGrundy数を求め、XORを取る」 だけのものと考えていると、ちょっと発想しにくいかも知れない。

「山が最初は1つで、1回の操作毎に複数の山に分割される」場合も使える。

|---1----|     |--3--|
       |---2----|
  |-4-|   |-5-|

区間1～5が残っている状態のgrundy数を $g(\{1,2,3,4,5\})$ と表現することにする。

たとえば区間5を選択すると、左 $\{1,4\}$ と右 $\{3\}$ の2つの山に分けられる。
もうこの2つが1回の操作で同時に変化することはない。

この場合、遷移先のgrundy数はこの2つの山のgrundy数のXOR、つまり $g(\{1,4\}) \oplus g(\{3\})$ となる。

計算過程は略すが、$g(\{1,4\})=1, g(\{3\})=1$ なので、
「$\{1,2,3,4,5\}$ から区間 $5$ を選んだ場合の遷移先grundy数は $0$」となる。

grundy数は、「その状態から遷移できない、最小の非負整数」なので、同じことを区間1～4に対してもやる。

• 区間1を選んだ場合: $g(\phi) \oplus g(\{3,5\})=0$
• 区間2を選んだ場合: $g(\{4\}) \oplus g(\phi)=1$
• 区間3を選んだ場合: $g(\{1,4,5\}) \oplus g(\phi)=0$
• 区間4を選んだ場合: $g(\phi) \oplus g(\{2,3,5\})=1$

より、$g(\{1,2,3,4,5\})=2$ となる。

1つの区間を選んだとき、どのように分割されるかを求める部分で実装に少し迷うが、 $N \le 100$ で少ないので、区間を仮定するたびに毎回 $N$ 個を走査して 分割後の左/右に含まれるどうかを調べればよい。

• 左端が $l$ である区間を選んだとき、左の区間は $R_i \le l$
• 右端が $r$ である区間を選んだとき、右の区間は $L_i \ge r$

Python3

import sys
from bisect import bisect_left, bisect


def calc_grundy(l, r):
    global lrs, grundy, ln, lbi, rbi
    if l >= ln:
        return 0
    if grundy[l][r] != -1:
        return grundy[l][r]

    mex = set()
    for li, ri in lrs:
        if li < l or r <= ri:
            continue
        lg = calc_grundy(l, lbi[li])
        rg = calc_grundy(rbi[ri], r)
        mex.add(lg ^ rg)

    for i in range(100):
        if i not in mex:
            grundy[l][r] = i
            return i


input = sys.stdin.buffer.readline
buf = []
t = int(input())
for _ in range(t):
    n = int(input())
    lrs = []
    lll_cmp = set()
    rrr_cmp = set()
    for i in range(n):
        l, r = map(int, input().split())
        lll_cmp.add(l)
        rrr_cmp.add(r)
        lrs.append((l, r))
    lll = sorted(lll_cmp)
    rrr = sorted(rrr_cmp)
    lll_rev = {l: i for i, l in enumerate(lll)}
    rrr_rev = {r: i for i, r in enumerate(rrr)}

    ln = len(lll)
    rn = len(rrr)

    lbi = [bisect(rrr, l) for l in lll]
    rbi = [bisect_left(lll, r) for r in rrr]

    new_lrs = []
    for i, (l, r) in enumerate(lrs):
        li = lll_rev[l]
        ri = rrr_rev[r]
        new_lrs.append((li, ri))

    lrs = new_lrs

    grundy = [[-1] * (rn + 1) for _ in range(ln)]

    ans = calc_grundy(0, rn)

    if ans == 0:
        buf.append('Bob')
    else:
        buf.append('Alice')

print('\n'.join(buf))