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

公開:2020/12/04
更新:2020/12/10
2 min読了の目安(約2000字TECH技術記事

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も確定するので2重ループで良い。計算量も

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...するのか???)