2021-05-15

Python初心者のためのABC201

AtCoder

A問題
B問題
C問題

A問題

$A_1\le A_2\le A_3$ となるように並べ替えた後，等差数列になっているかを確認すれば良い．もちろん， $A_1\ge A_2\ge A_3$ となるように並べ替えても構わない．

A = list(map(int,input().split()))

A.sort()

if A[2]-A[1]==A[1]-A[0]:
  print('Yes')
else:
  print('No')

別解を示す．条件式を変形すると，

$A_3-A_2=A_2-A_1$
$A_1+A_3=2A_2$
$3(A_1+A_3)=2(A_1+A_2+A_3)$

となる． $A_1$ と $A_3$ は $A$ の中の最小値と最大値であることを利用して，以下のように書ける．

A = list(map(int,input().split()))

if 3*(min(A)+max(A))==2*sum(A):
  print('Yes')
else:
  print('No')

B問題

atcoder.jp

Pythonのソートsortにはkeyという引数があり，並び替えるときの基準を指定することができる．

# 7で割った余りを出力する関数
def f(x):
    return x % 7

a=[2, 5, 8, 14]
a.sort(key = f)   # keyで指定した関数の値に応じて並べ替える

print(a)
> [14, 8, 2, 5]   # 7で割った余りが小さい順にソートされる

今回の場合，各要素が $[S,T$ ]（ $S$ は山の名前， $T$ は山の高さ）となっており， $T$ の値の降順に並び替える必要がある．普通にsortを用いると昇順にソートされるが，引数にreverse = Trueと指定することで降順にソートされる．

N = int(input())
mountain = []

for i in range(N):
  S,T = input().split()
  T = int(T)
  mountain.append([S,T])

# 各要素X=[S,T]が与えられたときにT=X[1]の値に応じてソートしたい 
def f(X):
  return X[1]

mountain.sort(reverse = True, key = f)
print(mountain[1][0])

別解として，山の名前と高さでリストを分けておいて，高さだけソートして2番目に高い山の高さを計算した後に山の名前を調べても良い．

N = int(input())
name = {}
height = []

for i in range(N):
  S,T = input().split()
  T = int(T)
  name[T] = S   # 高さTの山の名前はSである
  height.append(T)
  
height.sort(reverse = True)
h = height[1]   # 2番目に高い山の高さ
print(name[h])

C問題

あらゆる問題を解くことができる最強の方法は，有り得るパターンをすべて試す全探索である．唯一の欠点は，パターンの数に比例した多大な計算コストを要することである．AtCoderの問題を見たら，まずは「計算量的に全探索できるかどうか？」を考える習慣をつけておくと，全探索で解ける問題が出たときに解法を考える時間を省いて瞬時に実装へと進むことができる．

今回の場合は調べるべき暗証番号の組み合わせは $10^4=10000$ 通りと少ないため，全探索が可能である．暗証番号全てを生成する方法として，最も単純なものとしてfor pin in range(10000)が考えられるが，

整数から○桁目の数を取り出す操作に手間がかかる（一旦文字列に変換する，商と余りを用いる，など）
0埋めの操作が必要（例えば，pin = 123は暗証番号「0123」として扱う必要がある）

といった点に注意する必要がある．今回は，代わりにテクニック集でも紹介したitertools.productを使ってみる．

from itertools import product

# 0,1,...,9から4回要素を取り出す全ての組み合わせをタプルで出力する
for pin in product(range(10), repeat = 4):
  print(pin)

> (0, 0, 0, 0)
> (0, 0, 0, 1)
> (0, 0, 0, 2)
> (0, 0, 0, 3)
> (0, 0, 0, 4)
       ︙

なお，タプル()はリスト[]と似ているが，いくつか違いがある．

要素の変更ができない（当然appendなども使えない）
dictのkeyとして指定できる

暗証番号は全て生成できるようになったので，後は各暗証番号が条件をみたすかどうかをチェックすれば良い．ポイントは

oの数字は全て暗証番号に現れる
暗証番号に現れる数字は全てxでない

