基本は 公式Editorial の通り。
上記ではセグメント木を使っているが、この問題は FenwickTree を使ってもよい。
通常、区間minはFenwickTree上で使うには厳しめの制約があるのだが、本問題では
という条件を満たすので、FenwickTreeを使え、定数倍高速になる。
（まぁ、無理してFenwickTreeを使わないと通らないような時間制約でもないので、セグ木を使えばよいのだが）
Python3
from collections import defaultdict
class FenwickTreeMin:
def __init__(self, n):
INF = 1 << 60
self.size = n
self.tree = [INF for _ in range(n + 1)]
self.depth = n.bit_length()
def add(self, i, x):
i += 1
tree = self.tree
while i <= self.size:
tree[i] = min(tree[i], x)
i += i & -i
def sum(self, i):
i += 1
s = 1 << 60
tree = self.tree
while i > 0:
s = min(s, tree[i])
i -= i & -i
return s
n = int(input())
seconds = {0}
boxes = defaultdict(list)
for _ in range(n):
a, b, c = sorted(map(int, input().split()))
boxes[a].append((b, c))
seconds.add(b)
s2i = {s: i for i, s in enumerate(sorted(seconds))}
INF = 1 << 60
fwt = FenwickTreeMin(len(s2i))
for a in sorted(boxes.keys()):
bcs = boxes[a]
for b, c in bcs:
i = s2i[b]
x = fwt.sum(i - 1)
if x < c:
print('Yes')
exit()
for b, c in bcs:
i = s2i[b]
fwt.add(i, c)
print('No')
空の箱を $N$ 個並べて、番号の付いたボールを1から順にどれかの箱に1個ずつ入れていき、順列を作ることをイメージする。
ボール $i$ は「$i-X$ より前の箱」か「$i+X$ より後の箱」にしか入れられないので、
その範囲の空いている箱の数を $i=1,2,...,N$ で乗じていけば答えとなる。
ただ、$i-1$ 以前のボールをどこに入れたかにより、$i$ を入れられる箱の数が変わってくる。
$i$ が禁止されていない箱に多く入れてたら、その分 $i$ を入れるときに空いている箱は減る。
N=9 X=3 i=5
箱 1 2 3 4 5 6 7 8 9
o o x x x x x o o : 5の玉を入れられる範囲
4 2 1 3 : 既に入れたボールの状態の一例
このとき、5のボールは2,8,9の3箇所の箱に入れられる
4 2 3 1 : 既に入れたボールの状態の一例2
このとき、5のボールは2の1箇所の箱にしか入れられない
なので、その状態別に分けてDPをおこないたい。
いま仮に、$[1, i-X]$、$(i-X, i+X)$、$[i+X, N]$ で区間を分けて、
それぞれで $i-1$ までのボールを入れた個数が判明していたら、
$i$ のボールを入れられる箱の個数は計算できる。
大まかにこういう感じの情報をDPに持たせればよさそうなのだが、、、
ただ、それを $i+1$ に遷移させると、必要な区間が $[1, i-X+1]$、$(i-X+1, i+X+1)$、$[i+X+1, N]$ となる。
$i-X+1$ と $i+X$ が区間境界をまたいで移るが、
それらに入ってる/入ってないのが何通りかがわからないと遷移ができない。
区間でまとめて個数をカウントしているため、パッと分からなそうに見える。
ところが、2つのうち「$i+X$」の方にボールが入っている/入ってないパターン数は、実は計算できる。
$i$ の小さい方から考えている以上、$[i+X, N]$ にはこれまでどのボールでも自由に入れられた。
また、その入れ方は $i+X-1$ より前とは独立している。
よって、DPに記録されたパターンは対称的であり、確率で按分できる。
例えば $[i+X,N]$ に入れたボールの数が $r$ 個の時にDPの値が $k$ だとすると、
となる。
$i-X+1$ の方は残念ながら対称的ではないのでこのような按分はできない。
ただ、$X$ が十分小さいので、$(i-X,i+X)$ の状態はbitsetで管理してやればよい。
$DP[i,j,S]=$ ボール $i$ まで入れる箱を決めて、$i+X$ より小さい箱に入れた個数が $j$ 個、うち $(i-X,i+X)$ の範囲の状態がbitset $S$ で表される状態のパターン数
こうすると、遷移は $O(1)$ であり、全体で $O(N^2 4^X)$ で求められる。
Python3
import os
import sys
import numpy as np
def solve(inp):
def mod_pow(x, a, MOD):
ret = 1
cur = x
while a:
if a & 1:
ret = ret * cur % MOD
cur = cur * cur % MOD
a >>= 1
return ret
def prepare_factorials(n, MOD):
factorials = np.ones(n + 1, np.int64)
for m in range(1, n + 1):
factorials[m] = factorials[m - 1] * m % MOD
inversions = np.ones(n + 1, np.int64)
inversions[n] = mod_pow(factorials[n], MOD - 2, MOD)
for m in range(n, 1, -1):
inversions[m - 1] = inversions[m] * m % MOD
return factorials, inversions
n, x = inp
MOD = 998244353
facts, finvs = prepare_factorials(n, MOD)
def ncr(n, r):
if n < r:
return 0
return facts[n] * finvs[r] % MOD * finvs[n - r] % MOD
x2 = x * 2 - 1
mask = (1 << x2) - 1
dp = np.zeros((n + 1, n + 1, 1 << x2), np.int64)
dp[0, 0, 0] = 1
pop_count = np.zeros(1 << x2, np.int64)
pop_count[1] = 1
for i in range(1, 1 << (x2 - 1)):
pop_count[i << 1] = pop_count[i]
pop_count[(i << 1) | 1] = pop_count[i] + 1
for i in range(n):
for j in range(i + 1):
for bitset in range(1 << x2):
if dp[i, j, bitset] == 0:
continue
# print(i, j, bitset, dp[i, j, bitset])
l_filled = j - pop_count[(bitset << 1) & mask]
l_empty = max(0, i - x + 1 - l_filled)
r_space = max(0, n - i - x)
r_filled = i - j
r_pattern_total = ncr(r_space + 1, r_filled)
r_pattern_next_empty = ncr(r_space, r_filled)
inv_r_pat = mod_pow(r_pattern_total, MOD - 2, MOD)
nxt_bitset0 = (bitset << 1) & mask
nxt_bitset1 = nxt_bitset0 | 1
# print('l_empty', l_empty, 'r_space', r_space, 'r_filled', r_filled)
next_empty = dp[i, j, bitset] * inv_r_pat % MOD * r_pattern_next_empty % MOD
next_filled = dp[i, j, bitset] * inv_r_pat % MOD * (r_pattern_total - r_pattern_next_empty) % MOD
# print('next_empty', next_empty, 'next_filled', next_filled)
if l_empty > 0:
if next_empty > 0:
dp[i + 1, j + 1, nxt_bitset0] += next_empty * l_empty % MOD
dp[i + 1, j + 1, nxt_bitset0] %= MOD
if next_filled > 0:
dp[i + 1, j + 2, nxt_bitset1] += next_filled * l_empty % MOD
dp[i + 1, j + 2, nxt_bitset1] %= MOD
r_empty0 = r_space - r_filled
if r_empty0 > 0:
dp[i + 1, j, nxt_bitset0] += next_empty * r_empty0 % MOD
dp[i + 1, j, nxt_bitset0] %= MOD
r_empty1 = r_space - (r_filled - 1)
if r_filled > 0 and r_empty1 > 0:
dp[i + 1, j + 1, nxt_bitset1] += next_filled * r_empty1 % MOD
dp[i + 1, j + 1, nxt_bitset1] %= MOD
# print(dp)
ans = dp[n, n].sum() % MOD
return ans
SIGNATURE = '(i8[:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
from numba.pycc import CC
cc = CC('my_module')
cc.export('solve', SIGNATURE)(solve)
cc.compile()
exit()
if os.name == 'posix':
# noinspection PyUnresolvedReferences
from my_module import solve
else:
from numba import njit
solve = njit(SIGNATURE, cache=True)(solve)
print('compiled', file=sys.stderr)
inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)
