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

こんにちは（午前三時）

昨日やっとこさカリバーンを鳥乗せてきました。うれしいね。わいわい。

1006100くらいで停滞してたのを頑張って乗せました。1日で30連奏くらいしたかも。7000以上の鳥寸も5回くらい踏んだけどなんとか。

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

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

＜序盤＞

・16~17小節

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

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

①の運指

②の運指

・57~58小節

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

・66~70、74~78小節

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

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

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

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

＜中盤＞

・90~93小節

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

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

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

・96~98小節

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

・107~108小節

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

・118~119小節

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

・121~122、123~124小節

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

・134~136小節

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

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

一応想定解の運指

・136~138小節

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

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

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

餡蜜の運指

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

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

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

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

続かね〜〜〜〜〜〜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）

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

今日は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日目（貪欲法）

プログラミング最近全然やってなかったのでリハビリ。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点まで持ってくることができました。

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

空白区切りで出力

T = [1,2,3,4]
print(' '.join(map(str, T)))

ってやると

1 2 3 4

って出力される

人間行動基礎論 まとめ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ベルマンフォード法

ある一点からスタートし、そこから残りの全ての頂点に達するのに必要な最短コストを計算するときに使える。計算量は、頂点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）の問題

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

幅優先探索

幅優先探索は、基本的に「次に訪れる島」をキューの形で保持しておくことが肝要です。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（クラスカル法）

こんにちは。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)

6/10（5/1） データ構造:stack,queue/priority queue、連想配列:map

5/1に書き始めたデータ構造の記事を今更書きます。怠惰。

データ構造

stack（スタック）とqueue（キュー）がある。くえぅえではない。

簡単なイメージは、
・スタックは「積み上げられた書類の山」。書類は上へ上へと積まれていき、あなたはそれを上から処理する。　
・キューは「順番待ちの列」。お店に入ってきた人は出来ている列の後ろに並び、先頭の人から注文を受けていく。
というもの。

キューには「優先度付きキュー」というのも存在するが、これは順番待ちの列で、階級が上の人が列の先頭へと優先的に並ぶことができるような状況。まあはっきり言ってしまえば、データが入ってくると逐一それをソートするようなデータ構造のこと。

スタック

push（プッシュ）とpop（ポップ）という二つの操作からなる。前者は「データを入れる」、後者は「データを取り出す」に相当。pythonだと、コマンドとしては、列のケツに突っ込むappendと、列のケツから取り出していくpopにあたる。
上へ書類を積むという比喩を用いたけど、実際には上に相当するのはリストの末尾です。そこだけ注意。

（例）
stack（リスト名はなんでもいいんだけど）に3,4,1を順に突っ込む

stack = []
stack.append(3)
stack.append(4)
stack.append(1) #ここまででstack = [3,4,1]

stackから要素を「入れた順番が新しい方から」取り出す

stack = [3,4,1]
a = stack.pop() #a == 1
b = stack.pop() #b == 4
c = stack.pop() #c == 3 , stack == []

練習問題↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_A&lang=jpjudge.u-aizu.ac.jp

逆ポーランド記法と呼ばれてるやつを計算しましょうねという問題。
リストを持っておいて、数字が入ってきたらそれをリストの末尾に追加、演算子が来たらそれをリストの後ろから数えて二つの数字に施し、一つになった数字をまたリストのケツに突っ込む。最終的にはリストの中に数字が一つだけ残るはずなので、それを出力すればよいという話。

キュー

dequeとかいうよくわからんのを使う。そもそも、このデータ構造は、リストで言えば「要素をリストのケツに突っ込んで、先頭から要素を取り出す」という風になっているので、普通のリストでやろうとすると「先頭から取り出す」の時に2番目以降の要素を一つずづずらす手間がかかる（多分O(n)）。だから、普通のリストでやるんじゃなくて、標準装備されている特殊な構造（今回はdeque）でやるんだよってことなのかな。

操作は、まずimport collectionsという呪文を唱えてから、リストqをdequeにするために、q = collections.deque()とする。それから、pushとpopに相当する操作として、リストに要素を入れるときはappend（これはリストの末尾に要素を加えるので、スタックと同じ）、リストの先頭（左端）から要素を取り出すのはpopleftというコマンドを使う。

（例）
queueに要素を入れる

import collections
q = collections.deque()
q.append(3)
q.append(4)
q.append(1) #ここまででq = [3,4,1]

queueから「入れた順番が速い方から」取り出す

q = [3,4,1]
a = q.popleft() #a == 3
b = q.popleft() #b == 4
c = q.popleft() #c == 1 , q == []

練習問題↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B&lang=jpjudge.u-aizu.ac.jp

いくつか仕事があって、1ターンでできる仕事の量が限られていて、その量を超過した仕事は、残りを後回しにされる。これを繰り返していつ仕事が終わりますかという問題。queueでデータを持っておいて、仕事をリストの先頭から取り出し、制限時間内でできたらリストから削除、できなかったら残りをリストの最後に入れるってのを繰り返していくアルゴリズムを実装する。

優先度付きキュー（プライオリティーキュー）

