ABC343をPythonで（A～E）

AtCoder Beginner Contest 343の解答等のまとめ

A問題

$0 + 0$のときに1を返して、それ以外は0でいい

A

print(0 if sum(map(int, input().split()))>0 else 1)

B問題

各行で1になっているところをすべて返せばいい

B

for _ in range(int(input())):
    s = list(map(int, input().split()))
    lst = [i + 1 for i, s_i in enumerate(s) if s_i == 1]
    print(*lst)

C問題

3乗して$N$以下の数は高々$10 ^ 6$なのでそれぞれで回文か調べればよい

C

n = int(input())
i = 0
ans = 0
while i ** 3 <= n:
    s = str(i ** 3)
    if s == s[::-1]:
        ans = i ** 3
    i += 1

print(ans)

D問題

それぞれのスコアと各スコアの個数と種類数をメモできるようにして順番にやっていく

D

n, t = map(int, input().split())

score = [0] * n
d = {0: n}
ans = 1
for _ in range(t):
    a, b = map(int, input().split())
    a -= 1

    d[score[a]] -= 1
    if d[score[a]] == 0:
        ans -= 1
    score[a] += b
    if score[a] not in d:
        d[score[a]] = 0
    d[score[a]] += 1
    if d[score[a]] == 1:
        ans += 1

    print(ans)

E問題

• 考察と感想
  1つを 0,0,0 に固定してそれぞれ$\pm7$ぐらいを全探索すればいいのはすぐに分かったが式の導出に40分ぐらい費やしたうえでTLEしたのでいったんFへ

考察はあっていたがPythonだと計算量を結構削らないと間に合わない
解説にある$[-1, 7]$で回しても間に合わなかったのでmain関数に入れて実行したら間に合った（グローバル変数にアクセスするのに時間がかかるというのを以前見かけたので）

E

def main():
    v = list(map(int, input().split()))
    t = 9
    count = 0
    for A in range(t ** 3):
        a1, b1, c1 = A // t ** 2 - 1, A // t % t - 1, A % t - 1
        for B in range(t ** 3):
            a2, b2, c2 = B // t ** 2 - 1, B // t % t - 1, B % t - 1
            count += 1
            if a2 < a1 and b2 < b1 and c2 < c1:
                continue

            tri = max((min(0, a1, a2) + 7 - max(0, a1, a2)), 0) * max((min(0, b1, b2) + 7 - max(0, b1, b2)), 0) * max(
                (min(0, c1, c2) + 7 - max(0, c1, c2)), 0)

            dub01 = max((min(0, a1) + 7 - max(0, a1)), 0) * max((min(0, b1) + 7 - max(0, b1)), 0) * max(
                (min(0, c1) + 7 - max(0, c1)), 0) - tri
            dub02 = max((min(0, a2) + 7 - max(0, a2)), 0) * max((min(0, b2) + 7 - max(0, b2)), 0) * max(
                (min(0, c2) + 7 - max(0, c2)), 0) - tri
            dub12 = max((min(a1, a2) + 7 - max(a1, a2)), 0) * max((min(b1, b2) + 7 - max(b1, b2)), 0) * max(
                (min(c1, c2) + 7 - max(c1, c2)), 0) - tri

            sol0 = 7 ** 3 - dub01 - dub02 - tri
            sol1 = 7 ** 3 - dub01 - dub12 - tri
            sol2 = 7 ** 3 - dub02 - dub12 - tri

            if v == [sol0 + sol1 + sol2, dub01 + dub02 + dub12, tri]:
                print("Yes")
                print(0, 0, 0, a1, b1, c1, a2, b2, c2)
                exit()

    print("No")


if __name__=="__main__":
    main()

F問題

• 考察と感想
  rangeAskのセグ木に「区間内で最大のものの値、←の個数、2番目の値、←の個数」を持たせればいける
  と思って実装したけどTLE