本記事について
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
さいごに
緑レベルの問題って，アルゴリズムの難易度はそうでもないんですけど，それに気付けるかどうかが鍵なんですよね．
これは経験を積んでいくしかないのか．
コメント