AtCoder Beginner Contest 105 に参加しました(Python)

サイトへのURL

AtCoder Beginner Contest 105 - AtCoder

以下では,li_input()関数を用います.

def li_input():
    return [int(_) for _ in input().split()]

A問題

問題文

高橋君は N 枚の AtCoder せんべいを K 人の AtCoder 参加者になるべく公平に配ることにしました。 N 枚すべてのせんべいを配るとき、せんべいを最も多くもらった人と最も少なくもらった人のもらったせんべいの枚数の差(の絶対値)の最小値を求めてください。  

解法

せんべいN枚をK人に均等に分けられる時,答えは0です.
均等に分けられない時,答えは1です.

ソースコード

def main():
    N, K = li_input()

    if N % K == 0:
        print(0)
    else:
        print(1)


main()

B問題

問題文

ABC 洋菓子店では, 1 個 4 ドルのケーキと 1 個 7 ドルのドーナツが売られている. このとき, 合計金額が N ドルとなる買い方はあるか, 判定せよ. ただし, 同じ商品を二個以上買っても良く, 買わない商品があっても良いものとする.

解法

ケーキを買う個数をx,ドーナツを買う個数をyとします.
また,合計金額pp = 4x + 7yとします.

問題文の条件より,Nはたかだか100なので,
1 <= p <= 100となるようなxyを全探索によって求めれば良いです.

ソースコード

def main():
    l = []

    for i in range(100):
        for j in range(100):
            if i * 4 + j * 7 <= 100:
                l.append(i * 4 + j * 7)

    N = int(input())

    if N in l:
        print("Yes")
    else:
        print("No")

C問題

問題文

f:id:Szarny:20180812013256p:plain

解法

公式解法とは全く異なります

細かいところについては,ソース内に書いているので省きます.
通常の10進数>2進数変換の際と同じように考えました.

  1. 最上位ビットの位置を決める(上位から順に b_k b_{k-1} b_{k-2} ... b_1 b_0 とする 当然b_{k}1)
  2. 2.1. 各ビットの-2進数の位を c_k c_{k-1} c_{k-2} ... c_1 c_0 とする
    2.2. 現在の値を c_kの値とする
    2.3. i = k-1とする

  3.  c_{i}が正の数である場合は4へ 負の数である場合は5へ
  4. 4.1.  c_{j} (j < i) である全ての正の数の総和と現在までの値を足してNに届かなければ, b_{i}のビットを立てる
    4.2. 現在の値 = 現在の値 +  c_{i}とする.

  5. 5.1.  c_{j} (j < i) である全ての負の数の総和と現在までの値を足してNを上回れば, b_{i}のビットを立てる
    5.2. 現在の値 = 現在の値 +  c_{i}とする.

  6. iをデクリメントして3に戻る

のような感じです.

ソースコード

c = []


# (i < limit, c[i] > 0となるc[i]の数を足して行った結果) + 現在の値 が
# Nを下回ればc[limit]を足す必要がある
def is_lower(limit, c_value, N):
    add_value = 0
    for i in range(limit - 1, -1, -1):
        if c[i] > 0:
            add_value += c[i]

    return c_value + add_value < N


# (i < limit c[i] < 0となるc[idx]の数の総和) + 現在の値 が
# Nを上回ればc[limit]を引く必要がある
def is_over(limit, c_value, N):
    sub_value = 0
    for i in range(limit - 1, -1, -1):
        if c[i] < 0:
            sub_value += c[i]

    return c_value + sub_value > N


