塩見周子の徒然日記

自分のことを塩見周子と思い込んでいるオタクです

復習2/6,2/7

atcoder.jp
<ずる>
O((HW)**2)とは分かったものの一個だけTLEが取れない。全部道である場合のみ特例で除外したら通ったけどこれPythonの正攻法はなんなんやろね。

atcoder.jp
<解説AC>
ロボットアームの動ける範囲の右端でソート→右端が小さい方から順番に、次のアームの左端が範囲に引っかかってたら入れない、大丈夫なら入れる、を繰り返す。右端を常に更新して管理しておくこと。

atcoder.jp
<凡ミス>
発想はあってたのに計算順序をミスったらWAが取れず1時間溶けた。たかが掛け算・割り算の順序と侮ってはいけない。次からはこういうことがないようにする。

atcoder.jp
<解説AC>
問題文の意味が理解できなかった。最初に与えられているのは「全点間の最小距離」である。
一回ワーシャルフロイドっぽいことをしてみて、与えられた全点間の距離のデータより小さくなってしまう(三角不等式において、a+b < cとなってしまうような状況。ここでa,b,cは全て「最短距離」であるはずなので、a+bがc未満になってしまうと都合が悪い)ケースが出てきてしまったら、その時点で調査を打ち切る。
a+b == cとなるケースにおいては、迂回した場合と直接向かった場合の距離が等しい→直接向かうような辺は削除してもオッケー(というか削除するべきで、なぜなら迂回した方が回れる点が多いので)なので削除。
ここで気をつけるべきは、一回削除したら「迂回するケース」の探索を打ち切ること。なぜなら、探索を続けてもう一つでもa+b == cとなるケースが出てきてしまった場合、削除すると決めた辺をもう一度消す事になってしまうから。

チュウニズム 15.75になりました

タイトルの通りです。
f:id:saguh:20200109222600j:plain

NAOKIの神威リミが収録されたのでやってきたら意外に出来たので、その勢いでレートを15.75に乗せてきました
f:id:saguh:20200109222529j:plain
f:id:saguh:20200109222543j:plain
Surrogate Lifeはいい曲


4000クレも突っ込んでました
f:id:saguh:20200109222618j:plain

ベスト枠は以下の通りです
f:id:saguh:20200109222659p:plain
f:id:saguh:20200109222724p:plain

ベ枠が15.74になってからもう2ヶ月が経ち、なかなか既存の13+に歯が立たなくて悔しい思いをしてきました(しかもレートを簡単に盛ることができない)が、ようやっと一つ目標を叶えることができました

思えば15.5になったのも去年の4月なんですね 0.25上げるのに9ヶ月かかったのか......

お金もかかるし時間も足りないので流石にもうウニ引退ですね 12月にボルテに手を出してみて、魔騎士までは取れたんですけどこれもいつまで続くのか 

アルゴリズムとデータ構造 第5章(有向グラフ[最短経路/トポロジカルソート])・第6章(無向グラフ[最小全域木])

第5章

5.1 ダイクストラアルゴリズム

ある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)
f:id:saguh:20191124023126p:plain


・フルアダー
全加算器ともいう。さっきのハーフアダーの拡張みたいな感じで、これは三つのビットの足し算の結果を返す。ハーフアダーを2つ組み合わせて使うとフルアダーになる(というかこれがハーフアダーの名の由来)。下の写真では1+1+1をしている(出力は11(十進法で3になっている)。
f:id:saguh:20191124025931p:plain


・3ビットリプルキャリーアダー
二進法で3桁の数字(つまり0~7)を表す二つの数字の足し算を行う。流れとしては、まず一の位の足し算を行い、その結果を受けて(繰り上がりも含めて)次に二の位、それから四の位と足し算を行う。繰り上がりの結果を持ち越す為にフルアダーを横に並べて使っているところがポイント。下の画像では7+3(つまり111+010。a1,a2,a3はそれぞれ前者の一、二、四の位。b1,b2,b3はそれぞれ後者の一、二、四の位)を行なっている様子。結果として1010(十進法だと10)が計算されてる。
※最初のFAの入力の一つはGroundに接続(つまり0が入っている)されている。
f:id:saguh:20191124030727p:plain


・7ビットスライスアダー
7個のビットの足し算を行い、その結果を0~7を表すビットとして返す。4つのフルアダーで実現される。
三段構成になっていて、一段目(FA2個)で6つのビットを3つ、3つにわけて足し算を行う。
二段目で、一段目の結果の一の位(2つ)と、最初に足されなかったビット1つの足し算をFAで行う。この出力で一の位が確定する。
三段目で、一段目の結果の二の位(2つ)と、二段目の結果の二の位の合計3つをFAで足し合わせて、二の位と四の位を確定させる、という流れでやっている。
下の画像では6つの1の足し算を行なっている様子。結果として110(十進法だと6)が出力されている。
f:id:saguh:20191124031758p:plain


・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)を表すことになる。
f:id:saguh:20191124035316p:plain

