結果

問題 No.2696 Sign Creation
コンテスト
ユーザー watacco
提出日時 2025-10-22 09:04:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 657 ms / 2,500 ms
コード長 6,047 bytes
コンパイル時間 426 ms
コンパイル使用メモリ 82,196 KB
実行使用メモリ 103,216 KB
最終ジャッジ日時 2025-10-22 09:04:11
合計ジャッジ時間 10,456 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#1022 08:50 壁に当たって次の行に行くときの隣り合った数字が星座判定になっているのを修正
#1022 08:50 divmodで座標を復元してマンハッタン距離そのもので判定し直した

#1022 09:03 単体の星が既にある星座にくっついた時によけいに減らしてしまっているのを修正

h,w,n,d=map(int,input().split())
mh_1=[-w,+w,+1,-1]
mh_2=[-w,+w,+1,-1,+2,-2,-2*w,+2*w,-(w-1),-(w+1),+(w-1),+(w+1)]
mh_3=[+1,-1,+2,-2,+3,-3,-w,+w,-2*w,+2*w,-3*w,+3*w,-w+1,+w+1,-2*w+1,+2*w+1,-w+2,+w+2,-w-1,+w-1,-2*w-1,+2*w-1,-w-2,+w-2]
mh_4=[+1,-1,+2,-2,+3,-3,+4,-4,-w,+w,-2*w,+2*w,-3*w,+3*w,+4*w,-4*w,-w+1,+w+1,-2*w+1,+2*w+1,-w+2,+w+2,-w-1,+w-1,-2*w-1,+2*w-1,-w-2,+w-2,-3*w+1,-2*w+2,-w+3,+w+3,+2*w+2,+3*w+1,-3*w-1,-2*w-2,-w-3,+w-3,+2*w-2,+3*w-1]
mh_5=[+1,-1,+2,-2,+3,-3,+4,-4,+5,-5,-w,+w,-2*w,+2*w,-3*w,+3*w,+4*w,-4*w,+5*w,-5*w,-w+1,+w+1,-2*w+1,+2*w+1,-w+2,+w+2,-w-1,+w-1,-2*w-1,+2*w-1,-w-2,+w-2,-3*w+1,-2*w+2,-w+3,+w+3,+2*w+2,+3*w+1,-3*w-1,-2*w-2,-w-3,+w-3,+2*w-2,+3*w-1,
-4*w+1,+4*w+1,-4*w-1,+4*w-1,-3*w+2,+3*w+2,-3*w-2,+3*w-2,-2*w+3,+2*w+3,-2*w-3,+2*w-3,-w+4,+w+4,-w-4,+w-4]

mh=[mh_1,mh_2,mh_3,mh_4,mh_5]
#計算量O(280)?

from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members
    
    def __str__(self):
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())


class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))
        
        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}
    
    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]
    
    def union(self, x, y):
        super().union(self.d[x], self.d[y])
    
    def size(self, x):
        return super().size(self.d[x])
    
    def same(self, x, y):
        return super().same(self.d[x], self.d[y])
    
    def members(self, x):
        root = self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [self.d_inv[i] for i, x in enumerate(self.parents) if x < 0]
    
    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.d_inv[self.find(member)]].append(self.d_inv[member])
        return group_members

uf = UnionFind(h*w+1)
star=[]
star_ck=[0]*(h*w+1)
for i in range(n):
  x,y=map(int,input().split())
  now=(x-1)*w+y
  star.append(now)
  star_ck[now]=1
#星を管理 計算量10**5 + 280？
for i in star:
  for m in mh[d-1]:
    if i+m < h*w+1 and i+m > 0 and star_ck[i+m] == 1:
      q1,mod1=divmod(i,w)
      q2,mod2=divmod(i+m,w)
      if mod1==0:
        mod1=w-1
      if mod2==0:
        mod2=w-1
      if abs(q1-q2) + abs(mod1-mod2) <= d:
        uf.union(i,i+m)
#星をくっつける n*60 なので最大10**5 * 60 = 10**5 *6
#ここまでで10**5 *6 + 10**2 *3 + 10**5 = 700300

#if文、とりあえずくっつけてるけど範囲外が先に出て怒られそうなら、最初の二つのand条件で分岐させる
#最大値：周りで新しい星座を爆誕させられるか +1 or +0
#最小値：周りにどれだけ多い星座があってくっつけられるか -?
star_min=0
star_max=0

for i in range(1,h*w): #星がなかったらそこに星を置くと仮定してチェック開始
  if star_ck[i]==0:
    watacco={} #もうくっつけた星座かどうか見た方がいいんじゃないかな〜
    now="ONLY" #1つ星同士しかくっつけてないかどうか？
    only_s=0 #単体星が既にある星座にくっつけられた時に差を引くのに使う
    for m in mh[d-1]:
      if i+m < h*w+1 and i+m > 0 and star_ck[i+m] == 1:
        q1,mod1=divmod(i,w)
        q2,mod2=divmod(i+m,w)
        if mod1==0:
          mod1=w-1
        if mod2==0:
          mod2=w-1
        if abs(q1-q2) + abs(mod1-mod2) <= d:
          #くっつけられる星座（星かも）発見！しました
          if uf.size(i+m) == 1: #くっつけ先の星が要素1しかないならとりあえずくっつける
            watacco[i+m]=0
            only_s+=1
          else:
            now="NO" #くっつけ先がすでに星座なら、増えるパターンないのでONLYを変える
            roots=uf.find(i+m) #くっつけた星座の根を記録する
            if roots not in watacco:
              watacco[roots]=0
    if now == "ONLY" and len(watacco) > 0:
      star_max=1
    else:
      star_min=max(star_min,len(watacco)-only_s)
    
check=uf.all_group_members()
sign=0
for i in check:
  if len(check[i]) > 1:
    sign+=1

if sign==0:
  print(0,sign+star_max)
else:
  if star_min == 0:
    print(sign,sign+star_max)
  else:
    print(sign-star_min+1,sign+star_max)
0