Codeforces Global Round 9(Rated for All) A～F解説
Codeforces Global Round 9のA～Fまでの解説です。
コンテスト中はA～Dまでの4完(2:20:00)でレート増減なしに終わりました。
前回のDiv.2と同様A～Dがパズル問題という得意セットだっただけにもう少しよい結果を出したかったですが、パズル問題は大コケしやすいこともあり失敗しなかったことをよしとしたいと思います。
問題のアドレスは以下になります↓
https://codeforces.com/contest/1375
問題の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/79731
A問題:
数列の各要素について、-,+,-,+,…,-もしくは+,-,+,-,…,+と並べればよいです(操作回数に制限はないのでどちらを選んでもよいです)。
-,+,-,+,…,-と並べると、奇数番目が必ず0以上、偶数番目が必ず0以下となり、+,-,+,-,…,+と並べると、奇数番目が必ず0以下、偶数番目が必ず0以上となり、いずれの場合も条件を満たします。
サンプルコード(Python):
https://codeforces.com/contest/1375/submission/86097049
t=int(input())
for _ in range(t):
n=int(input())
arr=list(map(int,input().split()))
for i in range(n): #+,-,+,-,…,+となるように符号を選ぶ
if i%2==0:
arr[i]=abs(arr[i])
else:
arr[i]=-abs(arr[i])
print(*arr)
B問題:
条件を満たすもののうち、各マスの値が最大となる並べ方は、
23…32
34…43
|4…4|
34…43
23…32
になります。
したがって、これと与えられた盤面を比較し、与えられた盤面のある要素が上記で示した可能な並べ方より大きいとき不可能(∵要素を小さくすることはできません)、そうでなければ可能であることがいえます。
サンプルコード(Python):
https://codeforces.com/contest/1375/submission/85938479
t=int(input())
for _ in range(t):
n,m=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(n)]
persuit=[[4]*m for _ in range(n)] #各マスの最大値の配列を作る
for i in range(n): #1・n行目と1・m列目の要素はすべて3に置き換える
for j in range(m):
if i==0 or i==n-1 or j==0 or j==m-1:
persuit[i][j]=3
persuit[0][0]=2 #四隅の要素はすべて2に置き換える
persuit[0][m-1]=2
persuit[n-1][0]=2
persuit[n-1][m-1]=2
flag=True
for i in range(n):
for j in range(m):
if board[i][j]>persuit[i][j]: #各マスの最大値を超えるような要素があれば不可能
flag=False
if flag==True: #可能なときは各マスの最大値の配列を出力すればよい
print('YES')
for i in range(n):
print(*persuit[i])
else:
print('NO')
C問題:
・ある時点で1,2,3,…が左端、もしくはn,n-1,n-2,…が右端にあれば可能
・ある時点で1,2,3,…が右端、もしくはn,n-1,n-2,…が左端にあれば不可能
の2つの条件について、どちらかの条件を先に満たすまで見ていけばよいです。
nが偶数のときは最後の2要素が、nが奇数のときは最後の3要素のうち少なくとも1要素が上記の条件を満たすので、必ずO(N)で判定できます。
サンプルコード(Python):
https://codeforces.com/contest/1375/submission/85958594
t=int(input())
for _ in range(t):
n=int(input())
arr=list(map(int,input().split()))
pos=[0]*(n+1)
for i in range(n): #各要素の位置を求めておく
pos[arr[i]]=i
mins=1
maxs=n
left=0
right=n-1
while 1:
if pos[mins]==left or pos[maxs]==right: #各時点での最小値が左端、もしくは最大値が右端にあれば可能
print('YES')
break
elif pos[mins]==right or pos[maxs]==left: #各時点での最小値が右端、もしくは最大値が左端にあれば不可能
print('NO')
break
else:
mins+=1
maxs-=1
D問題:
元の列から0,1,2,…,n-1の列を作ることを考えます。
まず、数列が0～n-1までの順列になるまで(mex=nとなるまで)、数列のmex番目(0-indexed)の要素をmexで置き換える操作を行います。
この際、必要であればmexを更新していきます。
この操作により、いくつかの要素を1回の操作でソート済みの位置に置くことができます。
mex=nになったら、その時点でのソートされていない最小の数(=i番目(0-indexed)に置かれていない最小のi)をmexで置き換え、ついで最小の数iをi番目に置きます。
このときmex!=nであれば、その数をi番目に置くことを繰り返します。
ふたたびmex=nになったら、上記と同様にソートされていない最小の数と置き換え、上記の操作を繰り返します。
この操作により、
・mex!=nのとき1回の操作で1要素をソート済みの位置に置くことができる
・mex=nのとき2回の操作で1要素をソート済みの位置に置くことができる
ことが分かるので、mex=nになるまでの操作と合わせて、高々2n回で与えられた列をソートできることが分かります。
数列が0～n-1までの順列になるまでの操作は、例えば優先度付きキューによりmexを管理することによりO(NlogN)で行うことができ、mex=nになったあとの操作はO(N)で行うことができるので、この問題をO(NlogN)で解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1375/submission/85993029
import heapq
import collections
t=int(input())
for _ in range(t):
n=int(input())
arr=list(map(int,input().split()))
ans=[]
counts=collections.Counter(arr)
mexs=[]
for i in range(n+1): #優先度付きキューによりMEXを管理
if i not in counts:
heapq.heappush(mexs,i)
while 1:
mex=heapq.heappop(mexs)
if mex==n: #MEX=nとなるまで操作を繰り返す
break
else:
counts[arr[mex]]-=1
if counts[arr[mex]]==0: #ある要素の個数が0になったらMEXに追加する
heapq.heappush(mexs,arr[mex])
arr[mex]=mex #MEX!=nのとき、MEX番目の位置にMEXの値を置く
ans.append(mex+1)
mex=n
pos=[0]*(n+1)
for i in range(n): #上記で置き換えた列の要素の位置を求めておく
pos[arr[i]]=i
persuit=0
cnt=0
while persuit!=n: #すべての要素を正しい位置に置くまで繰り返す
if mex==n: #MEX=nのとき、正しい位置に置かれていない要素の最小値と置き換える
if pos[persuit]==persuit:
persuit+=1
else:
arr[pos[persuit]]=mex
mex=persuit
ans.append(pos[persuit]+1)
else: #MEX!=nのとき、MEX番目の位置にMEXの値を置く
tmp=arr[mex]
arr[mex]=mex
pos[mex]=mex
ans.append(mex+1)
mex=tmp
print(len(ans))
print(*ans)
E問題:
サンプルからなんとなく予想がつきますが、実は与えられた配列のすべてのInversion Swapを適切に並び替えることで、必ず与えられた配列をソートすることができます。
以下これを示します。
配列の末尾から順に見ていくことを考えます。
末尾の要素がソート済みの列の末尾の要素と等しくないとき、必ず末尾の要素より前の要素でその要素と交換可能なものが存在します(∵ソート済みの列の末尾の要素は配列の最大値に等しいので、末尾の要素は配列の最大値ではありません)。
ここで、末尾の要素と交換可能なすべての要素について、その要素の小さい順に交換を行うことを考えると、必ず末尾の要素はソート済みの列の末尾の要素に等しくなります(∵最後に配列の最大値と交換することになります)。
この操作により、配列の末尾の要素anと、その要素と交換可能なすべての要素b1,…,bkが、b1=an,b2=b1,…,bk=b(k-1),an=bkと移動することになります。
これを繰り返し行っていくと、bkには各時点での最大値が入ることになるので、末尾から順に最大値が置かれていくことになり、最終的に与えられた配列をソートすることができます。
この並び替えは、まずすべてのInversion Swap(u,v)を生成しておき、arr[u]について昇順に並べたあと、この並び順を保存したままvを降順に並べることで得ることができ、すべてのInversion Swapを生成するのにO(N^2)、ソートにO(N^2logN)かかるので、トータルO(N^2logN)でこの問題を解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1375/submission/86099969
n=int(input())
arr=list(map(int,input().split()))
ans=[]
for i in range(n): #すべてのInversion Swapを生成
for j in range(n-1,i,-1):
if arr[i]>arr[j]:
ans.append((arr[i],i+1,j+1))
ans=sorted(ans,key=lambda x:x[0]) #arr[i]の小さい順に並び替える
ans=sorted(ans,reverse=True,key=lambda x:x[2]) #vの大きい順に並び替える
print(len(ans))
for _,u,v in ans:
print(u,v)
F問題:
まず、同じ数が3つある場合は明らかに先攻が勝利します。
また、同じ数が2つある場合も容易に先攻が勝利できることが分かります。
具体的には、最小値が2つあるケースはyとして最大値と最小値の差を取ることで勝利でき、最大値が2つあるケースはまずyとして最大値と最小値の差を取ると必ず列の高さの差が等しくなり、直前に操作した位置が列の最大値になっているので、yとして列の差を取ることで勝利できます。
したがって、同じ数が1つもない場合について考えることにします。
各時点において、yを加えた箇所が常にその時点の最大値になるようなyを選ぶようにすると、このような操作を繰り返して列の高さの差を等しくできたとき、先攻が必ず勝利できます。
したがって、列の高さを小さい順にa,b,cと書くことにすると、
[b,c,a+y]についてc-b=a+y-cを満たし、[a,c,b+y]についてc-a=b+y-cを満たすようなyが存在すればよいです。
上記を式変形することによりy=2c-a-bが得られ、いまc>a,bを満たすので、a+y,b+y>cを満たします。
これより、まず適当なy(>=c-a)を取り、yを加えた箇所がその時点の最大値になるようにします。
次に、このときのa,b,cからy=2c-a-bを取ると、必ず列の高さの差が等しくなります。
最後にyとして列の高さの差を取ることで、先攻が勝利することができます。
以上により、同じ数が3つある場合・2つある場合・1つもない場合のすべての場合について、必ず先攻が勝利できる方法を示すことができたので、この問題を解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1375/submission/86034798
arr=list(map(int,input().split()))
print("First",flush=True) #先攻で必ず勝利できるので先攻を選ぶ
if len(set(arr))==1: #同じ要素が3つあるとき
print(1,flush=True) #どのようなyを選んでも1ターンで勝利できる
_=int(input())
exit()
elif len(set(arr))==2: #同じ要素が2つあるとき
if arr.count(max(arr))==1: #最大値が1つしかなければ、yとしてmax-minを選ぶことで1ターンで勝利できる
y=max(arr)-min(arr)
print(y,flush=True)
pos=int(input())
exit()
else: #最大値が2つあるとき、まずyとしてmax-minを選び、もう1度先ほどのyを選ぶことで勝利できる
y=max(arr)-min(arr)
print(y,flush=True)
pos=int(input())
arr[pos-1]+=y
print(y,flush=True)
pos=int(input())
exit()
else: #すべての要素が異なるとき
y=max(arr)-min(arr) #まず、y=max-minを選び最後にyを加えた場所が最大値となるようにする
print(y,flush=True)
pos=int(input())
arr[pos-1]+=y
y=3*max(arr)-sum(arr) #次に、列を小さい順にa,b,cとおいたとき、y=2c-a-bを選び列が等差数列になるようにする
print(y,flush=True)
pos=int(input())
arr[pos-1]+=y
y=(max(arr)-min(arr))//2 #最後に、yとして等差数列の差を選ぶと、最大値が最後にyを加えた場所になっているので、必ず勝利できる
print(y,flush=True)
pos=int(input())
exit()
この記事が気に入ったらサポートをしてみませんか？