AtCoder ABC177
2020-08-29(土)に行われたAtCoderBeginnerContest177の問題をA問題から順に考察も踏まえてまとめたものとなります．
前半ではABCまでの問題を扱います．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF
A問題 Don't be late
問題文
高橋君は青木君と待ち合わせをしています。
待ち合わせ場所は高橋君の家から$D$メートル離れた地点であり、待ち合わせの時刻は$T$分後です。
高橋君は今から家を出発し、分速$S$メートルで待ち合わせ場所までまっすぐ移動します。
待ち合わせに間に合うでしょうか？
d, t, s = map(int, input().split())
if d <= t * s:
print("Yes")
else:
print("No")
B問題 Substring
問題文
$2$つの文字列$S, T$が与えられます。
$T$が$S$の部分文字列となるように、$S$のいくつかの文字を書き換えます。
少なくとも何文字書き換える必要がありますか？
ただし、部分文字列とは連続する部分列のことを指します。例えば、'xxx' は 'yxxxy' の部分文字列ですが、'xxyxx' の部分文字列ではありません。
$S,T$は$1$文字以上$1000$文字以下なので，全部の可能性を時間内に計算することができます．
例えば，7文字の'abcdefg'と3文字の'efh'を考えると，'abc'，'bcd'，'cde'，'def'，'efg'の各々に対して，何文字書き換える必要があるか計算し，最小のものが答えとなります．
s = input()
t = input()
min_count = 1000
for i in range(len(s) - len(t) + 1):
count = 0
for j in range(len(t)):
if s[i+j] != t[j]:
count += 1
min_count = min(count, min_count)
if min_count == 0:
break
print(min_count)
C問題 Substring
問題文
$N$個の整数$A_1,…,A_N$が与えられます。
$1 \leq i < j \leq N$を満たす全ての組$(i,j)$についての$A_i×A_j$の和を$mod(10^9+7)$で求めてください。
求める和は，$A_1×(A_2+...+A_N) + A_2×(A_3+...+A_N) + ... + A_{N-1}×(A_N)$となるので，個別に全て計算するよりも，計算量を抑えることができる．
n = int(input())
a_list = list(map(int, input().split()))
ans = 0
total = 0
mod = 10 ** 9 + 7
for i in range(n):
total += a_list[i]
if total >= mod:
total = total % mod
for i in range(n - 1):
total -= a_list[i]
if total < 0:
total += mod
ans += a_list[i] * total
if ans >= mod:
ans = ans % mod
print(ans)
前半はここまでとなります．
最近は公式の解説がとても丁寧に記述してあったので，詳しい解法はそちらを参考にしてもらえたらと思います．
前半の最後まで読んでいただきありがとうございました．
後半はDE問題の解説となります．
後半に続く．