これまでにも何度か出てきたけどここでおさらい。キューとほぼ同じ構造を持っているけど、違うのは「リストに要素を入れた後でソートする」というひと手間が加えられていること。
例えば1000個の品物があって、そこから価値の高い品物ベスト10を選ぼうみたいな問題が出されたとき、（「まあリスト全部突っ込んでソートすればよくない？」みたいなツッコミはおいといて）前から順番に舐めていって、その時その時のベスト10を更新するのがこのデータ構造でできるようになる。

pythonだとheapqというコマンドを使います。ここもqueueとは違う点（queueはdequeを使うよね）なので注意します。使うコマンドは、
①heapq.heapify(リスト名）　　　　　　　　　これはリストを「優先度付きキュー」として扱うようにする
②heapq.heappush(リスト名,要素）　　　これはリストに要素を追加する（のと、それを含めてソートする）
③heapq.heappop(リスト名）　　　　　　これはリストの先頭（左端）から要素を取り出す
の三つ。ややこしい。

特に①は、普通に持っていたリストをいきなり優先度付きキューとして扱いたい場合に使うと覚えとくのがいいかも。空のリストを優先度付きキューとして扱いたいのなら普通にheappushとheappopだけで事足りるけど、最初からいくつか要素が入っているリストをいきなり優先度付きキューとして扱いたい場合は、一回heapifyを使って優先度付きキューに直してから使う。

（例）
優先度付きキューに要素を入れる

import heapq 
Q = []
heapq.heappush(Q,3) # Q == [3]
heapq.heappush(Q,4) # Q == [3,4]
heapq.heappush(Q,1) # Q == [1,3,4]

リストから要素を取り出す

a = heapq.heappop(Q) # a == 1
b = heapq.heappop(Q) # b == 3
c = heapq.heappop(Q) #c == 4

import heapq 
Q = [3,4,1]
heapq.heapify(Q) # なぜかこの時点だと昇順にならず、Q = [1,4,3]になっている模様。なんで？？？？？
a = heapq.heappop(Q) # a == 1 , Q == [3,4]
b = heapq.heappop(Q) # b == 3 , Q == [4]
c = heapq.heappop(Q) #c == 4 , Q == [] popは正常に動作している

意図しない挙動をしてしまったけど見なかったことにしよう。いいね？
↑heapqは、「先頭要素が常に最小要素になるデータ構造」なので、全部の要素が大小の順番を保っているとは限らない。それだけの話でした。

練習問題↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_9_C&lang=jpjudge.u-aizu.ac.jp

問題自体は大したことない、素直な実装をすればいいと思うけど、「大きいほうから取り出す」、つまり「リストの末尾（右端）から取り出す」という点がpopleftと違い、一筋縄ではいかない。
残念ながら大きい方から取り出すコマンドはないが、今回の問題のような場合は「要素を入れる際にマイナスをつける」「取り出すときにまたマイナスをつける」の操作を行うことで、大きい数字はより小さい数字として扱われるので対処できる。

なんか、プライオリティーキューの練習にいいよみたいに言われてる問題がこれ。
atcoder.jp

3*N個の要素が並んだ列からN個の数字を抜いて、残りの2*N個の要素を前半、後半に分けた後で、「前半の和」と「後半の和」の差ができるだけ大きくなるようにしようねっていう問題。

結局、

①0 <= k <= Nのkに対して、前半のN+k要素の総和の最大と、後半の2*N-k要素の総和の最小を別々に求めておき、リストに入れる。
（例）
SUML = [（前半N要素の総和の最大）,（前半N+1要素の総和の最大）、......、（前半2*N要素の総和の最大）]
SUMR = [（後半2*N要素の総和の最小）、（後半2*N-1要素の総和の最小）、......、（後半N要素の総和の最小）]
②0 <=i <= N-1のiに対して、SUML[i]-SUMR[i]を求め、その最大値を答えとして返す

ってのが基本方針になり、①の所でheapqが必要になる。
（あんまり参考にならない僕の解答↓）
atcoder.jp

連想配列

map

例えば
Thank you for your mail and your lectures
という文章中に出てくる単語と、その回数を見たいとき、これは有用である。

L = list(input().split())
dict = {}
for i in range(len(L)):
    if L[i] in dict:
        dict[L[i]] += 1 #「リストのn番目」に相当するのが単語になったみたいな感じ。単語が目印となる
    else:
        dict[L[i]] = 1
#dict == {'Thank': 1, 'you': 1, 'for': 1, 'your': 2, 'mail': 1, 'and': 1, 'lectures': 1}
#max(dict) == 'your'

【Python】辞書型（連想配列）の使い方 | 西住工房

ディクショナリ | Python-izm

6月の目標

生きてます。

テスト終わってのんびりして、実家に帰ったりしてたらもう6月も上旬終わるので、そろそろ動き始めなくてはと危機感を抱いたので6月だけの目標を立てます。

大目標

①3科目勉強する
②AtCoder水色になる（プログラミングをする）
③本を読む

中目標

①

• キゴロンは毎週予習してから行く
• 人間行動基礎論は月曜日の空きコマとかに毎回復習する
• 量子コンも毎回予習してから行く、レポートをさっさと片づける

②

• python3で~500点の問題に戦える力をつける
• C++、C言語を復習する(A解いて慣れる）
• Mac届いたらLinuxに触れる
• 情報の教科書読む

③

• 認知心理学（6/9~15)
• これから「正義」の話をしよう(6/16~22)
• 人工知能のための哲学塾(6/23~29)

AtCoder,AOJ（再帰、dpの初期化）

こんにちは。無気力に日々を過ごしています。とーです。

ABC115D

バンズとパティだけで構成されるハンバーガーをめっちゃ重ねて、その下からX層を食べるとパティは何枚食べられますか、という問題。ちなみに僕はチーズバーガーが大好きです。

解き方は、「レベルNバーガー」という情報と「下からX枚食べる」という2つの情報から、何枚パティを食べることになるかに重きを置いて考えれば、パティの枚数を求めるf(N,X)という関数を定義すればよいことになる。

まず、レベル1~Nバーガーについて、「何枚の層で構成されているか」というリストaと、「何枚のパティが入っているか」というリストpを作る。最初はa = [1]、p = [1]で、
a[i+1] = 2*a[i]+3
p[i+1] = 2*p[i]+1
で求めていけばよい　

レベルNバーガーは構成的には「バンズ：N-1バーガー：パティ：N-1バーガー：バンズ」となっているので、
N != 0において、（N==0は適当に求める）

ア：X == 1なら、当然0（一番下のパンしか食べられない。悲しい）

イ：1 < X <= 1+a[N-1]なら（つまりパン＋レベルN-1バーガーまでなら）、f(N-1,X-1)を返す（N-1バーガーの下からX-1層を食べる。Xから一番下のパンを引いておくことに注意）

ウ：X == 2+a[N-1]なら（パン＋レベルN-1バーガー＋ど真ん中のパティなら）、p[N-1]+1を返す

エ：2+a[N-1] < X <= 2+2*a[N-1]なら（パン＋レベルN-1バーガー＋パティ＋レベルN-1 バーガーまでなら）、p[N-1]+1+f(N-1,X-2-a[N-1])を返す（これもイと同様の考え方）

オ：X = 3+2*a[N-1]なら（全部食べる）、2*p[N-1]+1を返す

これを愚直に書けばよい。少なくとも次はN-1バーガーについて調べることになるので、N+1回以下のステップで答えが求まる。

DPL_1_B

ナップザック問題 | 動的計画法 | Aizu Online Judge

以下のa,bのうち、どちらが正しいコードでしょうか

a

n,w = map(int,input().split())
L = []
for i in range(n):
  L.append(list(map(int,input().split())))
dp = []
for i in range(n+1):
    T = [0]*(w+1)
    dp.append(T)
for i in range(n-1,-1,-1):
    for j in range(w+1):
        if j < L[i][1]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-L[i][1]]+L[i][0])
print(dp[0][w]) 

b

n,w = map(int,input().split())
L = []
for i in range(n):
  L.append(list(map(int,input().split())))
dp = []
T = [0]*(w+1)
for i in range(n+1):
    dp.append(T)
for i in range(n-1,-1,-1):
    for j in range(w+1):
        if j < L[i][1]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-L[i][1]]+L[i][0])
