AtCoder Beginner Contest 167(ABC167) A〜F解説
AtCoder Beginner Contest 167(ABC167)のA~Fまでの解説です。
コンテスト中はA~Eまでを解き(60:16+1WA)、前回に引き続き青パフォを出せ、レートを少し伸ばすことができました*
問題のアドレスは以下になります↓
https://atcoder.jp/contests/abc167/
公式の解説(Editorial)は以下になります↓
https://img.atcoder.jp/abc167/editorial.pdf
A問題:
制約よりTはSより1文字多い文字列であることが保証されるので、Tの末尾-1文字まで見たものがSに等しいかを確かめればよいです。
B問題:
明らかに、まずAから取り、次にBから取り、最後にCから取るのが最善です。
K<=A+Bのとき、答えはmin(K,A)に等しく、K>A+Bのとき、答えはA-(K-(A+B))=2A+B-Kに等しくなります。
C問題:
制約からも分かる通り、いわゆるbit全探索の問題です。
どの参考書を買うかの組み合わせをbitのオンオフで表すと考え、すべてのパターンについて、M個のアルゴリズムの理解度がX以上になるかを確かめ、理解度がX以上になるものの中で費用が最小になるものを求めます。
各パターンについてアルゴリズムの理解度を愚直に計算すると、計算量はO(NM2^N)となりこの問題を解くことができます。
実装の際は、計算すべきパラメータが2つあることに注意してください。
サンプルコード(Python):
https://atcoder.jp/contests/abc167/submissions/13036937
n,m,x=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
ans=10**18
for i in range(2**n): #すべての買い方のパターンを試す
flag=format(i,'b')
flag='0'*(n-len(flag))+flag
tmp=0
check=[0]*(m)
for j in range(n):
if flag[j]=='0':
continue
tmp+=arr[j][0] #ある参考書を買う場合、その費用を加える
for k in range(m): #参考書で得られるアルゴリズムの理解度を加える
check[k]+=arr[j][k+1]
for j in range(m):
if check[j]<x: すべてのアルゴリズムについて、理解度がX以上かを確かめる
break
else: #すべてX以上であれば費用の最小値を更新する
ans=min(ans,tmp)
if ans==10**18: #条件を満たすものが1つもなければ-1を返す
print(-1)
else: #そうでなければ最小値を返す
print(ans)
D問題:
制約より要素数はN<=2*10^5で、どの要素からも必ずいずれかの要素に移動することから、高々N回の移動で同じ場所に戻ってくることが分かります。
つまり、問題のような移動は高々N以下の周期を持つので、同じ点に2回到達するまでの移動経路をシミュレートし、ループに含まれる頂点に到達するまでの移動回数とループの長さを求めることで、高々O(2*N)でこの問題を解くことができます。
また、ダブリングと呼ばれる手法を用いることで、O(NlogK)でこの問題を解くこともできます。
サンプルコード(Python)(周期性を用いたもの):
https://atcoder.jp/contests/abc167/submissions/13469263
n,k=map(int,input().split())
arr=list(map(int,input().split()))
l=[-1]*(n+1) #何回目にそれぞれの頂点に到達したか
tmp=[] #頂点の移動経路
pos=1 #初期位置
cnt=0 #移動回数
while 1:
if l[pos]!=-1: #ある頂点に2回到達したとき
t=cnt-l[pos] #ループの長さは(今の移動回数)-(前にその頂点に到達したときの回数)で得られる
if k<cnt: #Kが頂点の移動経路の長さより小さい、移動経路のK番目の要素が答えとなる
print(tmp[k])
else: #経路の長さより大きいとき、2回到達した頂点を始点として、最終的にループのどの頂点に到達するかを求める
print(tmp[l[pos]+(k-cnt)%t])
break
l[pos]=cnt
cnt+=1
tmp.append(pos)
pos=arr[pos-1]
サンプルコード(Python)(ダブリング):
https://atcoder.jp/contests/abc167/submissions/13049014
n,k=map(int,input().split())
arr=list(map(int,input().split()))
for i in range(n):
arr[i]-=1
flag=format(k,'b')
flag=flag[::-1]
pos=0 #初期位置
for i in range(len(flag)):
if flag[i]=='1': #Kの2^i乗のbitがオンであれば、2^i回の移動を行う
pos=arr[pos]
tmp=[]
for j in range(n): #2^k回の移動を2回行うと、2^(k+1)回の移動が表現できる(ダブリング)
tmp.append(arr[arr[j]])
arr=tmp
print(pos+1)
E問題:
制約よりK<=10^5なので、隣り合うブロックの組であって同じ色で塗られている組がk(0<=k<=K個)であるものをそれぞれ考えれば解けることが分かります。
ここで、すべてのグループの要素数が1以上になるようにN個のブロックをm個のグループに分け、同じグループのブロックはすべて同じ色で塗り、隣り合うグループのブロックは異なる色で塗ることを考えます。
すると、上記の方法で色を塗ったとき、隣り合うブロックの組であって同じ色で塗られている組はN-m個であることが分かります。
これがK以下であればよいので、N-m<=K⇔N-K<=m(<=N)より、mとしてはN-KからNまでを考えればよいです。
すべてのグループの要素数が1以上になるようにN個のブロックをm個のグループに分ける場合の数は、(N-1)C(m-1)で求めることができ、最初のグループはM通りの塗り方があり、以降のグループは(M-1)通りの塗り方があることから、各mについて、(N-1)C(m-1)*M*(M-1)^(m-1)を足し合わせたものが答えとなります。
事前に階乗と階乗の逆元をO(NlogN)で求めておくことで上記の計算はO(logm)で行うことができるので、トータルO(NlogN+Nlogm)でこの問題を解くことができました。
サンプルコード(Python):
https://atcoder.jp/contests/abc167/submissions/13095931
mod=998244353
fact=[1]
for i in range(1,2*10**5+1): #mod上での階乗を求める
fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,2*10**5+1): #mod上での階乗の逆元をフェルマーの小定理を用いて求める
revfact.append(pow(fact[i],mod-2,mod))
n,m,k=map(int,input().split())
ans=0
for i in range(k,-1,-1): #各m(N-K<=m<=N)について場合の数を求める
group=n-i
tmp=fact[n-1]*revfact[group-1]*revfact[n-1-(group-1)]
tmp%=mod
tmp*=m
tmp%=mod
tmp*=pow(m-1,group-1,mod)
ans+=tmp
ans%=mod
print(ans)
F問題:
まず、与えられた文字列から括弧列を取り除いたものを考えることとします(これは括弧列の構成での常套手段のようです)。
すると、与えられた文字列を、開き括弧のみのもの、閉じ括弧のみのもの、閉じ括弧が1つ以上続いたあと開き括弧が1つ以上続くもの(以下これを閉じ開き括弧と呼びます)、の3つに分類することができます。
ここで、与えられた文字列から括弧列を作るとき、何個の括弧列を作るのが最善かを考えます。
すると、k(>1)個の括弧列が作れると仮定したとき、そのうちの1つを他の括弧列の内側に挿入することで、k-1個の括弧列も同様に作れることが分かります。
これより、k(>1)個の括弧列が作れるとき、必ず1個の括弧列を作れることが分かります。
一方、この操作は可逆であることから、1個の括弧列が作れないとき、k(>=2)個の括弧列も同様に作ることができません。
したがって、1個の括弧列を作れるかどうかを判定すれば十分であることが分かります。
これより、開き括弧のみのものは先頭に持ってくるのが最善であり、また閉じ括弧のみのものは末尾に持ってくるのが最善であることが分かります。
残る閉じ開き括弧について、これらをすべて繋げると、最終的に1つの閉じ開き括弧ができます。
このとき、閉じ開き括弧の閉じ括弧のみの総和と開き括弧のみの総和の差は、どのように閉じ開き括弧を繋げても変化することはありません。
したがって、開き括弧のみのものの総和と閉じ括弧のみのものの総和の差と、閉じ開き括弧の閉じ括弧の総和と開き括弧の総和の差が異なるとき、括弧列を構成することは不可能です(∵必ず開き括弧か閉じ括弧のいずれかが余ります)。
一方、最終的にできる閉じ開き括弧の閉じ括弧と開き括弧の個数は、繋ぎ方によって変化し、上記の条件を満たしている場合であっても、開き括弧のみのものの総和<最終的にできる閉じ開き括弧の閉じ括弧の個数、もしくは閉じ括弧のみのものの総和<最終的にできる閉じ開き括弧の開き括弧の個数を満たすとき、括弧列を構成することは不可能です(∵閉じ開き括弧を"包む"括弧の個数が足りないので、最終的にできる文字列は開き括弧もしくは閉じ括弧になります)。
したがって、上記の条件を満たすような閉じ開き括弧の繋ぎ方があるかを確かめる必要があります。
これは、閉じ開き括弧の閉じ括弧の総和と開き括弧の総和を求めておくと、閉じ開き括弧を繋げる際の左端の閉じ開き括弧と右端の閉じ開き括弧をすべて試すことで求めることができますが、これを愚直に行うと最悪の場合O(N^2)となり間に合いません。
ここで、左端の閉じ開き括弧の閉じ括弧の個数をa、右端の閉じ開き括弧の開き括弧の個数をbとすると、diff=(閉じ開き括弧の閉じ括弧の総和-a)-(閉じ開き括弧の開き括弧の総和-b)が0以上であれば最終的にできる閉じ開き括弧の閉じ括弧の個数はa+diff、開き括弧の個数はbとなり、diffが0以下であれば最終的にできる閉じ開き括弧の閉じ括弧の個数はa、開き括弧の個数はb-diffとなります。
a+diffにdiffの中身を代入すると、b+(閉じ開き括弧の閉じ括弧の総和-閉じ開き括弧の開き括弧の総和)となり、同様に、b-diffにdiffの中身を代入すると、a+(閉じ開き括弧の開き括弧の総和-閉じ開き括弧の閉じ括弧の総和)となります。
さらに、diffが0以上となるのはdiff>=0⇔(閉じ開き括弧の閉じ括弧の総和-a)-(閉じ開き括弧の開き括弧の総和-b)>=0⇔b+(閉じ開き括弧の閉じ括弧の総和-閉じ開き括弧の開き括弧の総和)>=aのとき、diffが0以下となるのはdiff<=0⇔(閉じ開き括弧の閉じ括弧の総和-a)-(閉じ開き括弧の開き括弧の総和-b)<=0⇔b<=a+(閉じ開き括弧の開き括弧の総和-閉じ開き括弧の閉じ括弧の総和)であることから、各aについて、開き括弧のみのものの総和>=a、閉じ括弧のみのものの総和>=a+(閉じ開き括弧の開き括弧の総和-閉じ開き括弧の閉じ括弧の総和)を満たし、かつb<=a+(閉じ開き括弧の開き括弧の総和-閉じ開き括弧の閉じ括弧の総和)を満たすbが存在するかを確かめ、同様に、各bについて、開き括弧のみのものの総和>=b+(閉じ開き括弧の閉じ括弧の総和-閉じ開き括弧の開き括弧の総和)、閉じ括弧のみのものの総和>=bを満たし、かつa<=b+(閉じ開き括弧の閉じ括弧の総和-閉じ開き括弧の開き括弧の総和)を満たすaが存在するかを2分探索などで確かめることで、O(NlogN)でこの問題を解くことができました。
また公式のEditorialにある通り、開き括弧が増えるような括弧列について、閉じ括弧が少ない方から順に取り、ついで開き括弧が減るような括弧列について、開き括弧が多い方から順に取る貪欲法によってもこの問題をO(NlogN)で解くことができます。
サンプルコード(Python)(構成が存在するかを2分探索で判定する方法):
https://atcoder.jp/contests/abc167/submissions/13595016
import bisect
n=int(input())
opens=0 #開き括弧のみのものの総和
closes=0 #閉じ括弧のみのものの総和
ls=[] #各閉じ開き括弧の閉じ括弧の個数
rs=[] #各閉じ開き括弧の開き括弧の個数
for _ in range(n):
s=input()
cnt1=0 #末尾から見た開き括弧の個数
cnt2=0 #先頭から見た閉じ括弧の個数
for i in range(len(s)):
if s[i]=='(': #開き括弧がきたら開き括弧の個数を増やす
cnt1+=1
else:
if cnt1==0: #開き括弧のストックがないときに閉じ括弧がきたら閉じ括弧の個数を増やす
cnt2+=1
else: #開き括弧のストックがあるときは開き括弧の個数を減らす
cnt1-=1
if cnt2==0: #開き括弧のみの場合
opens+=cnt1
elif cnt1==0: #閉じ括弧のみの場合
closes+=cnt2
else: #閉じ開き括弧の場合
ls.append(cnt2)
rs.append(cnt1)
ls=sorted(ls) #2分探索するのでソートしておく
rs=sorted(rs)
lefts=sum(ls) #閉じ開き括弧の閉じ括弧の総和
rights=sum(rs) #閉じ開き括弧の開き括弧の総和
if opens-closes!=lefts-rights: #(開き括弧のみのものの総和)-(閉じ括弧のみのものの総和)が(閉じ開き括弧の閉じ括弧の総和)-(閉じ開き括弧の開き括弧の総和)に一致しないとき構成は不可能
print('No')
else:
flag=False
if len(ls)==0: #上記の差が等しく、かつ閉じ開き括弧がなければ構成は可能
flag=True
for a in ls: #すべての閉じ開き括弧の閉じ括弧の個数について、条件を満たす開き括弧の個数が存在するかを確かめる
if opens<a or closes<a+(rights-lefts): #外側の開き括弧、閉じ括弧の個数を上回る場合は構成は不可能
continue
pos=bisect.bisect_right(rs,a+(rights-lefts))
if pos!=0: #b<=a+(rights-lefts)を満たすbが存在すればOK
flag=True
break
for b in rs: #すべての閉じ開き括弧の開き括弧の個数について、条件を満たす閉じ括弧の個数が存在するかを確かめる
if opens<b+(lefts-rights) or closes<b: #外側の開き括弧、閉じ括弧の個数を上回る場合は構成は不可能
continue
pos=bisect.bisect_right(ls,b+(lefts-rights))
if pos!=0: #a<=b+(lefts-rights)を満たすaが存在すればOK
flag=True
break
if flag==True:
print('Yes')
else:
print('No')
サンプルコード(Python)(貪欲法):
https://atcoder.jp/contests/abc167/submissions/13593195
n=int(input())
arr1=[]
arr2=[]
for _ in range(n):
s=input()
cnt1=0
cnt2=0
for i in range(len(s)):
if s[i]=='(':
cnt1+=1
else:
if cnt1==0:
cnt2+=1
else:
cnt1-=1
if cnt1-cnt2>=0: #開き括弧が増える場合
arr1.append([cnt1,cnt2])
else: #開き括弧が減る場合
arr2.append([cnt1,cnt2])
arr1=sorted(arr1,key=lambda x:x[1]) #閉じ括弧の少ない順に見ていく
arr2=sorted(arr2,reverse=True,key=lambda x:x[0]) #開き括弧の多い順に見ていく
arr=arr1+arr2
cnt=0 #最初の開き括弧は0個
for a,b in arr:
if b>cnt: #ある時点で閉じ括弧の個数が開き括弧の個数よりも多いとき、構成は不可能
print('No')
break
else: #そうでないとき、開き括弧の個数をa-bだけ増減させる
cnt+=a-b
else: #最後まで括弧列を見たとき
if cnt==0: #開き括弧の個数が0になっていれば構成は可能
print('Yes')
else: #そうでなければ構成は不可能(開き括弧か閉じ括弧が余る)
print('No')
この記事が気に入ったらサポートをしてみませんか?