塩見周子の徒然日記

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

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

Pythonによるスクレイピング&機械学習

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セレクタ,再帰処理でリンク先を丸ごとダウンロード

Pythonによるスクレイピング&機械学習

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＞とかって書いた時に普通にリンク見たいな感じになってウケる
こんな感じ

Pythonでスクレイピング 1-2/BeautifulSoup

Pythonによるスクレイピング&機械学習

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)

f:id:saguh:20190917021731p:plain
実行結果(+soupの中身）はこんな感じ。

Pythonでスクレイピング 0-1,1-1/urllib

Pythonによるスクレイピング&機械学習

https://www.amazon.co.jp/Pythonによるスクレイピング-開発テクニック-BeautifulSoup-scikit-learn-TensorFlowを使ってみよう/dp/4802610793

コマンドラインから実行してるけど普通に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曲鳥のせてきました。（なにがあった）
f:id:saguh:20190910210008j:plain
ぱっと見難しいけどコツが掴めると案外イケる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鍵が恐ろしく早いので、右手で擦って階段を取り、それからその手を折り返して巻き込むように右側のタップを取る。厳しかったら分業してもいい。
f:id:saguh:20190910210346p:plain



larva

・15~16小節
腕交差が厳しければ、真ん中を中心に2レーンずつ分けた単純な左右交互として捉えて、多少大げさにエアーを取るみたいなのでもいける。
f:id:saguh:20190910210425p:plain

・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小節
交互の直前の階段がうまく入れなかったら擦る。
f:id:saguh:20190910210537p:plain

・95~99小節
98小節までは丁寧に見切りながら乱打。それ以降は擦り。

・107~111小節
「タタタタン」はゆっくり目+ノーツの切れ目を意識してとる。

・113~116小節
乱打はゆっくり！！！！！！！！！！丁寧に。

チュウニズム　Caliburne ～Story of the Legendary sword～　鳥支援解説

音ゲー

こんにちは（午前三時）

昨日やっとこさカリバーンを鳥乗せてきました。うれしいね。わいわい。
f:id:saguh:20190907034915j:plain
1006100くらいで停滞してたのを頑張って乗せました。1日で30連奏くらいしたかも。7000以上の鳥寸も5回くらい踏んだけどなんとか。

以下、やっていくうちに気をつけなきゃいけないなと思ったところを書いていきます。こういうの書いてもどうせやるときになったらいちいち思い出していられないと思うので、こんなところを気をつけるのか程度に思っておいて、あとは自分の体に覚え込ませていくのがいいと思います。

※画像は全てCHUNITHM譜面保管所様よりお借りしました。ありがとうございました。
https://sdvx.in/chunithm/03/03089mst.htm



＜序盤＞

・16~17小節

いきなりのくの字+両手トリル。対処法としては
①見たまま押す
②くの字は擦り、両手トリルだけ真面目にとる
③全部擦り
くらいだと思いますが（僕は③はやったことがない）、①も②も上手にやれば全ピカすると思います。

ただ僕はいつまでたっても安定せず、アタが1~2個くらいここで出ていました。全部光らせるという観点から言えば①がオススメですが、くの字がうまく押せない（僕もそうです）場合は②で妥協するのもいいんじゃないでしょうか。鳥とった時は②でやってました。

①の運指
f:id:saguh:20190907033337p:plain

②の運指
f:id:saguh:20190907033418p:plain


・57~58小節

f:id:saguh:20190907033908p:plain
右利きで左手のトリルがうまくできない場合は擦りで対処しましょう。左右反転したものがもう一度出てきますがそれも同様。


・66~70、74~78小節

f:id:saguh:20190907033506p:plain
僕個人的には一番難しいと思う場所です。何回かやってみましたが安定するやり方が見つからず、合計で3~5個くらいのアタが割と出てました。
身もふたもないですが、何度もやってリズムを覚えていくしかないと思います。「タン/シャシャシャ　タン/シャシャシャ　タン　タン　タン」のリズム、わかっていてもうまく捌けないと思うのですが、もうこれは何回もやって腕に染み込ませてください。

注意することは、
①「Exタップ」と「普通のタップ+フリック×2」の間隔は無視できないので、なんとかリズム通りにとりましょう。Exタップをとってから一回手を離して無理やり空白状態を作り、赤タップを改めて取るというイメージがいいと思います。

②フリックはゆっくりめで取りましょう。Vallistaのイントロ直後のフリックの柱や、8-EMのイントロで出てくる5重フリックでも同じことですが、詰まってないフリックは「回数分だけ」「最後までしっかり」擦るのが鉄則です。

③スライドは終点までしっかり押さえましょう。判定が最後まで付いているので離すのが早すぎるとアタックが出ます。



＜中盤＞

・90~93小節

f:id:saguh:20190907033550p:plain
最初の二つのフリック、抜けるとムカついて筐体爆破したくなりますよね。

抜ける原因はおそらく擦るのが早すぎる、もしくは遅すぎる（自分は遅すぎた）です。直前のExタップについたエアーを振り下ろしでとり、両手でフリックをわしゃわしゃすると抜けなくなります。その際にスライドが抜けないようにしましょう。


f:id:saguh:20190907033628p:plain
後半の折り返しフリックは「端から端までゆっくりと」を意識してください。Halcyonに登場する折り返しフリック同様、多少手を広げて取ると安定感は増すと思います。


・96~98小節

f:id:saguh:20190907033650p:plain
ジングルベル地帯。前半3つと後半3つで、くの字の幅が違います。それに留意しながら、しっかり譜面を見て取りましょう。ちゃんと見る以外の対処法がありません......。


・107~108小節

f:id:saguh:20190907033714p:plain
108小節のところ、左手で取る赤タップ+Exタップが重なっていて非常に抜けやすいです。僕は107~108小節の部分を気持ち遅めにとって、赤タップを取った手で巻き込むようにExタップを取るように意識していました。


・118~119小節

f:id:saguh:20190907033731p:plain
ジングルベル地帯にも言えることですが、タップスライドは気持ち遅めを意識して取りましょう。あとは中指+薬指の指先で取ることを意識します。<終盤>

・121~122、123~124小節

f:id:saguh:20190907033758p:plain

①フリックを早くとりすぎるとホールドの始点でアタックが出てしまう
②一分割Exタップ×2はエアーがくっついていて、気を抜いてるとアタックが出てしまう
この二点に留意しましょう。単純なようで案外難しいです。


・134~136小節

f:id:saguh:20190907033832p:plain

右手で8分、左手で4分みたいな感じで取るのが想定解っぽいんですが、切れ目が非常に抜けやすくなかなかしんどいです。僕は鳥取った時も8分全押し+全エアーをしてました。慣れれば安定します。

コツとしては、意外と遅い（初音ミクの消失のラストほどではない）ので、手首で取ろうとするのではなくしっかり手のひらをセンサーに反応させる意識でエアーを取りながら全押しすることです。
必然的に台パンになるので周りの迷惑にならないようにしましょう。

一応想定解の運指
f:id:saguh:20190907034004p:plain


・136~138小節

f:id:saguh:20190907034042p:plain

ラストの発狂です。右手始動の16分交互12回+端から端までのタップスライド×4。普通にやるとしんどいですが、幸い（？）タップスライドは餡蜜することが可能です。

YouTubeの動画コメント欄とかに「普通に交互するとアタックが出て崩壊する」みたいなことが書いてあったりするんですけど、「多分そのまま餡蜜すると、右手でとる方の8分割タップの一番左側の赤タップを反応させるのが早すぎて、緑が確定で出てしまうみたいなことを言ってるんだろうな〜」みたいな気持ちにプレイしながらなっていました。

正直餡蜜の勝率は低くて、全部光るのは3割くらい、あとは1、2アタで抜けられたら御の字くらいでしょうか。

餡蜜の運指
f:id:saguh:20190907034114p:plain

とりあえず光らせるためのコツとしては、最初の16分交互×12の時点からすでに遅めに入っておくことです。具体的に言えばJUSTICEのうちでもSLOWの判定が出るくらいでしょうか。
気持ち遅めなのはもちろん、判定として遅いとわかってるくらいで入れば、餡蜜もそこそこうまくいくとは思います。鳥許容超えて適当に餡蜜やったらハマったみたいなこともあったので、餡蜜がうまくいかない（ATTACKが出てしまう）原因は「入りが早すぎる」一択だと思います。

あとは抜けないように、ちゃんと両手でスライダー全体をカバーできるくらいに広げておくくらいでしょうか。どうしても134~136小節を全押しでとってしまうと気持ちが焦って16分交互も早く入ってしまいがちです。ラストでも落ち着いていきましょう。鳥取った時の話ですが、すでに鳥許容の6-2だったのに落ち着いて遅めに餡蜜したら全部光ってくれました。



こんなところでしょうか。まあとにかく回数積めばなんとかなるので頑張ってください。

Python3でまったり競技プログラミング　3日目（二分探索）

精進(python3)

続かね〜〜〜〜〜〜wwwwwwwwwwwwwww

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D&lang=jp

n,k = map(int,input().split())
W = []
for i in range(n):
    W.append(int(input()))
l = max(W)-1
#トラックの積載容量は少なくとも「荷物の中で一番重いもの」を乗せられなければならない
#二分探索では、lは「これを下回ってはいけない」値に相当するので、-1しておく
#（↑一つの荷物がバカ重い場合とかは、答えがmax(W)になることは当然ある）
W.append(10**13) #1つのトラックで10**6の重さを10**6個積まないといけない場合を想定
h = sum(W)
while l+1 < h:
    ok = (l+h)//2
    track = 0
    cur = 0
    for i in range(n+1):
        cur += W[i]
        if cur > ok:
            track += 1
            cur = W[i]
        elif cur == ok:
            if i != n-1: #最後は番兵で絶対に数える事になるから、i == n-1の場合だけは数えないでおく
                track += 1
                cur = 0
    if track > k:
        l = ok
    else:
        h = ok
print(h)

Python3でまったり競技プログラミング　2日目（DP）

精進(python3)

はわわ〜〜〜〜〜〜〜〜。


今日はDP。


Edit Distance (Levenshtein Distance) | Aizu Online Judge

レーベンシュタイン距離（編集距離）は何回の操作である文字列を別の文字列に変形できるか、を表したもの。
qiita.com
詳しい説明と実装方法は上に載ってる。

s = input()
t = input()
w = len(s)+1
h = len(t)+1
dp = []
for i in range(h):
    L = [0]*w
    dp.append(L)
for i in range(w):
    dp[0][i] = i
for i in range(h):
    dp[i][0] = i
for i in range(h-1):
    for j in range(w-1):
        if t[i] == s[j]:
            dp[i+1][j+1] = min(dp[i][j],dp[i][j+1]+1,dp[i+1][j]+1)
        else:
            dp[i+1][j+1] = min(dp[i][j]+1,dp[i][j+1]+1,dp[i+1][j]+1)
print(dp[h-1][w-1])

最長増加部分列 | 動的計画法 | Aizu Online Judge

最長部分増加列(LIS)の問題。いつかに解説を書いてたのでそれ参照。





C - BBuBBBlesort!

DPじゃないけど。
n個の数字を与えられるので、それを座標圧縮（大小関係を保ったまま0~n-1に直す）して、偶奇が同じであれば1つ飛ばしのソートで適切な場所に戻せるので、偶奇が異なる部分がいくつあるかを数えればいい。

例えば、
1 3 2 4 5 7 6
は、
1 2 3 4 5 6 7
と4箇所違うので、2回の入れ替え（4÷2）が必要になる、みたいな。

Python3でまったり競技プログラミング　1日目（貪欲法）

精進(python3)

プログラミング最近全然やってなかったのでリハビリ。1週間続くかな。続くといいな。

実践的プログラミングの資料から適当に抜粋してやっていこうと思う。

Make Purse Light | Aizu Online Judge

coin = [10,50,100,500,999999]
J = True
while True:
    n = int(input())
    if n == 0:
        break
    else:
        if not J:
            print()
        else:
            J = False
        L = list(map(int,input().split()))
        S = 10*L[0]+50*L[1]+100*L[2]+500*L[3]
        res = S-n #とりあえず硬貨を全部使ったものと仮定する
        change = [res%coin[i+1]//coin[i] for i in range(4)] #ここでお釣りとしてどの硬貨が何枚戻ってくるかを計算している
        
        for i in range(4):
            if change[i] < L[i]: #お釣りとして戻ってくる枚数の方が少なければ採用
                print(coin[i],L[i]-change[I])

最初、各硬貨は20枚までと決まってるし全探索すれば（1ケースあたり20**4通り）まあいけるやろ〜〜〜なんて安易に考えてたら普通に通りませんでした。

というか普通に発想自体難しくてワロタよ
日本の硬貨は、それより小さい金額のお金が大きい金額を割り切るという特質があるため、「大きい金額で払えるならばできるだけ支払った方が得（枚数が少なくて済む）」という戦略が取れます。そうでない場合は違う戦略をとる必要が出てくる。







※通らなかったコード　供養

while True:
    n = int(input())
    if n == 0:
        break
    else:
        L = list(map(int,input().split()))
        S = sum(L)
        ans = float('inf')
        coin = [10,50,100,500]
        for i in range(21):
            for j in range(21):
                for k in range(21):
                    for l in range(21):
                        if i <= L[0] and j <= L[1] and k <= L[2] and l <= L[3]:
                            t = i*10+j*50+k*100+l*500
                            if n-t > 0:
                                None
                            elif n-t == 0:
                                ans = S-(i+j+k+l)
                                p = [i,j,k,l]
                            else:
                                cur = S-(i+j+k+l)
                                z = t-n
                                cur += z//500
                                z = z-(z//500)*500
                                cur += z//100
                                z = z-(z//100)*100
                                cur += z//50
                                z = z-(z//50)*50
                                cur += z//10
                                if cur < ans:
                                    ans = cur
                                    p = [i,j,k,l]
        for a in range(4):
            if p[a] != 0:
                print(coin[a],p[a])
        print()

東京大学理学部情報科学科に内定しました

日常

こんにちは。とーです。

タイトル通りです。第一段階で決まってよかったなあという気持ちです。

思えば、自信満々で大学初の成績表をもらった時に、数理科学演習「可」の文字に驚愕してから一年と二ヶ月。あれから割と頑張ってきたんじゃないのかな、なんて思います。平均点も82.02点まで持ってくることができました。

これからの道のりは絶対にこの比ではないほど厳しいと思いますが、なんとかドロップアウトしない程度には頑張っていきたいと思います。それでは。

人間行動基礎論　まとめ

お勉強

テスト勉強ということで、授業のまとめをします。
基本的に一問一答のような感じで



・イアン＝パブロフ
ソ連の生理学者。「パブロフの犬」の実験で知られる。犬に、ベルを鳴らしてから餌を与えることを繰り返した結果、犬はベルを鳴らしただけで唾液を出すようになった。このように、動物が後天的に獲得する反射の事を条件反射と呼ぶ。これは学習の中でも特に「古典的条件付け」にあたる。

・フィリップ＝ジンバルドー
アメリカの心理学者。スタンフォード監獄実験の責任者として知られる。刑務所を舞台とし、普通の人が特殊な肩書きや地位を与えられると、その役割に合わせて行動するようになることを証明しようとした実験を行った。結果として、看守役を任された人間は残忍に、囚人役を任された人は従順に振る舞い、状況の力が人間に与える影響を示したが、のちに刑務所長役の人物が、看守役に残忍に振る舞うよう指示していたことが判明する。

・賢いハンス
ドイツにいた馬。計算ができる馬として有名であったが、実際は質問者や観客の反応を察知しているだけであるとわかった。実験者の「こういう結果になってほしい」という願望が被験者に影響を与えてしまう「実験者効果」の例で知られ、心理学実験において実証的な裏付けの必要性を示した。

・心理学ではなぜ実証的な証拠を重視する？
①現実の問題を扱うため。
②現代社会で最も合意の取りやすい理由づけだから。
③事実に基づく結論であれば、あとで修正が可能だから。

・心理学の歴史
1879年に、ヴントがドイツのライプツィヒ大学で心理学実験室を創設する。のちに、19世紀後半は構成主義、20世紀前半は要素批判主義（ゲシュタルト心理学）や古典的行動主義、20世紀後半は認知主義と変遷していく。

・ヴントの心理学
化学モデルを用い、意識を要素に分解し、それらの間の結合法則を明らかにするという考え方の、要素主義と構成主義からなる。また、心的要素を五感からなる純粋感覚や、快ー不快、興奮ー鎮静、緊張ー弛緩などの簡単感情に分け、これらの複合体として意識があると考えた。また、「内観」を用い、実験で明らかにできない側面を言語報告で行なった。

・ゲシュタルト心理学
ヴントの構成主義を批判する形で、20世紀初頭にドイツで生まれた心理学。人間の精神は部分の総和ではなく、それ以上のものであると考え、全体性に重点を置いている。

・古典的行動主義
二度の大戦を経て学問の中心がアメリカに移り、そこで興った。J.B.ワトソンはドイツ心理学の内観法を批判し、主観を排した客観的データに基づく科学的な手法を考え、刺激（S)と反応（R）との関係を重視した。しかし、客観性は程度問題であり、客観性にこだわりすぎたために思考や言語、創造性や悩みなどの客観的に観察できないものが検討できなくなってしまう欠点もあった。

・バンデューラのボボ人形実験
1950年代、テレビが家庭に普及し始めた。テレビの影響と暴力との間に関係があるのではないかと考えられ、「暴力を観察すると暴力的になるのではないか」という仮説が立てられ、それを検証するためにこの実験が行われた。独立変数は、暴力を観察するかどうか（人形を殴る大人、普通に遊ぶ大人）で、従属変数は、暴力行動の生起（人形に対する暴力の回数、程度を測定）である。結果として暴力を見ると子供は暴力的になることがわかった。これに性差、人種差はなかった。

・心理学における二種類の研究法
実験的研究と、観察的研究の二種類がある。前者は、独立変数を変え、従属変数を測定するもので、因果関係を見るタイプ。人工的に作られた実験環境であり、倫理的な問題を回避するのが難しい。一方、後者は、予測変数と基準変数を測定し、相関関係を見るタイプ。現実の状況を対象にするため、倫理的な問題が起こりにくい。

・心理学研究の難しさ
ノイズが多かったり、測定条件を均一にすることが難しい。そのため、再現可能性が低いという問題も多かった。現在、それをなんとかするためにも、追試を促進するためにデータを公開するなどの対策が取られている。

・知覚が能動的である例
資格を反転させるメガネをかけた状態でずっと生活していると、いつしか視界が逆転して元にもどるというもの

・眼球運動が知覚に関係している例
トロクスラー効果（円環状に配置された色のドットのど真ん中を見ていると、それが見えなくなってしまう現象）

・視覚のモジュール構造の例
ミュラーリヤーの矢を見て、二つの矢が同じ長さであると知識では理解しているとしても、同じ長さに見えてしまうというもの

・カプセル化したモジュール
カプセル化とは、他との連絡が極めて制限され、認知的に不可侵であることを指す。例として、脳の左右半球がある。左側にKey/右側にRingと見せられると、脳の左半球に言語野があるため、'Ring'と発音できるが、運動野は右半球にあるために、右側のRingを取ることができない、というもの。

・脳の損傷、それによって与えられる示唆
MT野の損傷によって、運動が見えなくなる（ストロボ写真のように見える）だとか、他の部位の損傷で色が見えない、顔がわからないなどの現象は、それぞれ独立して起こるため、視覚情報はモジュールごとに別々に処理され、それらが統一されることで、初めて視覚経験を生んでいる。

・「何経路」と「どこ経路」
「何経路」とは、後頭葉から側頭葉に至る経路で、物体の形状を把握する。「どこ経路」は後頭葉から頭頂葉に至る経路で、空間認識や場所認識に関わる（左と右の弁別など）。

・脳内の情報処理
制御処理と自動処理。熟達した制御処理が自動処理になる。

・ジョナサン＝ハイトの例え
欲求、感情の方が、意志や理性よりも圧倒的に強い、ということを「象と乗り手」と例えた。

・道徳のジレンマ
公にされない不道徳な行為の是非について問うと、労働者階級の方が知識階級より圧倒的に「罰するべき」と答えた。知識階級の人々は、公共の福祉に反しない限りは自由が尊重されるという考え方が無意識的に働くため、許容する答えが多くなった。道徳のジレンマは、理性がそれを許容するが、感情はそれを許容できないことを示している。

・感情とは
適応的な身体的反応（闘争ー逃走反応）。複合的な性質を持っていて、身体の生理的賦活（体温上昇、発汗）や行動としての表現（叫ぶなど）、その意識（悲しみ、怒り）などがある。

・感情が生じる二つの説と、それらの妥当性
キャノン、バードという二人の人物が、感情の中枢起源説という考えを提唱した。これは、認識をしてから感情生起があるという考え方で、電鋸で手首を切るビデオに「無音」、「役者が声をつけたと説明」、「実際の映像と説明」した場合、認識により恐怖のレベルに変化が生じたというのが妥当性の補強をしている。簡単に言えば、「怖いから叫ぶ」ということである。
一方、ジェームズ、ランゲという二人の人物は、感情の抹消起源説を提唱した。これは、感情生起から認識に繋がるという考え方で、表情を無理やり作ると、それに伴って感情が変化するという実験を行い、妥当性を示した。これも簡単に言うと、「叫ぶから怖い」という感じ。

・感情が文化普遍的であるという考えの中心人物
ダーウィン、エクマン

・感情の次元説の2軸
興奮⇆安静、快⇆不快

・興奮と、それがパフォーマンスに与える影響
ヤーキス・ドットソンの法則は、課題レベルに対して中程度の興奮があったほうが、パフォーマンス的には一番良いということを示している。

・闘争＝逃走反応
キャノンによって提唱された、動物の恐怖への反応のこと。動物は、恐怖に反応して自身に戦うか逃げるかを選択をさせる。それに伴い、心臓や肺の機能が高まるといった、適応的な身体的反応が可能になる。

・基本六感情
怒り、悲しみ、喜び、嫌悪、不安、恐れの6つの感情を指す。エクマンは、これらの感情が文化普遍的にあると考えた。

・トロクスラー効果
円環状に色を配置し、真ん中を見つめているとその周辺の色が消える、つまり色が見えなくなる現象。強制的に眼球運動を止めると見えなくなる例として知られ、知覚の能動性を示す効果である。

・記憶、とは一言で言うとどういうものか
過去の経験を保持し、のちにそれを再現し、利用する機能

・記憶の種類、時間的な区分
感覚記憶、短期記憶、長期記憶

・系列位置効果
系列の最初の方を覚えている「初頭効果」と、最後の方を覚えている「終末効果」から成る。前者は少し間隔をおいても残るが、後者は短期記憶を反映しているため、数十秒で失われる。

・記憶の種類を内容で区分
エピソード記憶、意味記憶、手続き記憶（自転車に乗る→手続き記憶）

・手続き記憶
精神、身体における一連の作業記憶
技能（発話、計算）、古典的条件付け（パブロフのイヌなど）、知覚運動学習（自転車など）

・学習
経験を通じて起こる、行動の比較的永続的な変化。一時的な変化は学習とは言わず、一般的な勉強以外も学習になりうる。環境と生体との相互作用がもたらす、一連の行動変容のこと。

・条件付け
古典的条件付け（レスポンデント条件付けとも言う。パブロフの犬が有名）、道具的条件付け（オペラント条件付けとも言う。スキナー箱が有名）

・随伴性
行動と、その直後との変化の関係を表す。例えば、ある行動を強化する際に、行動の後に報酬が出れば快を感じ、その行動が強化されるというもの。

・評価的条件付け
情動的な刺激と対提示されると、情動に対応した評価が下されてしまうというもの。

・無力感
無力感は、①自分で状況を統制できない、②状況を予測できない、という二つの条件の時に学習される。圧迫的な罰によって無気力になってしまうと、他の学習まで止まってしまうという悪影響が生じる。

・孵化効果
解けない問題が放っておくと解けるようになる現象。これは、誤った問題表象を忘れ（制約の解放）、問題を改めて理解し（再符号化）、新たな情報を得る（精緻化）を行なっている。解が一つに定まる収束的思考問題より、解が様々あって、創造的な問題解決が求められる発散的思考問題において有用性が高い。

・創造性
新奇性があり、適切なアイデアで物を作り出す能力。

ベルマンフォード法

精進(python3)

ある一点からスタートし、そこから残りの全ての頂点に達するのに必要な最短コストを計算するときに使える。計算量は、頂点V、辺の数EとしてO(VE)。負の辺があっても使えるのが、ダイクストラ法と違うところ（強み）。

構造は単純で、頂点の数vから1引いた数だけループを回す。つまり、始点以外のv-1個の頂点に対して最短経路を出すには、多くてもv-1回回せば十分ということだ。それ以上やっても更新できない（逆に、更新できてしまったら、ループ上を周回することで無限にコストを小さくすることができる「負のループ」が存在することになってしまう）。
そして、多くてもv-1回のループに対して、すべての辺を参照する。始点と繋がってる頂点から伸びた辺を介して、到達可能な点がじわじわ増えていく印象。全ての辺を見ても更新がなければ、もうそれで最短経路が確定しているのでそこでループを打ち切って、答えを出力する。（ここの省エネがないと結構時間がかかったりする）



judge.u-aizu.ac.jp

答え↓

v,e,r = map(int,input().split()) #v:頂点数、e:辺数、r:始点
D = [float('inf')]*v #D[i]は始点rからiの最短距離を表す、0インデックス
L = []
find_negative = False #負のループ検出
for i in range(e):
    s,t,d = map(int,input().split()) #s:始点、t:終点、d:コスト
    L.append([s,t,d])
D[r] = 0 #スタート地点はコスト0で到達可能
for i in range(v):
    update = False #辺の更新判定
    for j in range(e):
        a,b,c = L[j][0],L[j][1],L[j][2] #a,b,cはs,t,dに相当
        if D[b] > D[a]+c: #bに到達するのに、aを介した方がいいとなれば
            D[b] = D[a]+c コストを更新
            update = True
            if i == v-1: #v回のループでまだ更新があるようであれば、
                find_negative = True #負のループが存在する
                break
    if not update: #全ての辺を見ても最短経路の更新がなければ
        break #これ以上やる意味がないのでここでループを抜ける
if find_negative:
    print('NEGATIVE CYCLE')
else:
    for i in range(v):
        if D[i] == float('inf'):
            print('INF')
        else:
            print(D[i])

幅優先探索（BFS）、深さ優先探索（DFS）の問題

精進(python3) 精進　まとめ

幅優先探索と深さ優先探索は似たような問題をカバーできるけど、幅優先の方があんまり考えなくても実装できる（気がする）。幅優先はキュー、深さ優先はスタックと仲良し。


幅優先探索


幅優先探索は、基本的に「次に訪れる島」をキューの形で保持しておくことが肝要です。import collections、collections.deque()、popleft()のおまじないを使っていきましょう。

幅優先探索を使う問題

A - Darker and Darker
（手数計算）
横wマス、縦hマスのグリッドがあり、白と黒で塗られている。1ターンごとに現在ある黒マスの上下左右を黒で塗る操作をすると、何ターンで全てのマスが黒マスになりますか、という問題。
最初の黒マスをターン0で塗れるものとし、1ターンごとに見ていき、次のターンで塗ったマスを手数+1足してキューに追加、それをキューが空になるまで続ける。全てのマスの中で最も手数が大きいものを出力。（Python3だとTLEする可能性がある）

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1130&lang=jp
（連結判定）
グリッド上に連結な点がいくつ存在するかを求める問題。

C - 幅優先探索
（最短経路）
迷路を幅優先で解く。一番上の問題とほぼ同じ要領でできる。

D: Grid Repainting - AtCoder Beginner Contest 088 | AtCoder
（最短経路）
実質迷路を解くのと同じ。最短経路のマス、#マス、.マスをそれぞれカウント。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C&lang=jp
（最短経路）
有向グラフの最短距離は幅優先探索を使うといい。ワーシャルフロイドみたいなのは無向グラフとかで使おうね。




深さ優先探索


深さ優先探索は、次に訪れる島の情報をスタックの形式で保持しておくイメージです。行けるところまで行ったら戻ってくる、みたいな「わかりそうだけどわからない」説明よりかはデータ構造の違いでコードを書いていきたい。

深さ優先探索を使う問題

A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder

スタックを使う実例を下に載せる。

h,w = map(int,input().split())
C = []
stack = []
visited = []
for i in range(h):
    T = [0]*w
    visited.append(T)
for i in range(h):
    s = input()
    L = []
    for j in range(w):
        L.append(s[j])
        if s[j] == 's':
            stack.append([i,j])
            visited[i][j] = 1
    C.append(L)
dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]
flag = False
while len(stack) > 0:
    now = stack.pop()
    if C[now[0]][now[1]] == 'g':
        print('Yes')
        flag = True
    for i in range(4):
        y = now[0]+dy_dx[i][0]
        x = now[1]+dy_dx[i][1]
        if 0 <= y < h and 0 <= x < w:
            if C[y][x] != '#' and visited[y][x] == 0:
                visited[y][x] = 1
                stack.append([y,x])
if not flag:
    print('No')

C - One-stroke Path

for文を使った再帰のような形。むずかし。

N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
cnt = [0]
def dfs(V, s):
    V[s] = 1
    if sum(V) == N:
        cnt[0] += 1                    
    else:
        for adj in G[s]:
            if V[adj] == 0:             
                dfs(V[:adj] + [1] + V[adj + 1:], adj)  #ここで分岐がたくさん発生する
dfs([0] * N, 0)
print(cnt[0])


D - Fennec VS. Snuke

今見た島の隣の島を見る素直な実装で解ける。

n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
visited = [0]*n
visited[0] = 1
visited[n-1] = 1
visited_all = [1]*n
nextF = edge[0]
nextS = edge[n-1]
black = 1
white = 1
while visited != visited_all:
    l = []
    for f in nextF:
        if visited[f] == 0:
            visited[f] = 1
            black += 1
            for x in edge[f]:
                l.append(x)
            nextF = l
    l = []
    for s in nextS:
        if visited[s] == 0:
            visited[s] = 1
            white += 1
            for y in edge[s]:
                l.append(y)
            nextS = l
if black > white:
    print('Fennec')
else:
    print('Snuke')

6/21 AOJ（クラスカル法）

精進(python3)

こんにちは。2S1の成績がとりあえず一安心できるくらいでホッとしているとーです。

学校の授業でクラスカル法をやったので復習。プリム法を勉強したのですがこっちは結構噛み砕くのが難しくかったのでまた後回し。どうやら実行時間は大して変わらないっぽい？

クラスカル法もプリム法も、最小全域木、つまり全ての島を最も少ないコストで結ぶような木を実現するのに必要なコストを求めるためのアルゴリズムです。

クラスカル法の流れは、

①とりあえず、[コスト（距離）,出発点の島,終着点の島]という辺のデータを、距離の短い順にソート
②n個の島0~n-1に対して、UF木を作っておく
③コストの短い辺から順番につなげていく。その際、出発点と終着点が同じ木に属していないことをUF木を用いて判定し、同じ木に属していれば辺で結ぶことはしない

という感じです。③については、同じ木に属しているのであれば、わざわざその辺で結ばなくとも迂回路が存在するため、このようなことになる。

練習問題↓
judge.u-aizu.ac.jp

コードはこんな感じ。

n = int(input()) #島はn*nの形式で与えられる
T = [] #ここにコストや出発、終着点の情報が入る
ans = 0 #ここに答え（最小コスト）が入る
for i in range(n):
    L = list(map(int,input().split()))
    for j in range(n):
        if L[j] != -1:
            T.append([L[j],i,j]) #島は0からスタート
T.sort() #辺のコストの小さい順にソート

#Union Find
rank = [0]*n
par = []
for i in range(n):
    par.append(i)
def find(x,par):
    if x == par[x]:
        return par[x]
    else:
        return find(par[x],par)
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    if x != y:
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1


for i in range(len(T)):
    if find(T[i][1],par) != find(T[i][2],par):
        ans += T[i][0]
        unite(T[i][1],T[i][2],par,rank)
print(ans)