AtCoder Beginner Contest 172(ABC172) A～E解説

たのん

AtCoder Beginner Contest 172(ABC172)のA～Eまでの解説です。
コンテスト中はA～CとEを解き(70:50+1WA)、E・Fが難しめだったこともあり初のパフォ1800+を出し最高レートを更新しました(コンテスト後すぐDも解きました)。
問題のアドレスは以下になります↓
https://atcoder.jp/contests/abc172/
公式の解説(Editorial)は以下になります↓
https://img.atcoder.jp/abc172/editorial.pdf

A問題:

与えられた数aについて、a^1+a^2+a^3を計算します。
a^1+a^2+a^3の計算方法については、掛け算を用いてaの2乗・3乗をそれぞれa*a,a*a*aで計算する、言語ごとの累乗を表す演算子や累乗を求める関数を用いて計算する、初項a、公比aの等比数列の和の公式を用いてa*(a^3-1)//(a-1)として計算するなどの方法があります。

B問題:

SとTを一致させるためには、Sのi文字目とTのi文字目が異なるとき、Sのi文字目をTのi文字目に置き換える必要があります。
したがって、for文などを用いてすべてのiについてS[i]!=T[i]となるiの個数を数えることで、求める答えを得ることができます。

C問題:

Aの上からi(0<=i<=N)冊とBの上からj(0<=j<=M)冊を読んだとき、所要時間がK分以下であれば、i+j冊を読めることが分かります。
すなわち、Aの上からi(0<=i<=N)冊を読んだときの所要時間をai、Bの上からj(0<=j<=M)冊を読んだときの所要時間をbjとすると、ai+bj<=Kを満たす(i,j)の組のうちi+jが最大になるものを求めることで、この問題を解くことができます。
ai,bjは、a0=0,a1=a0+A1,a2=a1+A2,…とそれまでの値を保持しながら先頭から順に足し合わせていくことでO(N+M)で求めることができます(これを累積和と呼びます)。

ここで、各iについて、jとしてbj<=K-aiを満たす最大のjを取るのが最善であることは明らかです。
したがって、各iについて最大のjを求める方法を考えます。
これを愚直に求めると、1回あたりO(N)かかり、トータルでO(N^2)となり制限時間に間に合いません。
これを効率よく求める方法としては、まずi=0についてMからスタートしてbj<=K-a0を満たす最大のjを求め、次にi=1について、i=0のときに求めたjからスタートしてbj<=K-a1を満たす最大のjを求め、…とすることで、すべてのiについてトータルO(M)で最大のjを求めることができます(このように、見るべき値が常に一定の方向に変化することを利用して計算量を減らす方法のことを「しゃくとり法」と呼びます)。
これにより、この問題をO(N+M)で解くことができました。

あるいは、各iについてjを2分探索により求めることもでき、この場合の計算量はO(NlogM)となります。

サンプルコード(しゃくとり法):
https://atcoder.jp/contests/abc172/submissions/14784796

n,m,k=map(int,input().split())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
acum1=[0]
for i in range(n): #累積和ai,bjを求める
 acum1.append(acum1[-1]+arr1[i])
acum2=[0]
for i in range(m):
 acum2.append(acum2[-1]+arr2[i])
ans=0
j=m
for i in range(n+1):
 if acum1[i]>k: #ai>Kであれば、どのようにjを選んでもai+bj<=Kとなることはないので探索を終了する
   break
 while acum2[j]>k-acum1[i] and j>0: #各iについて、bj<=K-aiを満たす最大のjを求める
   j-=1
 ans=max(ans,i+j)
print(ans)

サンプルコード(2分探索):
https://atcoder.jp/contests/abc172/submissions/14784546

import bisect

n,m,k=map(int,input().split())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
acum1=[0]
for i in range(n): #累積和を求める
 acum1.append(acum1[-1]+arr1[i])
acum2=[0]
for i in range(m):
 acum2.append(acum2[-1]+arr2[i])
ans=0
for i in range(n+1):
 if acum1[i]>k:
   break
 j=bisect.bisect_right(acum2,k-acum1[i])-1 #2分探索によりbj<=K-aiを満たす最大のjを求める
 ans=max(ans,i+j)
print(ans)

D問題:

ABC170のD問題でエラトステネスの篩を用いる問題が出たこともあり、この問題を見たときにエラトステネスの篩が脳裏をよぎった方も多いのではないでしょうか。
この問題について、sum[K=1 to N]K*f(K)の中身をどのように見るかによって様々な解法があるのでそれらを順に紹介します。

