幅優先探索（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通過できるようになったことを自分の成長と捉えると、気持ちを折らずにチュウニズムが続けられると思います

4/11 AtCoder

こんにちは。最近10時に寝て7時に起きるという小学生顔負けの生活リズムのとーです。

ABC087D

二人の人の間の距離が渡されるのでそれらの情報が矛盾していないかどうかを確認する問題
解き方としては、起点の情報から見ていって、座標の情報がまだ更新されていなかったらとりあえず今持っている情報で更新し、すでに更新されていたら、今持っている情報と更新済みの情報が矛盾しないかをチェックしていくという感じ

一つ確認し、それに連なる点の情報を見る、という作業を続けていくので、FIFOのデータ構造が使える

以下はpython3による答えのコード

from collections import deque
N,M = map(int,input().split())
edge = [[] for i in range(N)] #edge[i]には点i-1に隣接する点と、距離が入る
x = [float('inf')]*N #ここに点の座標の情報が入る(最初は全て未更新)
for i in range(M):
  L,R,D = map(int,input().split())
  edge[L-1].append([R-1,D]) #左から右を見るときは距離Dが入る
  edge[R-1].append([L-1,-D]) #右から左を見るときは距離-Dが入る
for i in range(N):
  if x[i] == float('inf'): #座標の情報が未更新なら
    x[i] = 0 #ここを起点とする
    q = deque([i]) #起点がqに入る
    while len(q) > 0: #qが空になるまで続く
      now = q.popleft()
      for e in edge[now]:
        if x[e[0]] == float('inf'): #次に見た点が未更新なら
          x[e[0]] = x[now]+e[1] #今見ている点から距離+D(e[1])だけ足す
          q.append(e[0]) #次に見た点をqに入れる
        elif x[e[0]]-x[now] != e[1]: #次に見る点が更新済み且つ情報と矛盾するなら
          print('No')
          exit()
print('Yes')

4/10 AtCoder

こんばんは。毎日めちゃくちゃ疲れているとーです。

ARC098D

数列の和とXORが等しくなる部分はいくつありますか、という問題
基本的に、XORと普通の和では、同じビットが立っているところはXORでは0になるので、XORの方が小さくなるということを念頭に置く
（想定解は、数列の各項を二進数に直し、ビットが立っている位を見ていって、その個数が1個以下であるならば足す、それ以外であれば左端を除く、ということを繰り返すものだったが今回は愚直に足していく方を採用）

解き方はいたって簡単で、端っこを固定し（ここでは左端）、伸ばせるところまで右を伸ばした後、右から左の数を引いて足す（これにより、固定した左端からスタートする数列の数が数えられたことになる）これを、左端が数列の右端に来るまで続ければよい