def main():
    global c

    N = int(input())
    c_value = None

    # コーナーケース
    if N == 0:
        print(0)
        return

    # 位を事前に計算
    for i in range(50):
        c.append((-2)**i)

    # NがPositiveの場合
    # (-2)**i (i=2k) の総和が目的の値を超えるところが最上位ビット
    if N > 0:
        tmpsum = 0
        for i in range(50):

            if c[i] > 0:
                tmpsum += c[i]

            if tmpsum >= N:
                idx = i
                c_value = c[i]
                break

    # NがNegativeの場合
    # (-2)**i (i=2k+1) の総和が目的の値を下回るところが最上位ビット
    else:
        tmpsub = 0
        for i in range(50):
            if c[i] < 0:
                tmpsub += c[i]

            if tmpsub <= N:
                idx = i
                c_value = c[i]
                break

    ans = "1"

    for c_idx in range(idx - 1, -1, -1):
        # c[c_idx]がNegativeのとき
        # c[c_idx]の値を加算しなければ
        # c_idx' < c_idx かつ c[c_idx']<0 となる任意のc[c_idx']の値を加算しても
        # 最終的な総和がNを上回ってしまうなら,c[c_idx]を加算する必要がある
        if c[c_idx] < 0:
            if is_over(c_idx, c_value, N):
                ans += "1"
                c_value += c[c_idx]
            else:
                ans += "0"

        # c[c_idx]がPositiveのとき
        # c[c_idx]の値を加算しなければ
        # c_idx' < c_idx かつ c[c_idx']>0 となる任意のc[c_idx']の値を加算しても
        # 最終的な総和がNを下回ってしまうなら,c[c_idx]を加算する必要がある
        else:
            if is_lower(c_idx, c_value, N):
                ans += "1"
                c_value += c[c_idx]
            else:
                ans += "0"

    print(ans)


main()

D問題

問題文

f:id:Szarny:20180812020237p:plain

解法

累積和を用います.
ただし,ここでは各累積和の Mの剰余が知れればいいので,計算時に Mの剰余のみを格納します.
つまり, A_{1}から A_{k}までの総和を Mで割った値を C_{k}とします.
(ただし, C_{0} = 0とする.)

ここで,条件を満たすような (l, r)の総数というのは, C_{l-1} = C_{r}となるような (l, r)において,それぞれの (l, r)の2つの組み合わせの個数の和のことです.
なぜなら, C_{l-1} = C_{r} ( C_{l-1} - C_{r} = 0)のとき, A_{l} A_{l+1} ... A_{r-1} A_{r}の総和は Mの倍数になるからです.
これを数え上げれば解くことができます.

ソースコード

import collections

def main():
    N, M = li_input()
    A = li_input()

    ans = 0
    d = collections.defaultdict(lambda: 0)

    cumsum = [0]
    c_sum = 0
    for a in A:
        c_sum = (c_sum + a) % M
        cumsum.append(c_sum)

    for c in cumsum:
        d[c] += 1

    for v in d.values():
        if v >= 2:
            ans += v * (v - 1) // 2

    print(ans)


main()

AtCoder Beginners Selection をPythonで解く

はじめに

競技プログラミングをぼちぼちやっています.
復習も兼ねて,Tasks - AtCoder Beginners SelectionPython(3)で解いていきます.

