Codeforces Round #635(Div.2) A～D解説

たのん

Codeforces Round #635 (Div.2)のA～Dまでの解説です。
Codeforcesは久々の参加となりましたが、無事にA～Dまでの4完を達成しレートを伸ばすことができました＊
問題のアドレスは以下になります↓
https://codeforces.com/contest/1337
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/76099

A問題:

制約よりa<=x<=b,b<=y<=c,c<=z<=dで、明らかにzが最長の辺となることからx+y>zを満たすようにx,y,zを選べばよいです。
ここでy=c,z=cとすると、任意のa<=x<=bについてx+y>zを満たすのでx,y,zは三角形を作ります。
以上によりこの問題を解くことができました。

サンプルコード(Python):
https://codeforces.com/contest/1337/submission/76818816

t=int(input())
for _ in range(t):
 a,b,c,d=map(int,input().split())
 x,y,z=b,c,c
 print(x,y,z)

B問題:

1つ目の呪文は、残りの体力が20より大きいとき呪文を使うことで必ず残りの体力を小さくでき、残りの体力が20以下のとき呪文を使っても残りの体力を小さくすることはできません。
また、1つ目の呪文は、残りの体力が大きいほど与えるダメージが大きくなる(与えるダメージが単調減少する)ので、1つ目の呪文を唱えることで与えられるダメージの総量は、残りの体力が20より大きい間、1つ目の呪文を連続して唱えたときに最大になります。
したがって、残りの体力が20以下になるまで1つ目の呪文を使い続け、2つ目の呪文を唱えられるだけ唱えたときに残った体力を削りきれるかどうかを判定すればよいです。
これはO(TNM)で行えるのでこの問題を解くことができました。

サンプルコード(Python):
https://codeforces.com/contest/1337/submission/76812300

t=int(input())
for _ in range(t):
 x,n,m=map(int,input().split())
 for _ in range(n):
   if x<=20:
     break
   x=x//2+10
 if 10*m>=x:
   print('YES')
 else:
   print('NO')

C問題:

ある頂点を選んだとき、全体のスコアがどのように変化するかを確かめます。
与えられたグラフを1を根とする木として見たとき、深さiの頂点kを選ぶと、i点が得られます。
一方、頂点kを選んだとき、頂点kの子の頂点はすべて得られる点が1小さくなります。
したがって、各頂点について、その頂点を選んだときのスコアを(その頂点の深さ)-(その頂点の子の頂点の数)で定めると、スコアの大きい順にK個選ぶことでこの問題を解くことができます。
このようにスコアを定めておくと、ある頂点が選ばれるのはその頂点の子である頂点がすべて選ばれたあとになるので、この方法で答えが得られることがいえます。
与えられたグラフについて、各頂点の1からの深さと、各頂点の子ノードの数を求めるのにDFSまたはBFSを行う必要がありO(N)、各頂点についてスコアを求め、これを大きい順に並び替えて大きい順にK個選ぶのにO(NlogN)かかり、結局この問題をO(NlogN)で解くことができました。

サンプルコード(Python):
https://codeforces.com/contest/1337/submission/76857415

import collections

n,k=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
 a,b=map(int,input().split())
 g[a].append(b)
 g[b].append(a)
q=collections.deque()
q.append((1,0))
checked=[0]*(n+1)
checked[1]=1
ds=[[] for _ in range(n+1)] #1からの深さごとに頂点を管理する
pairs={} #ある頂点の親の頂点を記録する
while len(q)!=0:
 v,d=q.popleft()
 ds[d].append(v)
 for u in g[v]:
   if checked[u]==0:
     checked[u]=1
     q.append((u,d+1))
     pairs[u]=v
cnt=[0]*(n+1) #各頂点の子の頂点の数を管理する
tmp=[]
for i in range(n,0,-1):
   for v in ds[i]:
       cnt[pairs[v]]+=cnt[v]+1 #ある頂点の親の頂点の子の頂点の数に、自身と自身の子の頂点の数を足し合わせる
       tmp.append(i-cnt[v]) #各頂点のスコアは(1からの深さ)-(その頂点の子の頂点の数)で求める
tmp=sorted(tmp,reverse=True)
print(sum(tmp[:k]))