まず、もっとも単純な発想として、すべてのKについて高速に素因数分解を行うことができれば、f(K)を(Kの素因数の個数)回の計算で求めることができ、この問題を解けそうだということが分かります。
すべてのKについて高速に素因数分解を行う方法として、エラトステネスの篩を拡張し、あるKが含む素因数のうち最大のものを求めておき、これを用いてKの素因数分解を行うというものがあります。
これは、エラトステネスの篩において、各数を見たかどうかを2値で持つ代わりに、その数が含む素因数のうち最大のものを持つようにすることで実現できます。
エラトステネスの篩の前計算がO(NloglogN)、すべてのKについて素因数分解を行い答えを求めるのにO(NlogN)となり、この問題をO(NlogN)で解くことができます(ただし定数倍がかなり重いです)。

次に、1～Nまでの素数pが、K*f(K)にどのように寄与するかについて考えてみます。
ここで、Kを素因数分解したときの形をp1^e1*p2^e2*…*pk^ekとすると、K*f(K)=p1^e1*p2^e2*…*pk^ek*(e1+1)*(e2+1)*…*(ek+1)=(e1+1)*p1^e1*(e2+2)*p2^e2*…*(ek+1)*pk^ekとなるので、素数pごとに指数eを求め、それらを掛け合わせていくことですべてのK*f(K)の値を求められることが分かります。
したがって、1～Nまでのすべての素数pについて、その倍数kを列挙し、その倍数に含まれるpの個数をeとしたとき、t[k]*=p^e*(e+1)と更新すると、sum(t)が答えに等しくなります。
この計算量はO(MlogMlogM)(Mは1～Nまでの素数の個数)で、素数定理よりM≒N/logNと近似できるので、これをO(MlogMlogM)に代入することでO(NlogN)程度で動作することが分かります。

また、f(K)は1～Kまでの数のうちKを割り切るものの個数であり、これを逆に見ると、1～Nまでのそれぞれの数kについて、f(kの倍数)+=1と更新することで、すべてのKについてf(K)を求めることができます。
この計算量は調和級数により近似することでO(NlogN)であることが分かり、この問題を解くことができます。

この解法からさらに考察を進めると、すべてのkについて、kの倍数をそれぞれ答えに足し合わせればよいことが分かる(∵上記より、各kについてkの倍数が1回答えに足し合わされます)ので、結局(N以下のすべてのkの倍数の総和)*kを足し合わせることでこの問題を解けることが分かります(Editorialで述べられている解法になります)。
これは上記と同様にしてO(NlogN)で求めることができますが、(N以下のすべてのkの倍数の総和)はkでくくることにより、k*(1～floor(N/k)までの総和)で求めることができるので、結局この問題をO(N)で解くことができました。

さらに、この問題はa*b<=Nを満たすすべての(a,b)の組についてa*bを足し合わせる問題であるというふうに読み替えることができ、このとき、min(a,b)<=sqrt(N)が成り立つ(∵min(a,b)>sqrt(N)のときa*b>Nとなり制約に反します)ことから、1～sqrt(N)までのすべてのkについて、k<=b<=N//kを満たすすべてのbの総和*2-kを求めればよいです。
これは等差数列の和の公式を用いてO(1)で求められるので、この問題をO(sqrt(N))で解くことができました(半分全列挙に近い考え方になります)。

サンプルコード(エラトステネスの篩を用いてO(NlogN)でf(K)を求める方法):
https://atcoder.jp/contests/abc172/submissions/14799167

def calc():
 n=int(input())
 table=[i for i in range(n+1)]
 for i in range(2,n+1):
   if table[i]<i: #iに含まれる最大の素因数がi未満のとき、処理をスキップする(これによりすべての素数についてのみ処理を行うことができる)
     continue
   for j in range(i,n+1,i): #iの倍数について、iの倍数に含まれる最大の素因数をiに更新する
     table[j]=i
 ans=0
 for i in range(1,n+1):
   cnt={}
   ret=i
   while i!=1:
     prime=table[i]
     if prime in cnt: #iに含まれる最大の素因数を追加する
       cnt[prime]+=1
     else:
       cnt[prime]=1
     i//=prime #iを最大の素因数で割る
   for val in cnt.values(): #(各素因数の個数+1)を掛け合わせたものがf(K)に等しい
     ret*=val+1
   ans+=ret
 print(ans)
calc()

サンプルコード(各素因数のK*f(K)への影響をO(MlogMlogM)で求める方法):
https://atcoder.jp/contests/abc172/submissions/14777477

import sys
input=sys.stdin.readline

