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