ABC177参戦記

日中は畑で草刈りして、夕方から子供と公園で遊んでコード書くこともできずにコンテスト時間になってしまいました。

作問が間に合わずに開催延期も示唆されていましたが、無事開催してくれました。
問題のwriterの方、運営の方々に感謝しつつ、今回のABC177に参加しました。

この記事は、ABCのC問題を安定して解けないくらいの灰色コーダーが、自分の思考過程などを言語化しているものです。
使用言語はPython3で、A問題からC問題までのACコード付きです。

A – Don’t be late

距離と時間、速度の問題。
プログラミングとしては条件分岐が書けるかの問題。

速度は時間単位あたりに進む距離を表しているので、同じ時間単位であれば、速度に時間を掛ければ進む距離が出てきます。

DとT分間で進む距離を比べて、T分間で進む距離がD以上であれば、待ち合わせ時間に間に合います。

それぞれの単位が異なる場合は、単位をそろえる必要がありますが、今回は「分」「メートル」「メートル/分」とすべてそろっているのでそのまま計算できます。

# AtCoder Beginner Contest 177
# A - Don't be late

D,T,S=map(int,input().split())
if D<=T*S:
    print("Yes")
else:
    print("No")

B – Substring

文字列(の一部)と文字列の２つを比較して、何文字書き換えたら同じ文字列になるかを確認する問題。また、文字列の一部をfor文で取り出して全パターンで確認し、最も書き換える文字が少ないパターンを確認する問題。

過去のABC172-B問題で出た、Minor Changeの応用問題です。
応用問題といえないほど難易度が上がっていると思いますけど・・・

ちなみに私はこの問題見た時に解法がよくわかりませんでした。
先にC問題に取り組んで、C問題は結局わからずにこのB問題に戻ってきて、2ペナしつつも、時間ギリギリでようやくACしました。

解法はまずは、上記のMinor Changeと同様、Tの長さのfor文で、T[i]とS[i]が一緒か確認します。
一緒であれば一致している文字列の個数のカウンタを1つ増やします。

S=input()
T=input()

Slen=len(S)
Tlen=len(T)

temp=0
for j in range (Tlen):
    if T[j]==S[j]:
        temp+=1
    else:
        continue
print(temp)

上記コードはSとTの長さが同じ場合は良いのですが、今回はSの長さはT以上であるため、Sの中から開始する文字の位置を変えてそれぞれ確認していく必要があります。

今回の入力例1
S=cabacc
T=abc
で考えると、

1. S[0]から始まるcabとabc
2. S[1]から始まるabaとabc
3. S[2]から始まるbacとabc
4. S[3]から始まるaccとabc

2の場合と4の場合どちらかで、Sを１つ変えれば、Tと一致する部分が作れることがわかります。

また、S[4]から始めると、ccまでしか文字列が取れないため、S[3]までを調べることになります。
ここから、for文で繰り返す回数は、Sの長さからTの長さを引いた数+1回であることがわかります。

Sの各開始位置でTと一致している個数をカウントし、一致している数が前回まで調べたものよりも大きければ更新していき、Tの長さから、一致している文字列の最大値を引いた値が答えになります。

# AtCoder Beginner Contest 177
# B - Substring

S=input()
T=input()

Slen=len(S)
Tlen=len(T)

m=0

for i in range (Slen-Tlen+1):
    temp=0
    for j in range (Tlen):
        if T[j]==S[i+j]:
            temp+=1
        else:
            continue
    else:
        if temp>m:
            m=temp
print(Tlen-m)

C – Sum of product of pairs

掛け算の分配法則と区間累積和の問題。

今回C問題は解けませんでした。itertoolsモジュールのcombinationsや、二重のfor文でTLE出しました。

writerの競プロフレンズさんは、ひっかかった！ひっかかった！と思っていることでしょう・・・(そんな性格悪くないかｗ

掛け算の和については、

A[i]×A[i+1] + A[i]×A[i+2] + A[i]×A[i+3] + ・・・は、A[i]で括って、A[i] × (A[i+1] + A[i+2] + A[i+3] + ・・・)とすることができますね。

解説にもある通り、1<=i<j<=Nであることから、かける数の個数は階段状に減ってくことがわかります。

これをN-1までiをfor文で繰り返す。
上記のかっこで括った部分は初めに累積和を求めておくことで区間累積和も求めることが可能になります。

毎回答えを加算してmodをとっておいて最後に答えを出力すればACします。

# AtCoder Beginner Contest 177
# C - Sum of product of pairs

N= int(input())
ls= list(map(int,input().split()))

mod=10**9+7

ans=0
accumls=[0]

for i in range (N):
    accumls.append(accumls[-1]+ls[i])

for i in range (N-1):
    ans+= ls[i]*(accumls[-1]-accumls[i+1])
    ans%=mod

print(ans)