ベイズ 緑本 3.3.3節 補足

扱っている本について

　通称緑本。

機械学習スタートアップシリーズ ベイズ推論による機械学習入門 (KS情報科学専門書)

　今回担当が当たったので解説を作ったのですが、はてなブログ上でうまくMarkdown+Mathjax表記が出来ないので、Github pagesを利用しました。

izuna385.github.io

　記事上では、これで終わりです。（何とかしてはてなブログ上に表示できないものか。。。）

AtCoder Beginner Contest 032 C 列 （しゃくとり法）

　C++始めると言ったのに最近精進できていない。D問題に解けるものが無く一つの壁に来た感じがある（典型アルゴやれ）

問題

https://beta.atcoder.jp/contests/abc032/tasks/abc032_c 
部分列に含まれる全ての要素の値の積が、K 以下であるようなものの最長列を求める。

解法

しゃくとり法が手っ取り早い

コード（Python）

微調整を繰り返したので、釈然としないしゃくとり法になった。

他にもどこをインデックスとして回すかは問題に依るので、もっと柔軟に書けるようにしておく必要がある。

n,k = map(int,input().split())
sl = []
for i in range(n):
    sl.append(int(input()))
left = 0 
right = 0    
kouho = 0
seki = 1
for i in range(n):
    
    if sl[i] == 0:
        break
    
    right = i
    if i == 0:
        seki = sl[left]
    else:
        seki = seki * sl[right]
        
    if seki <= k:
        kouho = max(kouho,right-left+1)
        continue
    else:
        while left <= right and seki > k:
            p = left
            seki = seki / sl[p]
            left = left + 1

if 0 in sl:
    kouho = n
print(kouho)

AtCoder Beginner Contest 054 C One stroke pass

問題

https://beta.atcoder.jp/contests/abc054/tasks/abc054_c

無向グラフについて、一筆書きの経路が有るかを判定する。

やった方法

節点の数が少ないので、今回は深さ優先探索を行った。

コード

簡単な部分について、内包表記を少しずつ取り入れるようにしています。

n,m = map(int,input().split())
H = [[0 for _ in range(n)] for _ in range(n) ]

for _ in range(m):
    a, b = map(int,input().split())
    H[a-1][b-1] = 1
    H[b-1][a-1] = 1
    
l = [0 for _ in range(n)]
ans = 0

def dfs(node,visited):
    global ans
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)

                visited[node_] = 0
dfs(0,l)
print(ans)