大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)

A. ^{-1}

果然是你 ABC 的 A。

// Problem: A - ^{-1}
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277)
// URL: https://atcoder.jp/contests/abc277/tasks/abc277_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
int main () {
	int n, x;
	scanf ("%d%d", &n, &x);
	for (int i = 1; i <= n; i ++) {
		int a;
		scanf ("%d", &a);
		if (a == x) {
			printf ("%d", i);
			return 0;
		}
	}
	return 0;
}

B. Playing Cards Validation

就。。。？ABC 的 B 名副其实。
能看出来出题人很爱打扑克牌。

// Problem: B - Playing Cards Validation
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277)
// URL: https://atcoder.jp/contests/abc277/tasks/abc277_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
map <string, bool> mp;
bool check(string s) {
	if (s [0] != 'H' &&
		s [0] != 'D' &&
		s [0] != 'C' &&
		s [0] != 'S') {
		return 1;	
	}
	if (s [1] != 'A' &&
		s [1] != '2' &&
		s [1] != '3' &&
		s [1] != '4' &&
		s [1] != '5' &&
		s [1] != '6' &&
		s [1] != '7' &&
		s [1] != '8' &&
		s [1] != '9' &&
		s [1] != 'T' &&
		s [1] != 'J' &&
		s [1] != 'Q' &&
		s [1] != 'K') {
			return 1;
	}
	return 0;
}
int main () {
	ios :: sync_with_stdio (false);
	cin .tie (0);
	cout .tie (0);
	int n;
	cin >> n;
	while (n --) {
		string a;
		cin >> a;
		if (mp [a]) {
			printf ("No");
			return 0;
		}
		if (check (a)) {
			printf ("No");
			return 0;
		}	
		mp [a] = 1;
	}	
	printf ("Yes");
	return 0;
}

C. Ladder Takahashi

好消息：升难度了。
坏消息：还是很水。

考虑用并查集维护最大值，因为数量过大用 unordered_map 维护。

打比赛的时候因为另外 2 个不会打 unordered_map 教了 20 分钟。

// Problem: C - Ladder Takahashi
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277)
// URL: https://atcoder.jp/contests/abc277/tasks/abc277_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
int fa [N], Max [N];
unordered_map <int,int> mp;
int getfa (int x) {
	if (x == fa [x]) {
		return x;
	}
	return fa [x] = getfa (fa [x]);
}
void merge (int x, int y) {
	x = getfa (x);
	y = getfa (y);
	if (x == y) {
		return ;
	}
	fa [x] = y;
	Max [y] = max (Max [x], Max [y]);
	return ; 
}
int main () {
	int n;
	scanf ("%d", &n);
	mp [1] = 1;
	Max [1] = 1;
	fa [1] = 1;
	int cnt = 1;
	for (int i = 1; i <= n; i ++) {
		int a, b;
		scanf ("%d%d", &a, &b);
		if (! mp [a]) {
			mp [a] = ++ cnt;
			Max [cnt] = a;
			fa [cnt] = cnt;
		}
		if (! mp [b]) {
			mp [b] = ++ cnt;
			Max [cnt] = b;
			fa [cnt] = cnt;
		}
		int ah = mp [a], bh = mp [b];
		merge (ah, bh);
	}
	printf ("%d", Max [getfa (1)]);
	return 0;
}

D. Takahashi's Solitaire

开题发现是数学题直接跑路了，没想到很简单……

暂时咕咕了……

E. Crystal Switches

怎么 ABC 这么喜欢出搜索了。

建分层图，2 层，1 层存 \(a_i=1\) 的边,2 层同理。
有“开关”的点 \(u\) 则可以连接一条 1,2 层 u 对应点的边。
跑个 01BFS 就行了。

// Problem: E - Crystal Switches
// Contest: AtCoder - Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277)
// URL: https://atcoder.jp/contests/abc277/tasks/abc277_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
vector <pair <int, int> > l [N * 2];
void add (int u, int v, int w) {
	l [u] .push_back ({v, w});
	return ;
}
int dis [N * 2], n;
void bfs () {
	for (int i = 1; i <= n * 2; i ++) {
		dis [i] = INT_MAX;
	}
	dis [1] = 0;
	deque <int> q;
	q .push_front (1);
	while (! q. empty ()) {
		int u = q .front ();
		q .pop_front ();
		for (pair <int, int> pii : l [u]) {
			int v = pii .first;
			int w = pii .second;
			int d = dis [u] + w;
			if (d < dis [v]) {
				dis [v] = d;
				if (w) {
					q .push_back (v);
				}
				else {
					q .push_front (v);
				}
			}
		}
	}
	return ;
}
int main () {
	int m, s;
	scanf ("%d%d%d", &n, &m, &s);
	for (int i = 1; i <= m; i ++) {
		int u, v, w;
		scanf ("%d%d%d", &u, &v, &w);
		if (w) {
			add (u, v, 1);
			add (v, u, 1);
		}
		else {
			add (u + n, v + n, 1);
			add (v + n, u + n, 1);
		}
	}
	for (int i = 1; i <= s; i ++) {
		int u;
		scanf ("%d", &u);
		add (u, u + n, 0);
		add (u + n, u, 0);
	}
	bfs ();
	int ans = min (dis [n], dis [n * 2]);
	if (ans == INT_MAX) {
		ans = -1;
	}
	printf ("%d", ans);
	return 0;
}