Educational Codeforces Round 71(Rated for Div.2) A～E解説
Educational Codeforces Round 71(Rated for Div.2)のA～Eまでの解説です。
コンテスト中にはA～CとEで4完し、コンテスト後にDも解きました(Codeforces2度目の4完を達成し、レートを伸ばすことができました＊)。
問題のアドレスは以下になります↓
https://codeforces.com/contest/1207/
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/69314
A問題:
制約が小さいので、各クエリについて、ハンバーガーを0～p個作りチキンバーガーを0〜f個作るという全探索を行い、それらの組み合わせのうち、実際に作ることが可能なものについて利益の最大値を求めればよいです。
この計算量はO(T*max(Pi)*max(Fi))となります。
B問題:
まず行列Aに含まれる1の個数cntを数えておき、その後Aの各要素a[i][j](i=1〜n-1,j=1〜m-1)について、a[i][j],a[i][j+1],a[i+1][j],a[i+1][j+1]のすべてが1であるとき、(i,j),(i+1,j),(i,j+1),(i+1,j+1)の4点をset型などに追加します。
すべての要素について見終えたとき、cnt=set型のサイズであればBをAに一致させることができ、そうでなければBをAに一致させることはできません。
この計算量はO(NMlogNM)となります。
サンプルコード(Python):
https://codeforces.com/contest/1207/submission/59284652
n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
one_cnt=0
for i in range(n): #行列Aに含まれる1の個数を数える
for j in range(m):
if arr[i][j]==1:
one_cnt+=1
cnt=0
act=[]
s=set()
for i in range(n-1): 各頂点を始点として、2x2の範囲の要素がすべて1であるかどうかを確かめる
for j in range(m-1):
if arr[i][j]==1 and arr[i+1][j]==1 and arr[i][j+1]==1 and arr[i+1][j+1]==1:
cnt+=1
act.append((i+1,j+1)) #すべてが1であれば、塗り始めの点を答えに加え、塗った点をset型に追加する
s.add((i,j))
s.add((i+1,j))
s.add((i,j+1))
s.add((i+1,j+1))
if one_cnt==len(s): #1の個数とset型のサイズ(実際に塗られた1の個数)が一致していれば、BをAに一致させられる
print(cnt)
for a,b in act:
print(a,b)
else: #そうでなければBをAに一致させることはできない
print(-1)
C問題:
まず、1が1つもなければ、そのような場合のコストはa*n+b*(n+1)となります。
また、1が1つまたは2つしかなければ、そのような場合のコストはa*(n+2)+b*(n+1+(2つの1の距離+1))となります。
1が3つ以上あるとき、101または10…01という区間が存在します。
101という区間については、ここで高さを下げることはできないので無視し、10…01という区間については、ここで高さを下げることにすると、コストはa*2-b*(0の長さ-1)変化します。
ここで、10…01という各区間について、高さを下げたとしても、他の区間に影響を与えることはありません。
したがって、コストの変化量が負であるようなとき、その部分では高さを下げるという貪欲法により、この問題をクエリあたりO(N)で解くことができるので、トータルとしてO(sum(N1,N2,…,Nn))で解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1207/submission/59299029
t=int(input())
for _ in range(t):
n,a,b=map(int,input().split())
s=input()
cnt=0
first_one=0
last_one=0
first_zero=0
last_zero=0
diff=0
for i in range(n):
if s[i]=='1': #最初の1の位置と最後の1の位置を求める
if first_one==0:
first_one=i
last_one=i
#10...01の区間について、高さを下げるとaが2つ増え、bが0の長さ-1減るので、その操作でコストが減るかどうかを判定する
if a*2<b*(last_zero-first_zero): #高さを下げることでコストを減らせるのであれば、その変化量を加える
diff+=a*2-b*(last_zero-first_zero)
first_zero=0 #10...01の区間が始まると考え、0の位置を初期化する
last_zero=0
if s[i]=='0':
if first_one!=0: #10...01の区間について、最初の0の位置と最後の0の位置を求める
if first_zero==0:
first_zero=i
last_zero=i
#上記の計算式にしたがい、最小コストを求める
if first_one==0: #1が1つもない場合
ans=a*n+b*(n+1)
else: #1が1つ以上ある場合
ans=a*(n+2)+b*((n+1)+(last_one-first_one+2))+diff
print(ans)
D問題:
良い列の総数を求めることは難しいので、悪い列の総数を求めることを考えます。
悪い列の総数は、包除原理より、({ai}が悪い列となる場合の数+{bi}が悪い列となる場合の数)-({ai},{bi}がともに悪い列となる場合の数)として求められます。
したがって、これらの場合の数が計算できれば、これをすべての場合の数から引くことで、良い列の総数を求めることができます。
{ai}が悪い列となる場合の数は、{ai}が単調非減少であることから、{ai}の要素として入れ替えられるのはai=aj(i!=j)なるai,ajについてのみなので、{ai}の各要素の個数を数え、それらの個数の階乗の積を計算することで求められます。
同様にして{bi}が悪い列となる場合の数も求めることができます。
{ai},{bi}がともに悪い列となる場合の数についてですが、与えられた列を{ai}についてソートしたあと{bi}についてソートしたとき、{ai}が良い列となってしまうのであればそのような場合は存在せず、{ai}が悪い列のままであれば、入れ替えが可能なのはai=ajかつbi=bj(i!=j)のときのみなので、aiとbiをペアにした各組の個数を数え、それらの個数の階乗の積を計算することで求められます。
この操作はソートの部分がネックとなることから、O(NlogN)で行うことができます。
サンプルコード(Python):
https://codeforces.com/contest/1207/submission/59353751
import collections
n=int(input())
arr_ab=[]
arr_a=[]
arr_b=[]
for _ in range(n): 列{ai},{bi},{(ai,bi)}をそれぞれ作成する
a,b=map(int,input().split())
arr_a.append(a)
arr_b.append(b)
arr_ab.append((a,b))
mod=998244353
tmp=1
facts=[1]
for val in range(1,n+1): #modの下での0!～n!を求める
tmp*=val
tmp%=mod
facts.append(tmp)
alls=facts[n] #全事象はn!で求められる
tmp=1
for value in collections.Counter(arr_a).values(): #{ai}が悪い列となる場合の数を求める
tmp*=facts[value] #{ai}の各要素の個数の階乗の積を計算する
tmp%=mod
bads_a=tmp #{ai}の各要素の個数の階乗の積が{ai}が悪い列となる場合の数となる
tmp=1
for value in collections.Counter(arr_b).values(): #{bi}が悪い列となる場合の数を求める
tmp*=facts[value] #{ai}の各要素の個数の階乗の積を計算する
tmp%=mod
bads_b=tmp #{bi}の各要素の個数の階乗の積が{bi}が悪い列となる場合の数となる
arr_ab=sorted(arr_ab)
flag=True
for i in range(n-1): #列{(ai,bi)}について、{ai}について昇順ソートしたとき、{bi}が昇順になっているかどうかを判定する
if arr_ab[i][1]<=arr_ab[i+1][1]:
continue
else:
flag=False
break
if flag==False: #{ai}について昇順ソートしたときに{bi}が昇順になっていなければ、{(ai,bi)}が悪い列になることはない
print((alls-(bads_a+bads_b))%mod)
else: #{(ai,bi)}が悪い列になりうるとき、その場合の数を求める
tmp=1
for val in collections.Counter(arr_ab).values():
tmp*=facts[val] #{(ai,bi)}の各要素の個数の階乗の積を計算する
tmp%=mod
bads_ab=tmp #{(ai,bi)}の各要素の個数の階乗の積が{(ai,bi)}が悪い列となる場合の数となる
print((alls-(bads_a+bads_b-bads_ab))%mod) #答えは全事象-(悪い列の総数)で求められる
E問題:
まず、重要な事実として、xorには交換則が成り立つことと、同じ数どうしのxorは0になることが挙げられます。
これより、あるクエリ{ai}を送ったときに返ってくる値ai xor x(i=1〜100)とaj(i=1～100)とのxorは、(ai xor aj) xor xと表せます。
同じ数どうしのxorは0になることから、i=jのとき(ai xor aj) xor x=xとなるので、集合{ai xor aj(i!=j)}と集合{bi xor bj(i!=j)}の共通部分が空であるような{ai},{bi}を取ることができれば、{ai xor aj xor x(j=1～100)}と{bi xor bj xor x(j=1～100)}の共通部分を求めることで、xを定めることができます。
このような{ai},{bi}の構成の方法についてですが、{ai}の各要素を下位7ビットがすべて1、上位7ビットのうち1～6個が1となっているような14桁の2進数、{bi}の各要素を上位7ビットがすべて1、下位7ビットのうち1～6個が1となっているような14桁の2進数として定め、{ai},{bj}はすべて相異なる数であるとすると、{ai xor aj(i!=j)}は下位7ビットがすべて0になり、上位7ビットのうち少なくとも1つは1になっており、また{bi xor bj(i!=j)}は上位7ビットがすべて0になり、下位7ビットのうち少なくとも1つは1になることから、{ai xor aj(i!=j)}と{bi xor bj(i!=j)}の共通部分は空となります。
このような{ai},{bi}は7C1+7C2+7C3+7C4+7C5+7C6=2^7-2=126>=100(∵二項定理)個存在することから、{ai},{bi}の要素数を100にすることができます。
以上の議論にしたがうことで、この問題を解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1207/submission/59413471
arr1=[]
arr2=[]
base_bit='1111111'
for i in range(1,101): #7ビットすべてが1の文字列と7ビットのうち1つ以上が1の文字列を組み合わせ、上記で述べた{ai},{bi}を構成する
add_bit=format(i,'b')
add_bit='0'*(7-len(add_bit))+add_bit
arr1.append(int(add_bit+base_bit,2)) #{ai}の構成
arr2.append(int(base_bit+add_bit,2)) #{bi}の構成
print('? '+' '.join(map(str,arr1)),flush=True)
x1=int(input())
s1=set()
for val in arr1: #{ai}について{ai xor aj xor x(j=1～100)}を求める
s1.add(val^x1)
print('? '+' '.join(map(str,arr2)),flush=True)
x2=int(input())
s2=set()
for val in arr2: #{bi}について{bi xor bj xor x(j=1～100)}を求める
s2.add(val^x2)
ans=list(s1&s2)[0] #{ai xor aj xor x(j=1～100)}と{bi xor bj xor x(j=1～100)}の共通部分が答えとなる
print('!',ans)
この記事が気に入ったらサポートをしてみませんか？