D問題:

(x-y)^2+(y-z)^2+(z-x)^2について、このうちの1変数を決め打ったとしても2変数関数の最小値を求めることになり、莫大な計算時間がかかります。
したがって考え方を変え、x<=y<=zを満たす(x,y,z)の組について考えることとします。
このとき、(x-y)^2+(y-z)^2+(z-x)^2が最小となるのは、|y-x|と|z-y|がそれぞれ最小のときです。
したがって、yを決め打ち、yに最も近いx,zを探し、上記の条件を用いてx,y,zを決めることで、(x-y)^2+(y-z)^2+(z-x)^2が最小となる(x,y,z)の組を求めることができ、答えが得られます。
ただし、(x,y,z)の取り方として、(r,g,b),(r,b,g),(b,r,g),(b,g,r),(g,r,b),(g,b,r)の6通りがあることに注意します。
yに最も近いx,zを探すのに2分探索を用いることと、そのためにx,y,zの列をソートする必要があることから、この問題をO(NlogN)で解くことができました。

サンプルコード(Python):
https://codeforces.com/contest/1337/submission/76891437

import bisect

t=int(input())
for _ in range(t):
   a,b,c=map(int,input().split())
   ans=10**30
   arr1=list(map(int,input().split())) #各列について2分探索を行うので事前にソートしておく
   arr1=sorted(arr1)
   arr2=list(map(int,input().split()))
   arr2=sorted(arr2)
   arr3=list(map(int,input().split()))
   arr3=sorted(arr3)
   for x in arr1: #yをrから取る場合
       pos=bisect.bisect_left(arr2,x) #列を2分探索し、最も近い数を探す
       if pos==0:
           y=arr2[0]
       elif pos==b:
           y=arr2[-1]
       else:
           if abs(x-arr2[pos])<=abs(x-arr2[pos-1]):
               y=arr2[pos]
           else:
               y=arr2[pos-1]
       pos=bisect.bisect_left(arr3,x) #列を2分探索し、最も近い数を探す
       if pos==0:
           z=arr3[0]
       elif pos==c:
           z=arr3[-1]
       else:
           if abs(x-arr3[pos])<=abs(x-arr3[pos-1]):
               z=arr3[pos]
           else:
               z=arr3[pos-1]
       tmp=(x-y)**2+(y-z)**2+(z-x)**2
       ans=min(ans,tmp)
   for y in arr2: #yをgから取る場合
       pos=bisect.bisect_left(arr1,y) #列を2分探索し、最も近い数を探す
       if pos==0:
           x=arr1[0]
       elif pos==a:
           x=arr1[-1]
       else:
           if abs(y-arr1[pos])<=abs(y-arr1[pos-1]):
               x=arr1[pos]
           else:
               x=arr1[pos-1]
       pos=bisect.bisect_left(arr3,y) #列を2分探索し、最も近い数を探す
       if pos==0:
           z=arr3[0]
       elif pos==c:
           z=arr3[-1]
       else:
           if abs(y-arr3[pos])<=abs(y-arr3[pos-1]):
               z=arr3[pos]
           else:
               z=arr3[pos-1]
       tmp=(x-y)**2+(y-z)**2+(z-x)**2
       ans=min(ans,tmp)
   for z in arr3: #yをbから取る場合
       pos=bisect.bisect_left(arr1,z) #列を2分探索し、最も近い数を探す
       if pos==0:
           x=arr1[0]
       elif pos==a:
           x=arr1[-1]
       else:
           if abs(z-arr1[pos])<=abs(z-arr1[pos-1]):
               x=arr1[pos]
           else:
               x=arr1[pos-1]
       pos=bisect.bisect_left(arr2,z) #列を2分探索し、最も近い数を探す
       if pos==0:
           y=arr2[0]
       elif pos==b:
           y=arr2[-1]
       else:
           if abs(z-arr2[pos])<=abs(z-arr2[pos-1]):
               y=arr2[pos]
           else:
               y=arr2[pos-1]
       tmp=(x-y)**2+(y-z)**2+(z-x)**2
       ans=min(ans,tmp)
   print(ans)

この記事が気に入ったらサポートをしてみませんか？