Atcoder ABC248 振り返り
A - Lacked Number【AC】
not inと書くことで，含まれていないときTrueが返ってきます．
N = input() for i in range(10): if str(i) not in N: print(i) break
B - Slimes【AC】
ドラえもんのバイバインの回を知っていれば，たとえK=2でも一瞬で10^9を超えちゃう事がイメージできます．
A, B, K = map(int, input().split()) ans = 0 while A < B : A *= K ans += 1 print(ans)
C - Dice Sum【解説AC】
DPが苦手すぎる……アルゴ式か何かでDPの徹底訓練をする必要がありそうです……
dp[i][j]=i項目まで値を決めたとき合計がjになる数列の個数
と定義します．1項目の値を決めたとき合計がjになる数列の個数は一つなのでdp[0][j]を1とします．
N, M, K = map(int, input().split()) dp = [[0 for _ in range(K+1)] for _ in range(N)] MOD = 998244353 for i in range(1, M+1): dp[0][i] = 1 for i in range(N-1): for k in range(K+1): for m in range(1, M+1): if m+k <= K: dp[i+1][m+k] += dp[i][k] dp[i+1][m+k] %= MOD print(sum(dp[-1]) % MOD)
D - Range Count Query【AC】
累積和的な考えで解きました．i番目に値Xが出現したらlist[X][i]に+1し，それぞれのlist[X]に対して累積和的を取ったら，cumsum[X][R]-cumsum[X][L]で求めることが出来ます．
しかし，これだとリストにNXの要素を持つ事が必要になり，時間が足りません．そこで，i番目に値Xが出現したらlist[X]にiをappendします．そして，LとRがlist[X]の何番目に存在するかを二分探索で求めれば，ただしい解を出すことが出来ます．
import bisect N = int(input()) A = [int(i) for i in input().split()] cumsum_dic = {a:[] for a in set(A)} for i, a in enumerate(A): cumsum_dic[a].append(i) for _ in range(int(input())): L, R, X = map(int, input().split()) L, R = L-1, R-1 try: cumsum = cumsum_dic[X] left = bisect.bisect_left(cumsum, L) right = bisect.bisect_right(cumsum, R) print(right - left) except KeyError: print(0)
Atcoder ABC186,177 振り返り
今までAtcoder Problemsを見て，一問もACしてないコンテストを選んでバーチャル参加してましたが，ついに今回でそのようなコンテストがなくなりました！次は灰diff, 茶diffを全て埋めます．
A - Brick【AC】
割り算/という演算子だけでなく，//という演算子は切り捨ての割り算をしてくれます．特に，既に割り切れる割り算9÷3でも，9/3=3.0とfloat型が返ってくるが，9//3=3とint型が返ってくるのが便利です．
N, W = map(int, input().split()) print(N // W)
B - Blocks on Grid【AC】
どのマスも同じ個数にするときの個数＝マスの最小の個数という所がポイントです．マスの最小値を求め，全てのマスに対し最小値との差を求めその和を出力します．
H, W = map(int, input().split()) A = [] min_a = 1 << 60 for _ in range(H): a = [int(i) for i in input().split()] min_a = min(min_a, min(a)) A.append(a) ans = 0 for a in A: ans += sum([i - min_a for i in a]) print(ans)
C - Unlucky 7【AC】
10進数を8進数に変換するにはoct()関数を使います．この関数はstr型で返ってくるのでinをそのまま使う事が出来ます．
N = int(input()) ans = 0 for i in range(1, N+1): if "7" in str(i): continue if "7" in oct(i): continue ans += 1 print(ans)
D - Sum of difference【解説AC】
ソートしても答えは変わらないと言うところがポイントでした．ソートしてi＜jの時が必ず成り立つなら，
が成り立つことを使います．これが成り立つなら，
を固定したときの全てのjに対する[tex: |A_i - A_j||は累積和を予め作っておくことでO(1)で求められます．累積和を使って解く方法は思い付いてましたが，ソートしても良いことに気付きませんでした……
N = int(input()) A = sorted([int(i) for i in input().split()]) cumsum_a = [0] for a in A[::-1]: cumsum_a.append(cumsum_a[-1]+a) ans = 0 for i in range(N-1): ans += cumsum_a[i+2] - (N - i)*A[i] print(ans)
A - Don't be late【AC】
Dメートルを分速Sで進むときかかる時間はD/Sです．
D, T, S = map(int, input().split()) print("Yes") if D/S <= T else print("No")
B - Substring【AC】
S<=1000と制約が小さいので，Sの部分文字列を全て列挙し，Tと異なる文字の数を数える全探索で求められます．
S = input() T = input() ans = 1<<60 for i in range(len(S) - len(T) + 1): substring = S[i:i+len(T)] change = 0 for j in range(len(T)): if T[j] != substring[j]: change += 1 ans = min(ans, change) print(ans)
C - Sum of product of pairs【AC】
ABC186Cとほぼ同じ問題でした．
N = int(input()) A = [int(i) for i in input().split()] cumpro = [0] MOD = 10**9 + 7 for a in A[::-1]: cumpro.append(cumpro[-1]+a) ans = 0 for i in range(N-1): ans += A[i]*cumpro[-i-2] % MOD ans %= MOD print(ans)
D - Friends【AC】
初めに最終的に出力する，同じグループに友だちがいないようなグループ分けをするために必要なグループ数はどのような値になるのか考えます．同じグループに友だちがいては行けないので，3人の友だちグループがあったら，最低でも必ず3つのグループを作らないといけません．
つまり，グループの数は友だちグループにいる人数の最大値であることが分かります．(1,2), (3,4,5), (6,7,8,9,10)だったとき，グループの人数の最大値は(6,7,8,9,10)の5人なので分けられるグループの数も5人です．
友だちグループの管理はUnionFindを使います．友だちグループに何人の人が居るかは，parリストの値を数えれば良いです．unite時に処理を追加すればより効率良く出来そうですが，制約が2*10^5なのでこの書き方でも間に合います．
class Unionfind: 略 N, M = map(int, input().split()) uf = Unionfind(N) for _ in range(M): A, B = map(int, input().split()) A -= 1 B -= 1 uf.unite(A, B) dic = {} for i in range(N): p = uf.find(i) dic.setdefault(p, 0) dic[p] += 1 ans = 0 for v in dic.values(): ans = max(ans, v) print(ans)
機械学習を解釈する技術 1,2章 まとめ
kaggleのように純粋に性能を求めるだけでなく，実務では意思決定者に対しモデルを説明する能力も必要だと感じ，この本を読むことにしました．
機械学習の解釈手法
本書で紹介されている解釈手法は以下の4つです．
- PFI：Permutation Feature Importance どの特徴量が重要か示す
- PD：Partial Dependence 特徴量と予測値の平均的な関係を示す
- ICE：Individual Conditional Expectation 個別のインスタンスに対して特徴量と予測値の関係を示す．
- SHAP：SHapley Additive exPlanations モデルが何故そのような予測値を出しているかの理由を示す．
解釈時の注意点
機会学習の解釈手法は，解釈性の低いブラックボックス化したモデルを解釈してくれるが，注意することもある．モデルの解釈結果から，どの程度の主張を行うかによって注意が必要である．
最も弱い主張は，解釈手法をモデルのデバッグに使う主張である．モデルの解釈結果がドメイン知識と一致しているか確認し，一致していなければデータやモデルに問題があるか確認すべきという主張である．このような使い方は，間違った解釈をする可能性が低く，安全な使い方であると言える．
次に弱い主張は，解釈手法をモデルの振るまいとして解釈する主張である．ある特徴量の値が増加したとき，モデルの予測値が大きくなるか小さくなるかが分かったとして，それを"特徴量と予測値の関係"として解釈する主張である．しかし，これはモデルの一側面を捉えているだけに過ぎないので，間違った解釈をする可能性が高い．
そして，強い主張は解釈手法を因果関係として解釈する主張である．"特徴量と予測値の関係"とするのでなく，”特徴量と目的変数の因果関係”として解釈する主張である．目的変数を予想したのが予測値なのだから，どちらも同じのようにも思えるが，両者はは異なり，目的変数の因果関係として解釈するのは強く，危ない主張である．
そもそも，因果関係を主張するには，因果推論と呼ばれる手法によりなされるものであり，機械学習の解釈手法から主張できる事柄ではない事に注意する．
線形回帰モデルが持つ解釈性
ニューラルネットや，ランダムフォレストのような複雑なモデルと比較し，線形回帰モデルは高い解釈性を持っている．
特徴量と予測値の平均的な関係の解釈
線形回帰モデル
\begin{align}
f(X_1, X_2, X_3) = β_0 + β_1X_1 + β_2X_2 + β_3X_3
\end{align}
を考える．
この式から，特徴量が1増加すると，予測値は
だけ増加する．このことから，線形回帰モデルは，回帰係数を見ることで，特徴量と予測値の関係を完全に把握することが出来る．更に，この関係はどのデータセットに対しても同一である．特徴量
を1増やすと予測値が
増えるという関係は，全てのデータセットで当てはまる．
この意味で，線形回帰モデルの回帰係数は特徴量と予測値の平均的な関係の解釈性を持つと言える．
特徴量と予測値のデータごとの関係の解釈
線形回帰モデル
\begin{align}
f(X) = β_0 + β_1X + β_2X^2
\end{align}
はXに関して線形ではない．なお，線形回帰モデルは，βに対して線形になっていれば良い．
このような例で，Xが1増加した時に予測値に与える影響は
\begin{align}
\frac{\partial f(X)}{\partial X} = β_1 + 2β_2X
\end{align}
と言える．つまり，Xが1増加した時に予測値に与える影響は，データXによって異なるという事が分かる．
このことから，線形回帰モデルは特徴量と予測値のデータごとの関係の解釈性を持つと言える．
特徴量の重要度
線形回帰モデル
\begin{align}
f(X_1, X_2, X_3) = β_0 + β_1X_1 + β_2X_2 + β_3X_3
\end{align}
について，例えばの時，予測値が最も大きく動くのは，
を動かした時である．逆に，
はどれだけ動かしても予測値は変化しない．このことから，
は重要度が低く，
は重要度が高いと言える．
しかし，特徴量のスケールが異なる場合，この限りでないことに注意する．例えば，
\begin{align}
幸福度 = 2*総資産 + 200*年齢
\end{align}
という線形回帰モデルがあったとき，回帰係数のみを見ると，年齢は総資産の100倍あり，重要度も100倍高いと言えてしまいそうである．しかし，そうではないと言える．なぜなら，年齢は高くても100前後の値しか取らないのに対し，総資産は数億から数兆まで幅広い値を取る．このように，特徴によってスケールが異なると，1増えた時の効果もスケールが異なるため，平等な比較が出来ない．
この問題を解決するために，特徴量の標準化がある．これは，一般的な標準化と同じように，各特徴量を平均0，標準偏差1となるように変形するものである．
\begin{align}
\widehat x_i = \frac{x_i - \overline{x_i}}{SD(x)}
\end{align}
SDはxの標準偏差である．
このように標準化を特徴量にすると，回帰係数はどの特徴量の回帰係数でも，"特徴量を1標準偏差だけ変化させた場合に予測値に与える影響"という意味に統一される．
こうすることで，線形回帰モデルは，予測にどの特徴量がどれほど重要なのかを知ることが知ることが出来る．
ゼロから作るDeep Learning 3 まとめ
まとめ
ゼロから作るディープラーニングシリーズの3作目でした．1は全て読み，2は途中まで読んで積んでる所でした．
3をやろうとしたきっかけは，コンペでディープラーニングのフレームワークを勉強しないといけない自覚からでした．テーブルデータ形式のコンペは何度か参加し，次は画像コンペに参加しようと思い色々調べたところ，ディープラーニングのフレームワークを避けて通るのは難しいと知りました．いきなりPyTorchなどの勉強をしてもよかったですが，ゼロからフレームワークを作るという刺激的な内容の本があるとしり，これをやることでPyTorchなどの理解もより進むというレビューを見たので，これを読もうと思い，取り組み始めました．
結果，非常に勉強になりました．特に，ディープラーニングの知識だけでなく，ソフトウェア開発や，Pythonの知識も新しくたくさん身につきました．非常におすすめの1冊です．
次はPytorchの勉強に移ります！
各ステップまとめ
第2ステージ
ステップ11~ステップ16
ステップ17~ステップ20
ステップ21~ステップ24
第3ステージ
ステップ25~ステップ32
ステップ33~ステップ36
第4ステージ
ステップ37~ステップ40
ステップ41~ステップ44
ステップ45~ステップ46
ステップ47~ステップ51
第5ステージ
ステップ52~ステップ54
ステップ55~ステップ58
ステップ59~ステップ60
Atcoder ABC192,191 振り返り
A - Star【AC】
100で割った余りを求めることで，100から溢れた数を求めることが出来ます．これを100で引く事によって，あといくつで100に到達するかを求めることが出来ます．
X = int(input()) print(100 - X%100)
B - uNrEaDaBlE sTrInG【AC】
大文字判定は.isupper()，小文字判定はislower()で出来ます．for~else文を使うとスッキリ書くことが出来ます．
S = input() for i in range(len(S)): if (i+1) % 2 == 0: if S[i].islower(): print("No") break if (i+1) % 2 == 1: if S[i].isupper(): print("No") break else: print("Yes")
C - Kaprekar Number【AC】
例えば，"123"に対して，list("123")とすると，["1", "2", "3"]と各文字を要素にしたリストになります．つぎに，["1", "2", "3"]を123という数字にしたいです．123=1*10^2 + 2*10^1 + 3*10^0という等式を利用します．1*10^2の2は"123"のlen=3から1引いた数字と分かります．そして，それを1ずつ引いていけば良さそうです．よって，["1", "2", "3"]を[100, 20, 3]というリストに変形し，それをsum()すれば，123になります．それを一行で表したのがg1, g2の行です．後はルールに沿って書けば解けます．
N, K = map(int, input().split()) for i in range(K): num_list = list(str(N)) g1 = sum([int(v)*10**(len(num_list) - i-1) for i, v in enumerate(sorted(num_list)[::-1])]) g2 = sum([int(v)*10**(len(num_list) - i-1) for i, v in enumerate(sorted(num_list))]) N = g1 - g2 print(N)
A - Vanishing Pitch【AC】
秒速Vmで進むボールはX秒後はXVm進んでます．これをつかってif文で判断します．
V, T, S, D = map(int, input().split()) print("No") if V*T <= D <= V*S else print("Yes")
B - Remove It【AC】
全てのAの要素に対して，Xと等しくないなら新しいリストA'に格納します．"○".join(["a", "b", "c"])とすると，a○b○cという文字列が返ってきます．つまり，""にある文字列をリストの各要素の間に挟んだ文字列が返ってきます．こうすると，リストをprintするときに, ["a", "b", "c"]と表示されるのを，a b cと表示することが出来ます．.join()に入れるリストは，中身の要素が全てstrでないとエラーになるので気をつけます．
N, X = input().split() A = list(input().split()) A_ = [] for a in A: if a != X: A_.append(a) print(" ".join(A_))
ゼロから作るDeep Learning 3 ステップ59~ステップ60 まとめ dezeroでRNN,LSTMを実装する
hirohirohirohiros.hatenablog.com
前回のVGGに引き続き，dezeroでRNNとLSTMを実装します！
ステップ55, 56
RNN
RNNは時系列データに対して効果を発揮するモデルです．それは，RNNが，出力を新たに入力してループする構造を持っているからです．これにより，RNNは状態を持つ事が出来ます．RNNにデータが入力されると，状態が更新されその状態に応じて出力が決まります．ループする構造を持ち，状態を保持すると言われると複雑そうに感じますが，dezeroではシンプルに実装が出来ます．
RNNの順伝播はという式で表されます．この式から分かるように，RNNは重みを二つ持ちます．一つは入力xに対する重み，もう一つは過去の出力を次の時刻の出力にする重みです．これらの入力は別々の重みとして管理します．
これをdezeroで書くとこうなります．
class RNN(Layer): def __init__(self, hidden_size, in_size=None): super().__init__() self.x2h = Linear(hidden_size, in_size=in_size) self.h2h = Linear(hidden_size, in_size=in_size, nobias=True) self.h = None def forward(self, x): if self.h is None: h_new = F.tanh(self.x2h(x)) else: h_new = F.tanh(self.x2h(x) + self.h2h(self.h)) self.h = h_new return h_new
__init__でレイヤーを二つ用意しています．そしてforwardでF.tanh(self.x2h(x) + self.h2h(self.h))として，上の式を実装しています．もちろん，一番最初の入力では，過去のデータが存在しないため，h_new=Noneとなり，F.tanh(self.x2h(x))となります．
Truncated BPTT
BPTTとはBackpropagation Through Timeの略です．これは時間を遡って逆伝播を行う事を意味します．RNNはデータの時系列の並びを学習するので，時間という単語が使われています．Truncatedは打ち切るといった意味があります．よって，Truncated BPTTは時間を遡る逆伝播を打ち切る処理になります．
RNNはデータをいくつでも与えることが出来ます．そして，その数に応じて計算グラフが長く伸びていきます．しかし，それだと逆伝播が上手く行えないので，ある程度の長さで打ち切る必要があります．これをTruncated BPTTと言います．しかし，本当に打ち切る必要性があるのか，打ち切ることでどの程度効果があるのか次の実験で試してみたいと思います．
サイン波の予測
サイン波にノイズを与えたデータを学習データとして与えて，波の形状を予測するモデルを作成します．学習データはサイン波で，テストデータはコサイン波とします．BPTTの長さを30としたときのlossの推移はこうなります．
更に，予測結果はこうなります．
少しデータに乱れがありますが，おおよそ正しく予測できていることが分かります．
Truncated BPTTの効果検証
本書ではTruncated BPTTを割と唐突に紹介され，実際なぜ必要なのか，どれくらい効果があるのかは分かりにくいため，検証してみます．同じサイン波の学習とコサイン波の予測を行ってみます．
まず，Truncated BPTTを1回も行わず，データ全てを逆伝播させて学習を行ってみます．Truncatedする長さを指定するbptt_lengthを3000に設定し，一度もTruncatedしないようにして，学習させます．lossの推移はこうなります．
bptt_length=30の時と比べ，lossの減少がだいぶ遅い事が分かります．更に，bptt_length=30の時はepoch100の時ほぼ0だったのに対し，bptt_lenght=3000では，10程度あるので学習があまり進んでないことも分かります．この状態でコサイン波を予測させるとこうなります．
それっぽい波の形状は出来てますが，全くコサイン波と一致してないことが分かります．正直ここまで学習が出来ていないとは思いませんでした……途中で打ち切るTruncated BPTTの大切さが分かります．
逆に，2回に1回は打ち切るbptt_lenghtも試してみます．bptt_length=1は過去のデータを一つも使わないので普通のニューラルネットワークとなってしまうため，bptt_length=2で試してみます．
bptt_length=30の時と同じように適切に学習が進んでいることが分かります．コサイン波の予測はこうなります．
正確に予測することが出来ています．bptt_lengthを適切に設定し，途中で逆伝播を切ってやることで，適切に学習が出来る事が分かります．
Atcoder ABC202, 201 振り返り
A - Three Dice【AC】
ある面と反対側の面を足すと7になるので，a, b, cの反対側の数は7-a, 7-b, 7-cとなるので，その和は21-1-b-cとなります．
a, b, c = map(int, input().split()) print(21-a-b-c)
B - 180°【AC】
決まった文字列の変換は辞書を使うと簡単です．
dic = {"0":"0", "1":"1", "6":"9", "8":"8", "9":"6"}
S = input()[::-1]
print("".join([dic[s] for s in S]))
C - Made Up【AC】
先に，BとCの変換を行っておきます．a in dic.keys()はO(n)かかると思うのですが実行時間はかなり短いです．辞書型のinはO(n)ではないのでしょうか……？
N = int(input()) A = [int(i) for i in input().split()] B = [int(i) for i in input().split()] C = [B[int(i)-1] for i in input().split()] dic_c = {} for c in C: dic_c.setdefault(c, 0) dic_c[c] += 1 ans = 0 for a in A: if a in dic_c.keys(): ans += dic_c[a] print(ans)
D - aab aba baa【解説AC】
なかなか難しかったです．まず，C[a][b] = "a"がa個，"b"がb個の文字列としてあり得る総数としたリストを作ります．これはDPを使って解ける基本的な問題です(ただ答えを見ないと分からなかったのでDP対策が必須です……)．
コアとなる考え方は，a?????とb?????の文字列があった時，辞書順で並び替えると，?にどのような文字を入れても全てのパターンについて，a?????
C[a-1][b]<=kの時、a???の総数がk個より少ないと言うことなので，先頭がbだと確定します．同様にそれ以降の文字を再帰的に求めます．使えbの数が1つ減ったのでb-1, kはそのままではいけません．次の文字を求めるとき，そのままだとa???の総数の情報が消えてしまうので，求めるのはk番目ではなく，kからa???の総数を引いた数です．よって，find_k(a, b-1, k-C[a-1][b])となります．
解説を読んだら理解出来るのですが自力でこれを構築するにはどうしたら良いのか……
A, B, K = map(int, input().split()) C = [[0 for _ in range(B+1)] for _ in range(A+1)] C[0][0] = 1 for i in range(A+1): for j in range(B+1): if i > 0: C[i][j] += C[i-1][j] if j > 0: C[i][j] += C[i][j-1] def find_k (a, b, k): if a == 0: return b*"b" if b == 0: return a*"a" if k <= C[a - 1][b]: return "a" + find_k(a-1, b, k) else: return "b" + find_k(a, b-1, k-C[a - 1][b]) print(find_k(A, B, K))
A - Tiny Arithmetic Sequence【AC】
等差数列なのでソートしてやれば，一つの組について調べれば答えが出ます．
a = sorted([int(i) for i in input().split()]) if a[2]-a[1] == a[1]-a[0]: print("Yes") else: print("No")
B - Do you know the second highest mountain?【AC】
文字と数値が混ざったリストも簡単にソートできます．
lis = [] for _ in range(int(input())): a, b = input().split() lis.append([int(b), a]) lis = sorted(lis) print(lis[-2][1])
C - Secret Number【AC】
有り得るパスワードの数は多くても10000個なので，全てのパスワードのパターンについて，Sが成り立つか調べても間に合います．set型を使う事で，複数同じ値が入っても一つとして扱われます．.zfillを使うと文字を簡単に0埋めできます．解き終わってから気付きましたがcould要りませんね……
S = input() ans = 0 must = set() can = set() for s in range(len(S)): if S[s] == "o": must.add(str(s)) if S[s] == "?": can.add(str(s)) for i in range(10000): musted = set() could = set() passward = str(i).zfill(4) for j in passward: if j in must: musted.add(j) if j in can: could.add(j) if j not in must and j not in can: break else: if must == musted: ans += 1 print(ans)
