エイシング プログラミング コンテスト 2020 A～E解説
エイシング プログラミング コンテスト 2020のA～Eまでの解説です。
コンテスト中はA～Dを解き(55:59+1WA)、DでもったいないミスをしたもののE・Fが難しかったこともあり、ぎりぎり青パフォを取ることができました。
問題のアドレスは以下になります↓
https://atcoder.jp/contests/aising2020
公式の解説(Editorial)は以下になります↓
https://img.atcoder.jp/aising2020/editorial.pdf
A問題:
1～Nまでの間に含まれるdの倍数の個数は、N//dで求めることができます。
したがって、L～Rまでの間に含まれるdの倍数の個数は、(1～Rまでの間に含まれるdの倍数の個数)-(1～L-1までの間に含まれるdの倍数の個数)、すなわち、R//d-(L-1)//dにより求めることができます(倍数の個数の求め方を予備知識として持っている必要があるため、A問題としては少し難しめの印象でした)。
B問題:
問題文のとおり、条件を満たす要素の個数を数えればよいです。
問題文では数列の番号が1から始まっている一方、一般的なプログラミング言語では配列の添え字が0から始まることに注意してください。
C問題:
各Nについてf(N)を求めようとすると、各NごとにO(sqrt(N)^2)回の操作が必要となり間に合いません。
ここで、可能なx,y,zの範囲はそれぞれ1<=x,y,z<=sqrt(N)であることから、すべてのx,y,zについて、x^2+y^2+z^2+xy+yz+zxを求めることを考えます。
すると、すべてのx,y,zについてx^2+y^2+z^2+xy+yz+zxの値を求めることはO(sqrt(N)^3)で可能なので、O(sqrt(N)^3)でx^2+y^2+z^2+xy+yz+zxの値の個数を数えることで、この問題をO(sqrt(N)^3)で解くことができました。
サンプルコード(Python):
https://atcoder.jp/contests/aising2020/submissions/15160000
#!/usr/bin/env python3
import collections
import sys
input=sys.stdin.readline
n=int(input())
ans=[0]*n
tmp=[]
for x in range(1,int(n**0.5)+1): #可能なすべてのx,y,zについてx^2+y^2+z^2+xy+yz+zxの値を求める
for y in range(1,int(n**0.5)+1):
for z in range(1,int(n**0.5)+1):
tmp.append(x**2+y**2+z**2+x*y+y*z+z*x)
cnt=collections.Counter(tmp) #x^2+y^2+z^2+xy+yz+zxの値の個数を数える
for i in range(1,n+1): #各iについて、x^2+y^2+z^2+xy+yz+zxの値がiであるものの個数が答えとなる
print(cnt[i])D問題:
Xは非常に大きな値になるので、単純にシミュレートすることはできません。
ここで、Xのpopcountは高々Nであることから、Xをpopcountで割った値は必ずN未満となります。
また、Xiを反転させたとき、そのような整数のpopcountは(Xのpopcount±1)に等しいです。
したがって、まず1～Nまでのすべての数について、それらをpopcountで割ったあまりに置き換えて0になるまでの操作回数を求めておき、次に、Xi=1であるような各桁について、(Xのpopcount+1)で割ったあまりの総和と(Xのpopcount-1)で割ったあまりの総和を求めておくと、f(Xi)を、Xiが1であれば、(Xのpopcount-1)で割ったあまりの総和-2^iを(Xのpopcount-1)で割ったあまりを求め、これを(Xのpopcount-1)で割ることで、N未満の数を得ることができ、同様に、Xiが0であれば、(Xのpopcount+1)で割ったあまりの総和+2^iを(Xのpopcount+1)で割ったあまりを求め、これを(Xのpopcount+1)で割ることで、N未満の数を得ることができます。
以上より、各Xiについて、0になるまでに必要な操作回数をO(1)で判定できることが分かりました。
ここで、1～Nまでのすべての数について操作回数を求めるための計算量について2*10^5以下の数のpopcountは高々18、18以下の数のpopcountは高々4、4以下の数のpopcountは高々2、2以下の数のpopcountは高々1であり、最大でも5回の操作で0に到達することが分かります。
したがって、O(NlogN)により、1～Nまでのすべての数について操作回数を求めることができることがいえ、この問題をO(NlogN)で解けることが分かりました。
ただし、Xのpopcountが0または1のケースに注意してください。
サンプルコード(Python):
https://atcoder.jp/contests/aising2020/submissions/15169814
#!/usr/bin/env python3
import sys
input=sys.stdin.readline
LEN=2*10**5+10
moves=[0]*LEN
for i in range(1,LEN): #1～Nまでのすべての数について、0になるまでの操作回数を求める
tmp=i
cnt=0
while tmp!=0:
popcount=0
for j in range(20):
if tmp&(1<<j):
popcount+=1
tmp%=popcount
cnt+=1
moves[i]=cnt
n=int(input())
x=input()
k=x.count('1') #Xのpopcountを求める
if k==0: #Xのpopcountが0のとき、答えは必ず0
for i in range(n):
print(1)
elif k==1: #Xのpopcountが1のとき、popcount-1=0となり0除算が起こるので、別途処理が必要
pos=x.index('1') #Xi=1となるiを求める
for i in range(n):
if i==pos: #Xi=1を反転させるとき、操作回数は0
print(0)
else:
if pos==n-1: #Xi=1となるiが末尾のビットのとき、Xを2で割ったあまりが1となるので操作回数は2
print(2)
else:
if i==n-1: #Xi=1となるiが末尾のビットでないとき、末尾のビットを反転させるときは操作回数が2、それ以外のときは1となる
print(2)
else:
print(1)
else:
sum1=0 #(Xのpopcount+1)で割ったあまりの総和
sum2=0 #(Xのpopcount-1)で割ったあまりの総和
tmp1=1
tmp2=1
for i in range(n-1,-1,-1): #(Xのpopcount+1)で割ったあまりの総和と(Xのpopcount-1)で割ったあまりの総和をそれぞれ求める
if x[i]=='1':
sum1+=tmp1
sum1%=k+1
sum2+=tmp2
sum2%=k-1
tmp1*=2
tmp1%=k+1
tmp2*=2
tmp2%=k-1
for i in range(n):
if x[i]=='0': #Xi=0であれば、そのbitに対応する2の累乗を(Xのpopcount+1)で割ったあまりを総和に加え、これを(Xのpopcount+1)で割ることで、事前に計算した値を用いて操作回数をO(1)で得られる
tmp=sum1+pow(2,n-i-1,k+1)
tmp%=k+1
print(moves[tmp]+1)
else: #Xi=1であれば、総和から2の累乗を引く操作を、(Xのpopcount-1)として行うことで操作回数をO(1)で得られる
tmp=sum2-pow(2,n-i-1,k-1)
tmp%=k-1
print(moves[tmp]+1)E問題:
まず、ラクダをL>=Rを満たすものとL<Rを満たすものの2組に分けて考えることとします。
すると、ラクダの並び順は、必ず(L>=Rのラクダで先頭からKi番目にいるもの)→(L>=Rのラクダで先頭からKi番目にいないもの)→(L<Rのラクダで先頭からKi番目にいるもの)→(L<Rのラクダで先頭からKi番目にいないもの)の順で表せることが分かります。
ここで、(L>=Rのラクダで先頭からKi番目にいるもの)の総和と、(L<Rのラクダで先頭からKi番目にいないもの)の総和を最大にすることを考えます。
L>=Rのラクダで先頭からKi番目にいるものについて、i=1,2,…,Nと見ていくと、i番目において、先頭からi番目以内にはi頭までのラクダしか置くことができません。
したがって、例えば優先度付きキューによりL-Rの小さい順にラクダを管理し、k番目ではKi=kなるすべてのラクダを追加し、優先度付きキューの長さがkになるまで小さいほうから要素を捨てる、という操作を繰り返すことで、最終的に(L>=Rのラクダで先頭からKi番目にいるもの)の総和を最大化することができます。
同様にして、L<Rのラクダで先頭からKi番目にいないものについても、i=N,N-1,…,1と見ていき、i番目において、末尾からi番目以内にはN-i頭までのラクダしか置くことができないことから、先頭の場合と同様に優先度付きキューを用いることで、(L<Rのラクダで先頭からKi番目にいないもの)の総和を最大化することができます。
以上の操作において、先頭の優先度付きキューの中に残ったすべてのラクダはLを取り、残らなかったラクダはRを取ることになります。
同様に、末尾の優先度付きキューの中に残ったすべてのラクダはRを取り、残らなかったラクダはLを取ることになります。
これにより実現できる最大値を求められるので、以上によりこの問題をO(NlogN)で解くことができました。
サンプルコード(Python):
https://atcoder.jp/contests/aising2020/submissions/15187053
#!/usr/bin/env python3
import heapq
import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
q=[]
ans=0
camels1=[[] for _ in range(n+1)]
camels2=[[] for _ in range(n+1)]
for k,l,r in arr: #Ki=kであるL>=Rのラクダの組とL<Rのラクダの組を作る
if l>=r:
camels1[k].append((l,r))
else:
camels2[k].append((l,r))
for i in range(1,n+1): #先頭から見ていき、L-Rの値が大きいラクダが残るように操作を行う
for l,r in camels1[i]:
heapq.heappush(q,(l-r,l,r))
while len(q)>i: #優先度付きキューから除かれるラクダはRを取ることになる
_,_,r=heapq.heappop(q)
ans+=r
while len(q)!=0: #優先度付きキューに残ったラクダはLを取ることができる
_,l,_=heapq.heappop(q)
ans+=l
for i in range(n,0,-1): #末尾から見ていき、R-Lの値が大きいラクダが残るように操作を行う
for l,r in camels2[i]:
heapq.heappush(q,(r-l,l,r))
while len(q)>(n-i): #優先度付きキューから除かれるラクダはLを取ることになる
_,l,_=heapq.heappop(q)
ans+=l
while len(q)!=0: #優先度付きキューに残ったラクダはRを取ることができる
_,_,r=heapq.heappop(q)
ans+=r
print(ans) #上記の操作によって定めた順番が最大値を与えるこの記事が気に入ったらサポートをしてみませんか？