AtCoderBeginnerContest177復習＆まとめ（前半）

AtCoder ABC177

2020-08-29(土)に行われたAtCoderBeginnerContest177の問題をA問題から順に考察も踏まえてまとめたものとなります．
前半ではABCまでの問題を扱います．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF

A問題　Don't be late

問題文
高橋君は青木君と待ち合わせをしています。
待ち合わせ場所は高橋君の家から$D$メートル離れた地点であり、待ち合わせの時刻は$T$分後です。
高橋君は今から家を出発し、分速$S$メートルで待ち合わせ場所までまっすぐ移動します。
待ち合わせに間に合うでしょうか？

abc177a.py

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'の各々に対して，何文字書き換える必要があるか計算し，最小のものが答えとなります．

abc177b.py

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)$となるので，個別に全て計算するよりも，計算量を抑えることができる．

abc177c.py

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問題の解説となります．
後半に続く．