at coder beginner contest 007 C 幅優先探索　D bitdp

B
文字列 A が与えられる。小文字アルファベット(a-z)のみを使って辞書順比較したとき文字列 A より小さいものを1つ何でも良いので出力せよ。ただし、文字列は 1 文字以上 100 文字以下でなければならない。もし存在しない場合は "-1" を出力せよ。
ただし、ある文字列 S=S1S2…Sn と T=T1T2…Tm について、辞書順比較した際に S<T であるとは、次のどちらか一方の状態が成り立っていることを言う。
ある整数 i(1≦i≦min(n,m)) に関して、 1≦j≦i−1 を満たすどの整数 j に関しても Sj=Tj が成立し、かつ Si<Ti が成立する
任意の整数 i(1≦i≦min(n,m)) に関して、 常に Si=Ti が成立し、かつ |S|<|T| である。ただし |X| は文字列 X の長さを表すものとする。
なにやら頭が痛くなる記述だが、言い換えると次の通りである。
それぞれの文字列の同じ位置同士を先頭から比較していって、初めて不一致になったら、その文字同士の(アルファベットでの)比較結果が文字列の全体の比較結果である。 例えば、"abcd" と "ax" を比較すると、2 文字目で、'b'<'x' となるので、"abcd"<"ax" である。
もし、比較している途中で片方の文字列が尽きてしまったら、文字列の長さが短い方が小さい。例えば "ab"<"abc"である。

なんか問題としてミスってる気がする

```
int main(){
  string a;
  cin >> a;
  if(a == "a") {
    cout << "-1" << endl;
  }
  else if(a.size() == 1){
    cout << "a" << endl;
  }
  else {
    a.erase(a.end()-1,a.end());
    cout << a << endl;
  }
}
```

```
#include<iostream>
#include<string>
using namespace std;
int main() {
	string a;
	cin >> a;
	if (a == "a")
		cout << -1 << endl;
	else cout << "a" << endl;
}
```
なんとかなるやつ

C
幅優先探索
1 行目には、行数 R(1≦R≦50)と列数 C(1≦C≦50)がそれぞれ空白区切りで与えられる。
2 行目には、スタート地点の座標 (sy,sx) が空白区切りで与えられる。スタート地点が sy 行 sx 列にあることを意味する。 1≦sy≦R　かつ 1≦sx≦C である。
3 行目には、ゴール地点の座標 (gy,gx) が空白区切りで与えられる。ゴール地点が gy 行 gx 列にあることを意味する。 1≦gy≦R　かつ 1≦gx≦C であり、(gy,gx)≠(sy,sx)であることが保障されている。
4 行目から R 行、長さ C の文字列が 1 行ずつ与えられる。各文字は . もしくは # のいずれかであり、i 回目 (1≦i≦R) に与えられられる文字列のうち j 文字目 (1≦j≦C) について、その文字が . なら、マス (i,j) が空きマスであり、# なら、マス (i,j) が壁マスであることをあらわす。
盤面は壁マスで囲まれている。つまり、i=1,i=R,j=1,j=C のうちいずれか1つでも条件を満たすマス (i,j) について、c(i,j) は #である。また、スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int main() {
	int R, C;
	int sy, sx, gy, gx;
	cin >> R >> C;
	cin >> sy >> sx >> gy >> gx;
	sy--; sx--; gx--; gy--;
	char c[51][51];
	int d[51][51];
	for (int i = 0; i < R; ++i) {
		for (int j = 0; j < C; ++j) {
			cin >> c[i][j];
			d[i][j] = INF;
		}
	}
	int dx[4] = { 1,0,-1,0 };
	int dy[4] = { 0,1,0,-1 };
	queue<pii>Q;
	Q.push({ sy,sx });
	d[sy][sx] = 0;
	while (!Q.empty()) {
		int y = Q.front().first;
		int x = Q.front().second;
		Q.pop();
		for (int i = 0; i < 4; ++i) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (0 <= ny && ny < R && 0 <= nx && nx < C&&c[ny][nx] == '.'&&d[ny][nx]==INF){
				Q.push({ ny,nx });
				d[ny][nx] = d[y][x] + 1;
			}
		}
	}
	cout << d[gy][gx] << endl;
    return 0;
}
```
幅優先探索



D

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
ll A, B;
ll dp[30][2][2];
ll solve(string S) {
	const int N = S.size();
	memset(dp, 0, sizeof(dp));
	dp[0][0][0] = 1;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < 2; ++j) {
			for (int k = 0; k < 2; ++k) {
				int x = j ? 9 : S[i] - '0';
				for (int d = 0; d <= x; ++d) {
					dp[i + 1][j || d < x][k || d == 4 || d == 9] += dp[i][j][k];
				}
			}
		}
	}
	return dp[N][0][1] + dp[N][1][1];
}
int main() {
	cin >> A >> B;
	cout << solve(to_string(B)) - solve(to_string(A - 1)) << endl;
	return 0;
}
```
桁dp