人間行動基礎論 まとめ

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

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

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

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

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

・心理学の歴史
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月までに毎月一本）

AtCoder（C++、include、or/and）

また詰まってんのかよって感じですが一応

入力は#include でも#include でもよくね？みたいな感じだったけど、なんか調べるとiostreamは遅いだのC++でしか使えないだのあまりよろしくない印象を受ける
まあでもC++使ってる人たち割とiostreamを使っている印象があるのでこっちでよいかなという気持ちにはなる

競プロで最初に言うべきおまじないってまだよくわからないのだけど

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

くらいでよいのかな
とりあえずiostream使うならcin,coutで統一した方がよさそう

そのうちお世話になるかもしれないサイト
忘れがちな C++ の標準ライブラリの使い方 - Qiita
C++文字列 - C++のstring型について調べるも… (凍結)

orとand

if文の中で例えば「aが1か2だったら」みたいなのは
if ( a == 1 || a == 2)
みたいに

という記号で書ける

andは&&で書く

4/20 AtCoder（python3、プリム法）

ARC076D
プリム法とは
>>>頂点をすべて結ぶのに必要な最小のコストを、辺E,頂点VとしてO(ElogV)で求めるアルゴリズム

構造は
①「『既に訪れた頂点(ア)』と繋がる『まだ訪れていない頂点(イ)』」とを結ぶ辺のリストの中で（ここではあくまで辺が主役）、最もコストが小さいものを選ぶ
②その辺のコストを足す（辺を使うことを確定させる）
③頂点(イ)と辺でつながる頂点のうち、その頂点がまだ訪れていないのであれば、辺のリストの中に追加する
④①に戻り、リストが空になるまで続ける

というもの

import heapq
def prim_heap():
    used = [True]*n #True:不使用
    edgelist = []
    for e in edge[0]: #連結なのでedge[0]は必ず存在する
        heapq.heappush(edgelist,e)
    used[0] = False #番号0の頂点を始点とする
    res = 0 #答え
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]: #取り出した辺の行き先が使用済みなら
            continue #捨てる
        v = minedge[1] #そうでないなら行き先を使用済みにする
        used[v] = False
        for e in edge[v]: #行き先の頂点がつながる辺において
            if used[e[1]]: #その先の頂点が未使用なら
                heapq.heappush(edgelist,e) #次につなげる辺の候補にする
        res += minedge[0] #コストを足す
    return res

n,w = map(int,input().split()) #n:頂点の数、w:辺の数
edge = [[] for i in range(n)] #edge[i]には、[コスト,行先]というリストがさらに内包される
for i in range(w):
    x,y,z = map(int,input().split())
    edge[x].append([z,y])
    edge[y].append([z,x])
print(prim_heap())

この問題では、全部の辺をつなげようとすると、N**2通りの辺が存在するので、N = 10**5だと間に合わない。少し考えると、かけるべき辺は、ある頂点とx座標、y座標のそれぞれで最も近い頂点との間のみでよいことが分かる（x座標の小さい方から並べた頂点ア、イ、ウに対し、ア、イ、ウすべてを訪れることを考えると、アーウとつなげる必要はなく、アーイ、イーウとつなげればよいから）
だからx,yのそれぞれでソートし、隣り合う頂点のみに辺を掛ければ、辺の数はO(N)になって間に合う

実装が重いので後でやります.......。

juppy.hatenablog.com

4/20 AtCoder（C++、クオーテーション、割り算）

ABC122A

シングルクオーテーションとダブルクオーテーションの違い

#include <iostream>
#include <stdio.h>
using namespace std;
int main() {
    char b;
    cin >> b;
    if (b == 'A'){
      printf("%s","T");
    }
    else if (b == 'T'){
      printf("%s","A");
    }
    else if (b == 'G'){
      printf("%s","C");
    }
    else {
      printf("%s","G");
    }
}

という例を考えると、
①if文の中で数値として扱っているのは'（シングルクオーテーション）
②if文の中で文字列として扱っていたり、printfの中は"（ダブルクオーテーション）
になる

例えば、Heiseiという文字列を出力するときにcoutを使うと、
cout << "Heisei" << endl;
でもいいし、
printf("%s\n","Heisei")
でもよい
ただ、cout << 'Heisei' << endl; や printf("%s\n",'Heisei') のようにシングルクオーテーションはダメ

ABC121A
空白で空いた二行二列の入力も、普通に
int H,W,h,w;
cin >> H >> W >> h >> w;
ってやって受け取ることができる

ABC120A

整数同士の割り算はその商が返ってくる（つまり切り捨ての値が返ってくる）
小数点以下を返してほしければ（実数）/（整数）みたいにすればよいとのこと
実数は、pythonと同じようにfloatで書けるが、doubleという形でもかける　こっちの方がメモリを食うけど表せる範囲が広いらしい

4/19 AtCoder(C++、入力、出力、改行、if/else、for)

こんばんは。昨日windowsのパソコンでUbuntuをインストールしたらバチバチに重くて泣いたとーです。

C++に挑戦、ということでこれからC++のコーディングを練習します。新しい言語を学習するとなると入力、出力が最初のネックになるけどここは我慢.......。

ABC124A,ABC123A
大枠をかっこ{ }で区切ってコードを書く

入力

空白区切りの数字二つは、

#include <iostream>
int main() {
  int a,b;
  cin >> a >> b;
}