3の次は4になる。以下の画像は3を数えた後の状態で(クロックが立ち上がって、再び0になった)次にクロックが再び立ち上がると、まず1つ目のQ(出力)が反転し、それが2つ目のラッチのクロックとして機能して2つ目のラッチのQ(出力)が反転して1になる。すると、さらに3つ目のラッチに入るクロックが立ち上がることになるので、3つ目のラッチのQも反転する。よって、1,2つ目のラッチの~Qは0になり、3つ目のラッチの~Qは1になる。以上より、0011だったビットが0100に変化し、4を表すことになる。
f:id:saguh:20191124035939p:plain


↓ほらね?
f:id:saguh:20191124040111p:plain


・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になる。
f:id:saguh:20191124050543p:plain

上の図では、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を入力しておく。
f:id:saguh:20191124053500p:plain
上の画像は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 鳥支援解説

デバステ鳥取ったので意識したことをメモっとく。
f:id:saguh:20191017005344j:plain

※画像は全てCHUNITHM譜面保管所様よりお借りしました。ありがとうございました。
CHUNITHM譜面保管所



3~4,7~8小節
f:id:saguh:20191017004345p:plain
ノーツ同士が結構近いのでアタが出やすいです。慎重に捌きましょう。



9~10小節
f:id:saguh:20191017004427p:plain
1/8ノーツ×2を正確に捌きましょう。ちゃんと触ってないとミスが出やすい。



19~21,23~25小節
f:id:saguh:20191017004456p:plain
タップを左手2回、右手1回で「タタタン」と叩くのと、右手2回、左手1回で叩くのが途中で入れ替わる部分です。
「タタタン」のリズムは5回現れ、入れ替わる所はちょうど3回目を叩き切ったところである、ということを頭に入れておくとやりやすい。



27~29小節
f:id:saguh:20191017004520p:plain
19~21,23~25小節のように、「タタタン」というリズムを8回叩かされます。3回叩くのを1セットとして、入れ替わりのところを「2セット-3セット-2セット」で覚えておきましょう。



31~34小節
f:id:saguh:20191017004652p:plain
右始動の単純な左右交互16回を計3セット叩かされます。セットごとの切れ目は「右手で2回叩く」を意識しておくのがいいです。

3セット目は分割が入ります。左手で最後まで叩き切ることを忘れずに。



39~42小節
f:id:saguh:20191017004846p:plain
ノーツの分割がレーンの真ん中(もしくはそれに近いところ)に入ってます。しっかり意識して叩きましょう。




42~43小節
f:id:saguh:20191017004909p:plain
「タタ/タッタッタッタッ/タタタッ/タタタッ」というリズムに乗るのが案外難しいので、最初の「タタタッ」は左右交互を意識、そのあとの「タッタッタッ」は右手で全部取る、そのあとの三連×2は擦り、という運指を採用していました。



71~75小節
f:id:saguh:20191017005019p:plain
リズム無視して諦めて目押ししましょう。擦りは安定しにくいです。ここやるときは無心になってひたすら叩きます。(左右同時押しが入るのでこれが出来ているという感覚を持っておくと目押しが崩れにくいかも)



75~79小節
f:id:saguh:20191017005050p:plain
ここが個人的に最難所でした。似た箇所が前の方に出てくるものの、ここの片手トリルはかなり離れていて指を伸ばして叩くのがしんどいです。なのでトリルをやめて、3連トリルの真ん中はエアーを取っている方の手で、後ろのExタップ+フリックを巻き込むようにして取る、というやり方を採用しました。

コツとしては、後ろのEx+Flickは早く取れさえすればJC通過するので、タップを正確に取ること、そして手を広げて取ることを意識することでしょうか。




79~81小節
f:id:saguh:20191017005119p:plain
1回目は外(薬指)始動の両手トリル、2回目は内(人差し指)始動の両手トリルとして捌くのがいいです。ただ最後の3連はトリルではないのでこすって対処してください。



81~83小節
f:id:saguh:20191017005146p:plain
最初の4回連続の3連トリルはおそらく指で押すことを想定してるんだと思うのですが、最悪擦っても緑は出ないです。(というかこすったほうが安定しました)。その後の「タタッ/タタッ/タタッ/タタッ」は気持ち遅めに入るのが吉。




あとは見たまま取りましょう。

チュウニズム Glorious Crown (tpz over-Over-OVERCUTE REMIX) 鳥支援解説

こんばんは。今日は新曲の追加日ですね。そろそろCHUNITHM AMAZONも終わり名前も変わるかというところで最後の曲追加?になるのでしょうか。追加される2曲とも13、13+と高難度で今からとても期待しています。ゲーセンに開凸したいので早く寝たい。

