【ABC172 A-D解法】累積和と等差数列に気付けるか【python】

AtCoder
この記事は約5分で読めます。

本記事について

AtCoder Beginner Contest 第172回のA~D問題を,Python3で解いてみた.
https://atcoder.jp/contests/abc172

使用したアルゴリズム

  • A問題:特になし
  • B問題:特になし
  • C問題:累積和
  • D問題:等差数列の和

A問題 「Calc」

解法

特に説明もすることはないので省略.

a=int(input())
print(a+a**2+a**3)

B問題 「Minor Change」

解法

文字列の長さが$ 2 \times 10^5 $以下という制約なので,計算量はO(n)で間に合う.

S=str(input())
T=str(input())
ans=0

for i in range(len(S)):
	if S[i]!=T[i]:
		ans+=1
print(ans)

C問題 「Tsundoku」

ダメな例

机A,机B上の冊数が$ 1 \le N \le 2*10^2$.
時間に関する制約($ K,A_i , B_i $)が $ 1 \le N \le 10^9$ である.

そのため,K分を超えないように1冊ずつ選んで足して...という貪欲法でやると時間切れになる.

解法

時間をどんどん足していく.ということは累積和が使えるんじゃないか
この仮説が出てくれば,あとは机Aと机Bにある本を読むのにかかる時間の累積和を求めれば良い.

しかしこれだけでは計算量が0($ N^2 $)なので間に合わない.

ということで,机Aに置かれている本から選んだ数(i=1,2,…,N)毎に,机Bから選べる最大冊数はいくつかを調べれば良い.

解答例は以下の通り.

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n,m,k=input2()
A=input_array()
B=input_array()
acc_A,acc_B=[0],[0] 

for i in range(n): # Aの累積和
	acc_A.append(A[i]+acc_A[i])
for i in range(m): # Bの累積和
	acc_B.append(B[i]+acc_B[i])

ans=0
tmp_m=m
for i in range(n+1):
	if acc_A[i]>k:
		break
	for j in range(tmp_m,-1,-1):
		if acc_B[j]<=k-acc_A[i]:
			ans=max(i+j,ans)
			tmp_m=j #探索開始地点の更新
			break
print(ans)

D問題「Sum of Divisors」

ダメな例

問題を鵜呑みにして,単純に処理すると以下のコードになる

これだと計算量が0($ N \sqrt{N} $)になるのでTLE(時間切れ)になる

n=int(input())

ans=0
for i in range(1,n+1):
	for j in range(1,i+1):
		if i%j==0:
			ans+=i
print(ans)
解法

今回の制約が $ 10^7 $ となっていて,「あれ?O($ N $)でも間に合わないんじゃね?」と思って試しにO($ N $)の適当なプログラムを提出してみたら,なんか通った.ならばこれは計算量がO($ N $)で解けるようになっているということか.

もしN=4のとき,上のダメな例では

  • i=1のとき,[1]
  • i=2のとき,[1,2]
  • i=3のとき,[1,3]
  • i=4のとき,[1,2,4]

という風に列挙する.
列挙するとき,if (i%j==0) という条件文で判定しているが,これは

iがjで割り切れる == iはjの倍数

と考えることができる.

となると,探索順番(iとj)を入れ替えても変わらないじゃないかということで,以下のコードで書ける.

n=int(input())

ans=0
for j in range(1,n+1):
	for i in range(1,n+1):
		if i%j==0:
			ans+=i
print(ans)

まだこのままでは計算量は$ 0(N ^2) $である.
ここでもう一度,N=4のときを考えてみる.

  • j=1のとき,[1,2,3,4]
  • j=2のとき,[2,4]
  • j=3のとき,[3]
  • j=4のとき,[4]

これだと少しわかりにくいので,N=100のときも考えてみる.

  • j=1のとき,[1,2,3,4,…,100]
  • j=2のとき,[2,4,6,8,…,100]
  • j=3のとき,[3,6,9,12,…,99]
  • j=4のとき,[4,8,12,16,…,100]…

見てわかる通り,「等差数列になってるじゃないか!!!
このことに気がつけば,あとは等差数列の和を求めていけば良いだけ.

解答例は以下の通り.

n=int(input())

ans=0
for j in range(1,n+1): # 割る数
	a=j #初項
	d=n//j #項数
	tmp=(a+(a*d))*d//2
	ans+=tmp
	
print(ans)
参考

以下の記事を参考に書かせていただきました.
https://qiita.com/DaikiSuyama/items/ab8d7812e549c2f2e9cf

さいごに

緑レベルの問題って,アルゴリズムの難易度はそうでもないんですけど,それに気付けるかどうかが鍵なんですよね.

これは経験を積んでいくしかないのか.

エンジニアになりたい人へ

現役エンジニアによるオンラインプログラミングスクール【CodeCamp】
現役エンジニアによるオンラインプログラミングスクール【CodeCamp】(無料体験実施中)

コメント

タイトルとURLをコピーしました