ABC289 参加記録
A - flip
問題概要
0と1の種類のみからなる文字列 2 が与えられます。 s に含まれるすべての s 0を1に、1を0に置き換えて出力してください。
1\leq |s| \leq 10 -
s 0と1のみからなる文字列
解説
どうやってもいいだろうけど、普通にforとかを回せばいい。
実装例
#include<iostream>
using namespace std;
int main() {
string s;
cin >> s;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '0') {
s[i] = '1';
}
else {
s[i] = '0';
}
}
cout << s << '\n';
}
#include<iostream>
using namespace std;
int main() {
string s;
cin >> s;
for (auto& c : s) {
if (c == '0') {
c = '1';
}
else {
c = '0';
}
}
cout << s << '\n';
}
B - レ
問題概要
から 1 までの整数が小さい順に一列に並んでいます。 N
整数の間には、個の「レ」が挟まっています。 M 個目の「レ」は、整数 i と整数の a_i の間にあります。 a_{i+1}
以下の手順に沿ってから 1 の数字を、一回ずつすべて読みます。 N
から 1 までの番号のついて無向グラフ N を考える。 G 個目の辺は頂点 i と頂点 a_i を結んでいる。 a_i+1 - 読まれていない整数が存在する間、以下を繰り返す
- 読まれていない整数のうち、最小のものを
とする。 x において G の含まれる連結成分 x を選び、 C に含まれる頂点の番号を降順にすべて読む。 C 整数の読まれた順番を教えてください。
1\leq N\leq 100 1\leq M\leq N-1 a_i<a_{i+1}(i<M) 1\leq a_i<N - 入力される値はすべて整数
解説
...Bにしてはかなり難しいと思う。Cとかにいそう。
ここでは、楽をしてUnionFindを使うことにする。
以下の手順を繰り返し行うことで、答えが求まる。
- まだ読んでいない頂点であって、最小のもの(問題文中の
x
\rightarrow -
y=N,N-1,\dots,1 x,y y
すでに読んでいるか?を持つフラグを管理し、連結判定にUnionFindを使えば十分高速に処理できる。
実装例
ACL(AtCoderLibrary)を使うといい。
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main() {
int n, m;
cin >> n >> m;
dsu uf(n);
for (int i = 0; i < m; i++) {
int a;
cin >> a;
a--;
uf.merge(a, a + 1);
}
vector<bool> flag(n);
while (1) {
int x = -1;
for (int i = 0; i < n; i++) {
if (!flag[i]) {
x = i;
break;
}
}
if (x == -1) {
cout << '\n';
return 0;
}
for (int y = n - 1; y >= 0; y--) {
if (uf.same(x, y)) {
cout << y + 1 << ' ';
flag[y] = true;
}
}
}
}
groupメソッドを使って、区間の左右を持っておけば
C - Coverage
問題概要
以上 1 以下の整数のみからなる N 個の集合 M がある。 S_1,S_2,\dots,S_M
からなります。 S_i=\{a_{i,1},a_{i,2},\dots,a_{i,C_i}\}
個の集合から M 個以上の集合を選ぶ方法は 1 通りありますが、そのうち、以下の条件を満たすものは何通りありますか? 2^M-1
なる任意の整数 1\leq x\leq N について、選んだ集合の中に x を含むようなものが少なくとも一つ存在する。 x
1\leq N\leq 10 1\leq M\leq 10 1\leq C_i\leq N j<j'\Rightarrow a_{i,j}<a_{i,j'} 1\leq a_{i,j}\leq N - 入力はすべて整数
解説
全列挙の部分ではビット全探索を使うと楽に実装できる。
実装例
setとかでやってもいいけど...
#include<iostream>
#include<vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> s(m);
for (auto& ss : s) {
int c;
cin >> c;
for (int i = 0; i < c; i++) {
int a;
cin >> a;
ss |= 1 << a; //aビット目を立てる
}
}
int ans = 0;
for (int msk = 1; msk < (1 << m); msk++) {
int us = 0; //選んだ集合らの和集合
for (int i = 0; i < m; i++) {
if (msk & (1 << i)) {
us |= s[i];
}
}
bool is_ok = true;
for (int i = 1; i <= n; i++) {
if (!(us & (1 << i))) {
is_ok = false;
}
}
if (is_ok) {
ans++;
}
}
cout << ans << '\n';
}
MEMO
bitset使ったりすると
選んだ集合を
と言い換えられます。これは、bit表現を使えば結構高速(N/64)になるはず。
D - Step Up Robot
問題概要
無限に続く階段があり、一番下から順に
段目, 0 段目...となっている。 1
いま、段目にロボットがいる。このロボットは、一回の動作で 0 段分上ることができます。 A_1,A_2,\dots,A_N
また、段目には到達することができません。 B_1,B_2,\dots,B_M
ちょうど段目に到達することができますか? X
1\leq N\leq 10 1\leq A_1<A_2<\cdots<A_N\leq10^5 1\leq M\leq 10^5 1\leq B_1<B_2\cdots<B_M<X\leq10^5 - 入力はすべて整数
解説
こういうのはDPをする
-
\text{dp}[i]=i (\text{true/false})
としよう。この時、
- 初期値:
\text{dp[i]}=\text{false}(i\neq 0),\text{dp}[0]=\text{true} - 遷移:
\text{dp[i]}=\text{dp}[i-A_1]\text{ or }\text{dp}[i-A_2]\text{ or }\cdots\text{ or }\text{dp}{[i-A_N]}
となる。なお、
これを
以上より、
実装例
#include<iostream>
#include<vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (auto& ai : a) {
cin >> ai;
}
int m;
cin >> m;
vector<int> b(m);
for (auto& bi : b) {
cin >> bi;
}
int x;
cin >> x;
vector<bool> flag(x + 1, false), dp(x + 1, false);
for (auto& bi : b) {
flag[bi] = true;
}
dp[0] = true;
for (int i = 1; i <= x; i++) {
if (flag[i])continue;
for (auto& ai : a) {
if (i - ai >= 0 && dp[i - ai]) {
dp[i] = true;
}
}
}
if (dp[x])cout << "Yes\n";
else cout << "No\n";
}
E - Swap Places
問題概要
頂点 N 辺の単純無向グラフ M が与えられる。また、各頂点には赤,青の色が塗られている。 G
現在、高橋君は頂点,青木君は頂点 1 にいる。 N 人は以下の行動を 2 回以上繰り返すことができます。 0
人が同時に、隣接している頂点に移動する。ただし、高橋君の行き先と、青木君の行き先は色が異なる必要がある。 2 高橋君が頂点
に、青木君が頂点 N にいる状態になるまでに必要な行動回数の最小値を求めてください。不可能なときは 1 -1を出力してください。
テストケースが個与えられるので、それぞれについて求めてください。 T
1\leq T\leq 1000 1\leq N\leq 2000 1\leq M\leq\min(\frac{N(N-1)}{2},2000) - 与えられるグラフ
G - 全てのテストケースに対する
N 2000 - 全てのテストケースに対する
M 2000 - 入力はすべて整数
解説
単にグラフ上を調べてもかなり難しい。なぜならば、遷移が2人の位置によるから。
こういう風に、遷移が単に「頂点だけ」「辺だけ」で決定できないときはBFS・DFSなどが使いにくい。
ということで、
すなわち、以下のようなグラフ
- 各頂点は「
の頂点」のペア G で表される。 (v,u)(1\leq v,u\leq N) - 頂点の組
について、以下の条件を満たすその時に限り p_1=(v_1,u_1),p_2=(v_2,u_2) に辺を張る。 p_1\to p_2
において、 G を結ぶ辺, v_1,v_2 を結ぶ辺がいずれも存在する。 u_1,u_2 において、 G に塗られた色と u_2 に塗られた色がことなる。 v_2
この
高橋君が頂点
にいて、青木君が頂点 v にいる u
という状態に対応する。したがって、この
これはBFSなりDFSなりを使えば
実装例
#include<iostream>
#include<queue>
#include<vector>
#include<tuple>
using namespace std;
using graph = vector<vector<int>>;
void solve() {
int n, m;
cin >> n >> m;
vector<int> c(n);
for (auto& cc : c) {
cin >> cc;
}
graph g(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u--, v--;
g[v].push_back(u);
g[u].push_back(v);
}
queue<pair<int, int>> que;
vector<vector<int>> dist(n, vector<int>(n, -1));
que.emplace(0, n - 1);
dist[0][n - 1] = 0;
while (!que.empty()) {
int u, v;
tie(u, v) = que.front();
que.pop();
for (auto nu : g[u])for (auto nv : g[v]) {
if (c[nu] == c[nv])continue;
if (dist[nu][nv] != -1)continue;
dist[nu][nv] = dist[u][v] + 1;
que.emplace(nu, nv);
}
}
cout << dist[n - 1][0] << '\n';
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
感想
Bが難しすぎる気がする...
Discussion