はじめてのあっとこーだー(Welcome to AtCoder

問題文の通りにやるだけです.

def main():
    a = int(input())
    b, c = [int(_) for _ in input().split()]
    s = input()

    print(a + b + c, s)

main()

Product

こちらも問題文の通りにやるだけです. 三項演算子を使っています.

def main():
    a, b = [int(_) for _ in input().split()]
    print("Even") if a * b % 2 == 0 else print("Odd")

main()

Placing Marbles

1の数を数えます.
count関数で特定の文字を文字数を数えることができるのでそれを利用します.

def main():
    print(input().count("1"))

main()

Shift only

全要素を割れなくなるまで2で割り,割れなくなった時のループ回数を表示しています.

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()

Coins

単純な全探索です.
O(n^3)ですが,A, B, Cはたかだか50なので大丈夫.

import sys

def main():
    A = int(input())
    B = int(input())
    C = int(input())
    X = int(input())

    ans = 0

    for nA in range(A + 1):
        for nB in range(B + 1):
            for nC in range(C + 1):
                if nA * 500 + nB * 100 + nC * 50 == X:
                    ans += 1

    print(ans)

main()

Some Sums

str(num)で文字列化し,list(...)によって各文字を要素とする配列に変換し,map(...)によって再度整数型にした後,sum(...)で合計を計算しています.

def main():
    N, A, B = [int(_) for _ in input().split()]

    ans = 0

    for num in range(1, N + 1):
        if A <= sum(map(int, list(str(num)))) <= B:
            ans += num

    print(ans)

main()

Card Game for Two

両者が最適な戦略をとる(=場にある数のうち最大のものを取り続ける)ので,
数を降順に並べ替えた後,
 1, 3, 5, ...番目に大きい数を加算し, 2, 4, 6, ...番目に大きい数を減算すれば良いです.

def main():
    N = int(input())
    A = sorted([int(_) for _ in input().split()], reverse=True)

    ans = 0
    for i, a in enumerate(A):
        if i % 2 == 0:
            ans += a
        else:
            ans -= a

    print(ans)

main()

Kagami Mochi

一見ややこしそうですが,入力値の重複を除くだけで解くことができます.
色々方法はありそうですが,ここでは単純にset関数を用いて集合化することで要素をユニークにしています.

def main():
    N = int(input())
    D = []

    for _ in range(N):
        D.append(int(input()))

    print(len(set(D)))

main()

Otoshidama

全探索しようとするとO(n^3)アルゴリズムになりそうですが,
10000円札の枚数と5000円札の枚数を決定した時点で

1000円札の枚数 = 全体の枚数 - 10000円札の枚数 - 5000円札の枚数

となり1000円札の枚数を決定できるため,計算量をO(n^2)に削減することが可能です.

import sys

def main():
    N, Y = [int(_) for _ in input().split()]

    for n_10k in range(N+1):
        for n_5k in range(N - n_10k + 1):
            n_1k = N - n_10k - n_5k

            if n_10k * 10000 + n_5k * 5000 + n_1k * 1000 == Y:
                print(n_10k, n_5k, n_1k)
                sys.exit()

    print(-1,-1,-1)

main()

白昼夢 / Daydream

 Tに文字列を付け足して Sを作ろうとするのではなく,
 Sから文字列を削除することで T(=空文字列)を作ることができるかを調べます.

ここで,前方から検索すると,dreamerereraseerが混じって面倒です.
後方から検索を行うことで,erに関係なく Sから文字列を削除することが可能です.

def main():
    S = input()

    while len(S) >= 5:
        if len(S) >= 7 and S[-7:] == "dreamer":
            S = S[:-7]
            continue

        if len(S) >= 6 and S[-6:] == "eraser":
            S = S[:-6]
            continue

        elif S[-5:] == "dream" or S[-5:] == "erase":
            S = S[:-5]
            continue

        else:
            break

    if len(S) == 0:
        print("YES")
    else:
        print("NO")

main()

Traveling

AtCoDeerくんが時刻  t に座標  (x, y) にいるとします.
そして,時刻  t' に座標  (x', y') に移動しなければいけない状況を考えます.

ここで, distance = |(x' - x)| + |(y' - y)|とします.
また, timedelta = t' - t とします.

 distance > timedelta であるとき,つまり移動量が移動可能時間よりも大きいとき,時間内に移動を終えることは不可能です.
よって,Noを出力して終われば良いです.

 distance = timedelta であるとき,つまり移動量と移動可能時間が同じとき,時間内に移動を終えることが可能です.
よって,Yesを出力し次の条件に移ります.

 distance \lt timedelta であるとき,つまり移動量より移動可能時間が大きいときは,条件を達成できる場合とできない場合があります.

例えば,時刻  0 に座標  (0, 0) にいて,時刻  4 に座標  (2, 0) に移動しなければならない時は (0, 0), (1, 0),  (2, 0),  (1, 0),  (2, 0)のように,目的の座標にたどり着いた後行ったり来たりを繰り返せば条件を達成することができます.

一方で,時刻  0 に座標  (0, 0) にいて,時刻  5 に座標  (2, 0) に移動しなければならない時は (0, 0),  (1, 0),  (2, 0),  (1, 0),  (2, 0),  ...となり,どう歩いても目的の座標に目的の時刻にたどり着くことは不可能です.

まとめると, distance \lt timedelta であるときは,ゴールにたどり着いた後,行ったり来たりして残り時間を消費できれば条件を達成することができるといえます.

これは, timedelta - distance の値,つまり目的地にたどり着いた後の余裕時間が  2 で割り切れるかを調べるとわかります.
なぜなら,目的地にたどり着いた後の余裕時間の値が  2 で割り切れるとき,行ったり来たりして目的の座標に戻ることができるからです.

import sys

def main():
    N = int(input())
    t, x, y = 0, 0, 0

    for _ in range(N):
        next_t, next_x, next_y = [int(__) for __ in input().split()]

        delta_t = next_t - t
        distance = abs(next_x - x) + abs(next_y - y)

        if distance > delta_t:
            print("No")
            sys.exit()

        if (delta_t - distance) % 2 != 0:
            print("No")
            sys.exit()

        t, x, y = next_t, next_x, next_y

    print("Yes")

main()

おわりに

はやく水色になりたい

「リーダブルコード」を読んだのでアウトプット

TL;DR

  • ちゃんと名前付けをする!
  • ブール値やブール値を返す関数は肯定形で!
  • 整列させて見た目をきれいに!
  • コメントは動作内容よりも目的や背景を!
  • ネストは浅く!
  • 説明変数・要約変数を導入する!
  • 大きな処理は下位問題を抽出して分割する!
  • 言語仕様やAPIのドキュメントを参照できるように準備しておく!

はじめに

タイトル通り,前々から読みたかった「リーダブルコード」を読みました.
本記事はそのアウトプットです.

コードは他の人が最短時間で理解できるように書かなければいけない.

www.oreilly.co.jp

ネーミングに関する指針

何も考えずにプログラムを書いていると,よくvarだのtmpだのvalueだのといった意味のない変数名を使ってしまいがちです.

また,意味があったとしても,retvalindexのように汎用的だったり抽象的だったりする名前を付けがちです.

以下は,(やりすぎな)例です.

def calc(h, w):
  r = w / (h**2)

  if r < 18.5:
    m = "slim"
  elif r >= 25:
    m = "fat"
  else:
    m = "healthy"

  return m

もはや適当すぎて何をやっているのかすら良く分かりません.
実際は,入力された身長と体重からBMIを計算して,結果に応じたメッセージを返却する関数です.

このようなコードは,関数名や変数名がそれ自身で意味を表すようにすると分かりやすくなります.

def get_message_for_bmi(height_meter, weight_kg):
  bmi = height_meter / (weight_kg ** 2)

  SLIM_RANGE_END    = 18.5
  HEALTHY_RANGE_END = 25.0

  if bmi < SLIM_RANGE_END:
    return "slim"
  elif bmi < HEALTHY_RANGE_END:
    return "healthy"
  else:
    return "fat"

かなり読みやすくなったと思います.
上記のコードからは,簡単に以下の事柄が推察できます.

  • この関数はbmiに対するメッセージを返す関数なんだろう
  • 引数として,メートル単位の身長とキログラム単位の体重を受け取るんだろう
  • XXX_RANGE_ENDは範囲の上限を表す定数なんだろう
  • 最終的に,bmiが範囲のどの部分に当てはまるかによって,異なったメッセージが返されるんだろう

便利なツール

類語辞典・シソーラス・対義語 - Weblio辞書
一番おすすめはシソーラスです.プログラミングに限らず,文章を書く時にも有用です.

codic - プログラマーのためのネーミング辞書
最近だと,codicとかも良いんではないでしょうか.

ブール値に関する指針

基本的に,否定形のブール値や条件判断は,肯定形のそれと比べて読みにくいことが多いです.

if is_not_logged_in:
  return loginPage
else:
  return userPage

肯定形に書き直してみます.
こちらの方が直感的に読めるのではないでしょうか.

if is_logged_in:
  return userPage
else:
  return loginPage

美しさに関する指針

見た目がきれいなコードがすべて読みやすいとは限りませんが,読みやすいコードは見た目もきれいだと思います.
具体的な指針は以下の通りです.

整列する

このコードより

first_greeting = "Hello"
name = "Szarny"
last_greeting = "bye"

print(first_greeting, name, last_greeting)

整列された以下のコードの方が読みやすと思います.

first_greeting = "Hello"
name           = "Szarny"
last_greeting  = "bye"

print(first_greeting, name, last_greeting)

意味のあるまとまりに分ける

意味的に分かれているコードは,見た目上でも分かれさせた方が見やすくなります.

こんなコードはごちゃごちゃしていて読む気になりませんが,

# 与えられた得点リストの平均と標準偏差を返す
def calculate_stats_of_test_points(points):
  total_point = 0
  for point in points:
    total_point += point
  average = total_point / len(points)
  deviation_square = 0
  for point in points:
    deviation_square += (point - average) ** 2
  variance = deviation_square / (len(points) - 1)
  standard_deviation = variance ** 0.5

  return (average, standard_deviation)

以下のようなコードは意味的にチャンキングされていて読みやすく感じます.(pythonならこんな処理書く必要ないですが...)

# 与えられた得点リストの平均と標準偏差を返す
def calculate_stats_of_test_points(points):
  # 総得点を求める
  total_point = 0
  for point in points:
    total_point += point

  # 平均を求める
  average = total_point / len(points)

  # 偏差の二乗平均を求める
  deviation_square = 0
  for point in points:
    deviation_square += (point - average) ** 2

  # 分散を求める
  variance = deviation_square / (len(points) - 1)

  # 標準偏差を求める
  standard_deviation = variance ** 0.5

  return (average, standard_deviation)

コメントに関する指針

コメントすべきではないことと,コメントすべきこと

コメントはコードからすぐに読み取れることを書くべきではありません.

TIMEOUT_LIMIT_SEC = 10 # タイムアウトを10秒に設定する

動作内容そのものよりも,その処理や変数を用いる目的や背景をメモしておくべきです.

TIMEOUT_LIMIT_SEC = 10 # 10秒経っても処理が終わらなければ大抵エラー

関数については,動作例を示しておくと分かりやすくなります.

# 与えられたリストから平方数の要素のみを返却する
# [1, 2, 4, "abc", 9, 25, 55, 100] -> [1, 4, 9, 25, 100]
def extractSquareNumbers(numbers):

制御フローに関する指針

人間は,何段にもネストされたコードを読むとき,そのコードをブロックごとに頭の中のスタックにプッシュしていく必要があります.

以下のような関数は,最初の条件分岐が関数全体に影響しているため,肝心な部分を集中して読むことができません.
また,Trueの時の処理を読み終わってelse節に入るときに,「そもそも条件ってなんだったっけ」となると読み返す必要が生じます.

# リストarrayに含まれる要素targetの数を返却する
# count_elements([1,2,3,2,3,2,3], 2) => 3
def count_elements(array, target):
  if(type(array) == type([])):

    match = 0

    for elem in array:
      if elem == target:
        match += 1

    return match

  else:
    return 0


なるべくネストを深くせずに,ガード節を設置して早く結果を返すようにすれば,精神的な負担が減ります.

# リストarrayに含まれる要素targetの数を返却する
# count_elements([1,2,3,2,3,2,3], 2) => 3
def count_elements(array, target):

  # arrayがリストでなければ0を返す
  if(type(array) != type([])):
    return 0

  match = 0

  for elem in array:
    if elem == target:
      match += 1

  return match

巨大な式に対する指針

巨大な式や複雑な式は,それが何を表しているのか説明する説明変数や,メタな視点から捉えた要約変数が有効です.

BMI計算関数の例(を改悪したもの)を再掲します.

def get_message_for_bmi(height_meter, weight_kg):
  SLIM_RANGE_END    = 18.5
  HEALTHY_RANGE_END = 25.0

  if height_meter / (weight_kg ** 2) < SLIM_RANGE_END:
    return "slim"
  elif height_meter / (weight_kg ** 2) < HEALTHY_RANGE_END:
    return "healthy"
  else:
    return "fat"

条件分岐のあたりが読みにくく感じます.
そもそも,height_meter / (weight_kg ** 2) BMIの数値を表しているため,単純に説明変数で置き換えるだけですっきりします.

def get_message_for_bmi(height_meter, weight_kg):
  bmi = height_meter / (weight_kg ** 2)

  SLIM_RANGE_END    = 18.5
  HEALTHY_RANGE_END = 25.0

  if bmi < SLIM_RANGE_END:
    return "slim"
  elif bmi < HEALTHY_RANGE_END:
    return "healthy"
  else:
    return "fat"

巨大な関数についての指針

ある問題を解決するための「巨大な関数」や「ひとかたまりの処理」は,いくつかの下位問題から構成されていることが多いです.
このような時は,そのカタマリの主目的とは関係のない部分を抽出するとうまくいきやすいです.

以下は,与えられた2つのファイルのハッシュ値が同一か検査する関数です.

# 2つのファイルのハッシュ値が同一か検査する
def is_hash_same(filename_1, filename_2):
  hash_value_1 = ""
  hash_value_2 = ""

  with open(filename_1, "rb") as f1:
    contents_1 = f1.read()
    sha256 = SHA256.new()
    sha256.update(contents_1)
    hash_value_1 = sha256.hexdigest()

  with open(filename_2, "rb") as f1:
    contents_2 = f1.read()
    sha256 = SHA256.new()
    sha256.update(contents_2)
    hash_value_2 = sha256.hexdigest()

  return hash_value_1 == hash_value_2

この関数の主目的は,ハッシュ値が同一か検査すること」のみです.

そのため,ファイルのオープンやハッシュ関数用モジュールの設定を事細かに記述するべきではありません.
これらは,主目的とか関係ない下位問題であるからです.

以下のように書き換えるとすっきりします.

# 2つのファイルのハッシュ値が同一か検査する
def is_hash_same_new(filename_1, filename_2):
  contents_1 = get_contents_of_file(filename_1)
  contents_2 = get_contents_of_file(filename_2)

  hash_value_1 = get_hash_value(contents_1)
  hash_value_2 = get_hash_value(contents_2)

  return hash_value_1 == hash_value_2

# ファイルの内容を取得する
def get_contents_of_file(filename):
  with open(filename, "rb") as f:
    return f.read()

# 入力値のSHA-256ハッシュ値を返却する
def get_hash_value(data):
  sha256 = SHA256.new()
  sha256.update(data)
  return sha256.hexdigest()

このコードには,以下のような利点もあります.

  • 抽出した関数は汎用的なので,再利用が容易である
  • 関数は独立しているので,修正や拡張が容易である

コードの長さに関する指針

最も読みやすいコードは,何も書かれていないコードだ.

複雑に書くよりもシンプルに書く方がいいに決まっています.

以下は,リストの重複を除く関数です.

def make_distinct(array):
  distinct_array = []

  for item in array:
    if item not in distinct_array:
      distinct_array.append(item)

  return distinct_array

これでも正しく動作しますが,もっと簡単に書けます.

def make_distinct(array):
  return list(set(array))

このような処理をサッと書けるようになるには,APIドキュメントを読んでおいて,必要な時に参照できるようになっておくと良いとのことです.
覚えておくのには限界がありますしね.

おわりに

「リーダブルコード」のアウトプットを行いました.

これでもまだ書籍全体の半分にも満たないと思います.
説明がうまく,コーディング例も平易なものが多かったので,肩に力を入れることなく読める一冊でした.おすすめです!

次は,デザインパターンとかのプログラムの構造に重きを置いた書籍を読みたいです.