Codeforces Round #634(Div.3) A～E2解説
Codeforces Round #634 (Div.3)のA～E2までの解説です。
問題のアドレスは以下になります↓
https://codeforces.com/contest/1335
公式の解説(Editorial)は以下になります↓
https://codeforces.com/blog/entry/75993
A問題:
与えられたキャンディが奇数個のとき、a=bとなることはありません。
したがって、a>b>0を満たすキャンディの分け方は、(キャンディの個数-1)/2に一致します(∵0<b<(キャンディの個数)/2を満たすbは、1から(キャンディの個数-1)/2までのいずれかです)。
与えられたキャンディが偶数個のとき、a=bとなることがあり得ます。
したがって、a>b>0を満たすキャンディの分け方は、(キャンディの個数)/2-1に一致します(∵0<b<(キャンディの個数)/2を満たすbは、1から(キャンディの個数)/2-1までのいずれかです)。
以上より、キャンディが奇数個のときは(キャンディの個数-1)/2を、キャンディが偶数個のときは(キャンディの個数)/2-1をそれぞれ答えればよいです。
サンプルコード(Python):
https://codeforces.com/contest/1335/submission/76652574
t=int(input())
for _ in range(t):
n=int(input())
if n%2==0:
print(n//2-1)
else:
print(n//2)
B問題:
まず、長さがa文字でアルファベットの種類数がbであるような文字列を作ります。
これは、例えば"a"から順にb-1種類のアルファベットを1文字ずつ繋げ、最後にb種類目のアルファベットをa-b+1文字付け加えることで作ることができます。
次に、残りのn-a文字を、どの長さa文字の連続した部分文字列についてもアルファベットの種類数がbとなるように付け加えます。
これは、すでに付け加えた文字列を末尾からa-1文字見たときに、その文字列のアルファベットの種類数がbであれば末尾の文字を付け加え、種類数がbでなければ末尾の文字の1つ次のアルファベットを付け加えることで実現できます。
ただし、aが1のとき見る文字列が空となってしまうので、この場合のみ末尾の文字列の1つ次のアルファベットを常に付け加えることとします。
以上を実装することによりこの問題をO(NAlogA)で解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1335/submission/76653398
t=int(input())
for _ in range(t):
n,a,b=map(int,input().split())
ans=''
cnt=0
for i in range(b-1):
ans+=chr(cnt+97)
cnt+=1
cnt%=26
if a>=b:
ans+=chr(cnt+97)*(a-b+1)
for i in range(n-a):
if a==1:
cnt+=1
cnt%=26
ans+=chr(cnt+97)
else:
if len(set(ans[-(a-1):]))==b:
ans+=chr(cnt+97)
else:
cnt+=1
cnt%=26
ans+=chr(cnt+97)
print(ans)
C問題:
1つ目のグループには同じ数を1つしか入れることができず、2つ目のグループには1つの数しか入れることができません。
これより、1つ目のグループは最大でも数列の要素の種類数の長さまでしか取ることはできず、2つ目のグループは最大でも数列の各要素の個数の最大値の長さまでしか取ることはできないことが分かります。
いま、1つ目のグループの長さを最大とすることを考えると、2つ目のグループの長さは最大で(数列の各要素の個数の最大値)-1となります(∵個数が最大であるような要素も1つ目のグループに1つ含まれる)。
このときの答えはmin(数列の要素の種類数,数列の各要素の個数の最大値-1)となります。
また、2つ目のグループの長さを最大とすることを考えると、1つ目のグループの長さは最大で(数列の要素の種類数)-1となります(∵個数が最大であるような要素は1つ目のグループに含まれません)。
このときの答えはmin(数列の要素の種類数-1,数列の各要素の個数の最大値)となります。
ここで、1つ目のグループの長さを最大値から2以上小さくしても、2つ目のグループの長さは数列の各要素の個数の最大値より大きくなることはなく、また同様に2つ目のグループの長さを最大値から2以上小さくしても、1つ目のグループの長さが数列の要素の種類数より大きくなることはありません。
したがって、上の2つのminの最大値を取ればよく、これによりこの問題をトータルO(N)で解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1335/submission/76652467
import collections
t=int(input())
for _ in range(t):
n=int(input())
arr=list(map(int,input().split()))
cnt=collections.Counter(arr)
variety=len(cnt.keys())
largest=max(cnt.values())
print(max(min(variety-1,largest),min(variety,largest-1)))
D問題:
あるマスを書き換えたとき、同じ数が2つ以上になる行・列・ブロックは高々1つしか増えません。
したがって、書き換える対象のマスは9つのブロックから1つずつ選ぶ必要があります。
ここで、すべての数はすべての行・列・ブロックに1つずつ含まれることから、書き換えた後の数は1つに固定してよく、またどのような数を選んでも解法に影響はないので、ここでは書き換えた後の数を1して議論を進めます。
各ブロックについて、書き換える対象のマスを1がある行から選ぶことにすると、書き換える対象のマスを1に書き換えることによって、すべての行とすべてのブロックについて同じ数が2つ以上含まれることになります。
よって、あとは各ブロックについて書き換える対象のマスを選んだとき、すべての列について同じ数が2つ以上含まれるようにする方法を考えればよいです。
ここで、書き換える対象のマスとして各ブロックの1があるマスの右隣のマス(ただし、1があるマスがブロックの右端にあるときはブロックの左端のマス)を選ぶことにすると、1はすべての列に1つずつ存在することから、書き換える対象のマスもすべての列に1つずつ存在することになり、ブロック内で書き換えるマスを選んでいることから、すべての行とすべてのブロックにも書き換える対象のマスが1つずつ存在することになります。
以上によりこの問題をO(T)で解くことができました(ただし定数倍が9*9倍ほどかかります)。
サンプルコード(Python):
https://codeforces.com/contest/1335/submission/76652040
t=int(input())
for _ in range(t):
board=[list(input()) for _ in range(9)]
for i in range(9):
for j in range(9):
if board[i][j]=='1':
tmp=3*(j//3)+(j%3+1)%3
board[i][tmp]='1'
break
for i in range(9):
print(''.join(map(str,board[i])))
E1問題:
a=bのとき、明らかに数列に含まれる要素の個数の最大値がa=bの下での列の長さの最大値に一致します。
a!=bのとき、制約より1<=ai<=26であり、aiの種類数が高々26であることから、すべての(i,j) (i!=j)について、a=ai,b=ajとしたときの列の長さの最大値を求め、それらの最大値を答えればよいです。
これは、a,bのそれぞれについて数列中の個数の累積和acum1,acum2を求めておき、acum1を2分探索することで数列の先頭からk番目のaの位置lkと数列の末尾からk番目のaの位置rkを求めると、rk>lkを満たすとき、列の長さは2*k+acum2[r]-acum2[l]に一致します。
これをすべての(i,j) (i!=j)について求めればよく、これよりこの問題をO(NlogN)で解くことができました(ただし定数倍が26*25倍程度かかります)。
サンプルコード(Python):
https://codeforces.com/contest/1335/submission/76690010
import bisect
t=int(input())
for _ in range(t):
n=int(input())
arr=list(map(int,input().split()))
variety=list(set(arr))
ans=0
for a in variety:
for b in variety:
if a==b:
ans=max(ans,arr.count(a))
else:
acum1=[0]*n
acum2=[0]*n
for i in range(n):
if arr[i]==a:
acum1[i]+=1
elif arr[i]==b:
acum2[i]+=1
acum1[i]+=acum1[i-1]
acum2[i]+=acum2[i-1]
for i in range(1,acum1[-1]//2+1):
l=bisect.bisect_left(acum1,i)
r=bisect.bisect_left(acum1,acum1[-1]-i+1)
tmp=i*2+acum2[r]-acum2[l]
ans=max(ans,tmp)
print(ans)
E2問題:
E2問題では、aiの種類数が高々200に増加しているためE1と同様の解法を使うことはできません。
ここで、すべてのaiの種類について、事前に数列中の個数の累積和を求めておくと、bとしてすべてのaiの種類を試す代わりに、lkとrkについてacum[ai][rk]-acum[ai][lk]が最大となるものを選べばよいので、すべてのaiの種類を試すのをaのみに絞ることができます。
また、数列の先頭からk番目のaの位置lkと数列の末尾からk番目のaの位置rkは、事前に数列中のaの位置を配列に取り出しておくことで2分探索を使わずに求めることができるので、以上よりこの問題をO(Nmax(ai)+max(ai)^3)で解くことができました。
サンプルコード(Python):
https://codeforces.com/contest/1335/submission/76692655
t=int(input())
for _ in range(t):
n=int(input())
arr=list(map(int,input().split()))
variety=list(set(arr))
cnts=[[0]*(n+1) for _ in range(201)]
poss=[[] for _ in range(201)]
for i in range(n):
cnts[arr[i]][i]+=1
poss[arr[i]].append(i)
for j in range(201):
cnts[j][i]+=cnts[j][i-1]
ans=0
for i in range(201):
tmp=cnts[i][n-1]
ans=max(ans,tmp)
for a in variety:
for i in range(n):
l=poss[a][i]
r=poss[a][-(i+1)]
if l>=r:
break
tmp=0
for j in range(201):
if j==a:
continue
tmp=max(tmp,cnts[j][r]-cnts[j][l])
tmp+=2*(i+1)
ans=max(ans,tmp)
print(ans)
この記事が気に入ったらサポートをしてみませんか？