AtCoder Beginner Contest 169(ABC169) A〜F解説
AtCoder Beginner Contest 169(ABC169)のA～Fまでの解説です。
コンテスト中はA～Eまでを解き(76:20+6WA)、E・Fが易しめの回だったこともあり水パフォでレート微減でした。
問題のアドレスは以下になります↓
https://atcoder.jp/contests/abc169/
公式の解説(Editorial)は以下になります↓
https://img.atcoder.jp/abc169/editorial.pdf
A問題:
問題文の通り、A*Bを出力すればよいです。
B問題:
まず、明らかに値が0の要素を含む場合は0を出力すればよいです。
多倍長整数をサポートしている言語であれば、0を1つも含まない場合、先頭から値を順次掛けていき、積が10^18を超えたら-1を出力して打ち切り、最後の要素まで積を求めたとき10^18を超えていなければその値を出力すればよいです。
ただし、多倍長整数をサポートしていない言語では、ある要素までの積が10^18を超えたときにオーバーフローする可能性があるので、代わりに、k-1番目までのすべての要素の積が10^18/(k番目の要素の値)を超えたかどうかで判定を行うとよいです。
0があるかの場合分けが面倒な場合は、まず配列を昇順にソートしておくと場合分けをせずに解くことができます。
配列をソートせずに解く場合はO(N)、ソートを用いる場合はO(NlogN)でこの問題を解くことができました。
サンプルコード(Python):
https://atcoder.jp/contests/abc169/submissions/13785869
n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr) #配列を昇順ソートしておく(配列に0がある場合0が先頭に来るので、場合分けの必要がなくなる)
ans=1
for val in arr:
ans*=val #Pythonは多倍長整数をサポートしているので単に積を求めれば十分
if ans>10**18:
print(-1)
break
else:
print(ans)
C問題:
Bを受け取る際、例えばB=0.1とすると2進数では正確に表現できず誤差が生じる可能性があります。
また、最終的な答えを小数として求め、その後小数点以下を切り捨てる、という風に計算すると誤差が生じる可能性があります。
そのため、まずBを100倍して整数に直してから、積を計算して最後に100で割ることで、整数の範囲で誤差なく計算を行うことができます。
具体的な実装としては、まずBを文字列として受け取り、1文字目の値を100倍、3文字目の値を10倍、4文字目の値を1倍した値を足し合わせ、B*100を求めます。
あとは(A*B)/100を計算すれば誤差なく計算を行うことができます。
(PythonであればDecimalモジュールを用いることで無理やり求めることもできます)
サンプルコード(Python)(Bを整数に変換する方法):
https://atcoder.jp/contests/abc169/submissions/13809974
a,b=map(str,input().split())
a=int(a)
b=100*int(b[0])+10*int(b[2])+1*int(b[3]) #bを100倍した値(整数)に直す
print((a*b)//100)サンプルコード(Python)(Decimalモジュールを用いる方法):
https://atcoder.jp/contests/abc169/submissions/13918164
import decimal
a,b=input().split()
a=decimal.Decimal(a)
b=decimal.Decimal(b)
print(int(a*b))
D問題:
まず、明らかにNの素因数ごとに操作を行うほうがよいことが分かるので、Nの素因数とその指数を求めます(例えば試し割り法を行うことでO(sqrt(N))でNの素因数とその指数を求められます)。
ある素因数pの累乗でNを割るとき、すでに使った数は使えないことから、p^1,p^2,p^3,…と順に割っていくのが最善であることが分かります。
これから、各素因数pの指数について、k(k+1)//2<(pの指数)を満たす最大のkを求め、それらを足し合わせることで答えを求めることができます。
N<=10^12より、素因数の指数は高々40以下であり、上記の不等式を満たすkは高々6以下であることが分かるので、各素因数の指数について、kを全探索すれば十分です(2分探索をする必要はありません)。
Nの素因数を求める部分がネックとなり、以上によりこの問題をO(sqrt(N))で解くことができました。
サンプルコード(Python):
https://atcoder.jp/contests/abc169/submissions/13797820
import collections
def primes(n): #試し割り法で各素因数とその指数を求める
cnt=collections.defaultdict(int)
for i in range(2,int(n**0.5)+1):
if n%i==0:
while n%i==0:
cnt[i]+=1
n//=i
if n!=1:
cnt[n]+=1
return cnt
n=int(input())
cnt=primes(n)
ans=0
for key in cnt.keys():
val=cnt[key]
for i in range(100): #各素因数の指数について、k(k+1)//2<=(指数)を満たす最大のkを求める
if (i*(i+1))//2>val:
ans+=i-1
break
print(ans)
E問題:
この問題の条件では、直感的に、中央値は中央値の下限と中央値の上限の間のすべての値を取ると予想できます。
以下でこのことを示します。
まずNが奇数であると仮定し、中央値((N+1)/2番目の値)が中央値の下限である状態からスタートします。
まず、要素の値が中央値の下限未満であるすべての要素について、可能な限り中央値の下限に近付けます。
この操作の対象になる要素はN/2個以下なので、この操作で中央値が変化することはありません。
この操作の後、中央値の下限に等しい要素を1増加させていくと、中央値が中央値の下限+1に変化します(下限と上限が等しい場合を除きます)。
この操作は中央値が上限に一致するまで繰り返すことができるので、中央値が下限から上限までのすべての値を取ることが示せました。Nが偶数の場合もほとんど同様に示すことができ、N/2番目の要素とN/2+1番目の要素が下限の状態からスタートし、まずN/2番目の要素の値未満であるすべての要素について可能な限りN/2番目の要素の値に近付け、ついでN/2番目の要素の値に等しい要素をN/2+1番目の要素の値に近付け、N/2+1番目の要素の値を1増加させ…という操作を、N/2番目の要素とN/2+1番目の要素が上限に到達するまで繰り返すことができるので、中央値が(N/2番目の要素の下限+N/2+1番目の要素の下限)/2から(N/2番目の要素の上限+N/2+1番目の要素の上限)/2までのすべての値を取ることが示せました。
以上より、Nが奇数の場合は(N+1)/2番目の値の下限と上限を、Nが偶数の場合はN/2番目の値とN/2+1番目の値の下限と上限をそれぞれ求めることで、この問題を解くことができます。
これは愚直に2分探索することによって求めることができます。
具体的には、中央値として定めた値について、中央値<Aiを満たすiの個数と、Bi<中央値を満たすiの個数をそれぞれ求めると、それぞれの個数が一定値より大きいと、定めた値が中央値の場所からはみ出てしまうので、その値は中央値になり得ません。中央値<Aiを満たすiの個数が一定値より大きい場合は値が小さすぎるので区間の左側を狭め、Bi<中央値を満たすiの個数が一定値より大きい場合は値が大きすぎるので区間の右側を狭めればよいです。
一定値以下の場合は、下限を求める場合は区間の右側を、上限を求める場合は区間の左側を狭めればよいです。
以上の2分探索により、求める下限、上限をO(NlogN)で得ることができます。
あるいは、考察を進めると、中央値の下限は{Ai}の中央値に等しく、中央値の上限は{Bi}の中央値に等しいことが分かります(∵{Ai}の中央値より小さい値を取ると、この値より大きい値の要素がN/2個以上存在することが明らかで、上記の2分探索の方法からこのときこの値が中央値になることはあり得ません)。
よって、{Ai}と{Bi}を昇順にソートすることで、2分探索せずに(N+1)/2番目の下限と上限、あるいはN/2番目とN/2+1番目の下限と上限をそれぞれ求めることができます(公式のEditorialで述べられている解法です)。
こちらの方法でも求める下限、上限をO(NlogN)で得ることができます。
Nが奇数の場合は(N+1)/2番目の上限-下限+1が、Nが偶数の場合は(N/2番目の上限+N/2+1番目の上限)-(N/2番目の下限+N/2+1番目の下限)+1がそれぞれ求める答えに等しくなります。
サンプルコード(Python)(2分探索で下限と上限を求める方法):
https://atcoder.jp/contests/abc169/submissions/13866481
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
if n%2==0: #Nが偶数の場合、N/2番目の要素の下限と上限、N/2+1番目の要素の下限と上限をそれぞれ求める
l=0
r=10**9+1
while r-l!=1: #N/2番目の要素の上限を求める
mid=(l+r)//2
cnt1=0
cnt2=0
cnt3=0
for a,b in arr:
if mid<a:
cnt1+=1
elif mid>b:
cnt2+=1
else:
cnt3+=1
if cnt1>n//2:
l=mid
elif cnt2>n//2-1:
r=mid
else:
l=mid
r1=l
l=0
r=r1+1
while r-l!=1: #N/2番目の要素の下限を求める
mid=(l+r)//2
cnt1=0
cnt2=0
cnt3=0
for a,b in arr:
if mid<a:
cnt1+=1
elif mid>b:
cnt2+=1
else:
cnt3+=1
if cnt1>n//2:
l=mid
elif cnt2>n//2-1:
r=mid
else:
r=mid
l1=r
l=0
r=10**9+1
while r-l!=1: #N/2+1番目の要素の上限を求める
mid=(l+r)//2
cnt1=0
cnt2=0
cnt3=0
for a,b in arr:
if mid<a:
cnt1+=1
elif mid>b:
cnt2+=1
else:
cnt3+=1
if cnt1>n//2-1:
l=mid
elif cnt2>n//2:
r=mid
else:
l=mid
r2=l
l=0
r=r2+1
while r-l!=1: #N/2+1番目の要素の下限を求める
mid=(l+r)//2
cnt1=0
cnt2=0
cnt3=0
for a,b in arr:
if mid<a:
cnt1+=1
elif mid>b:
cnt2+=1
else:
cnt3+=1
if cnt1>n//2-1:
l=mid
elif cnt2>n//2:
r=mid
else:
r=mid
l2=r
print((r1+r2)-(l1+l2)+1) #答えは(各要素の上限の和)-(各要素の下限の和)+1に等しい
elif n%2==1: #Nが奇数のとき、中央値の下限と上限を求める
l=0
r=10**9+1
while r-l!=1: #中央値の上限を求める
mid=(l+r)//2
cnt1=0
cnt2=0
cnt3=0
for a,b in arr:
if mid<a:
cnt1+=1
elif mid>b:
cnt2+=1
else:
cnt3+=1
if cnt1>n//2:
l=mid
elif cnt2>n//2:
r=mid
else:
l=mid
l1=l
r1=r
l=0
r=l1+1
while r-l!=1: #中央値の下限を求める
mid=(l+r)//2
cnt1=0
cnt2=0
cnt3=0
for a,b in arr:
if mid<a:
cnt1+=1
elif mid>b:
cnt2+=1
else:
cnt3+=1
if cnt1>n//2:
l=mid
elif cnt2>n//2:
r=mid
else:
r=mid
l2=l
r2=r
print(l1-r2+1) #答えは(中央値の上限)-(中央値の下限)+1に等しいサンプルコード(Python)(AとBをソートして下限と上限を求める方法):
https://atcoder.jp/contests/abc169/submissions/13921004
n=int(input())
arr1=[]
arr2=[]
for _ in range(n):
a,b=map(int,input().split())
arr1.append(a)
arr2.append(b)
arr1=sorted(arr1) #{Ai}を昇順ソートすると下限が分かる
arr2=sorted(arr2) #{Bi}を昇順ソートすると上限が分かる
if n%2==1: #Nが奇数の場合と偶数の場合に、それぞれ下限と上限を求める
l=arr1[n//2]
r=arr2[n//2]
else:
l=arr1[n//2-1]+arr1[n//2]
r=arr2[n//2-1]+arr2[n//2]
print(r-l+1) #上限-下限+1が答えに等しい
F問題:
あるk個の要素の和がSになるような組を考えると、その組を含むすべての集合が条件を満たすことから、その組は(あるk個の要素の和がSになるような組の個数)*2^(N-k)回だけf(T)の総和に現れることになります。
これをDPで求めることを考えると、DP[i][j][k](i:i番目の要素まで見ている、j:j個取っている、k:i番目の要素まで見てあるj個の要素を選んだとき総和がkである)を定め、初期値としてDP[0][0][0]=1をおくと、DP[i][j][k]=DP[i-1][j][k]、k-a(i-1)>=0かつDP[i-1][j-1][k-ai]!=0のときDP[i][j][k]+=DP[i-1][j-1][k-a(i-1)]と更新することで、DP[N][k][S]に、あるk個の要素の和がSになるような組の個数が入ることになります。
あとは、各kについてDP[N][k][S]*2^(N-k)を求めて足し合わせることで、答えをO(N^2S)で求めることができます。
制約よりこれは制限時間に間に合わないので、計算量を改善する方法を考えます。
O(NS)にできれば制限時間に間に合うので、Nを1つ減らす方法を考えます。
ここで、上記のDPがO(N^2S)となるのはk個の要素を取っていることをパラメータとして持っているからで、もしこのパラメータを除くことができれば、DPの計算量をO(NS)とすることができます。
i番目の要素まで見たときを考えると、i番目の要素までを用いたある集合について、i+1番目の要素を付け加えるかどうかの選択肢があります。
すなわち、上記のDPの更新において、DP[i][j][k]=DP[i-1][j][k]とする代わりに、DP[i][j][k]=2*DP[i-1][j][k]とすることで、k個の要素を取っていることをパラメータとして持つ必要がなくなります(∵最後の計算の2^(N-k)の部分をDP遷移に埋め込むことができます)。
以上により、DPをDP[i][j](i:i番目の要素まで見ている、j:i番目の要素まで見て総和がjである)を定め、初期値としてDP[0][0]=1をおき、DP[i][j]=2*DP[i-1][j]、j-a(i-1)>=0かつDP[i-1][j-ai]!=0のときDP[i][j]+=DP[i-1][k-a(i-1)]と更新することで、DP[N][S]に求める答えが入ることになります。
これにより、k個の要素を取っているというパラメータを除くことができたので、DPをO(NS)で計算することができ、この問題を解くことができました。
あるいは、(2+x^a1)(2+x^a2)…(2+x^an)を計算し、x^Sの係数を求めることでもこの問題を解くことができます(多項式の積を用いた数え上げという考え方です、詳しくはhttps://maspypy.com/%e5%a4%9a%e9%a0%85%e5%bc%8f%e3%83%bb%e5%bd%a2%e5%bc%8f%e7%9a%84%e3%81%b9%e3%81%8d%e7%b4%9a%e6%95%b0%e6%95%b0%e3%81%88%e4%b8%8a%e3%81%92%e3%81%a8%e3%81%ae%e5%af%be%e5%bf%9c%e4%bb%98%e3%81%91を参照してください)。
具体的には、(i番目の要素までの多項式の積)*(2+x^a(i+1))を展開すると2*(i番目の要素までの多項式の積)+x^a(i+1)*(i番目の要素までの多項式の積)となり、上記のDPの更新と同じ式が得られます。
またこの解法は上記のDPの更新の妥当性を与えています。
x^Sの係数は、x^(S+1)以上の係数を無視してよいことから上記のDPと同様にO(NS)で計算することができ、この問題を解くことができます。
サンプルコード(Python):
https://atcoder.jp/contests/abc169/submissions/13903188
mod=998244353
n,s=map(int,input().split())
arr=list(map(int,input().split()))
dp=[[0]*(s+1) for _ in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
val=arr[i-1]
for j in range(s,-1,-1):
dp[i][j]=2*dp[i-1][j] #すでに求めた項に2を掛ける
dp[i][j]%=mod
if j-val>=0 and dp[i-1][j-val]!=0: #j+ai<=Sとなるような項について、jの個数を足し合わせる
dp[i][j]+=dp[i-1][j-val]
dp[i][j]%=mod
print(dp[n][s])
この記事が気に入ったらサポートをしてみませんか？