本日の精進：二分探査，DFS，BFS

本日も[こちらの記事(by e869120氏)](https://qiita.com/e869120/items/eb50fdaece12be418faa)を中心に精進．

[AtCoder Beginner Contest 077 C - Snuke Festival](https://atcoder.jp/contests/abc077/tasks/arc084_a)
二分探索．それだけなのだが，Bに着目すればよいことに気が付かずに3回ほどWA．結局解説を見てコーディングした次第です．
こういう場合，視点を変える柔軟性が欲しい．
あと，"以上"か"より大きい"かでupper_boundとlower_boundのどちらを使うかが変わってくるので注意したい．というか，この辺の挙動がまだ身に付いてない．
こちらの記事が非常に参考になります．↓
[lower_boundとupper_boundの使い方(by ganariya氏)](https://qiita.com/ganariya/items/33f1326154b85db465c3)

ACコード:

```AC.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main(void){
  int N; cin >> N;
  vector<int> A(N),B(N),C(N);
  for (int i = 0; i < N; i++) cin >> A[i];
  for (int i = 0; i < N; i++) cin >> B[i];
  for (int i = 0; i < N; i++) cin >> C[i];
  sort(A.begin(),A.end()); sort(B.begin(),B.end()); sort(C.begin(),C.end());
 
  ll ans = 0;
  for (int i = 0; i < N; i++){
    ll A_lower = lower_bound(A.begin(),A.end(),B[i]) - A.begin();
    ll C_upper = C.end() - upper_bound(C.begin(),C.end(),B[i]);
    ans += A_lower * C_upper;
  }
  cout << ans << "\n";
  return 0;
}
```


[AtCoder Beginner Contest 138 D - Ki](https://atcoder.jp/contests/abc138/tasks/abc138_d)
深さ優先探索:DFS(木構造)．DFSが組めることに加え，各ノードのカウンタは「自分への加算操作＋親ノードへの加算操作」である，という気づきが必要．
これさえわかれば，まず自分への加算操作だけ計算した後，DFSするときに「子ノードカウンタ」+=「親ノードカウンタ」とすればよいだけ．
だが，初見ではまあまあ悩んだ．

ACコード:

```AC.cpp
#include <bits/stdc++.h>
using namespace std;
 
using Edge = pair<int, int>; //エッジ(本問題では使わない))
using Graph = vector<vector<int>>;	//グラフ
 
int N, Q;
Graph G;
 
// res は答え
vector<int> res;
 
// 深さ優先探索(再帰)
// v:現在のノード p:親ノード
void dfs_recursive(int v, int p) {
	for (auto e : G[v]) {
		if (e == p) continue;	//親ノードにさかのぼらない
		res[e] += res[v];		//親の答えを子に足し合わせる
		dfs_recursive(e, v);	//vから下流に進む，このときvが親ノードになる
	}
}
 
int main(void){
  cin >> N >> Q;
  G.assign(N, vector<int>());
  for (int i = 0; i < N - 1; i++) {
    	int u, v; cin >> u >> v;
		u--, v--;
		G[u].push_back(v);
		G[v].push_back(u);
  }
  
  res.assign(N, 0);
  
  for (int i = 0; i < Q; i++) {
    	int p,x; cin >> p >> x;
    	res[p-1] += x;
  }
  
  dfs_recursive(0,-1);
  
  for (int i = 0; i < N; i++) cout << res[i] << "\n";
  
}
```

[AtCoder Beginner Contest 007 C - 幅優先探索](https://atcoder.jp/contests/abc007/tasks/abc007_3)
結構昔の問題．迷路の最短経路を幅優先探索:BFSで解く問題．BFSが組めれば問題ない感じ．
手数のカウントに若干悩んだ．どうやってもよいが，自分はqueueに格納する次マスの座標値に手数の情報も加えることで対処した．
文字列が入るときは基本的にpythonでやってます．が，ちょっと文字が入る程度ならC++でやった方がいいと思う(後述)．

ACコード:

```AC.py
R,C = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
sy -= 1
sx -= 1
gy -= 1
gx -= 1
graph = [[i for i in input()] for j in range(R)]
visited = [[False for i in range(C)] for j in range(R)]
 
def bfs(start_y,start_x):
  queue = [[start_y,start_x,0]]
  while queue:
    now = queue.pop(0)
    if now[0]==gy and now[1]==gx: return now[2]
    for next in [[1,0],[-1,0],[0,1],[0,-1]]:
      if visited[now[0]+next[0]][now[1]+next[1]]: continue
      if graph[now[0]+next[0]][now[1]+next[1]]=='#': continue
      queue.append([now[0]+next[0],now[1]+next[1],now[2]+1])
      visited[now[0]+next[0]][now[1]+next[1]] = True
 
print(dfs(sy,sx))
```


[AtCoder Beginner Contest 151 D - Maze Master](https://atcoder.jp/contests/abc151/tasks/abc151_d)
帰ってきた幅優先探索．上記の問題の発展形となっている．
最初，スタートとゴールを全パターン網羅しようとしてTLE(O((HW)^3)解法になっていた？pythonだと超効率化しないと無理)．
何とかスタート・ゴールの組み合わせを特定しようとするも挫折．
結局，スタートだけ全探索して，ゴールはBFSしたときに一番遠いマス，とすればよいとのことでした．

こういうとき，pythonでやってTLEになると「C++なら行けたのでは...???」という疑念が生じる．よくない．

ACコード:

```AC.py
R,C = map(int,input().split())
graph = [[i for i in input()] for j in range(R)]
visited = [[False for i in range(C)] for j in range(R)]
 
def bfs(start_y,start_x):
  queue = [[start_y,start_x,0]]
  while queue:
    now = queue.pop(0)
    visited[now[0]][now[1]] = True
    for next in [[1,0],[-1,0],[0,1],[0,-1]]:
      if now[0]+next[0] < 0 or now[1]+next[1] < 0: continue
      if now[0]+next[0] > R-1 or now[1]+next[1] > C-1: continue
      if visited[now[0]+next[0]][now[1]+next[1]]: continue
      if graph[now[0]+next[0]][now[1]+next[1]]=='#': continue
      queue.append([now[0]+next[0],now[1]+next[1],now[2]+1])
      visited[now[0]+next[0]][now[1]+next[1]] = True
  return now[2]
 
ans = 0
for row_s in range(R):
  for column_s in range(C):
      if graph[row_s][column_s]=='#': continue
      visited = [[False for i in range(C)] for j in range(R)]
      ans = max(ans,dfs(row_s,column_s))
    
print(ans)
```


この辺の問題，自分はやっていて手ごたえがあるのだが，Atcoder Problemsで見ると大体緑相当の難易度になっている(絶望)．
この難易度帯を安定的に解ければ水色が見えてきそう．
まずは基本的なアルゴリズムを使いこなすことに専念して精進していく所存です．