読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

ABC043を解いてみた

abc043.contest.atcoder.jp

A問題

 1からNまでの和をn(n+1)/2で求めます。

n = int(input())
print(int(n*(n+1)/2))

B問題

 sの長さは10以下と非常に短いため、条件に従って答えとなる文字列を操作していけばよさそうです。この方針で実装しました。

s = list(input())

ans = ""
for i in s:
    # 0を連結
    if i == "0":
        ans = ans + "0"
    # 1を連結
    elif i == "1":
        ans = ans + "1"
    # 一番右側の文字を削除
    elif i == "B":
        ans = ans[:len(ans)-1]

print(ans)

C問題

 NとAの範囲が狭く全探索で問題なさそうです。置き換える後の数字はAの制約である-100から100の範囲で必ず収まります。置き換える後の数字を全て、全てのNに対して試せばよさそうです。O(AN)≒O(20000)程度で収まるため実行時間も問題なさそうです。
 最初、range(-100, 100)としていて範囲に100が入っておらず一回WAを出してしまったので気をつけたいです。

n = int(input())
a = [int(i) for i in input().split()]

mincost = 10000000
for i in range(-100, 101):
    cost = 0
    for j in range(n):
        cost += (a[j]-i) ** 2
    mincost = min(cost, mincost)

print(mincost)

D問題

 最初、しゃくとり法を使う方針で考えて提出しましたがWAを出してしまい考え直すと、長さが3の部分文字列がアンバランスでないときにその部分文字列を含む長さが4の部分文字列がアンバランスであることはありえません。そこで文字列を3文字ずつに区切っていきアンバランスであるかを確かめていけばよさそうです。この方針で実装したところWA… コーナーケースを考えると入力sが"aa","ff"といった同じ文字2文字の場合があり、この入力sはアンバランスな部分文字列となりますが、3文字以上の文字列に対してのみ確認を行っていたため判定できていませんでした。修正を行って提出してAC!

import sys
s = input()

# 同じ文字2文字はアンバランス
if len(s) == 2 and s[0:1] == s[1:2]:
    print(1, 2)
    sys.exit()

for i in range(len(s)-2):
    #3文字で区切る
    temp = s[i:i+3]
    #アンバランスな部分文字列が存在すれば
    if temp[0:1] == temp[1:2] or temp[1:2] == temp[2:3] or temp[2:3] == temp[0:1]:
        print(i+1, i+3)
        sys.exit()

print(-1, -1)

雑感

 点数が低めのやさしめな問題だったのもあって自力で4完とれました。今日この後あるABCも頑張りたいです。