print(dp[0][w]) 

正解はa
なんでかというと、aでは「n+1回、0埋めしたリストTを作ってappend」しているが、bでは「0埋めしたリストTを作って、n+1回append」しているという違いがあり、bの方だと値参照になってしまうため、全部のリストが同じものになってしまう（どこか一か所の変更がすべてに適用されてしまう）という不具合が起こるからです。これのせいで二時間無駄にした。みんなはこんなミスしないようにしようね。

AtCoder(C++、max、累乗)

C++で複数個（2つ以上）の値の最大値が欲しければ、
#include (アルゴリズムと打ちましょう）

としてから
max({a,b,c})
とする 中括弧を忘れないように

ちなみに二つの時はmax(a,b)でいいっぽい　なんでやねん

累乗が欲しかったら
#include

としてから
pow(n,k)

とすればn**kが出る

7月までの目標

目標立てとかないと動けないことにようやく気付いたので立てます

大目標

①取った科目は全部優をとる
②AtCoder水色になる（プログラミングをする）
③情報を勉強する
④エロゲをやる
⑤R18ssを書く

中目標

①
- 物性・生命を早いうちに仕上げて（できれば5月中旬までに）、演習をやる

• キゴロンは毎週予習してから行く
• 人間行動基礎論は月曜日の空きコマとかに毎回復習する
• 量子コンも毎回予習してから行く、レポートをさっさと片づける

②

• python3で~500点の問題に戦える力をつける
• C++、C言語の入力に困らないくらいにはなる（~300点の問題を実装できるくらいにはなる）
• できたらLisp(Scheme)の勉強をする

③

• 情報の教科書読む
• 学校のPCなりでLinuxに触れる

④
- その日の獣には、
- Misssing -X- Link
- レビューも頑張って書く

⑤
- 音声作品シナリオコンテスト（~ゴールデンウィーク）

• 販売用（~7月までに毎月一本）