【AtCoder】ABC291 E,F 解説 【C++】

# E問題
不等号だけで数列を特定できるか判定する問題。

https://atcoder.jp/contests/abc291/tasks/abc291_e

## コンテスト中に考えたこと
DFSして、深さが$n$になったものから頂点を確定。順に深さが$i+1$の頂点が確定していれば、それにつながっている深さが$i$の頂点を確定させる、みたいな感じで解けると思ったけど、考えてから数分後に反例が存在することに気づく。$s$から$t$への経路が2通り存在するケースなど。頂点の次数とか、すべて一回ずつ通るパスが関係するのはわかったけど、解答には気づかず。
巡回セールスマンの特殊ケースや、経路復元についてあれこれ調べている間にコンテスト終了。こういうときは大体ドツボにはまっている。

## 解答
[トポロジカルソート](https://ja.wikipedia.org/wiki/%E3%83%88%E3%83%9D%E3%83%AD%E3%82%B8%E3%82%AB%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88#:~:text=%E3%83%88%E3%83%9D%E3%83%AD%E3%82%B8%E3%82%AB%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88%EF%BC%88%E8%8B%B1%3A%20topological%20sort,%E3%82%BD%E3%83%BC%E3%83%88%E3%81%99%E3%82%8B%E3%81%93%E3%81%A8%E3%81%8C%E3%81%A7%E3%81%8D%E3%82%8B%E3%80%82)を使えば簡単に解けた。完全に頭から消えていた。一意性はソートしたすべての隣接頂点間に辺が存在することと同値。トポロジカルソートの部分は、すべての頂点・辺に対して1回だけ調べるため$O(N+M)$。一意性の部分は``map``を用いて、隣接間の辺を調べるため$O(NlogN)$。結局$O(M + NlogN)$となる。
```cpp
const int MX = 2e5 + 2;
vi e[MX];
int a[MX];
bool vst[MX];
int deg_in[MX];
int n, m;
vi ts_node;
map<pii, bool> mp;
 
void bfs(int s) {
	qi Q; Q.push(s);
	while (!Q.empty()) {
		int x = Q.front(); Q.pop();
		vst[x] = true; ts_node.push_back(x);
		for (int y : e[x]) {
			deg_in[y]--;
			if (deg_in[y] == 0 && !vst[y]) {
				Q.push(y);
			}
		}
	}
}
 
void ts() {
	rep(i, n) vst[i] = false;
	rep(i, n) {
		if (!vst[i] && deg_in[i] == 0) bfs(i);
	}
}
 
int main() {
	//(void)scanf("%d",& );
	//(void)scanf("%d%d",& ,& );
	cin >> n >> m;
	rep(i, m) {
		int x, y; (void)scanf("%d%d", &x, &y);
		--x; --y;
		e[x].push_back(y); deg_in[y]++;
		mp[make_pair(x, y)] = true;
	}
	ts();
 
	bool flag = false;
	rep(i, ts_node.size() - 1) {
		int s = ts_node[i], t = ts_node[i + 1];
		if (!mp[make_pair(s, t)]) flag = true;
	}
 
	if (flag) cout << "No" << endl;
	else {
		cout << "Yes" << endl;
		rep(i, ts_node.size()) {
			a[ts_node[i]] = i + 1;
		}
		rep(i, n) {
			if (i == n - 1) cout << a[i] << endl;
			else cout << a[i] << " ";
		}
	}
 
 
	return 0;
}
```

# F問題
$+1$から$+M$のパス移動を繰り返して、1つの頂点を経由せずに$1$から$N$へ到達できるときの最短路を$k$回求める問題。

https://atcoder.jp/contests/abc291/tasks/abc291_f

## 解答
- ``fdp[i]`` : 頂点$1$から$i$への最短路(経路がない場合は``infi``)
- ``bdp[i]`` : 頂点$i$から$N$への最短路(経路がない場合は``infi``)

としてそれぞれ前・後ろからDPしておく。計算量は$O(NM)$。次に、各$k$に対して求める値を$X$とすると、$i=k-M+1$ ～ $k-1$、$j=k+1$ ～ $k+M-1$として、
``fdp[i]``と``bdp[j]``が有限値で、$i$から$j$に移動可能なら、
```math
X=min(fdp[i]+bdp[j]+1,X)
```
という更新を行う。この部分が計算量最大で$O(kM^2)$となり、全体として制約的に$O(NM^2)$。
```cpp
const int MX = 1e5 + 2;
int fdp[MX], bdp[MX];
vector<string> s;
int n, m;
 
 
int main() {
	//(void)scanf("%d",& );
	//(void)scanf("%d%d",& ,& );
 
	//1-indexed
	cin >> n >> m;
	rep(i, n) {
		string str; cin >> str; s.push_back(str);
	}
	repa(i, n) { fdp[i] = bdp[i] = infi; }
	fdp[1] = 0; bdp[n] = 0;
 
	//fdp
	repa(i, n) {
		if (fdp[i] != infi) {
			string str = s[i - 1];
			rep(j, str.length()) {
				if (str[j] == '1' && i+j+1 <= n) {
					fdp[i + j + 1] = min(fdp[i + j + 1], fdp[i] + 1);
				}
			}
		}
	}
 
	//bdp
	for (int i = n; i >= 1; i--) {
		if (bdp[i] != infi) {
			for (int nxt = i - 1; nxt >= max(1, i - m); nxt--) {
				string str = s[nxt - 1];
				if (str[i - nxt - 1] == '1') {
					bdp[nxt] = min(bdp[nxt], bdp[i] + 1);
				}
			}
		}
	}
 
	vi v;
	for (int k = 2; k < n; k++) {
		int ans = infi;
		for (int i = max(1, k - m + 1); i < k; i++) {
			if (fdp[i] != infi) {
				string str = s[i - 1];
				for (int j = k + 1; j <= min(n, k + m - 1); j++) {
					if (j - i <= m && bdp[j] != infi) {
						if (str[j - i - 1] == '1') {
							ans = min(ans, fdp[i] + bdp[j] + 1);
						}
					}
				}
			}
		}
		if (ans == infi) v.push_back(-1);
		else v.push_back(ans);
	}
 
	rep(i, v.size()) {
		if (i == v.size() - 1) cout << v[i] << endl;
		else cout << v[i] << " ";
	}
 
	return 0;
}
```