[Python]AtCoder 版！蟻本 (初級編) 精進日記

0 はじめに

言わずとしれた、けんちょんさんのAtCoder版！蟻本 (初級編)をPythonで精進していく日記です。
毎日精進していきます（目標&願望）。
もっと良いコードの書き方等あればどしどしご意見ください。
START(2020/12/04)

1-6 気楽にウォーミングアップ

例題 1-6-1　三角形

【AtCoder上の類題】

・ARC 004 A 2点間距離の最大値

【解答例】

arc004a.py

import math
N=int(input())
X=[]
Y=[]
for i in range(N):
    x,y=input().split()
    X.append(int(x))
    Y.append(int(y))

ans = 0
for j in range(N):
    for t in range(N):
        if math.sqrt(pow(X[t] - X[j],2) + pow(Y[t] - Y[j],2)) > ans:
            ans = math.sqrt(pow(X[t] - X[j],2) + pow(Y[t] - Y[j],2))

print(ans)

【感想】
圧倒的全探索。平方根はsqrt、べき乗はpowで対応。
もっと簡潔な入力できそう。

・ABC 051 B Sum of Three Integers

【誤答】

k,s = map(int,input().split())

ans = 0
for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if x + y + z == s:
                ans += 1
print(ans)

時間足りなかった。解説から計算量は

$$O(K^3)$$

であるので駄目。なので以下のように書き換えた。
【解答例】

abc051b.py

k,s = map(int,input().split())

ans = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if 0 <= z <= k:
            ans += 1
print(ans)

【感想】
単純にX+Y+Z=SからZ=S-X-Yなので、X,Y決まった時点でZも確定するので２重ループで良い。計算量も

$$O(K^2)$$

に減るので解決。

・ARC 061 C たくさんの数式

arc061c.py

s = input()
n = len(s)

ans = 0

for bit in range(1 << (n - 1)): #左へビットシフト
    #各場合で式fを生成
    f = s[0]
    for i in range(n - 1):
        if bit & (1 << i):
            f += "+"
        f += s[i + 1]
    ans += sum(map(int, f.split("+")))

print(ans)

【感想】
みんな大好きbit全探索。下記記事を参考にした。まだまだ使いこなせてない感満載なので、練習を積みたい。
【参考】
bit全探索

(to be continue...するのか？？？)