def calc():
 n=int(input())
 table=[1]*(n+1) #各KごとのK*f(K)の値
 check=[False]*(n+1) #各iが素数であるかどうかを判定する
 for i in range(2,n+1):
   if check[i]==True: #iが素数でなければ処理を行わない
     continue
   check[i]=True
   for j in range(1,n//i+1):
     check[i*j]=True #i*jは素数ではない
     tmp=j
     cnt=1
     while tmp%i==0:
       tmp//=i
       cnt+=1
     table[i*j]*=(i**cnt)*(cnt+1) #各k(=i*j)ごとに素数iの指数cntを求めて掛け合わせる
 print(sum(table)-1)
calc()

サンプルコード(f(K)をO(NlogN)で求める方法):
https://atcoder.jp/contests/abc172/submissions/14785879

import sys
input=sys.stdin.readline

def calc():
 n=int(input())
 table=[0]*(n+1)
 for i in range(1,n+1): #各iについて、iの倍数の約数の個数table[i*j]を1増やす
   for j in range(i,n+1,i):
     table[j]+=1
 ans=0
 for i in range(1,n+1):
   ans+=i*table[i] #すべてのKについてf(K)を求められたので答えを計算する
 print(ans)
calc()

サンプルコード(上記を等差数列の和の公式によりO(N)に高速化したもの):
https://atcoder.jp/contests/abc172/submissions/14785962

n=int(input())
ans=0
for i in range(1,n+1): #各iについて、i*(1～n//iまでの総和)を足し合わせればよい
 k=n//i
 ans+=i*(k*(k+1)//2)
print(ans)

サンプルコード(上記を半分全列挙によりO(sqrt(N))に高速化したもの):
https://atcoder.jp/contests/abc172/submissions/14799773

n=int(input())
ans=0
for i in range(1,int(n**0.5)+1):
 sums=((n//i)*(n//i+1))//2-(i*(i-1))//2
 ans+=2*sums*i-i*i #各iについて、i*(i<=b<=n//iを満たすbの総和*2-i)を答えに足し合わせる
print(ans)

E問題:

問題文の条件のうち、任意のiについてAi!=Biを満たすことを条件1、任意のi,jについてAi!=AjかつBi!=Bjを満たすことを条件2と呼ぶことにします。
条件2を整理すると、数列A,Bとして条件2を満たすものは、1～Mまでの数から重複しないようにN個を選び、それらを好きな順に並び替えたものに等しいことが分かります。
このことから、まず条件2を満たす数列Aの個数がmCn*n!で求められることが分かります。
したがって、条件2を満たすある数列Aに対して、条件2を満たす数列Bのうち条件1を満たすものの場合の数を求めることができれば、(mCn*n!)*(求めた場合の数)として答えを求めることができます。

ここで、条件2を満たす数列Bは、上記と同様にしてmCn*n!で求められ、これは数列Aと0個以上等しい要素がある数列の場合の数となります。
いま求めたいのは数列Aと1つも等しい要素を持たない数列Bの個数、すなわち0個等しい要素がある場合の数なので、包除原理により、等しい要素が偶数個のとき場合の数を足し、奇数個のとき場合の数を引くことで、求める場合の数を得ることができます。
等しい要素がk個あるときの場合の数は、(N個の要素から等しい要素をk個選ぶ場合の数)*(M-k個からN-k個の要素を選ぶ場合の数)*(N-k個の要素を好きな順番に並べる場合の数)として求めることができ、階乗とその逆元を前計算しておくことにより、この問題をO(NlogN)で解くことができました。

サンプルコード(Python):
https://atcoder.jp/contests/abc172/submissions/14786609

mod=10**9+7
fact=[1]
for i in range(1,5*10**5+1): #階乗とその逆元を前計算する
 fact.append((fact[-1]*i)%mod)
revfact=[1]
for i in range(1,5*10**5+1):
 revfact.append(pow(fact[i],mod-2,mod))
n,m=map(int,input().split())
patternA=(fact[m]*revfact[n]*revfact[m-n]*fact[n])%mod #数列Aの場合の数はmCn*n!
patternB=0
for i in range(n+1): #ある数列Aに対する数列Bの場合の数を包除原理により求める
 tmp=(fact[n]*revfact[i]*revfact[n-i])*(fact[m-i]*revfact[n-i]*revfact[m-n])*fact[n-i] #ある数列Aとi個以上要素が等しい数列Bの場合の数を求める
 if i%2==0:
   patternB+=tmp
   patternB%=mod
 else:
   patternB-=tmp
   patternB%=mod
print((patternA*patternB)%mod) #(数列Aの場合の数)*(数列Bの場合の数)が答えとなる

この記事が気に入ったらサポートをしてみませんか？