schedule2018-01-21

AtCoder BC 116の記録 | Python

AtCoderPython競プロ

気になっていたAtCoderのコンテストに初参加しました。まだまだひよっこですが、今後の成長のためにも復習を兼ねて記録していきます。

言語はPython3.4です。

コンテスト

2019-01-20(日) 21:00 ~ 2019-01-20(日) 22:40

AtCoder Beginner Contest 116

成績

result

順位は665位で上から40％ぐらいの位置についた。 BC問題に時間がかかってD問題は集中力が切れてしまった。

提出したコードとどう考えたか

解説を見るか同じ言語の回答を見れば良いものですが、備忘録のため提出したコードをどう考えて書いたかのメモしておく。コメントはあとでつけました。

A - Right Triangle

問題

直角三角形の面積を計算する問題。 $\angle ABC = 90^\circ$ は問題文からわかる。３辺の長さを受け取り、面積を出力する。入力の順序からどの辺の長さか決まっているので、 $AB \times BC / 2$ で良い。

ab, bc, ca = list(map(int, input().split()))

S = ab * bc / 2
print(int(S)) # 割り算すると.0がつくため整数にして出力。

解説をみて

間違ってなかった。

B - Collatz Problem

問題

とある規則を持った数列の繰り返しが出現する箇所を特定する問題。数列の作成はすぐに浮かんだが、条件を理解することに手間取ってしまった。同じ数値が初めて現れる番号を出力すれば良い。

def f(n):
    # 数列の規則
    if n % 2 == 0:
        return int(n / 2)
    else:
        return 3 * n + 1
 
if __name__ == "__main__":
    s = int(input())
 
    a = s
    arr = [s]
    for i in range(1000000): # m < 1000000となるので
        a = f(a)
        if a in arr:
            # 同じ数値が現れたた出力
            print(len(arr) + 1)
            break
        # 数列の格納
        arr.append(a)

解説をみて

4 → 2 → 1 → 4のループに必ずなるCollatz problemらしい。 4が出現したm+3で求まる。

リファクタリング

def f(n):
    # 数列の規則
    if n % 2 == 0:
        return int(n / 2)
    else:
        return 3 * n + 1
 
if __name__ == "__main__":
    s = int(input())
    if s == 2 or s == 1:
        # 2と1もループになる。
        print(4)
        exit()
    for m in range(1, 1000000): # m < 1000000となるので
        if s == 4:
            print(m + 3)
            break
        s = f(s)

配列をもたずに判定するように書き換えたが、メモリ消費も実行時間も変わらなかった。。。。

C - Grand Garden

問題

花を指定の高さまで水をあげて育てる最小手数を求める問題。水をやると高さが+1。花は並んでおり、隣り合う範囲はまとめて水をやれる。

高さ配列の要素を最小値で引いていけば、0の箇所で配列を分割できると考えた。手数はその最小値分足していく。分割した配列を同様に処理する。これを再帰的に解いていく。

count = 0


def mizu(h):
    global count
    # 終端処理
    if len(h) is 0:
        return
    if len(h) is 1:
        count = count + h[0]
        return
    # その範囲の最小値
    m = min(h)
    count = count + m
    # 残りの高さ
    h = [i - m for i in h]
    while 0 in h:
        # （最小値だった）0の箇所で分割
        mizu(h[:h.index(0)])
        h = h[h.index(0)+1:]
    mizu(h)

if __name__ == "__main__":
    N = int(input())
    h = list(map(int, input().split()))
    mizu(h)
    print(count)