Codeforces Round #654(Div.2) A～E2解説
Codeforces Round #654 (Div.2)のA～E2までの解説です。
約1ヶ月ぶりの参加となりましたが、Div.2では初となるA～E1までの5完でレートを伸ばし紫に復帰できました＊(A～Dまでが発想一発な問題で、普段のCodeforcesとは一味違った問題セットでした)
問題のアドレスは以下になります↓
https://codeforces.com/contest/1371
問題の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/79624
A問題:
まず、nが奇数のとき、1+(n-1),2+(n-2),…として長さがnの棒を(n+1)//2本作ることができます。
次に、nが偶数のとき、1+n,2+(n-1),…としてn//2本の同じ長さの棒を作ることができます。
nが奇数の場合、偶数の場合のいずれの場合も、このような作り方が最善であることは明らかです(∵(n+1)//2本より大きい数の同じ長さの棒を作れるとすると、そのような長さの棒が2本以上必要になりますが、これは制約に反します)。
以上より、(n+1)//2を出力することでこの問題を解くことができます。
サンプルコード(Python):
https://codeforces.com/contest/1371/submission/85641747
t=int(input())
for _ in range(t):
n=int(input())
print((n+1)//2)
B問題:
1<=k<=rを満たすkについて、kがn以上となるかで場合分けします。
まず、k>=nを満たすすべてのkについて、n個のマスを横一列に塗るしかなく、その塗り方はただ1通りに定まります。
次に、k<nを満たすkについて、その置き方はkごとにk通りあり、それらはすべて異なります(∵塗り方の一番上の行について右端から1～k個塗る塗り方を考えることができ、kごとに塗ったマスの幅が互いに異なるので、上記の毛結論を得ます)。
したがって、n,rについて、n>rのとき(1～rまでの総和)、すなわちr(r+1)//2を、n<=rのとき(1～n-1までの総和)+1、すなわち1+n(n-1)//2をそれぞれ出力すればよいです。
サンプルコード(Python):
https://codeforces.com/contest/1371/submission/85642779
t=int(input())
for _ in range(t):
n,r=map(int,input().split())
if n>r: #n,rの関係性で場合分け
print((r*(r+1))//2)
else:
print(1+(n*(n-1))//2)
C問題:
n人いるタイプ1のゲストは、常に最適にクッキーを食べてくれる(∵残っている数が多いほうを食べてくれる)ので、タイプ1のゲストについて、並べる順番を考慮する必要はありません。
一方、m人いるタイプ2のゲストは、常に少ないほうのクッキーを食べるので、タイプ2のゲストが食べられるクッキーが最大になるように並べる順番を考える必要があります。
ここで、どのようにゲストの順番を決めても、タイプ2が食べられるクッキーの総数がmin(a,b)より大きくなることはありません(∵ある時点で最小のクッキーの数を増やすことはできません)。
したがって、min(a,b)<mの場合と、a+b<n+mの場合(ゲストの総数に対してクッキーの総数が足りない場合)はNo、それ以外の場合はYesとなります。
サンプルコード(Python):
https://codeforces.com/contest/1371/submission/85643215
t=int(input())
for _ in range(t):
a,b,n,m=map(int,input().split())
if a+b<n+m or min(a,b)<m:
print('No')
else:
print('Yes')
D問題:
(max(R)-min(R))^2+(max(C)-min(C))^2の最小値を実現する配列を求める問題です。
ここで、具体的にどのように配列を構築するのが最善かを考えてみます。
まず、max(R)-min(R)を最小化するような置き方について考えると、1行ずつずらして置いていくのが最善であることが容易に分かります。
また同様にmax(C)-min(C)を最小化するような置き方について考えると、1列ずつずらして置いていくのが最善であることが分かります。
したがって、例えば、(1,1),(2,2),…,(n,n)→(1+1,1),(2+1,1),…,(n+1,n)→…(1+2,1),(2+2,1),…,(n+2,1)というふうに置くことで、max(R)-min(R)とmax(C)-min(C)の両方を最小化することができ、このような置き方はO(N^2)で具体的に求めるることができます。。
このような置き方をするとき、kがnの倍数であればmax(R)=min(R)、max(C)=min(C)となり、そうでない場合、max(R),max(C)=ceil(k/n),min(R),min(C)=floor(k/n)となるので、最小の値をO(1)で計算できます。
以上によりこの問題を解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1371/submission/85649620
t=int(input())
for _ in range(t):
n,k=map(int,input().split())
board=[[0]*n for _ in range(n)]
cnt=0
for i in range(n): #最小となる行列(のうちの1つ)を具体的に構築する
for j in range(n):
if cnt==k:
break
board[(j+i)%n][j]=1
cnt+=1
if cnt==k:
break
if k%n==0: #kがnの倍数のとき最小値は0
print(0)
else: #そうでないとき最小値は2*(ceil(k/n)-floor(k/n))^2で求められる
maxs=(k+n-1)//n
mins=k//n
print(2*((maxs-mins)**2))
for i in range(n):
print(''.join(map(str,board[i])))
E1問題:
まず、確かめるべきxの範囲について考えます。
すると、x>=max(ai)を満たすxはすべて無視できることが分かります(∵x>=max(ai)のとき場合の数はn!ですが、p<=nよりpはn!を必ず割り切ります)。
また、x<min(ai)を満たすxもすべて無視できます(∵場合の数は0となります)。
以上より、min(ai)<=x<max(ai)を満たすxについてのみ考えれば十分であることが分かります。
aiの制約より、制約が小さいので、このようなxは高々2000個しかありません。
したがって、各xについて、O(N)またはO(NlogN)での判定が行えればこの問題を解くことができます。
aiは昇順ソートしているものとし、xを小さい順に見ていくことにします。
すると、ai<=xのとき、そのaiはいつ取ってもよく、またx+i<aiのとき、そのようなxですべての要素を取ることは不可能です。
また、x<ai<=x+iのとき、aiは1+ai-x番目以降にしか取れません。
以上のように各aiに取れる順番を定め、この順番を逆に並べたものをpatternとすると、あるiについてpattern[i]-i<=0または(pattern[i]-i)%pを満たすとき不可能、そうでないとき可能となります(∵あるxのもとで取りうる場合の数はprod[i=0 to n-1](pattern[i]-i)で求められますが、あるiについてpattern[i]-i<=0のときには場合の数は0となり不適、またあるiについて(pattern[i]-i)%pのとき場合の数がpで割り切れるので不適となります)。
これは各xごとにO(N)で求められるので、この問題を解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1371/submission/85835178
import sys
input=sys.stdin.readline
n,p=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
mins=arr[0]
maxs=arr[-1]
ans=[]
for x in range(mins,maxs): #min(ai)<=x<max(ai)を満たすxについて条件を満たすかを確かめる
pattern=[0]*n
for i in range(n): #各aiについて、いくつ置く場所があるかを求める
if arr[i]<=x:
pattern[i]=n
elif arr[i]>x+i:
pattern[i]=0
else:
pattern[i]=n-(arr[i]-x)
pattern=pattern[::-1]
for i in range(n): #場合の数が0またはpで割り切れるとき、そのxは条件を満たさない
if (pattern[i]-i)%p==0 or pattern[i]-i<=0:
break
else: #条件を満たすxを答えに追加する
ans.append(x)
print(len(ans))
print(*ans)
E2問題:
E1問題と比べるとaiの制約が非常に大きくなっており、上記のようにすべてのxについて愚直に求めるのは不可能です。
ここで、上記の判定方法から、xの範囲をさらに絞る方法がないかについて考えてみます。
すると、条件を満たすxについて、少なくとも場合の数が0になることはないので、条件を満たすxはすべてのiについてai-i<=xを満たします。
したがって、探索すべきxの範囲がmax(ai-i)<=x<max(ai)となり、xの個数は高々n(<=10^5)以下であることが示せました。
上記によりxの探索範囲は十分に絞れましたが、E1と同様の解法ではトータルの計算量がO(N^2)となり間に合いません。
したがって、計算量改善の方法を考えることにします。
E1の解法において、あるiについてpattern[i]-i<=0を満たすとき、そのxは不適であることが分かりますが、上記のxの探索範囲において、この式を満たすxは存在しません。
したがって、すべてのiについて、(pattern[i]-i)%p=0を満たすかどうかを判定する方法を考えれば十分です。
x>=aiを満たすiがp個以上あるとき、あるiについて(n-i)%p=0を必ず満たすのでそのようなxは不適となりますが、これはxの最大値をa(p-1)-1とすることにより、x>=aiを満たすiがk(<p)個となります。
また、このようなiについて場合の数はk!となり、これはpで割り切ることができないので、以下ではxの探索範囲をmax(ai-i)<=x<a(p-1)として考えます。
上記の議論により、max(ai-i)<=x<a(p-1)を満たすxでは、pattern[i]=nとなるすべてのiについて考える必要がなく、残るiについてはpattern[i]は必ずn-(ai-x)で表せ、E1の解法においてpattern[i]は逆に並べて考えているので、
(pattern[i]-i)%p=0⇔((n-(a(n-i-1)-x))-i)%p=0⇔(p-(n-a(n-i-1)-i))%p=x%pとなるようなiがあるとき、そのxは不適となります。
ここで、(p-(n-a(n-i-1)-i))%pはxによらないので、arr[i]=(p-(n-a(n-i-1)-i))%pとして新たに数列を作ることを考えます。
最初に可能なあまりを0～p-1までのすべての数として、可能なあまりからarr[i]を取り除いていくことを考えます。
このとき、これまでの議論により、可能なあまりの中にx%pが含まれていればそのxは条件を満たし、そうでなければxは条件を満たさないことが分かります。
いまpattern[i]=n-(ai-x)となるすべてのiについて、xを最大値から最小値まで順に見ていくことにすると、iが変化しないか、iが増加するかのどちらかになることが分かります。
したがって、最初にxを最大値としたときにpatten[i]=n-(ai-x)となるすべてのiについて可能なあまりからarr[i]を取り除いておくと、iの変化はしゃくとり法の考え方により高々N回しか起こらず、iは例えば2分探索によりO(logN)で求めることができるので、トータルO(NlogN)でxが条件を満たすかを判定することができ、この問題を解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1371/submission/85836890
import bisect
import sys
input=sys.stdin.readline
n,p=map(int,input().split())
arr1=list(map(int,input().split()))
arr1=sorted(arr1)
mins=0
for i in range(n):
mins=max(mins,arr1[i]-i)
maxs=arr1[p-1]
arr2=[0]*n
for i in range(n): #上記のarrを求める
arr2[i]=(p-(n-arr1[n-i-1]-i))%p
arr2=arr2[::-1]
can=set(range(p))
pos=bisect.bisect_right(arr1,maxs-1)
for i in range(pos,n): #最大のxについて可能なあまりからarr[i]を取り除く
can.discard(arr2[i])
ans=[]
prev=pos #xが最大値のときのiの位置を記録しておく
for x in range(maxs-1,mins-1,-1): #xを最大値から順に見る
pos=bisect.bisect_right(arr1,x)
if pos==prev: #iが変化していなければ、x%pが可能なあまりに含まれているかを見ることで判定できる
if x%p in can:
ans.append(x)
else: #そうでなければ、まず可能なあまりからarr[i]を取り除いてから、x%pが含まれているかを見ることで判定できる
for i in range(pos,prev):
can.discard(arr2[i])
if x%p in can:
ans.append(x)
prev=pos
ans=ans[::-1] #条件を満たすxが降順になっているので逆順にする
print(len(ans))
print(*ans)
この記事が気に入ったらサポートをしてみませんか？