【AtCoder】ABC177の問題を初心者的書き方で解説する with Python

ここではAtCoderの問題を解説していきます。
AtCoderの解説は基本的にC++が多く、私のような初心者には難しく書かれていたりするため、
A~Cの問題を基本的な書き方で書いていきます。
分かりやすさ重視のため、コードの書き方も長く書いています。
そもそも自分がBeginnerなので、初心者の自分でもわかる必要最低限のスキルを使ってまとめていきたいと思います。

A問題 Don't be late

高橋君は青木君と待ち合わせをしています。
待ち合わせ場所は高橋君の家から $D$ メートル離れた地点であり、待ち合わせの時刻は $T$ 分後です。高橋君は今から家を出発し、分速 $S$ メートルで待ち合わせ場所までまっすぐ移動します。待ち合わせに間に合うでしょうか？
入力は以下の形式で標準入力から与えられる。
$D \hspace{1cm}T \hspace{1cm}S$

小学生の時からお馴染みの公式
(時間) = (距離)÷(速さ)
を使えばいいと思います。すなわち、かかった時間 $\frac{D}{S}$ が目標の時間 $T$ よりも長いか短いかで判断します。

かかった時間がT分以下ならYesを、T分よりも大きいならNoを出力するコードを書けばいいです。

解答は以下の通り。

s = list(map(int, input().split())) 
D = s[0]
T = s[1]
S = s[2]
 
if D/S <= T:
    print("Yes")
else:
    print("No")

B問題 SubString

2つの文字列S, Tが与えられます。Tが Sの部分文字列となるように、Sのいくつかの文字を書き換えます。
少なくとも何文字書き換える必要がありますか？
ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。
入力は以下の形式で標準入力から与えられる。
S
T
Sを書き換える文字数の最小値を出力せよ。

書き換える文字数の最小値は何かという問題は、SとTで最小何文字異なっているか答える問題と同じです。そのため、
①SからT文字分取り出す(この文字列をUとします)
②UとTで何文字異なっているか数える
③各Uに対して異なっている数をリストに数える
④最後にそのリストの最小値を答える
という手順で行います。

問題例に挙げられている
S：cabacc
T：abc
を用いて考えると、
①S：cabaccからTの文字数である3文字分を頭から取り出します。
U：cab
T：abc
②この場合いずれの文字も異なっているため3文字分異なっています。
③リストに3を追加します。
score = [3]

この操作を繰り返していきます。次は1文字分ずらして、
①S：cabaccからTの文字数である3文字分を頭から1文字ずらして取り出します。
U：aba
T：abc
②この場合"ab"の2文字が一致しているため、1文字分異なっています。
③リストに1を追加します。
score = [3,1]

これを繰り返して、最後にリストの最小値を求めればよいです。

S = input()
T = input()

score = []
for i in range(len(S)-len(T)+1):
    U = S[i: i+len(T)]
    cnt = 0
    for j in range(len(T)):
        if U[j] != T[j]:
            cnt = cnt + 1
    score.append(cnt)
print(min(score))

C問題 Sum of product of pairs

$N$ 個の整数 $A_{1},\cdots,A_{N}$ が与えられます。
$1$ $\leq$ $i$ $<$ $j$ $\leq N$ を満たす全ての組 $(i,j)$ についての
$A_{i}\times A_{j}$ の和を $mod(10^{9}+7)$ で求めてください。
入力は以下の形式で標準入力から与えられる。
$N$
$A_{1},\cdots,A_{N}$

問題の答え自体は、以下のコードで行うことが出来ますが、TLEになってしまいます。2重ループが存在することが原因です。

N = int(input())
A = list(map(int, input().split())) 
 
goukei = 0
for i in range(N):
    for j in range(i+1,N):
      goukei = goukei + A[i] * A[j]
k = 10**9 + 7
print(goukei%k)

そのため2重ループをなくすことを目標にコードを書き換えていきましょう。
例えば
$A_{1},A_{2},A_{3},A_{4},A_{5}$
という数値を入力したとき、まず $A_{1}$ に対しては
$A_{2},A_{3},A_{4},A_{5}$
をかけていきます。つまり、
$A_{1}\times A_{2} + A_{1}\times A_{3} + A_{1}\times A_{4} + A_{1}\times A_{5}$
ですが、まとめると
$A_{1}\times (A_{2}+A_{3}+A_{4}+A_{5})$
で表されます。同様に $A_{2}$ に対しては
$A_{2}\times (A_{3}+A_{4}+A_{5})$
を計算していきます。
すなわち、
①リストAの合計値をあらかじめ求める(A[0]+…A[4])
②リストAから最初の値を取り出す(A[0])
③リストAから最初の値を取り除く(A = [A1,…A4])
④①の合計値から取り除いた値を引く
⑤④で得た値と取り出した②で取り出した値をかけて、新しい合計値とする
これを全ての要素に対して行えばよいです。

N = int(input())
A = list(map(int, input().split())) 
 
goukei = 0

sumA = sum(A)
for i in range(N):
    a = A[i]
    sumA = sumA - a
    goukei = goukei + sumA*a

k = 10**9 + 7
print(goukei%k)