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ドキュメントを読んでおいて,必要な時に参照できるようになっておくと良いとのことです.
覚えておくのには限界がありますしね.

おわりに

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

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

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

ReactのLifting State Upをひとつずつ

はじめに

Reactの公式ドキュメントのLifting State Up(Lifting State Up - React)が若干分かりにくかったので,別のコードで実装し直してみます.
使いどころが多そうなので今後のためにもメモを残しておきます.

Lifting State Up

Lifting State Up(Stateを持ち上げる)とは,いくつかの子コンポーネントで共通のデータを扱う必要があるときに,それを親コンポーネントに持ち上げた上で管理してもらう方法です.
よく分かりにくいので,例を挙げて示します.

Example

キロメートル/メートル変換ツール

例えば,キロメートル(kilometer)とメートル(meter)を相互変換するようなツールを考えます.
値の入力には,以下のようなフォームとイベントハンドラを合わせたコンポーネント(DistanceForm)を利用するとします.

import React from 'react';
import ReactDOM from 'react-dom';

class DistanceForm extends React.Component {
    constructor(props) {
        super(props);

        this.onChange = this.onChange.bind(this);

        // コンポーネントが管理するフォームのvalue
        this.state = {
            value: 0
        }
    }

    // フォームの値が変更された際に呼び出されるイベントハンドラ
    onChange(e) {
        this.setState({ value: parseInt(e.target.value) });
    }

    render() {
        return (
            <input
                type="text"
                onChange={this.onChange}
                name={this.props.name}
                value={this.state.value}
            />
        )
    }
}

const element = (
    <div>
        <DistanceForm name="kilometer" />
        <DistanceForm name="meter" />
    </div>
)

ReactDOM.render(
    element,
    document.getElementById("root")
)

ここで問題が発生します.
それぞれを別のコンポーネントとして管理してしまうと,片方の状態の変更をもう片方に伝播する方法がありません.
f:id:Szarny:20180115235534p:plain

これを解決する方法がStateの持ち上げです.
具体的には,以下のような手順でStateを持ち上げることで,片方の状態の変更がもう片方に伝播するようにします.

その1 子コンポーネントを内包する親コンポーネントを定義する

それぞれのコンポーネントの状態の変更を管理するメタなコンポーネントを定義します.
ここでは,DistanceFrameという名前にします.
f:id:Szarny:20180116001210p:plain

その2 子コンポーネント内で管理している状態を親コンポーネントで共通的に管理する

それぞれのコンポーネントが個別に状態(state)をもっていると,状態の共有ができません.
そのため,親コンポーネントでまとめて管理することにします.
f:id:Szarny:20180116001552p:plain

その3 親コンポーネントのpropsにイベントハンドラを設定する

その2において,状態の管理を親コンポーネントでまとめてすることにしたので,状態を更新するためのイベントハンドラも親コンポーネントで管理することにします.
このイベントハンドラの処理内容は,setState関数を用いて,stateを更新することです.
フォームの内容の変更を処理するイベントハンドラなので,名前はhandleChangeとしておきます.
f:id:Szarny:20180116002438p:plain

その4 子コンポーネントのpropsに親コンポーネントイベントハンドラを設定する

コンポーネントのpropsに親コンポーネントイベントハンドラを設定します.
そして,子コンポーネントが管理するフォームタグのonChange属性に,この親から渡されたイベントハンドラを設定します.
こうすることで,子コンポーネントのフォームタグの内容が変化したときに,親コンポーネントイベントハンドラが呼び出されるようになります.
f:id:Szarny:20180116002940p:plain

その5 親コンポーネントにrender関数を追加する

コンポーネントに子コンポーネントを含めてレンダリングするrender関数を追加します.
f:id:Szarny:20180116003234p:plain

結果

これでどうなるでしょうか.
コンポーネントであるmeterコンポーネントのフォームの値が変更された時の流れを考えてみます.
すると,以下のようになるはずです.

  1. 値が変更され,propsで渡された親コンポーネントイベントハンドラが呼び出される
  2. コンポーネントのstateが変化する
  3. stateの変化を観測したReactは,render関数を再度実行する
  4. コンポーネントのstateが,propsを通して子コンポーネントに伝播される

f:id:Szarny:20180116005344p:plain

これで,当初の目的であったコンポーネント間での状態の共有」が達成できました!

実装にあたっては,キロメートルとメートルの相互変換とかデータフォーマットチェックとかが必要ですが,本記事の目的とは関係ないので省略します.

実装

以上の手順を実装した結果が以下になります.

デモ

f:id:Szarny:20180116005057g:plain

ソースコード

class DistanceFrame extends React.Component {
    constructor(props) {
        super(props);

        this.handleChange = this.handleChange.bind(this);

        // 親コンポーネントで管理する状態
        this.state = {
            distance: 0,
            type: "kilometer"
        };
    }

    // 子コンポーネント内で発生するイベントのハンドラ
    handleChange(e) {
        this.setState({
            distance: parseInt(e.target.value),
            type: e.target.name
        });
    }

    convertDistance(distance, type) {
        let kilometer;
        let meter;

        if (Number.isNaN(distance)) {
            return [0, 0];
        }

        if (type === "kilometer") {
            kilometer = distance;
            meter = distance * 1000;
        } else {
            kilometer = distance / 1000;
            meter = distance;
        }

        return [kilometer, meter];
    }

    render() {
        let kilometer;
        let meter;

        [kilometer, meter] = this.convertDistance(this.state.distance, this.state.type);

        return (
            <div>
                <label>Kilometer:</label>
                <DistanceForm
                    onChange={this.handleChange}
                    name="kilometer"
                    value={kilometer}
                />
                <br />
                <label>Meter:</label>
                <DistanceForm
                    onChange={this.handleChange}
                    name="meter"
                    value={meter}
                />
            </div>
        );
    }
}

class DistanceForm extends React.Component {
    constructor(props) {
        super(props);
    }

    render() {
        return (
            <input
                type="text"
                onChange={this.props.onChange}
                name={this.props.name}
                value={this.props.value}
            />
        );
    }
}

ReactDOM.render(
    <DistanceFrame />,
    document.getElementById("root")
);

おわりに

ReactのLifting State Upについてまとめました.
割と使いどころが多そうなので,今のうちにマスターしておきたいです.