グロクラという名前でおなじみGlorious Crown(トパゾリミ)の鳥が取れました。わいわい。
f:id:saguh:20191010012307j:plain


やる前は1002500くらいだったのに突然5000点伸びて乗っちゃいました。あまりの伸びに自分でもびっくりです。

以下、気をつけたところを書いていきます。譜面研究した訳ではなく、今日二回目のプレイで出てしまったものなので、偶発性の高い運指もあるとは思うのですがそこは許してください。

※画像は全てCHUNITHM譜面保管所様よりお借りしました。ありがとうございました。
CHUNITHM譜面保管所





・17~19小節
f:id:saguh:20191010012531p:plain
気合いで真面目に押します(擦りでも普通に行けそう)。俯瞰的な意識を持って折り返しを意識するとうまくハマると思います。ここは勝率低かったのであんま言うことないんですけど一つ一つ丁寧に処理する意識を持つとよさそう。



・33~34小節
f:id:saguh:20191010012556p:plain
正攻法で取れる人はすごいと思う。僕はIQ30なのでわしゃわしゃって擦りました。適当に擦る場合は、直後に左手で取る赤+Exタップをタイミング通り取ることをしっかり意識するのが大切(巻き込みアタックが怖いので)。



・52~56小節
f:id:saguh:20191010012706p:plain
多分この曲の中で一番難しいところ。3鍵がたくさん来るんですけど、スライドを取ってる手で取る1つ+逆の手で擦って取る2つ、に分けて取ると勝率高めです。というか階段の一つ目のノーツをタイミング良く取る意識をするのが重要っぽい(ここは表拍に合ってると思うのでリズムよく取れると思う)。



・68~75小節
f:id:saguh:20191010012925p:plain
Exタップとフリックを分業するやり方もあると思うんですけど、それだと思うように取れなかったので見た通りに腕を動かして取りました。腕を交換する時は分割してあるExタップを巻き込むように取ると抜けが減って安定します。



・98~99小節
f:id:saguh:20191010013028p:plain
「指で押しなさい!」という強い意志を感じられる場所ですが、真面目に押すためには腕が四本生えてないと不可能です。ホールドの始点にくっついているExタップにリズムを合わせて、片手の人差し指、中指の二本だけで取る意識をすると普通に通過できます。



・139~140小節
f:id:saguh:20191010013126p:plain
ここまで鳥許容内で、1/16ノーツを普通に指押しできる人はめちゃくちゃ肝が座ってると思います。擦ったほうが安定するので擦りました(サンプル数1)。直後の「タタタタタンッ!」に合わせてタップを取れるようにそこにも注意を払っておくのがいいです。




以上になります。上に書いてない所は普通に目押しして取りましょう。

夏休み やったこと

やった

  • 理情内定
  • 帰省してバイト
  • ss販売


読んだ


観た

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)

結果(一部)↓
f:id:saguh:20190919051159p:plain

多くのWeb APIの結果は、XMLJSON形式で返されるとのこと。


2-5

cron(クロン)は「定期的なデータのクローリング」を行うのに便利。一般に、①データ収集②バックアップ③システム動作監視に使われる。

まあなんか設定すれば動きそうだねみたいな雰囲気を感じとって終了。

Pythonでスクレイピング 2-1/requestsモジュール

2-1

・HTTP通信
基本的に「要求に対して応答を返す」方式。ステートレス通信(同じURLのアクセスに対して、同じデータが返される通信)であり、前回どんなデータがやりとりされたかの情報を保持することはない。

・クッキー
WEBブラウザを通じてサイトの訪問者のコンピュータに一時的なデータを保存しておく仕組み。HTTP通信のヘッダーを介して入出力されることになっていて、訪問者(サイト閲覧者)が容易にデータの改変を行うことができる。

・セッション
クッキーを使ってデータを保存するのは同じだが、保存するデータは「訪問者に付与する固有ID」のみで、実際のデータはWebサーバ側に保存しておく。

セッションを利用することによって、データを保存することができるようになり、会員制サイトや通販サイトを実現できる。

requestsモジュール
本の内容と前後するけど......。

requestsモジュールでデータを取得できる。
f:id:saguh:20190918193814p:plain
出力の一行目は普通のテキスト、二行目はb'...'となっており、これはpythonでバイナリであることを示している。バイナリで受け取れると都合がいいのが画像データ。
f:id:saguh:20190918194010p:plain
これで得られる画像↓
f:id:saguh:20190918194050p:plain
.......。




⭐︎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:「ページのソースを表示」をクリック
f:id:saguh:20190917040750p:plain

2:「要素」をクリック→選択した部分の上で「要素の詳細を表示」をクリック
f:id:saguh:20190917040941p:plain

3:要素のCSSセレクタをコピー
f:id:saguh:20190917041321p:plain

このようにして得られた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)



余談:はてな記法で書いてると、<a>とかって書いた時に普通にリンク見たいな感じになってウケる
こんな感じ