みたいな風に入力を受け取ればよい

改行区切りで数字が増えても同じようにする

出力
出力は、printf()というのとcout << ナントカ ( <というおまじないが必要
一方でprintf()は最初にinclude とするらしい　（試しにやってみたらこれなくても動いたんだけど......）

また、coutは本来std::coutと書くべきだけど、最初にusing namespace std;とすればstd::の部分は省略できる
std::の部分は名前空間というらしく、coutというコマンドがstdという領域内のコマンドであることを示しているっぽい　これ（名前空間）によって、例えば（こういうことをするのはまずいとは思うけど）自作のコマンドcoutを作ったとしても、std::coutとは区別ができるようになる
（全てについてstd::を省略するのは不都合が生じることもあるらしいので、using std::cout; としておけば、coutだけはstd::の部分を省略できるようになる、{ }で括った部分に入れれば、その{ }内でのみstd::が省略されるようになったりする）

結局、C言語の入出力関数(printfなど)を使用するのには #include が必要で、C++の入出力オブジェクトを使用するのには #include が必要

programming.pc-note.net

で、結局どちらを使うのがいいのかって話になると難しくて、蟻本なんかだとprintfを使ってたりする
おそらく型変換とか改行とかがやりやすいのかな？だから競プロ向けで使ってるのかもしれん　とりあえずprintfでやっていく

printfでやる場合、例えば

#include <stdio.h>
int main() {
    char *str1 = "Hello";
    char *str2 = "World";
    int number = 10; 
    printf("%s %s %d \n", str1, str2, number);
}

となる

まず、charとかintとかで型宣言をしておくのはよくて、その次のprintfの中の%sとか%dとか\nとかなんやねん、って感じになるが、printf()は型を指定してprintができるということらしい

%c →　char 文字
%s →　char * 文字列
%d → int 10進整数
%f →　float　 実数

みたいな対応をしている　たぶん競プロでは%cよりかは%sの方が使うんじゃないかな

で、\n（\は￥(半角)と同じ）は改行を表す特殊文字だそうです　競プロ改行が大事になりがちなので覚えます

使い方は、printf("型の宣言",適当な引数)という感じになる
a = 11として
printf("%d/n",a);
とすれば、11が出力され、その後に改行が入る
a = 11,b = appleとして
printf("%d %s\n", a,b);
とすれば、11 appleと空白区切りで出るし、%d%s\nとつなげれば11appleと出る

webkaru.net

条件分岐
if/elseの書き方は、

if (条件){
　　\\ なにか
} else if (条件) {
　　\\ なにか
} else {
　　\\ なにか
}

という感じ（つまり一つの判定につき括弧を一つ使う）

比較演算子（以下、以上とか）はpythonと同じ

for文

簡単なコードを例にとってみる

int i;
for(i=0; i<3; i++){
   printf("%d\n",i);
}

見れば分かるように、i=0に対してiを出力しインクリメント（1加算）、というのを、i=0,1,2に対して行う
なんかi++と++iという二種類の書き方があるっぽいけど何もなければi++でいいっぽい

二ヶ月のまとめ

こんばんは。とーです。

AtCoderを再開してから２ヶ月が経ちました

一か月で120問くらい解きました　Dに挑戦するようになったのですがなかなか厳しいです　水色になりたいけど基本的にC速解きが要求されるようになる昨今本当につらいです

レートの推移がこちらです

ちょっとずつは上がってきていますがやっと緑折り返しといった感じ　水色が遠い
Dをもっと早く解けるようになるといいですね

これから天下一とかあるのでそこらへんでレート盛り盛り森鴎外できたらいいなって思います　頑張ります

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

こんばんは　とーです
つい最近、チュウニズムのレートが15.5になりました

アイリちゃん最高！！！！！！！！！！！！！！！

マジで13.5とは思えない簡単さの曲が出てきたので速攻で乗せてきました

15.50達成時のベスト枠がこちらになります　15.50達成する人って何かしら得意な13.7,13.8くらいの曲で盛ることが多いと思うんですけど、僕はベスト枠平均が15.5超えていたにも関わらずそういう得意曲がなかったため、なかなか15.50になれず苦しかったです

見ての通り13+の鳥が一つしかありません 15.50になるには少なくとも13+の鳥が一つはないと厳しいかもです(それでも以前に比べれば圧倒的になりやすくなったわけですけど)

クラスエンブレムも更新しました

これまでの約一年間の軌跡です 主に13鳥の情報が載ってます（ジングルベル15.6は15.16の誤記です）

鳥取るのが大変だったのは
①分からない
②立川浄穢捕物帳
③Phantasm Brigade
④ラクガキスト
⑤優曇華院
⑥とれびちゃん
らへんです　ここらへん本当に苦労しました

なんだかんだ一年続けてきて、3000クレも費やしましたが、何とか15.5になることができてよかったです
始めた頃はここまで来ることは全く想像できなかったのですが、いざなってみても自分はまだまだだなあと思わされるばかりです

他人と競い合うことも大切ですが、それが白熱しすぎて自分がこのゲームを楽しいなって思えなくなると本末転倒なので、自分の楽しい範囲でやるのが大事だなって最近思うようになりました

あと、別に鳥が取れなくても、単純にハイスコアを更新したり苦手なところがAJ通過できるようになったことを自分の成長と捉えると、気持ちを折らずにチュウニズムが続けられると思います