の2点である．oの数字，xの数字をリストなどで管理して調べていけば良い．

from itertools import product

S = input()
maru = []
batsu = []

for i in range(10):
  if S[i]=='o':
    maru.append(i)
  if S[i]=='x':
    batsu.append(i)

ans = 0

# 0,1,...,9から4回要素を取り出す全ての組み合わせをタプルで出力する
for pin in product(range(10), repeat = 4):
  
  ok = True   # 条件をみたすかどうか
  
  # 条件1
  for i in maru:
    if i not in pin:
      ok = False
      
  # 条件2
  for i in pin:
    if i in batsu:
      ok = False
      
  if ok:
    ans += 1
    
print(ans)

別解として，oの個数とxの個数から組み合わせ論的に答えを導出できるが，今回の場合は全探索のコードを書いてしまう方が早いだろう．

2021-05-10

Python初心者のためのAtCoderテクニック集

AtCoder

PythonとPyPyの使い分け
テンプレートの作成
よく使うパッケージ集
再帰に関するテクニック
拡張機能のすすめ

PythonとPyPyの使い分け

AtCoderではコードを提出するプログラミング言語を数十種類の中から選ぶことができる． Pythonのコードを書いたのであれば当然「Python」で提出すれば良いように思われるが，実は「PyPy3」という言語でも提出することができる．結論から言うと，基本的にコードは全て「PyPy3」で提出した方が良い．理由は「Python」よりも圧倒的に速いからである．「Python」ではTLEしたコードを「PyPy3」で提出したらACした，なんてことはしばしばある．

「PyPy3」を用いる上での注意点と，その対処法を以下に述べておく．

再帰関数を用いる場合は非常に遅い -> 「Python」を使う
行列計算などを行うパッケージ numpy が使えない -> 「Python」を使う
$x^{-1}\ (\mathrm{mod}\ p)$ （ $p$ は素数）を求めるために pow(x,-1,p) を用いるとエラーが出る -> pow(x,p-2,p) を用いる

テンプレートの作成

よく用いる操作は予め準備して関数として準備しておくと，コードを書くスピードを上げることができる．例えば，以下のようなテンプレートが便利である．

以下の入力を受け取るプログラムを書け．ただし，値は全て整数とする．
$N$ 　 $K$
$A_1$ 　 $A_2$ 　 $\cdots$ 　 $A_N$

# テンプレートを用いない場合

N,K = map(int,input().split())
A = list(map(int,input().split()))

# テンプレートを用いた場合

def mint():
  map(int,input().split())
def lint():
  list(map(int,input().split()))

N,K = mint()
A = lint()

最大公約数の計算には math.gcd が使えるが，2つの数の最大公約数しか計算できず，最小公倍数を計算できる関数は用意されていないため，自分で準備しておくと役に立つかもしれない．

from functools import reduce
from math import gcd

# 2数の最小公倍数の計算
def lcm(x,y):
    return x * y // gcd(x, y)

# リストに含まれる数全ての最大公約数の計算
def lgcd(l):
    return reduce(gcd, l)

# リストに含まれる数全ての最小公倍数の計算
def llcm(l):
    return reduce(lcm, l)

よく使うパッケージ集

Pythonでよく用いるパッケージを以下に挙げる．テンプレートに from ooo import xxx のように書いておくと良いかもしれない．

math：最大公約数・最小公倍数や三角関数などが扱える．
bisect：リストに対する二分探索を行う．
heapq：ヒープと呼ばれるデータ構造を扱える．最短経路問題でお馴染みのDijkstra法には欠かせない．
collections
- deque：両端キューと呼ばれるデータ構造．リストの先頭・末尾に対する要素の追加・削除を高速に行うことができる．特に先頭に対する操作は，通常のリストだとものすごく遅いので避けるべきである．
- defaultdict：初期値が指定できる辞書．通常の dict だと存在しないキーを指定するとエラーが出るが，defaultdict の場合は指定した初期値を返してくれる．初期値には set や list なども指定できる．
itertools：様々な全探索を行うことができる．
- product：複数のリストに対し各リストから要素を1つずつ取り出すような組み合わせ全てを探索する．
- permutations：1つのリストから指定した個数の要素を取り出す順列全てを探索する．
- combinations：1つのリストから指定した個数の要素を取り出す組み合わせ全てを探索する．

