Codeforces Round #646(Div.2) A〜E解説
Codeforces Round #646 (Div.2)のA～Eまでの解説です。
前半でつまずいたもののDをスムーズに通すことができ、4完でレート微増という結果でした。
問題のアドレスは以下になります↓
https://codeforces.com/contest/1363
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/78202
A問題:
いくつか要素を選んだときの総和が奇数となるとき、奇数は奇数個選ばれることになります。
したがって、まず要素の中に奇数が存在しなければ総和を奇数とすることは不可能です。
また、xが偶数のとき、奇数は奇数個しか選べないことから、偶数が存在しなければx個取ったときに総和が奇数とすることは不可能です。
したがって、要素のうち奇数のものの個数oddと偶数のものの個数evenを数えておき、上記の条件をまず確かめます。
上記の条件を満たさないとき、まず奇数を1つ取り、その後は奇数を偶数個、もしくは偶数を好きな数だけ取り、取った個数がx個以上になれば総和を奇数とすることができ、取った個数がx個未満になれば総和を奇数とすることができません。
以上はeven+((odd-1)//2)*2>=x-1で判定することができ、これを満たせば可能、これを満たさなければ不可能となります(((odd-1)//2)*2はodd-1以下の最大の偶数に等しいです)。
サンプルコード(Python):
https://codeforces.com/contest/1363/submission/82149201
t=int(input())
for _ in range(t):
n,x=map(int,input().split())
arr=list(map(int,input().split()))
for i in range(n):
if arr[i]%2==0:
arr[i]=0
else:
arr[i]=1
if arr.count(1)==0: #奇数が存在しなければそもそも不可能
print('No')
continue
if x%2==0 and arr.count(0)==0: #xが偶数のとき、偶数が存在しなければ不可能
print('No')
continue
if arr.count(0)+((arr.count(1)-1)//2)*2>=x-1: #上記の条件を満たさないとき、構成が可能かを確かめる
print('Yes')
else:
print('No')
B問題:
部分文字列として"101"と"010"を含んではいけないので、よい文字列は、明らかに("0"を0個以上並べたもの)+("1"を0個以上並べたもの)で構成できる文字列、もしくはその逆の文字列であることが分かります。
よって、与えられた文字列の0番目から|S|番目の各地点kについて、k以前の文字列はすべて0、k以降の文字列はすべて1とするときのコストと、その逆のコストをそれぞれ求めると、その最小値が答えとなります。
これは全探索でO(|S|^2)で求めることができ、計算量はO(T|S|^2)で10^8のオーダーなので間に合わないことはないのですが、0の個数と1の個数の累積和を事前に計算しておくと、コストの計算をO(|S|)で行うことができるようになり高速に動作するようになります。
サンプルコード(Python):
https://codeforces.com/contest/1363/submission/82072690
t=int(input())
for _ in range(t):
s=input()
l=len(s)
acum1=[0]
acum2=[0]
for i in range(l): #0の個数と1の個数の累積和を求める
if s[i]=='0':
acum1.append(acum1[-1]+1)
acum2.append(acum2[-1])
else:
acum1.append(acum1[-1])
acum2.append(acum2[-1]+1)
ans=10**18
for i in range(l+1): #|S|+1箇所の地点について、"0…01…1"と"1…10…0"に変更するコストをそれぞれ求める
tmp1=(acum1[i]-acum1[0])+(acum2[l]-acum2[i])
tmp2=(acum2[i]-acum2[0])+(acum1[l]-acum1[i])
ans=min(ans,tmp1,tmp2)
print(ans) #すべてのコストの最小値が答えとなる
C問題:
頂点xの次数が1以下であれば、明らかに1手目で頂点xを取れるので先攻の勝利となります(頂点xの次数が0のケース、すなわちN=1のケースが存在することに注意します)。
頂点xの次数が2以上のとき、頂点xを取れるのは、頂点xの子ノードのうちまだ取られていないものが1つ以下になったときです。
お互いが最適に行動すると、最終的に頂点xとその子ノード2つが残った状態に遷移し、ゲームはn-1個の頂点を取ったときに終了することになります。
以下これを示します。
頂点xの次数が2以上のとき、頂点xの子ノードを根とする部分木について、1つの部分木を除いてすべての頂点を取ったとき、すなわち頂点xの子ノードを1つを除いてすべて取ったとき、頂点xを取れるようになります。
しかし、そのような状態を自分が作ると相手が頂点xを取ってしまうので、頂点xの子ノードを取る代わりに残る部分木から1頂点を取ることになります。
これを、次に必ず頂点xが取れる状態(頂点xとその子ノード2つが残った状態)になるまで続けることになるので、結局n-1個の頂点を取ることになります。
したがって、n-1が奇数であれば先攻が、n-1が偶数であれば後攻が勝利することになり、勝敗をO(1)で判定できます。
サンプルコード(Python):
https://codeforces.com/contest/1363/submission/82101910
t=int(input())
for _ in range(t):
n,x=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)
if len(g[x])<=1: #頂点xの次数が1以下であれば先攻の勝利
print('Ayush')
else: #そうでないとき、結局n-1個の頂点を取ることになり、n-1番目の頂点(=頂点x)を取った方が勝つ
if (n-1)%2==1: #n-1が奇数であれば先攻がn-1番目の頂点を取る
print('Ayush')
else: #n-1が偶数であれば後攻がn-1番目の頂点を取る
print('Ashish')
D問題:
制約より、与えられた部分集合Siについて、異なる部分集合は共通部分を持たないことに注目します。
Aのすべての要素の最大値を求めると、Aは最大値に等しい要素を少なくとも1つ含むことが分かります。
この要素の番号がもし分かれば、その番号を含まないすべての部分集合について、それらの部分集合の要素を除いた要素の最大値はAのすべての要素の最大値に等しいことが分かります(∵各部分集合の要素を除いた要素は最大値に等しい要素を必ず含みます)。
また最大値に等しい要素の番号を含む部分集合については、1回のクエリでその部分集合の要素を除いた要素の最大値を求めることができます。
よって、最大10回のクエリで最大値に等しい要素の番号を求めることができれば、この問題を解くことができます。
これは2分探索を用いることで判定でき、いまN<=1000であることから、高々10回のクエリで必ず最大値に等しい要素の番号を求めることができます(∵1回の探索で探索範囲を1/2にできることから高々10回のクエリで最大値に等しい要素の番号を求められることが分かります)。
具体的には、2つの区間A,Bのうち片方の要素すべての最大値を尋ね、それが全体の最大値に等しければその区間を1/2した区間を新たにA,Bとして定め、全体の最大値に等しくなければもう一方の区間を1/2した区間を新たにA,Bとして定めることで、常にどちらかの区間に最大値に等しい要素を含む状態を保つことができます。
以上によりこの問題を解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1363/submission/82125629
t=int(input())
for _ in range(t):
n,k=map(int,input().split())
arr=[set(list(map(int,input().split()))[1:]) for _ in range(k)]
ans=[0]*k
query=['?']+[n]+[i for i in range(1,n+1)] #すべての要素の最大値を求める
print(*query,flush=True)
maxs=int(input())
range1=[1,n//2]
range2=[n//2+1,n]
for _ in range(10): #2分探索により最大値に等しい要素の番号を1つ求める
query=['?']+[range1[1]-range1[0]+1]+[i for i in range(range1[0],range1[1]+1)] #左側の区間について尋ねる
print(*query,flush=True)
tmp=int(input())
if tmp==maxs: #左側の区間に最大値に等しい要素がある
if range1[0]==range1[1]: #区間幅が1であればその番号が求める番号に等しい
pos=range1[0]
break
else: #区間幅が2以上であれば区間を2分割し改めて質問する
range2=[range1[0]+(range1[1]-range1[0])//2+1,range1[1]]
range1=[range1[0],range1[0]+(range1[1]-range1[0])//2]
else: #左側の区間に最大値に等しい要素がない
if range2[0]==range2[1]: #区間幅が1であればその番号が求める番号に等しい
pos=range2[0]
break
else: #区間幅が2以上であれば区間を2分割し改めて質問する
range1=[range2[0],range2[0]+(range2[1]-range2[0])//2]
range2=[range2[0]+(range2[1]-range2[0])//2+1,range2[1]]
for i in range(k):
if pos in arr[i]: #求めた番号を含む部分集合は、それらの要素を除いた要素の最大値がパスワードになる
tmp=[]
for j in range(1,n+1):
if j in arr[i]:
continue
tmp.append(j)
query=['?']+[n-len(arr[i])]+tmp
print(*query,flush=True)
ans[i]=int(input())
else: #求めた番号を含まない部分集合は、全体の最大値がパスワードになる
ans[i]=maxs
query=['!']+ans
print(*query,flush=True)
s=input()
if s=="Correct":
continue
else:
exit()
E問題:
まず、bi=1なる個数とci=1なる個数が等しいことを確かめます。
もしこれが等しくなければ構成は不可能なので-1を出力します、もし等しければ与えられたグラフは木なので必ず構成は可能です。
以下構成が可能な場合を考えます。
明らかに、初期状態と最終状態が等しいものは交換すると損であることが分かります。
また、鳩ノ巣原理により交換は2点交換のみを考えれば十分であることが分かります(∵初期状態の0の個数をi、1の個数をjとしたとき、鳩ノ巣原理よりabs(i-j)個の頂点は初期状態と最終状態が等しくなるので、結局min(i,j)個の組を交換することになります)。
ある2頂点の状態を交換するとき、それら2頂点の最小共通祖先とその祖先すべてを交換の始点として選べ、それらのうち最もコストが小さいものを始点として選ぶので、なるべく深い頂点から順に交換する方が得であることが分かります(∵最小共通祖先が深いほど交換コストを小さくできます)。
したがって、葉ノードから親の頂点を順に見ていって、その時点で交換できるものがあれば交換、なければ親の頂点に移動するという操作を繰り返していく貪欲法でこの問題を解くことができます。
各頂点を始点とする交換コストはBFSなどでO(N)で事前計算できます。
答えの計算は、まず各頂点iについてbi=0,ci=1であればcnt[i][0]=1、bi=1,ci=0であればcnt[i][1]=1としておき、ある頂点vの子の頂点uについて、cnt[v][0]+=sum(cnt[u in g[v]][0])、cnt[v][1]+=sum(cnt[u in g[v]][1])と更新すると、
ans+=cost[v]*(2*min(cnt[v][0],cnt[v][1]))として求めることができます。
答えの計算後、cnt[v][0],cnt[v][1]はそれぞれcnt[v][0],cnt[v][1]=cnt[v][0]-min(cnt[v][0],cnt[v][1]),cnt[v][1]-min(cnt[v][0],cnt[v][1])として更新する必要があります(∵min(cnt[v][0],cnt[v][1])組の頂点を交換しています)。
これは例えばDFSを用いることで実装でき、O(N)でこの問題を解くことができます(こどふぉの仕様上(？)DFSだとスタックオーバーフローしてしまうので、サンプルコードではBFSでコストを計算する際に頂点を辿った順を記録しておき、その逆順で頂点を辿り答えを求めるという実装を行っています)。
サンプルコード(Python):
https://codeforces.com/contest/1363/submission/82183788
import collections
import sys
input=sys.stdin.readline
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
cnt1=0
cnt2=0
cnt=[[0,0] for _ in range(n+1)]
cost=[10**18]*(n+1)
for i in range(n):
a,b,c=arr[i]
cost[i+1]=a
if b==1 and c==0:
cnt1+=1
cnt[i+1][0]=1
if b==0 and c==1:
cnt2+=1
cnt[i+1][1]=1
if cnt1!=cnt2: #初期状態の0,1の個数と終了状態の0,1の個数が等しくなければ構成は不可能
print(-1)
else:
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)
checked=[0]*(n+1)
checked[1]=1
visit=[]
child=[[] for _ in range(n+1)]
while len(q)!=0:
v=q.popleft()
visit.append(v)
for u in g[v]:
if checked[u]==0:
checked[u]=1
cost[u]=min(cost[v],cost[u]) #各頂点を始点とする交換コストの最小値を更新する
child[v].append(u) #BFSで辿った頂点の順番と各頂点の子ノードを記録する
q.append(u)
ans=0
for v in visit[::-1]: #BFSで辿った頂点の順番を逆順に見る(葉ノードから順番に見る)
for u in child[v]: #各頂点の子ノードについて、b=0,c=1である組とb=1,c=0である組の個数を求める
cnt[v][0]+=cnt[u][0]
cnt[v][1]+=cnt[u][1]
m=min(cnt[v][0],cnt[v][1]) #それらの組のうち小さい方が交換できる最大の個数になる
ans+=cost[v]*(2*m) #答えに(その頂点での交換コストの最小値)*(2*交換できる組の個数)を加える
cnt[v][0]-=m #交換した分だけ個数を補正する
cnt[v][1]-=m
print(ans)
この記事が気に入ったらサポートをしてみませんか？