2015
2014
2013
2007
2005
2004
アルゴリズムとデータ構造 第5章（有向グラフ[最短経路/トポロジカルソート]）・第6章（無向グラフ[最小全域木]）
第5章
ある1つの頂点から、各頂点に向かう最短経路を求めるアルゴリズム。
コストが非負の時のみに動作することに注意。頂点の数をN、辺の数をEとして、O(N**2)とO((N+E)logN)の2つのやり方がある（正直N**2の方は競プロ向けではない）。前者は完全グラフ（頂点の数Nに対し、辺の数がN**2）のような「密なグラフ」に有効。後者は、例えばE=N**2の時O(N**2logN)になり、辺の数が多いと前者よりも時間がかかってしまうデメリットがあるため、「疎なグラフ」（頂点と辺の数がほぼ同じ。この場合O(NlogN)程度になり、O(N**2)より計算量が小さい。）に有効。
O(N**2)の方はわかりやすい実装。全ての頂点について、それを経由して目的の頂点まで行くことがコストの節約につながるかを判定する。頂点を選ぶのにO(N)、それを経由して経路が短くなるかの判定を残りの頂点について確認するのにO(N)（これは内側のループ）なので、O(N**2)かかる。
用意するべきは、頂点i,j間の距離が入った二次元配列cost[i][j]、それに加えて、その頂点を途中で通過するかどうかを判断したか否かを持っておく真理テーブル、そして、最短経路が入るコストテーブルC[i]。
まず、出発点から直接行ける頂点についてコストテーブルを更新し、真理値表のスタートのところを通過済みにしておく。それから、まだ途中の経路として検討していない頂点の中で、コスト最小なものを取り上げ、それを経由した方が果たして距離が短くなるかを、すべての点について走査していく。これを、全ての頂点が途中に通過するかどうかを判定し終えるまで続ける。
O((N+E)logN)の場合もだいたいO(N**2)の時と同じ考え方で、全ての頂点が途中に通る点として考慮されるまでループを回す、というやり方をとる。ただ、頂点の管理にヒープを使うという違いがある。
用意するべきは、i番目の要素に頂点iからjに向かう経路のコストdが入ったリスト[d,j]を、N個の頂点全てについて集めたリストe。それに加えて、その頂点を途中で通過するかどうかを判断したか否かを持っておく真理テーブル、そして、最短経路が入るコストテーブルC[i]、さらに、[頂点Vまでの最短距離,Vの名前]というリストが入ったヒープが必要になる。
まずヒープの最小要素（つまり、最短距離d[V]が最も短いVのリスト[d[V],V]）を取り出し、頂点Vが経路として考慮済みであれば（真理値表を見て検討）それを捨てる。そうでなければ、Vを経路として考慮済みにし、e[V]の要素の中で、Vから次に向かう頂点e[1]が経路として未検討であれば、[e[0]+d[v],e[1]]をヒープに加えてe[1]を通過点として検討する候補に入れておく。このヒープが空になるまで操作が続く。
教科書にはコストの更新のところにif文が使われているが、これは取り出して経路として検討済みになった頂点と繋がる頂点に対して比較を行っている。距離で頂点をソートするとかいう不自然なことをしているからこんな風になっているのだが、実際はもっと単純に上記の実装をして、頂点として考慮したところだけ最短距離を更新していけばいい。（計算量自体は変わらないのだが、教科書の方が実装が圧倒的に面倒くさくてなんでこんなのを載せたのかわからない。あと流石にヒープはライブラリ使ってもいいよね......）
練習用問題
D: トレジャーハント - AtCoder Beginner Contest 035 | AtCoder
提出したコード（O(N**2)の方。N=10**2くらいのケースではACもらってますが、流石にN=10**5ではTLEします。32,43行目の不等号にイコールがつくことに注意。あと37,48行目のコストが逆になっていることに注意（一方通行であるため）。）
Submission #8640764 - AtCoder Beginner Contest 035 | AtCoder
提出したコード（O((N+E)logN)の方。こっちは上手に書けばN=10**5でもACがもらえる。ポイントはちゃんとダイクストラのマクロを組むことと、頂点の最短経路更新を一回にすること。）
Submission #8641310 - AtCoder Beginner Contest 035 | AtCoder
5.2 フロイドのアルゴリズム
ワーシャルフロイド。計算量はNの3重ループなのでO(N**3)。ある2頂点の距離を入れたリストを、残りの点を経由して通過した際に距離が節約できるかを確かめてまわるアルゴリズム。ダイクストラが1対Nの関係を求めるものだったのに対し、こちらはN対Nの全ての頂点間の最短距離が求められる。
練習用問題・提出したコード（Python3だとTLEするのでPypyで）。双方向に連結されているので、最初にcostのリストに国iと国jを結ぶ距離cを代入する際、L[i][j] = L[j][i] = cとするように。
D - joisino's travel
Submission #8640345 - AtCoder Beginner Contest 073
練習問題↓（普通のワーシャルフロイドをやるだけじゃなくて、頂点iからiへの移動コストをちゃんと0に初期化すること、そしてそれが負になったら負の閉路が存在することを判定する。cost[i][i] < 0だけで閉路判定できるの楽だね！）
Aizu Online Judge
v,e = map(int,input().split()) cost = [] for i in range(v): T = [float('inf')]*v T[i] = 0 cost.append(T) for i in range(e): a,b,c = map(int,input().split()) cost[a][b] = c for k in range(v): for i in range(v): for j in range(v): cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j]) flag = True for i in range(v): for j in range(v): if cost[i][j] == float('inf'): cost[i][j] = 'INF' elif i == j and cost[i][j] < 0: flag = False break if flag: for i in range(v): print(' '.join(map(str,cost[i]))) else: print('NEGATIVE CYCLE')
5.3 有向グラフの探索（トポロジカルソート）
閉路のない有向グラフを、順序関係でとらえなおしたものをトポロジカルソートと呼ぶ。（その順番は一意に定まるわけではない。）
受け売りの説明だが、「例えばある講義A,B,C,D,Eをとるときに、BはAとEを履修していなければならず、AとDはCを履修していなければならず、EはDを履修していなければならないとした時に、どういう順序で講義を履修すればいいか？という関係を考えたもの（ここではC→A→D→E→B）」ということらしい。
まず、それぞれの頂点に入る矢印の本数をカウントするリストins[i]、それから頂点iから向かう矢印の行き先を入れたリストouts[i]を用意する。標準入力でグラフを受け取ると、まずはins[i]==0となる頂点、すなわち入る辺が存在しない頂点から探索を始める。木でとらえ直せば、これが木の根っこということになる。
入る辺が無い頂点を「入次数0の頂点」と呼ぶ。入次数0の頂点はキューに入る。このキューをQと表すと、Q.popleft()で先頭を取り出し、最終的な答えを入れるリストに入れる。この先頭要素から出る辺の行き先に対して、ins[i]をそれぞれ-1する。ins[i]が0になったら、それは入次数が0になったということなので、Qに入れる。これを順次繰り返し、木の根っこの方から（つまりトポロジカルソートの前の方から）調べていき、Qが空になるまでそれを続ける。
練習問題↓
Aizu Online Judge
from collections import deque v,e = map(int,input().split()) ins = [0]*v outs = [[] for i in range(v)] ans = [] for i in range(e): a,b = map(int,input().split()) outs[a].append(b) ins[b] += 1 S = deque([]) for i in range(v): if ins[i] == 0: S.append(i) while len(S) > 0: cur = S.popleft() ans.append(cur) for e in outs[cur]: ins[e] -= 1 if ins[e] == 0: S.append(e) for i in range(v): print(ans[i])
練習問題↓
D - Restore the Tree
答え↓
Submission #8678690 - NIKKEI Programming Contest 2019
参考ページ↓
トポロジカルソートがわからなかったので調べてBFSで実装したのち、AtCoderの問題を解いてみた。 - Qiita
※実は、有向グラフが閉路を持たないことと、トポロジカルソート可能（トポロジカルソートした時に、要素数が元のDAGの要素数と一致する）であることは必要十分条件になっている。
有向グラフの閉路検査の問題↓（トポロジカルソート可能かだけを判定すればよい）
Aizu Online Judge
第6章
6.1 最小木
プリムのアルゴリズム
ほとんどダイクストラと構築が同じ。最小全域木（最短コストで木の各頂点を回れるようにしたもの）を構築するアルゴリズム。辺の長さをヒープで持っておいて、コストが小さい方から最小全域木を構成する辺として採用し、全部の頂点を見終わるまで続ける。
計算量は、素直な実装（n個の頂点を見て、その内側でn個の各頂点に対して、全域木までのコストを更新する）場合はO(N**2)だが、ヒープを使うことでO((N+E)logN)にすることができる。ただ、これもダイクストラと同じように、後者は密なグラフに弱い。
練習問題↓
Aizu Online Judge
import heapq n = int(input()) ans = 0 cost = [] for i in range(n): L = list(map(int,input().split())) cost.append(L) used = [False]*n used[0] = True #島0から探索を始める。 edge = [] for i in range(n): T = [] edge.append(T) for i in range(n): for j in range(n): if L[i][j] != -1: T[i].append([L[i][j],j]) P = T[0] P.sort() while len(P) != 0: cur = heapq.heappop(P) if cur[1] == True: continue cur[1] = True cur[0] += ans for e in T[cur[1]]: heapq.heappush(P,[e[0],e[1]]) print(ans)
フロイドのアルゴリズムと並んで簡単なんじゃないか？（嘘かも）これもプリム法と同じく全域木を構築するアルゴリズム。
UF木と組み合わせると楽なのでそうやって使う。[頂点A,Bを結ぶ辺のコスト,頂点A,頂点B]を要素として持つリストをまずは辺のコストでソートし、辺の短い方から使っていく。もし頂点Aと頂点Bが同じ木に属していなければ、その辺を木の辺として用いる（頂点A,Bを結ぶ）。属していれば、辺を捨てる。これを全ての辺についてやればいい。よって計算量自体は「辺を全部見るO(E)」と「辺をソートするO(ElogE)」と「UF木を構築するO(？)」になるけど、UF木を構築するのはクソ早くできるので、今回は辺のソートのみが問題になり、計算量はO(ElogE)となる。
練習問題↓
D - Built?
答えのコード↓（各頂点をもう一回インデックスつけ直して10**5までで扱えるようにする。張る辺が隣接する頂点どうしのみ考慮すればいいことから、x,yそれぞれでソートして辺の距離を出し、最大で2*(10**5)本くらいの辺に対してクラスカルのアルゴリズムをやってあげればいい。（Pythonだと流石にギリギリね）
Submission #8666576 - AtCoder Beginner Contest 065
練習問題↓
Aizu Online Judge
Logisimで遊んだ
Logisimたらいう回路を作って実際にその挙動を確かめられるシミュレータをインスコしたので、これまでのハードウェア構成法の復習（？）も兼ねて遊んでみた。というか挙動をこの目で確かめられてないのでこの際に確かめてみようってワケ。
作ってみたのはこいつら
・ハーフアダー(HA)
・フルアダー(FA)
・3ビットリプルキャリーアダー
・7ビットスライスアダー
・4ビットバイナリカウンタ
・4ビットジョンソンカウンタ
・4ビットリングカウンタ
※GIFにするのがめんどいので静止画です。すんません。
・ハーフアダー
半加算器ともいう。二つのビットの足し算をして、繰り上がりがおこるかどうかの判定をしてる。下の写真は0+1を計算してる様子。上の方が下位ビットを表しており、演算結果が01(十進法では1)なので上が立ってる。1+1なら結果は10になるので下のビットが立つ。
実装は簡単で、下位ビットと上位ビットの導出をそれぞれ分けて行えば良い。（下位ビットはXOR、上位はAND）
・フルアダー
全加算器ともいう。さっきのハーフアダーの拡張みたいな感じで、これは三つのビットの足し算の結果を返す。ハーフアダーを2つ組み合わせて使うとフルアダーになる（というかこれがハーフアダーの名の由来）。下の写真では1+1+1をしている（出力は11（十進法で3になっている）。
・3ビットリプルキャリーアダー
二進法で3桁の数字（つまり0~7）を表す二つの数字の足し算を行う。流れとしては、まず一の位の足し算を行い、その結果を受けて（繰り上がりも含めて）次に二の位、それから四の位と足し算を行う。繰り上がりの結果を持ち越す為にフルアダーを横に並べて使っているところがポイント。下の画像では7+3（つまり111+010。a1,a2,a3はそれぞれ前者の一、二、四の位。b1,b2,b3はそれぞれ後者の一、二、四の位）を行なっている様子。結果として1010（十進法だと10）が計算されてる。
※最初のFAの入力の一つはGroundに接続（つまり0が入っている）されている。
・7ビットスライスアダー
7個のビットの足し算を行い、その結果を0~7を表すビットとして返す。4つのフルアダーで実現される。
三段構成になっていて、一段目（FA2個）で6つのビットを3つ、3つにわけて足し算を行う。
二段目で、一段目の結果の一の位（2つ）と、最初に足されなかったビット1つの足し算をFAで行う。この出力で一の位が確定する。
三段目で、一段目の結果の二の位（2つ）と、二段目の結果の二の位の合計3つをFAで足し合わせて、二の位と四の位を確定させる、という流れでやっている。
下の画像では6つの1の足し算を行なっている様子。結果として110（十進法だと6）が出力されている。
・4ビットバイナリカウンタ
まずはカウンタのお話から。カウンタはその名の通り「数える」ことができる機構であり、それを回路で実現することを考える。
回路は電気信号のやりとりで動いていて、単位時間あたりのやりとりの回数（もしくはやりとり自体）を「クロック」と呼ぶ。
このクロックを「0,1のスイッチ」とみなして、これのオンオフでカウンタを動かしていくことを基本としている。
バイナリカウンタは、「n個の『ラッチ』と呼ばれる機構を用いて、0~2^n-1までを表現できるカウンタ」である。ラッチは「1ビットの状態を保存できる機構」であり、ここで保存された0,1が、表したい数字のビット列を構成している。フリップフロップとも呼ばれる。(某アイドル育成ゲームの曲ではない)
このバイナリカウンタで用いるラッチは「JKラッチ」と呼ばれるもので、このラッチは2つの入力J,Kがどちらも1である場合、出力（保存された状態）をクロックに合わせて変化させることができる。（クロックが1->0->1->0->1->0->.....と変化すると、出力Qが1->0->1->......と変化する感じ）この性質を用いて、クロックの立ち上がり（01の周期のうち、1になる時）ごとに各ラッチのバイナリの状態を変化させていくのが、バイナリカウンタの基本原理である。
[以下はLogisimの使い方であげた2つめのサイトから引用した。]
一番左のSマークがクロックで、このクロックの立ち上がり(電気が通る=1=薄い緑)で、一番左側のJKフリップフロップが動作します。クロックが薄い緑になるたびに、JKフリップフロップの出力Qが、薄い緑(=ON)または濃い緑(=OFF)になります。
出力Qを次のJKフリップフロップのクロック入力に繋げているのがポイントです。出力Qと出力~Q（Qの否定を表す。図中のQの下にある薄い「0」のところ。Qが1なら~Qは0、Qが0なら~Qは1）が交互になるという事は、入力信号に対してQは1/2でしかONにならなくなります。よって右隣りのJKフリップフロップは1/2の速度の動作になっていきます。
-
-
-
-
-
-
-
-
- -
-
-
-
-
-
-
-
以下はバイナリカウンタで2を数えている時の状態。2つ目のラッチだけQが0になっていて、そこだけ(~Q=1より）ビットが立ち上がっている。この後、クロックが再び立ち上がると、1つ目のラッチのQが0になり、~Qが1になることで一の位のビットが立つ。よって、0011（つまり3）を表すことになる。
3の次は4になる。以下の画像は3を数えた後の状態で（クロックが立ち上がって、再び0になった）次にクロックが再び立ち上がると、まず1つ目のQ（出力）が反転し、それが2つ目のラッチのクロックとして機能して2つ目のラッチのQ（出力）が反転して1になる。すると、さらに3つ目のラッチに入るクロックが立ち上がることになるので、3つ目のラッチのQも反転する。よって、1,2つ目のラッチの~Qは0になり、3つ目のラッチの~Qは1になる。以上より、0011だったビットが0100に変化し、4を表すことになる。
↓ほらね？
・4ビットジョンソンカウンタ
ジョンソンカウンタは、n個のラッチで2n個の状態を表現する。例えば、4ビットであれば、0000->1000->1100->1110->1111->0111->0011->0001->0000->......という風な変化を経ることで8つの状態を表すことができる。
構造は、Dラッチ（Dフリップフロップ）というラッチをつなげて作る。Dラッチは入力がDとクロックの二つ（ジョンソンカウンタを作る際には三つだが、これは後述する）と、出力Qの一つからなる。Dが1になったら、次のクロックの立ち上がりで出力Qが1に、逆にDが0になったらQは0になるという、DとQが1クロック分遅れた動きをする。（クロックが0の時、D,Qには影響がない）
ジョンソンカウンタは出力Qをそのまま追って見ていけばよく、ラッチの出力Qが後ろにつながるラッチの入力Dになっている（ム○デ人間とか言わない）。ただ、注意するのは最後のラッチの出力Qを先頭に巻き戻すのではなく、~Qの方を先頭の入力Dにするところである。これをしないと例で挙げたぐるっと一周しなくなってしまう。
下の図では、次に動くのは3つ目のラッチのQである。これからクロックが再び立ち上がることで、入力Dが1クロック分遅れてQに伝わり、その結果として出力を4つ並べると1110になる。
上の図では、Dラッチの二つの入力に加えて下から1が入力されている。実はこれがなくても正常に動作するのだが、これがないとこのカウンタがバグった時に元に戻らなくなってしまう。ジョンソンカウンタはn状態のうち、2n状態しか使わず、残りの2^n-2n個の状態は使われない。
もしジョンソンカウンタの内部状態がなにかの拍子でその使われない状態に遷移してしまった場合、本来実現すべき数字表現ができなくなるループに陥ることが考えられる。（例えば、4ビットの場合、0100->1010->1101->0110->1011->0101->0010->1001->0100->......というループになった場合、これは正常な動作ではない）
これを回避するために、もしこのようなまずいループに陥った時に一旦リセットをかける意味で、Dラッチの下から1が入力されている。これが1になる時、ラッチの出力Qは強制的に0になる（つまりジョンソンカウンタの0000に状態がリセットされる）。
※本当はリセットの時だけ1になるべきで、普段は0になっているべきなんですけど、実際に動かしてみたらここが0だと回路が回らなくなってしまったのでなんか間違えてるのかも？
・4ビットリングカウンタ
n個のラッチでn状態を表現するクソ贅沢なカウンタ。各状態では必ずビットが1つだけ立っており、1000->0100->0010->0001->1000->......と状態が遷移する。
ジョンソンカウンタと同じく、前のDラッチの出力Qを後ろのDラッチの入力Dにするようにつなげて使う。最初のラッチの入力Dは、最後以外のラッチの出力QのNORを取ればよい。なぜなら、最後の出力Qが1になる時以外は必ず、最後以外のどこかのラッチの出力Qが1になっているため、NORの出力は0になり、最後が1になる時だけNORが1になり、最初に入力として1を施すという仕組みが構成されるからである。
また、これもジョンソンカウンタと同じように、バグった時用のリセット手段として、Dラッチの下から1を入力しておく。
上の画像は0001の時の様子。NORが働いて最初のラッチの入力に1が入り、次のクロックの立ち上がりで最初のラッチの出力Qが1になり、1000に移行する。
Logisimの使い方↓
論理回路シミュレータ Logisim の使い方
hajimete-program.com
実際にLogisimで回路を書いている人の様子↓
www.youtube.com
回路関連で参考になりそうなページ↓
daisan-y.private.coocan.jp
risc-vでアセンブリ
2つの整数を受けとり、大きいほうを返す関数maxof2をアセンブリで実装せよ。
int maxof2(int x, int y);
とりあえずmainはこんな感じになる（と思われる）
#include <stdio.h> //main.cに保存 int maxof2(int x, int y); int main(){ int x,y; scanf("%d%d", &x, &y); printf("%d\n",maxof2(x,y)); return 0; }
最初のmaxof2という関数を実装するという趣旨の問題っぽい。
以下のどちらでも良い。
#func.sに保存 .align 2 .globl maxof2 maxof2: ble a1, a2, label1 j label2 label1: mv a0, a2 ret label2: mv a0, a1 ret
.align 2 .globl maxof2 maxof2: ble a1, a2, label1 j label2 label1: mv a0, a2 label2: mv a0, a1 ret
何がどう違うのかわからんけどまあ動いたのでヨシ！！！！！！！！
spike(risc-vのシミュレータ）のインスコは
brew install riscv/riscv/riscv-tools
でできる。
RISC-Vアーキテクチャの環境で利用できるコードを生成するためには、cの場合はただのgccじゃなくてriscv64-unknown-elf-gccでコンパイルする（これをクロスコンパイルと言う）。これでRISC-Vアーキテクチャで実行可能なプログラムが生成される。
main.cをアセンブリにかけてそれをファイルにしたい（アセンブリ言語の記述が見たい）ときは、
riscv64-unknown-elf-gcc main.c -S main.c
riscv64-unknown-elf-gcc -S main.c
のどっちでもできる。
で、実行するときは、
$ riscv64-unknown-elf-gcc main.c func.s -o main
$ spike pk main
ってやるとbbl loaderって出てくるので、下に（例えば今回は引数を受け取るので適当に2 3とでも入力すれば）出力が返ってくる（3が表示される）
チュウニズム Devastating Blaster 鳥支援解説
デバステ鳥取ったので意識したことをメモっとく。
※画像は全てCHUNITHM譜面保管所様よりお借りしました。ありがとうございました。
CHUNITHM譜面保管所
3~4,7~8小節
ノーツ同士が結構近いのでアタが出やすいです。慎重に捌きましょう。
9~10小節
1/8ノーツ×2を正確に捌きましょう。ちゃんと触ってないとミスが出やすい。
19~21,23~25小節
タップを左手2回、右手1回で「タタタン」と叩くのと、右手2回、左手1回で叩くのが途中で入れ替わる部分です。
「タタタン」のリズムは5回現れ、入れ替わる所はちょうど3回目を叩き切ったところである、ということを頭に入れておくとやりやすい。
27~29小節
19~21,23~25小節のように、「タタタン」というリズムを8回叩かされます。3回叩くのを1セットとして、入れ替わりのところを「2セット-3セット-2セット」で覚えておきましょう。
31~34小節
右始動の単純な左右交互16回を計3セット叩かされます。セットごとの切れ目は「右手で2回叩く」を意識しておくのがいいです。
3セット目は分割が入ります。左手で最後まで叩き切ることを忘れずに。
39~42小節
ノーツの分割がレーンの真ん中(もしくはそれに近いところ)に入ってます。しっかり意識して叩きましょう。
42~43小節
「タタ/タッタッタッタッ/タタタッ/タタタッ」というリズムに乗るのが案外難しいので、最初の「タタタッ」は左右交互を意識、そのあとの「タッタッタッ」は右手で全部取る、そのあとの三連×2は擦り、という運指を採用していました。
71~75小節
リズム無視して諦めて目押ししましょう。擦りは安定しにくいです。ここやるときは無心になってひたすら叩きます。（左右同時押しが入るのでこれが出来ているという感覚を持っておくと目押しが崩れにくいかも）
75~79小節
ここが個人的に最難所でした。似た箇所が前の方に出てくるものの、ここの片手トリルはかなり離れていて指を伸ばして叩くのがしんどいです。なのでトリルをやめて、3連トリルの真ん中はエアーを取っている方の手で、後ろのExタップ+フリックを巻き込むようにして取る、というやり方を採用しました。
コツとしては、後ろのEx+Flickは早く取れさえすればJC通過するので、タップを正確に取ること、そして手を広げて取ることを意識することでしょうか。
79~81小節
1回目は外（薬指）始動の両手トリル、2回目は内（人差し指）始動の両手トリルとして捌くのがいいです。ただ最後の3連はトリルではないのでこすって対処してください。
81~83小節
最初の4回連続の3連トリルはおそらく指で押すことを想定してるんだと思うのですが、最悪擦っても緑は出ないです。（というかこすったほうが安定しました）。その後の「タタッ/タタッ/タタッ/タタッ」は気持ち遅めに入るのが吉。
あとは見たまま取りましょう。
チュウニズム Glorious Crown (tpz over-Over-OVERCUTE REMIX) 鳥支援解説
こんばんは。今日は新曲の追加日ですね。そろそろCHUNITHM AMAZONも終わり名前も変わるかというところで最後の曲追加？になるのでしょうか。追加される2曲とも13、13+と高難度で今からとても期待しています。ゲーセンに開凸したいので早く寝たい。
グロクラという名前でおなじみGlorious Crown（トパゾリミ）の鳥が取れました。わいわい。
やる前は1002500くらいだったのに突然5000点伸びて乗っちゃいました。あまりの伸びに自分でもびっくりです。
以下、気をつけたところを書いていきます。譜面研究した訳ではなく、今日二回目のプレイで出てしまったものなので、偶発性の高い運指もあるとは思うのですがそこは許してください。
※画像は全てCHUNITHM譜面保管所様よりお借りしました。ありがとうございました。
CHUNITHM譜面保管所
・17~19小節
気合いで真面目に押します（擦りでも普通に行けそう）。俯瞰的な意識を持って折り返しを意識するとうまくハマると思います。ここは勝率低かったのであんま言うことないんですけど一つ一つ丁寧に処理する意識を持つとよさそう。
・33~34小節
正攻法で取れる人はすごいと思う。僕はIQ30なのでわしゃわしゃって擦りました。適当に擦る場合は、直後に左手で取る赤+Exタップをタイミング通り取ることをしっかり意識するのが大切（巻き込みアタックが怖いので）。
・52~56小節
多分この曲の中で一番難しいところ。3鍵がたくさん来るんですけど、スライドを取ってる手で取る1つ+逆の手で擦って取る2つ、に分けて取ると勝率高めです。というか階段の一つ目のノーツをタイミング良く取る意識をするのが重要っぽい（ここは表拍に合ってると思うのでリズムよく取れると思う）。
・68~75小節
Exタップとフリックを分業するやり方もあると思うんですけど、それだと思うように取れなかったので見た通りに腕を動かして取りました。腕を交換する時は分割してあるExタップを巻き込むように取ると抜けが減って安定します。
・98~99小節
「指で押しなさい！」という強い意志を感じられる場所ですが、真面目に押すためには腕が四本生えてないと不可能です。ホールドの始点にくっついているExタップにリズムを合わせて、片手の人差し指、中指の二本だけで取る意識をすると普通に通過できます。
・139~140小節
ここまで鳥許容内で、1/16ノーツを普通に指押しできる人はめちゃくちゃ肝が座ってると思います。擦ったほうが安定するので擦りました（サンプル数1）。直後の「タタタタタンッ！」に合わせてタップを取れるようにそこにも注意を払っておくのがいいです。
以上になります。上に書いてない所は普通に目押しして取りましょう。
Pythonでスクレイピング 2-4,2-5/Web API,cron
2-2,2-3をなんで飛ばしたかというと、開発中止になったPhantomJSの話が割とメインだったからです。2-3,2-4でもPhantomJSを使わない部分をかいつまんでやっていきます。
2-4
OpenWeatherMapから天気の情報を取得するコード
import requests import json apikey = '（32桁のAPIキーを入れる）' cities = ['Tokyo,jp', 'London,UK', 'New York,US'] #APIの雛形 api = 'https://api.openweathermap.org/data/2.5/weather?q={city}&APPID={key}' #絶対温度を摂氏に変換 k2c = lambda k: k-273.15 for name in cities: url = api.format(city=name, key=apikey) #formatでcity,keyの部分を置換 r = requests.get(url) #urlのデータをリクエストする data = json.loads(r.text) #JSON形式のデータをPythonのデータに変換する print('+ 都市=', data['name']) print('| 天気=', data['weather'][0]['description']) print('| 最低気温=', k2c(data['main']['temp_min'])) print('| 最高気温=', k2c(data['main']['temp_max'])) print('| 湿度=', data['main']['humidity']) print('| 気圧=', data['main']['pressure']) print('| 風向き=', data['wind']['deg']) print('| 風速度=', data['wind']['speed']) print('') print(data)
結果（一部）↓
多くのWeb APIの結果は、XMLかJSON形式で返されるとのこと。
2-5
cron（クロン）は「定期的なデータのクローリング」を行うのに便利。一般に、①データ収集②バックアップ③システム動作監視に使われる。
まあなんか設定すれば動きそうだねみたいな雰囲気を感じとって終了。
Pythonでスクレイピング 2-1/requestsモジュール
2-1
・HTTP通信
基本的に「要求に対して応答を返す」方式。ステートレス通信（同じURLのアクセスに対して、同じデータが返される通信）であり、前回どんなデータがやりとりされたかの情報を保持することはない。
・クッキー
WEBブラウザを通じてサイトの訪問者のコンピュータに一時的なデータを保存しておく仕組み。HTTP通信のヘッダーを介して入出力されることになっていて、訪問者（サイト閲覧者）が容易にデータの改変を行うことができる。
・セッション
クッキーを使ってデータを保存するのは同じだが、保存するデータは「訪問者に付与する固有ID」のみで、実際のデータはWebサーバ側に保存しておく。
セッションを利用することによって、データを保存することができるようになり、会員制サイトや通販サイトを実現できる。
requestsモジュール
本の内容と前後するけど......。
requestsモジュールでデータを取得できる。
出力の一行目は普通のテキスト、二行目はb'...'となっており、これはpythonでバイナリであることを示している。バイナリで受け取れると都合がいいのが画像データ。
これで得られる画像↓
.......。
⭐︎Webサイトにログインするプログラム（仮）
requestsモジュールを使うことで、ログインに必要な情報をポスト（入力）できたり、リンクをゲットできる。
import requests from bs4 import BeautifulSoup from urllib.parse import urljoin USER = 'JS-TESTER' PASS = 'ipCU12ySxI' #sessionでログインを行う session = requests.session() #back,mml_idはログイン時に指定する値。username_mmlbbs6みたいなのは値を入れる場所につけられた名前（ソースを見ればわかる） login_info = { 'username_mmlbbs6': USER, 'password_mmlbbs6': PASS, 'back' : 'index.php', 'mml_id' : '0' } url_login = 'https://uta.pw/sakusibbs/users.php?action=login&m=try' #本にはhttpとなっているがhttpsにしないとエラーが出る res = session.post(url_login, data = login_info) #ログインを行う res.raise_for_status() #エラーならここで例外を発生させる soup = BeautifulSoup(res.text, 'html.parser') a = soup.select_one('.islogin a') #isloginは1つしかないのでCSSセレクタで抽出 if a is None: print('マイページが取得できませんでした') quit() url_mypage = urljoin(url_login, a.attrs['href']) print('マイページ=', url_mypage) res = session.get(url_mypage) res.raise_for_status() #お気に入りデータの表示 soup = BeautifulSoup(res.text, 'html.parser') links = soup.select('#favlist li > a') #favlistの下の階層がliであることを表している（favlist > liでもいい） for a in links: href = a.attrs['href'] title = a.get_text() print('-', title, '>', href)
Pythonでスクレイピング 1-3,1-4/CSSセレクタ,再帰処理でリンク先を丸ごとダウンロード
1-3
DOM（Document Object Model）の話。正直HTMLとの違いがわかりません......。DOMの要素を引っ張ってくる為の話をしてました。
ブラウザを利用したセレクタの利用例（青空文庫で公開されている夏目漱石の作品一覧を取得するプログラム）
1:「ページのソースを表示」をクリック
2:「要素」をクリック→選択した部分の上で「要素の詳細を表示」をクリック
このようにして得られたCSSセレクタの値は
body > ol:nth-child(8) > li:nth-child(1)
となる。これは、「HTMLで上から辿っていくと、＜body＞→8番目に出てくる＜ol＞タグ→1番目に出てくる＜li＞タグが指しているのが、今回の『イズムの功過』なんだよ」という意味。こんな感じで、このページのHTMLの構造を掴んだら、いよいよ作品一覧を取得するプログラムを書く。
from bs4 import BeautifulSoup import urllib.request as req url = 'https://www.aozora.gr.jp/index_pages/person148.html' res = req.urlopen(url) soup = BeautifulSoup(res, 'html.parser') #select(セレクタ)はセレクタを複数取り出してリストの形で持つ li_list = soup.select('ol > li') for li in li_list: #ここのliは、<li><a href = ~~>（アンカーテキスト）</a>（アンカーテキスト）</li>という形をしている a = li.a #aは何も適当に決めたわけではなく、<li>の中の<a href = ~~>（アンカーテキスト）</a>を取ってきたものになる if a != None: name = a.string #aのアンカーテキストを取ってくる href = a.attrs['href'] #URL部分の取得 print(name, '>', href)
上の例では、セレクタを'ol > li'としていた。これは、「＜ol＞の直下に＜li＞がありますよ（そこからliの要素を取ってきてねん）」という意味だった。
CSSセレクタはこの他にも色々な書き方がある。（ここでは割愛）
1-4
・相対パス、絶対パスの違いの話。
https://webliker.info/78726/
＜a＞タグのリンク先が外部サイトであれば、絶対パスにしなければならない。（相対パスは、あくまで同じサーバー内での話）というわけで、相対パスを絶対パスに直すための工夫をする。
相対パスを絶対パスに直すには、urllibのparse.urljoin()を使う。urljoin(基本となるURL,解決したいパス）と入れる。
・リンク先を丸ごとダウンロードするために、途中でぶった切られないようにウェブページを再帰的にダウンロードすることが必要。
（最後に書いてあったコードは長いのでパス。まあそのうち向き合うっしょ！w）
Pythonでスクレイピング 1-2/BeautifulSoup
1-2
Pythonでスクレイピング（HTMLやXMLから情報を抽出）をするときの便利なライブラリにBeautifulSoup（綺麗なスープ！！！！？？？？？？？！？！？！！？？！！？？！？！）がある。
※「データ抽出」のみの機能であり、ダウンロードの機能はないので、そこはurllibを使って自分で組む必要がある。
BeautifulSoup使い方その１（HTMLの文字列からデータを取得する）
ア:HTMLから情報を抽出（基本ver）
from bs4 import BeautifulSoup #解析したいHTMLの例 html = ''' <html><body> <h1>スクレイピングとは？</h1> <p>Webページを解析すること。</p> <p>任意の情報を抽出すること。</p> </body><html> ''' #HTMLの解析。第一引数にhtml（上の文章）、第二引数に文を解析するもの（パーサー）を入れる。今回はHTMLなのでhtml.parserを入れる soup = BeautifulSoup(html, 'html.parser') #HTMLと同じようにアクセスできる。例えば、h1は<html><body><h1>にある要素なので、それをドットでつないでアクセス h1 = soup.html.body.h1 p1 = soup.html.body.p p2 = p1.next_sibling.next_sibling #pタグは二つあり、後ろの方（「任意の情報を抽出すること。」の一文）にアクセスするには「p1の次」というアクセスの仕方をする。1つ目のnext_siblingはp1直後の改行、スペースを得る。 #出力 print('h1 = ' + h1.string) print('p = ' + p1.string) print('p = ' + p2.string)
ア':find()を使って、任意のidで探す（アのように、ルートから一つずつ辿るのは面倒なので）
from bs4 import BeautifulSoup html = ''' <html><body> <h1 id = 'title'>スクレイピングとは？</h1> <p id = 'body'>ページから任意のデータを抽出すること。</p> </body></html> ''' soup = BeautifulSoup(html, 'html.parser') title = soup.find(id = 'title') body = soup.find(id = 'body') print('#title=' + title.string) print('#body=' + body.string)
ア'':find_all()を使って複数要素を取得
from bs4 import BeautifulSoup #ulは順序のないリストを指す。a hrefはリンクを指すタグ。 html = ''' <html><body> <ul> <li><a href='http://uta.pw'>uta</a></li> <li><a href='http://oto.chu.jp'>oto</a></li> </ul> </body></html> ''' soup = BeautifulSoup(html, 'html.parser') #flnd_all()メソッドでaタグ（リンク）を全て取り出す links = soup.find_all('a') #リンク一覧を表示。href属性（リンクの部分）はattrs['href']のようなattrsプロパティで取得できる。textはstringから。 for a in links: href = a.attrs['href'] text = a.string print(text, '>', href)
BeautifulSoup使い方その２（urlopen()を使ってリンク先を持ってくる）
郵便番号検索APIにアクセスして、郵便番号の「県」「市」「町」を表示させる
from bs4 import BeautifulSoup import urllib.request as req #ここの数字の部分を変えれば任意の住所が検索できる url = 'http://api.aoikujira.com/zip/xml/1500042' #urlopenでデータ取得 res = req.urlopen(url) #データ解析（なんでXML読んでんのにパーサーがhtmlなのかは分からん） soup = BeautifulSoup(res, 'html.parser') #soup（XMLとして読んだ情報）の中から、find('ken')なら<ken>東京都</ken>となっているところを文字列として取り出す ken = soup.find('ken').string shi = soup.find('shi').string cho = soup.find('cho').string print(ken,shi,cho)
BeautifulSoupの使い方その３（CSSセレクタを使う）
CSS(Cascading Style Sheets:要はHTMLみたいなのでできた文章のレイアウトを指定するヤツ）を指定して、その要素を抽出するみたいなことを行う。
from bs4 import BeautifulSoup #divはその部分をくくってひとまとめのグループにする意味。ulは順序のないリスト。 html = ''' <html><body> <div id='meigen'> <h1>トルストイの名言</h1> <ul class='items'> <li>汝の心に教えよ、心に学ぶな。</li> <li>謙虚な人は誰からも好かれる。</li> <li>強い人々は、いつも気取らない。</li> </ul> </div> </body></html> ''' soup = BeautifulSoup(html, 'html.parser') #select_one(セレクタ)でCSSセレクタで要素を一つ取り出す。div#meigen > h1はHTMLの木構造をイメージ。「meigenっていう名前のついたdivタグの中にあるh1」みたいな h1 = soup.select_one('div#meigen > h1').string print('h1 =', h1) #リスト部分を取得。select(セレクタ)でCSSセレクタで複数要素取り出し、リスト型で返す。 li_list = soup.select('div#meigen > ul.items > li') for li in li_list: print('li =', li.string)
まとめ
Yahoo!ファイナンスの為替情報（USD/JPY）をスクレイピングしてみる。
from bs4 import BeautifulSoup import urllib.request as req url = 'https://stocks.finance.yahoo.co.jp/stocks/detail/?code=USDJPY=X' res = req.urlopen(url) soup = BeautifulSoup(res, 'html.parser') #なぜかわからないがここのstoksprice、stocks(株式)じゃなくてstoksになってる むずむずするわね price = soup.select_one('.stoksPrice').string print('usd/jpy=', price)
実行結果(+soupの中身）はこんな感じ。
Pythonでスクレイピング 0-1,1-1/urllib
コマンドラインから実行してるけど普通にjupyter notebook入れた方が早いと思いました。まる。
0-1
・スクレイピング:Webサイトの情報を抽出すること。HTML形式で作られているWebの情報を抽出するための工夫や、広告などの不要な情報を除くためのサイトの構造解析、それに、ログイン必要なサイトの情報を抽出するための工夫などが必要。
・クローリング:プログラムがWebサイトを巡回して、情報をダウンロードすること。
機械学習ではデータを収集、抽出することが大事。その上で、これらの技術が必要。
1-1
PythonでWebサイトのデータを取得するために「urllib」を使う（urllibライブラリと書いてあったけどlibがライブラリじゃね？）
・ウェブサイトからファイルをダウンロードする方法×2
[手法1] urllib.requestモジュールの中のurlretrieve()を使う。urlretrieve(第一引数, 第二引数)の第一引数は取得したいファイルのurlを、第二引数はセーブ先ファイルの名前をつけてあげる。
import urllib.request as req #いちいちurllib.requestとか書いてるのは面倒なのでreqにする url = '（ここにファイルのurlが入る）' savename = '（適当な名前をつけて保存）' req.urlretrieve(url, savename)
[手法2] urllib.requestモジュールの中のurlopen()を使う。直接ファイルに保存するのではなく、データがPythonのメモリ上に保存される。メモリ上に保存→明示的にファイルに保存、という2ステップを踏まないとファイルに保存できない。
⭐︎with構文:開始と終了時にしなければならない作業を実行する(e.g.ファイルのオープン、クローズ/通信開始、終了)。例えば、with open〜と書けば、close()と明示的に書かなくてもclose()の処理も行ってくれる。
import urllib.request as req url = '（ここにファイルのurlが入る）' savename = '（適当な名前）' #ダウンロード、urlopen()でURLリソースを開き、read()で読み取る mem = req.urlopen(url).read() #fはセーブしたファイルを「w:書き込み」「b:バイナリ」で開いたもの。fにmem（メモリー上に保存されたファイル）を書き込む with open(savename, mode='wb') as f: f.write(mem)
・ウェブサイトからデータを取得（XML、HTML）
・IP確認APIにアクセスして情報を取得
import urllib.request as req #データ取得 url = "http://api.aoikujira.com/ip/ini" data = req.urlopen(url).read() #取得データをUTF-8（ぱっと見読める形）に変換 text = data.decode('utf-8') print(text) #表示
・任意のパラメータをつけてリクエストを送信、それに対する情報を受け取る
ア:郵便番号をパラメータとして送り、それに対応する住所を得る
import urllib.request as req import urllib.parse as parse #parseは「解析」の意、これからparserなどが出てくる API = 'http://api.aoikujira.com/zip/xml/get.php' #このAPIにアクセス予定 #変数設定 values = { 'fmt': 'xml', #ここではxmlに指定、他にもhtmlとかいろいろできる 'zn': '1100001' #検索したい郵便番号を入れる } params = parse.urlencode(values) #変数をURLに登場する形に成形（e.g.「fmt=xml」） url = API + '?' + params #URLの形はAPIで指定したアドレス+はてな+変数 print('url=', url) #データダウンロード data = req.urlopen(url).read() text = data.decode('utf-8') print(text) #表示
イ:文字を入力して、それが入ってる百人一首の句を探す
import sys import urllib.request as req import urllib.parse as parse #sys.argv変数でコマンドラインから単語を読む。sys.argv[0]はスクリプト名、sys.argv[1]にコマンドライン引数が入る。入力として何もなければ（len(sys.argv)<1）USAGE（使い方）を表示 keyword = sys.argv[1] if len(sys.argv) <= 1: print('USAGE: hyakunin.py (keyword)') sys.exit() #パラメータをURLエンコード。コマンドラインじゃなくてもここのkeyword弄れば適当に検索はできる API = 'http://api.aoikujira.com/hyakunin/get.php' query = { 'fmt': 'ini', 'key': 'keyword' } params = parse.urlencode(query) url = API + '?' + params print('url=', url) #データをダウンロードして表示 with req.urlopen(url) as r: b = r.read() data = b.decode('utf-8') print(data)
チュウニズム 定数13.7の比較的やりやすい曲で鳥を取るために意識すること
9/8~9/10の間で定数13.7の曲を5曲鳥のせてきました。（なにがあった）
ぱっと見難しいけどコツが掴めると案外イケるlarva
そこで意識したことを自分用のメモ的な感じで書いておきます。
※画像は全てCHUNITHM譜面保管所様よりお借りしました。ありがとうございました。
https://sdvx.in/chunithm/03/03089mst.htm
お品書き
・CITRUS MONSTER
・VERTeX
・larva
・ouroboros -twin stroke of the end-
・初音ミクの激唱
CITRUS MONSTER
（追記 定数.6に下がっちゃいましたね しくしく）
・18~32小節
巻き込みがヤバイので、3鍵階段よりかは2分割タップの方を意識して取っていく。階段を気持ち遅めにとる。
・90~97小節
タップスライドはちゃんと目で見て速さを確認。左始動が厳しい場合は、一旦ミラーをかけて右始動にしてからタイミングを掴む練習をして、それから改めてやるといい。
VERTeX
・8~9小節
フリックは両手で分割して取る。手がガッツリぶつかるくらいでちょうどいい。始点を意識する。
・47~50小節
リズムが難しいところ。右手側を意識する。（50小節あたりの左手の赤タップで早アタが出てしまうのを防止する）
・73小節
スライド終点にちゃんと手を置いておく。（ここに限った話ではないけどここは左手が右レーンに入るくらいなので......）
・90~106小節
乱打。左手を意識。ゆっくり目で丁寧に一つ一つ処理する。
・127~128小節
3鍵が恐ろしく早いので、右手で擦って階段を取り、それからその手を折り返して巻き込むように右側のタップを取る。厳しかったら分業してもいい。
larva
・15~16小節
腕交差が厳しければ、真ん中を中心に2レーンずつ分けた単純な左右交互として捉えて、多少大げさにエアーを取るみたいなのでもいける。
・17~24小節
乱打はひたすら「遅め」に叩くことを意識。早すぎるとミス出がち。23~24小節は擦りで通る。
・54~55小節
最初の「タン/タン/タカタン」の「タカタン」からのスライド移行がしんどいので「タカタン」は右手で擦る。（できる人はそんなことしなくていいです）
・63~69小節
ここも「遅め」を意識。
・80小節
手をわしゃわしゃやるとスライド終点が抜けて悲しくなっちゃう。
・81~82小節
Exタップとった手をいつまでもそこに置いとかないですぐ傍に避けてスライドをとる。
・90~95小節
「タタタ/タン(Ex)/タカタン」が難しい。ここも「遅め」を意識しつつ、「タタタ」はゆっくりこすって「タカタン」はガチ押し。地力の勝負。
・100~101、102~103小節
フリックは両手で分業。
・105~108小節
左右交互8回+3鍵階段2回+4鍵階段1回と見る。「遅め」意識。
・109~111小節
擦り。
・111~115小節
一番忙しいところ。しっかり見切ってガチ押し。
・116~117小節
遅め意識の餡蜜。
ouroboros -twin stroke of the end-
・6~7小節
抜けが発生する場合は、「ホールドを早く離しすぎてないか」、「Exタップまでちゃんと擦れているか」、「フリックをとる速さが適切か」をちゃんと確認する。だいたいExタップまでちゃんと擦れていれば抜けはないと思うけど......。
・10~11小節
外始動だし指押しイケるやろ（適当）丁寧に見切ること。餡蜜は非推奨。
・24~25小節
交互トリルが死ぬほどアタックが出やすいので指先でちょんちょん触る感じでとる。
・26~27小節
擦り。
・30~31、34~35小節
速い階段なので左右分業してこすったほうがいい。終点まで擦るのはもちろんだが、始点のタイミングがずれるとすぐミスが出たり、適当にこすったりすると簡単にアタックが出てしまうので慎重に。
・59~61小節
右1回と左2回が右2回と左1回に入れ替わる地味に難しいところ。指先で突くようにとると安定する。
・78~79小節
内側始動の24分。何回もやってちゃんと譜面を見ながらタイミングよく擦るくらいしか対策がありません......。
・116~117小節
6~7小節と同じ。
初音ミクの激唱
・66~69小節
右手の赤タップは二本の指でガチ押し、左手の方は擦り。
・83小節以降
ゆっくり！！！！！！！！！！！！を意識。ミスは大体タイミングが早すぎるせい。
・87~89小節
交互の直前の階段がうまく入れなかったら擦る。
・95~99小節
98小節までは丁寧に見切りながら乱打。それ以降は擦り。
・107~111小節
「タタタタン」はゆっくり目+ノーツの切れ目を意識してとる。
・113~116小節
乱打はゆっくり！！！！！！！！！！丁寧に。