from itertools import product, permutations, combinations

X = [0, 1]
Y = ['A', 'B', 'C']

for v in product(X, repeat=3):
  print(v)
> (0, 0, 0)
> (0, 0, 1)
> (0, 1, 0)
> (0, 1, 1)
> (1, 0, 0)
> (1, 0, 1)
> (1, 1, 0)
> (1, 1, 1)

for v in permutations(Y, 2):
  print(v)
> ('A', 'B')
> ('A', 'C')
> ('B', 'A')
> ('B', 'C')
> ('C', 'A')
> ('C', 'B')

for v in combinations(Y, 2):
  print(v)
> ('A', 'B')
> ('A', 'C')
> ('B', 'C')

再帰に関するテクニック

再帰関数を使う場合には，以下に注意する．

PyPyじゃなくてPythonを使う
メモ化する（詳細は参考書などを参照）
以下のコードを必ず書く（テンプレートにしても良い）

import sys
sys.setrecursionlimit(500000)

1・2は高速化に関するテクニック． 3.は再帰回数の上限を引き上げるためのもの． 3.はAtCoderをPythonで行う上での最大の落とし穴といっても過言ではない．

拡張機能のすすめ

ブラウザの拡張機能を使ってAtCoderライフを快適にすることができる．詳細は以下のサイトが分かりやすい．オススメの拡張機能は以下の通り．

ac-predictor：コンテスト中にレートの変動の予測値が見られる．逆に焦りの原因になることもある．
AtCoder Difficulty Display：Atcoder Problemsで表示されている問題の難易度を表示する．
atcoder_all_open：問題ごとに別タブで一気に開く．速解きに慣れてきたら重宝する．
AtCoder Easy Test：問題ページでサンプルケースに対するジャッジを行ってくれる．コンテスト中はジャッジに時間がかかったり，たまによく分からないエラーが生じたりするので，あくまで補助的なツールとして使うと良い．
AtCoderPerformanceColorizer：レートやパフォーマンスに色付けして見やすくする．

kato-hiro.github.io

2021-05-09

Python初心者のためのABC200

AtCoder

A問題
B問題
C問題

A問題

atcoder.jp

西暦と世紀の関係を観察してみる．西暦 $N$ 年が $X$ 世紀になるとすると，

N	X
1 〜 100	1
101 〜 200	2
$\vdots$	$\vdots$
2901 〜 3000	30

どうやら

$N$ を100で割る（割った値を $N_0$ とする）

$N_0$ を整数に切り上げた値を $X$ とする

とすれば良さそう．割り算は / を使えばできるし，整数への切り上げはググると math.ceil という関数が出てくる．これらを使って，

from math import ceil

N = int(input())
N0 = N / 100
X = ceil(N0)
print(X)

とすればACできる．

しかし，この解き方はオススメしない．

Pythonの数値には，整数型 int と小数型 float の2種類がある．上のコードにおける各数値の型は以下のようになっている．

N = int(input()) # int
N0 = N / 100     # float
X = ceil(N0)     # int

今回の問題の場合は扱う数が比較的小さいので問題ないが，float の計算は一般には誤差が生じてしまう．例えば，222222222222222222を111111111111111112で割って整数に切り上げた値は1（1.999... -> 1）だが，

from math import ceil
print(ceil(222222222222222222/111111111111111112))

> 2

となってしまう．そのため，数値はなるべく int のままで扱う方が望ましい． Pythonでは，整数の割り算は // と % で行うことができる．

