AtCoder Beginner Contest 173(ABC173) A～F解説
AtCoder Beginner Contest 173(ABC173)のA～Fまでの解説です。
コンテスト中はA～Dを解き(20:57+2WA)、Eで大きくつまずきレート微減という結果に終わりました。
問題のアドレスは以下になります↓
https://atcoder.jp/contests/abc173/
公式の解説(Editorial)は以下になります↓
https://img.atcoder.jp/abc173/editorial.pdf
A問題:
与えられたNについてN%1000を求めると、これはもう1枚千円札を出して支払うべきあまりの金額を表していることが分かります。
ここで、N%1000=0のときは支払うべきあまりが存在しないので0を出力すればよく、N%1000!=0のときはもう1枚千円札を出して支払いを行う必要があり、このときのお釣りは1000-N%1000として求めることができます。
また、与えられたNについて、N以上となる最小の1000の倍数を求めることでもこの問題を解くことができます。
B問題:
与えられたSiに、AC,WA,TLE,REのそれぞれが何個含まれているかを数える問題です。
個数を数える際には、for文を用いてそれぞれのSiがAC,WA,TLE,REのいずれと一致するかを確かめる方法や、配列arrayの中の特定の要素の個数を求める関数(Pythonであればarray.count())を用いる方法、配列arrayの中の各要素の個数を求める関数(Pythonであればcollections.Counter(array))を用いる方法などがあります。
C問題:
制約が小さいので、各行・各列について塗りつぶす方法をすべて試すことでこの問題を解くことができます。
具体的には、各行と各列について塗りつぶすかどうかを2値で表すことにすると、これを2進数とみなすことができ、0から(2^H)-1までと0から(2^W)-1を見ることで、すべての各行・各列を塗りつぶす方法を列挙することができます。
各行について、左からi番目のビットが1のときi行目を塗りつぶし、同様に、各列について、左からi番目のビットが1のときi列目を塗りつぶすこととすると、i行目j列目の要素が塗りつぶされないのは、各行のi番目のビットと各列のi番目のビットがともに0のときのみです。
したがって、すべての塗りつぶし方について、すべての要素が塗りつぶされるかどうかを確かめ、塗りつぶされない要素について、そのマスが黒マスであれば個数を+1し、個数の総和がKに等しければ答えを+1することで、この問題を解くことができます。
この計算量は(2^H*2^W*HW)となり、H,W<=6より十分高速に動作します。
サンプルコード(Python):
https://atcoder.jp/contests/abc173/submissions/15028341
h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
ans=0
for paint_h in range(2**h): #すべての行の塗りつぶし方を2進数で列挙する
for paint_w in range(2**w): #すべての列の塗りつぶし方を2進数で列挙する
cnt=0
for i in range(h): #すべてのi行目j列目の要素についてみる
for j in range(w):
if (paint_h>>i)&1==0 and (paint_w>>j)&1==0: #各行のi番目のビットと各列のj番目のビットがともに0であればそのマスは塗りつぶされない
if board[i][j]=='#': #塗りつぶされないマスが黒マスであれば個数を+1する
cnt+=1
if cnt==k: #塗りつぶされない黒マスの個数がKに等しければ答えを+1する
ans+=1
print(ans)
D問題:
まず、N人を追加する順として、直感的にaiを降順にソートした順で追加するのがよさそうだと分かります(∵ある人iが到着したとき、ai>ajなる人jがすでに到着していたとすると、人iと人jの到着順を入れ替えることで答えを真に大きくすることができます)。
したがって、追加する順としてaiを降順にソートした順を考えることにすると、人kが人iと人jの間に入ったとき得られる値はmin(ai,aj)に等しく、人iと人kの間、人kと人jの間が新たに割り込める場所として追加されます。
これより、min(ai,aj)の最大値を順に取っていくことで求める最大値を得ることができます。
人が1人到着するごとに区間が1増えることから、これを愚直に行うとO(N^2)となり制限時間に間に合いませんが、min(ai,aj)を優先度付きキューを用いて管理することにより、人が1人割り込むごとにO(logN)でmin(ai,aj)の最大値を得ることができるので、トータルO(NlogN)でこの問題を解くことができました。
さらに考察を進めると、上記のmin(ai,aj)の最大値として取られるのは、順にa1,a2,a2,a3,a3,…となるので、sum[i=2 to n](a(i+1)//2)を求めることでも答えを得ることができ、この計算量はソートがネックとなりO(NlogN)となります。
サンプルコード(優先度付きキューで値を管理する方法):
https://atcoder.jp/contests/abc173/submissions/15028695
import heapq
n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True)
ans=0
q=[]
heapq.heappush(q,-arr[0]) #人1がすでに到着しているとしたとき、得られる値はa0に等しい
for i in range(1,n):
tmp=heapq.heappop(q) #Pythonの優先度付きキューは最小値を取り出すので-を掛けて最大値を取り出せるようにしている
tmp*=-1
ans+=tmp #各時点でのmin(ai,aj)の最大値を答えに足し合わせる
heapq.heappush(q,-arr[i]) #新たに割り込める場所として追加された人iと人kの間・人kと人jの間で得られる値akを優先度付きキューに追加する
heapq.heappush(q,-arr[i])
print(ans)サンプルコード(上から貪欲に取る方法)
https://atcoder.jp/contests/abc173/submissions/15035065
n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True) #aiを降順にソートしておく
ans=0
for i in range(1,n): #sum[i=2 to n](a(i+1)//2)を求める
ans+=arr[i//2]
print(ans)
E問題:
(Editorialの方針1で解きました、コンテスト中に最初に書いたのは方針2のものだったのでこちらも簡単に述べます)
まず、明らかにK=Nのときすべての要素を掛け合わせるほかなく、このときの値は一意に定まります。
最終的な答えを非負にできるとき、絶対値が大きい順に取るのが最善であり、逆に答えが負にしかならないとき、絶対値が小さい順に取るのが最善であるのは明らかです。
したがって、K!=NのときにK個の積が負になるようなケースについて考えます。
これは、Kが奇数かつすべての要素が負のときに限ります。
よって、このようなケースについては絶対値が小さい順にK個掛け合わせればよいです。
上記の条件を満たさない場合、最終的な答えは必ず非負にできます。
したがって、まず絶対値が大きい順にK個取り、その積を求めます。
この値が非負であれば、その値が答えに等しいです。
一方、この値が負であるとき、答えを非負に調整する必要があります。
この方法としては、
・絶対値が大きい順のK個のうち絶対値が最小の負の数と、残るN-K個のうち最大の非負の数を入れ替える
・絶対値が大きい順のK個のうち絶対値が最小の非負の数と、残るN-K個のうち絶対値が最大の負の数を入れ替える
の2つがあります。
上記の条件を満たさない場合、2つの方法のうち少なくとも1つは実行することができます。
したがって、どちらか一方しか行えないときは、その操作を行ったときの値が答えに等しく、どちらも行える場合は、それらの操作を行ったときの値を比較し、より大きいほうを選べばよいです。
具体的には、1番目の方法では答えは(K個のうちの最大の非負の数)/(N-K個のうちの最小の負の数)倍、2番目の方法では答えは(K個のうちの最大の負の数)/(N-K個のうちの最小の非負の数)倍されるので、これより、(K個のうちの最大の非負の数)*(N-K個のうちの最小の非負の数)と(K個のうちの最大の負の数)*(N-K個のうちの最小の負の数)のどちらが大きいかを判定すればよいです。
以上によりこの問題をO(NlogN)で解くことができました。
また、上記と同様にして値が負になる場合を除いておき、答えが0になる場合も除いておくと、正の数を大きいほうから2数かけたものと負の数を大きいほうから2数かけたもののうち大きいほうを採用する、という操作を繰り返すことで、積を最大にすることができます(Editorialの方針2になります)。
このとき、Kが奇数であれば、はじめに正の数のうち最大のものを1つ取っておくことで、Kが偶数の場合に帰着でき、上記により積の最大値を求めることができます。
この解法はソートがネックとなりO(NlogN)となります(個人的には方針2のほうが思いつきやすく、かつバグらせにくいと思います)。
サンプルコード(Editorialの方針1):
https://atcoder.jp/contests/abc173/submissions/15029720
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr,reverse=True,key=lambda x:abs(x)) #絶対値の順にソートする
if k==n: #k=nのときはすべてを掛け合わせるほかない
ans=1
for i in range(n):
ans*=arr[i]
ans%=mod
print(ans)
else:
if k%2==1 and max(arr)<0: #答えが負になる場合は絶対値の小さい順にK個掛け合わせる
ans=1
for i in range(k):
ans*=arr[n-1-i]
ans%=mod
print(ans)
else:
ans=1
cnt=0
for i in range(k): #絶対値の大きい順にK個掛け合わせる
if arr[i]<0: #負数を掛けた回数を数えておく
cnt+=1
ans*=arr[i]
ans%=mod
if cnt%2==0: #負数を偶数回掛けていれば答えは非負なのでそのまま出力
print(ans)
else: #そうでなければ調整を行う
min_plus=-1
min_minus=1
for i in range(k): #絶対値の大きい順にK個を見て最小の非負の数・負の数を探す
if arr[i]>=0:
min_plus=arr[i]
else:
min_minus=arr[i]
max_plus=-1
max_minus=1
for i in range(k,n): #残るN-K個を見て最大の非負の数・負の数を探す
if arr[i]>=0 and max_plus==-1:
max_plus=arr[i]
if arr[i]<0 and max_minus==1:
max_minus=arr[i]
if min_plus==-1: #もし最小の非負の数がなければ、最小の負の数を取り除くしかない
arr.remove(min_minus)
ans=1
for i in range(k-1):
ans*=arr[i]
ans%=mod
ans*=max_plus
ans%=mod
elif min_minus==1: #もし最小の負の数がなければ、最小の非負の数を取り除くしかない
arr.remove(min_plus)
ans=1
for i in range(k-1):
ans*=arr[i]
ans%=mod
ans*=max_minus
ans%=mod
elif min_plus*max_plus>=min_minus*max_minus: #そうでなければより倍率の大きいほうを選ぶ
arr.remove(min_minus)
ans=1
for i in range(k-1):
ans*=arr[i]
ans%=mod
ans*=max_plus
ans%=mod
else:
arr.remove(min_plus)
ans=1
for i in range(k-1):
ans*=arr[i]
ans%=mod
ans*=max_minus
ans%=mod
print(ans)サンプルコード(Editorialの方針2):
https://atcoder.jp/contests/abc173/submissions/15036508
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
cnt_plus=0
cnt_zero=0
cnt_minus=0
arr_plus=[]
arr_minus=[]
for i in range(n):
if arr[i]>0:
cnt_plus+=1
arr_plus.append(arr[i])
elif arr[i]<0:
cnt_minus+=1
arr_minus.append(-arr[i])
else:
cnt_zero+=1
if cnt_plus+cnt_minus<k: #K個の積の中に0を含む場合、答えは0
print(0)
exit()
if k==n: #K=Nの場合
if cnt_zero!=0: #0がひとつでもあれば答えは0
print(0)
else:
ans=1
for i in range(cnt_plus):
ans*=arr_plus[i]
ans%=mod
for i in range(cnt_minus):
ans*=arr_minus[i]
ans%=mod
if cnt_minus%2==0: #負の数が偶数個であれば積は正
print(ans)
else: #そうでなければ積は負となる
print((-ans)%mod)
exit()
if cnt_plus==0 and k%2==1: #正の数がないとき
if cnt_zero!=0: #0がひとつでもあれば答えは0にできる
print(0)
else: #0がないときは負の数を絶対値が小さい順に掛けるのが最善
arr_minus=sorted(arr_minus)
tmp=1
for i in range(k):
tmp*=arr_minus[i]
tmp%=mod
print((-tmp)%mod)
exit()
else: #正の数と負の数から合計K個取れるとき
arr_plus=sorted(arr_plus,reverse=True)
arr_minus=sorted(arr_minus,reverse=True)
if k%2==0: #Kが偶数であれば何もしない
ans=1
pos_plus=0
pos_minus=0
cnt=0
else: #Kが奇数であれば正の数から最大のものを取っておき、Kが偶数の場合に帰着させる
ans=arr_plus[0]
pos_plus=1
pos_minus=0
cnt=1
while cnt<k:
cand1=0
if pos_plus<=cnt_plus-2: #正の数を2つ取れるなら取る
cand1=arr_plus[pos_plus]*arr_plus[pos_plus+1]
cand2=0
if pos_minus<=cnt_minus-2 #負の数を2つ取れるなら取る:
cand2=arr_minus[pos_minus]*arr_minus[pos_minus+1]
if cand1>=cand2: #正の数を2つ取った積のほうが大きい場合
pos_plus+=2
ans*=cand1
ans%=mod
else: #負の数を2つ取った積のほうが大きい場合
pos_minus+=2
ans*=cand2
ans%=mod
cnt+=2
print(ans)
exit()
F問題:
まず、あるf(L,R)について連結成分の個数を考えてみます。
すると、f(L,R)に含まれる頂点数は(R-L+1)個であり、両端がLとRの間に含まれるような辺の本数をk本とすると、f(L,R)の連結成分の個数は(頂点数)-(辺の本数)で求められます(∵(R-L+1)個の頂点に辺を張っていくと、辺を1本張るごとに連結成分が1少なくなります)。
ここで、頂点数と辺の本数は独立しているので、sum[L=1 to n]sum[R=L to n](頂点数)とsum[L=1 to n]sum[R=L to n](辺の本数)をそれぞれ求めればよいです。
まず頂点数の総和について、L=1のとき1+2+…+n、L=2のとき1+2+…+n-1、…L=n-1のとき1+2、L=nのとき1となるので、1*n+2*(n-1)+…+(n-1)*2+n*1を求めればよいです。
次に辺の本数の総和について、各辺が何回数えられるかを考えることとすると、辺(u,v)(u<v)を含む最小の区間は[u,v]に等しいことから、1<=L<=uかつv<=R<=nを満たすすべての(L,R)の組について、辺(u,v)がf(L,R)に含まれることになります。
したがって、辺(u,v)は(u-1+1)*(n-v+1)=u*(n-v+1)回数えられることになります。
以上より、まずO(N)で頂点数の総和を求めておき、ついでO(N)でn-1本の辺(ui,vi)についてui*(n-vi+1)を頂点数の総和から引いていくことで、この問題をO(N)で解くことができました。
上記では辺(u,v)についてu<vを仮定していますが、入力では辺(u,v)についてu>vを満たす場合があることに注意します。
サンプルコード(Python):
https://atcoder.jp/contests/abc173/submissions/15025939
n=int(input())
ans=0
for i in range(1,n+1): #頂点数の総和を求める
ans+=i*(n-i+1)
for _ in range(n-1): #各辺についてu*(n-v+1)を頂点数の総和から引く
u,v=map(int,input().split())
if u>v: #上記ではu<vを仮定しているのでu>vのときuとvを入れ替える
u,v=v,u
ans-=u*(n-v+1)
print(ans)
この記事が気に入ったらサポートをしてみませんか？