ABC045を解いてみた

abc045.contest.atcoder.jp

A問題

　台形の面積の公式を実装するだけです。

a = int(input())
b = int(input())
h = int(input())

print(int((a+b)*h/2))

B問題

　Sa, Sb, Sc <= 100 と制約がゆるいので条件に従ってシミュレーションしました。O(100^3)なので問題ないはず。とりあえずで書いたら冗長な形になってしまった。

import sys

stra = input()
strb = input()
strc = input()

flag = 1

while True:
    if flag == 1:
        if len(stra) == 0:
            print("A")
            sys.exit()
        if stra[0:1] == 'a':
            flag = 1
        elif stra[0:1] == 'b':
            flag = 2
        elif stra[0:1] == 'c':
            flag = 3
        stra = stra[1:len(stra)]
    elif flag == 2:
        if len(strb) == 0:
            print("B")
            sys.exit()
        if strb[0:1] == 'a':
            flag = 1
        elif strb[0:1] == 'b':
            flag = 2
        elif strb[0:1] == 'c':
            flag = 3
        strb = strb[1:len(strb)]
    elif flag == 3:
        if len(strc) == 0:
            print("C")
            sys.exit()
        if strc[0:1] == 'a':
            flag = 1
        elif strc[0:1] == 'b':
            flag = 2
        elif strc[0:1] == 'c':
            flag = 3
        strc = strc[1:len(strc)]

C問題

　10の分割数は確か50くらいだったので+を入れる全てのパターンについて考えても問題なく動くと考え全パターンについて考える方針で実装しました。itertools.combinations()とjoin()とsplit()を活用して実装しました。

import itertools

s = input()
n = [i for i in s]
ans = 0

# +の個数
for i in range(len(n)):
    # +を入れるパターンを全探索
    for j in itertools.combinations(range(len(n)-1), i):
        temp = [i for i in s]
        # +を挿入
        for k in j[::-1]:
            temp.insert(k+1, "+")
        # list から 文字列に
        temp = "".join(temp)
        # +で区切ってリストに
        temp = temp.split("+")
        # リストの要素をint型に変換して総和を足す
        temp = map(int, temp)
        ans += sum(temp)

print(ans)

D問題

　h, w <= 10^9 と非常に大きくh, w回のループを回すのは無理そうです。n<=10^5と小さいのでn回のループで処理を行う方針で行ければ実行時間は問題なさそうです。１つの黒マスについて3×3の範囲を確かめることで全ての3×3マスの四角形について黒マスが何個あるのかを調べられます。その後配列の要素別の個数をカウントするところでO(HW)の方法しか思い浮かばず詰まってしまいました…　pair型でソートする方法で実装しました。Pythonのtupleやpairについて学べてよかったです。

from collections import Counter, defaultdict
h, w, n = map(int, input().split())
ab = [[int(i)-1 for i in input().split()] for j in range(n)]

d = defaultdict(int)

for i in range(n):
    for j in range(3):
        for k in range(3):
            if ab[i][0] - j >= 0 and ab[i][1] - k >= 0 and ab[i][0] - j < (h - 2) and ab[i][1] - k < (w - 2):
                d[(ab[i][0]-j, ab[i][1]-k)] += 1

print((h-2)*(w-2)-len(d))

c = Counter(d.values())
for i in range(1, 10):
    print(c[i] if i in c else 0)