a, b = 7, 3
print('aをbで割った商:', a//b)
print('aをbで割った余り:', a%b)

> aをbで割った商: 2
> aをbで割った余り: 1

これを用いれば，「 $N$ を100で割った余りを整数に切り下げた値」は N//100 で求めることができる．一方，整数に切り上げた値はというと，

$a, b$ を整数とする． $\frac{a}{b}$ を整数に切り上げた値は $\lfloor\frac{a+b-1}{b}\rfloor$ で求められる．

ということを利用すれば，

N = int(input())
X = (N+100-1) // 100
print(X)

のようにしてACを得られる．上記のコードでは，数値を終始 int で扱っているため誤差の心配はない．

B問題

atcoder.jp

変数の型には，A問題で扱ったような int や float の他に，文字列 str というものが存在する．それぞれで行うことのできる操作が違うので，型にゆるいPythonといえども明示してやる必要がある．

int_100 = 100    # int
str_100 = '100'  # str

print(int_100 + int_100)
> 200

print(str_100 + str_100)
> 100100

数値に対する + は足し算だが，文字列に対する + は結合をあらわす．数値と文字列同士を足し算しようとするとエラーになる．今回の問題のポイントを整理すると，

決められた操作を $K$ 回行う -> for を使う

$N$ の値に応じて操作が異なる -> if を使う

数値的な操作と文字列的な操作の2種類がある -> int，str を使い分ける

となるので，以上を丁寧に実装してやると良い．

N,K = map(int,input().split())

# 操作をK回繰り返す
for i in range(K):

  # Nが200で割り切れるかどうかで場合分け
  if N%200==0:
    N = N//200
  else:
    N = str(N)  #文字列に変換する
    N = N + '200'
    N = int(N)  #整数に戻す

print(N)

なお，else 以下の操作は「 $N$ を1000倍してから200を足す」という操作に置き換えれば，いちいち文字列に変換する必要はなくなる．基本的に文字列の結合は遅く文字列の長さに比例した計算時間がかかるため，長い文字列の結合を扱う問題の場合には注意する必要がある．

C問題

atcoder.jp

まずは素直に実装してみる．

N = int(input())
A = list(map(int,input().split()))

ans = 0

for i in range(N):
  for j in range(i+1,N):
    if (A[i]-A[j])%200==0:
      ans += 1

print(ans)

無事TLEが得られる．この方法だと，調べる必要のある $(i,j)$ の組は ${}_{N}\mathrm{C}_2$ 通りあり， $N\le 2\times 10^5$ という制約から最大で $10^{10}$ 通り程度になる． AtCoderのジャッジシステムにおいて2秒以内で可能な計算回数は $10^7\sim 10^8$ 程度であるため，上記の解法では制限時間に間に合わないことが分かる．計算量の話をする際によくオーダーという言葉が用いられるが，上記の解法は $N^2$ に比例した計算時間がかかる $O(N^2)$ の解法である．今回の問題の場合， $O(N^2)$ の解法では例えC++などの速い言語を用いたとしてもTLEしてしまうため，別の解法を考える必要がある．

ここで $j$ を固定した場合に条件をみたす $i$ の個数の効率的な求め方を考えてみる．条件を満たす $i$ というのは，

$i \lt j$ をみたす

$A_i$ と $A_j$ を200で割った余りが等しい

ようなものである． $i$ の値自体に興味はなく， $i, j$ の大小関係と $A_i, A_j$ を200で割った余りさえ気にすればいいことが分かる．そのため，

$cnt_j[k$ ]： $A_1,\dots,A_{j-1}$ のうち200で割った余りが $k$ であるような要素の個数

のようなリストがあれば，ある $j$ に対して条件をみたす $i$ の個数は $cnt_j[A_j\%200$ ]で求められる．また， $cnt_j$ は $cnt_{j-1}[A_{j-1}\%200$ ] に1を足しただけの $cnt_{j-1}$ と等しいので， $j$ が小さい順に同じリストを使い回して値だけを更新していけば良い．

N = int(input())
A = list(map(int,input().split()))

ans = 0
cnt = [0]*200

for a in A:
  k = a % 200
  ans += cnt[k]
  cnt[k] += 1

print(ans)

なお，前処理として $A$ の要素全てを200で割った余りに変換しておいたり，最初に「 $A$ の要素のうち200で割った余りが $k$ であるような要素の個数」を求め，各 $k$ に対して「200で割った余りが $k$ であるような $A$ の異なる2つの要素を選ぶ場合の数」を求めて足し合わせても良い．

N = int(input())
A = list(map(int,input().split()))

# 各要素を200で割った余りに変換
A = [a%200 for a in A]

ans = 0
cnt = [0]*200

for a in A:
  cnt[a] += 1
  
for c in cnt:
  ans += c*(c-1)//2  # c個の要素から異なる2つの要素を選ぶ場合の数

print(ans)

いずれの解法も $N$ に比例した計算時間しかかからない $O(N)$ の解法であるため，無事ACを獲得できる．

2021-03-04

機械学習の勉強メモ

Model Architecture

PreAct-ResNet

　オリジナルのResNetは以下のような構造を持つ．

Conv. -> BN -> ReLU -> Conv. -> BN -> Add -> ReLU

ここで，Conv.は畳み込み層，BNはbatch normalization，ReLUは活性化関数，Addはshortcut connectionの加算を表す．これを以下のように修正することで精度の改善が見られた．

BN -> ReLU -> Conv. -> BN -> ReLU -> Conv. -> Add

なお．論文中ではshortcut connectionについても議論がされている（e.g. 加算時に重み付けを行う，dropoutを追加する）が，オリジナルのshortcut connectionが最も良かった．

arxiv.org

EfficientNet

　2019年に発表．CNNの性能を上げるには，

層数 $\alpha$ （深さ）
チャンネル数 $\beta$ （広さ）
入力画像のサイズ $\gamma$ （解像度）

を大きくするのが一般的だが，適切にパラメータを調整しないと，計算コストの割に性能が向上しないなんてことになる．これら3つのパラメータの関係を解析することで， $2^N$ 倍の計算資源が使える場合には， $\alpha, \beta, \gamma$ をそれぞれ $\alpha^N, \beta^N, \gamma^N$ に置き換えればいいことが分かった．なお， $\alpha, \beta, \gamma$ の初期値についてはgrid searchを行う．

Squeeze-and-Excitation

　簡単に言うと，各チャンネルに対して重み付けを行う．

def SE_block(input, channels, r):
    x = GlobalAveragePooling2D()(input)
    x = Dense(channels//r, activation="relu")(x)
    x = Dense(channels, activation="sigmoid")(x)
    return Multiply()([input, x])

各チャンネルの代表値をGlobalAveragePooling2Dで抽出（Squeeze）し，一旦チャンネル数を1/rに減らした全結合層に結合した後，元のチャンネル数と同じ全結合層から得られる値で重み付け（Excitation）する． ResNetのresidual block内に組み込むことも可能．

arxiv.org

Learning Method

Knowledge Distillation

　モデルを学習させる際，真のラベルを真値とするのではなく，学習済みモデルの出力する予測値を真値として扱う．これにより，「正解が何か」という真のラベルから得られる情報だけでなく，「どれくらい予測に自信があるか」，「他のラベルの中に正解に似ているものはあるか」などの情報も，今から学習させようとしているモデルに引き継ぐことができる．これを知識の蒸留（knowledge distillation）という．

codecrafthouse.jp

　本来は，高性能なモデルを訓練された教師モデルとして，計算資源が限られた環境で用いられることを想定した低性能なモデルに情報を受け継がせる手法である．しかし，同程度の性能を持つモデル同士で知識の蒸留を行ったり，入力に複数通りの前処理を行ったものそれぞれから教師モデルの出力を得て，出力のアンサンブルを知識の蒸留に用いたりすることで，モデルの性能の向上が確認されている．

arxiv.org arxiv.org

Data Augmentation

CutMix

　2019年に発表された画像専用のデータ拡張手法．異なるラベルの画像を切り貼りして1枚の新たな画像を作り，画像の面積比に応じてラベルをミックスさせる．従来のMixup（異なるラベルの画像を重ね，透明度に応じてラベルをミックスさせる）や Cutout（画像の一部を真っ黒にする）などの手法を上回った．

arxiv.org

Activation Function

Swish

　2016年に発表．様々な関数をユニットとして，どの関数の組み合わせが最適かを探索することにより得られた活性化関数．

$f(x) = x\cdot sigmoid(\beta x) = \frac{x}{1+e^{-\beta x}}$

ここで， $\beta$ は定数（ $\beta = 1$ が良さげ）またはtrainable parameterである． $\beta\to\infty$ とすると，SwishはReLUに一致する．

arxiv.org

Mish

　2019年に発表．Swishよりも高い性能を示した．

$f(x) = x\cdot\tanh(softplus(x)) = x\cdot\tanh(\ln(1+e^x))$

Swish ( $\beta = 1$ ) に似た形のグラフになる．

arxiv.org

Snake

　2020年に発表．活性化関数に周期性を持たせることにより外挿（観測値が得られた範囲外の予測）も可能になった．

$f(x) = x + \sin^2 x$

気温の変化，株の値動きなど，周期的な数値を予測したいときに適している．

arxiv.org

Optimization Algorithm

　Adamまでの最適化アルゴリズムについては以下の記事がめちゃくちゃ分かりやすい．簡単にまとめると，

Adam = RMSProp（学習率の調整）× momentum SGD（更新方向の調整）

ということらしい．

qiita.com

RAdam

　学習が進むにつれ学習率を徐々に小さくしていくというテクニックは一般的である．しかし，学習をランダムな初期点から始める場合，学習の初期における挙動の良し悪しは分からないという問題がある．そこで，最初の数ステップでは学習率を増加させ，一定数のステップ後は学習率を減少させるというテクニックがある．これはwarmupと呼ばれ，様々な最適化手法に対し性能を向上させている．

　2019年に発表されたRAdamは，Adamをベースに学習率を特定のルールに従ってadaptiveに調整する手法である．学習率が安定しない内はmomentum SGDで更新を行い，安定後は（補正を施した）Adamで更新する． warmupのルールを自分で決定する必要がないという利点がある．

arxiv.org

AdaBelief

　Adamのようなadaptive methodは収束が早いのに対し，SGDと比べると精度が低下する傾向にある．

arxiv.org

　2020年に発表されたAdaBeliefは，以下の3つの性質を兼ね備えている．

Adamのような収束の速さ
SGDのような精度の良さ
GANなどの複雑な設定下での安定性

学習率を調整したりSGDと切り替えたりすることなく，Adamのアルゴリズムの一部を変えているだけなので，非常に理解しやすい．

arxiv.org

Other Technique

Label Smoothing

　分類問題では損失関数にcross-entropy，真値にone-hotベクトルを用いるのが一般的．

$f(y, \hat{y}) = \sum_{i} y_{i}\log\hat{y}_{i},\quad y=(0,\dots,1,\dots,0)$

label smoothingでは，真のラベル以外に対しても正の予測値を持たせたベクトルを真値とする．

$y^{LS}_{i} = (1-\alpha)y_{i} + \frac{\alpha}{K}$

ここで， $K$ はラベルの種類数， $\alpha$ はハイパーパラメータである．例えば，3クラス分類問題において $\alpha=0.15$ とすれば， $y=(1, 0, 0)$ は $y^{LS}=(0.9, 0.05, 0.05)$ のようになる．

　下記の論文によると，label smoothingには以下の特徴がある．

出力がラベルごとにきれいなクラスターを作るようになる．
calibration効果：「自信満々のハズレ」が少なくなる．
知識の蒸留には適していない．

arxiv.org

きゃねろぐ

とある「おひさま」の徒然日記

Python初心者のためのABC201

A問題

B問題

C問題

Python初心者のためのAtCoderテクニック集

PythonとPyPyの使い分け

テンプレートの作成

よく使うパッケージ集

再帰に関するテクニック

拡張機能のすすめ

Python初心者のためのABC200

A問題

B問題

C問題

機械学習の勉強メモ

Model Architecture

PreAct-ResNet

EfficientNet

Squeeze-and-Excitation

Learning Method

Knowledge Distillation

Data Augmentation

CutMix

Activation Function

Swish

Mish

Snake

Optimization Algorithm

RAdam

AdaBelief

Other Technique

Label Smoothing