みなさんこんにちは。ABC269のA-Eの解説を書いていきたいと思います。
F問題の解説は、こちらに書いています。
リンク：https://qiita.com/swapman/items/6b485982549721b22b86
僕は毎日夜21時からswapコンというバーチャルコンテストを開いており、そこで解けた問題と、解けなかった問題を分けて解説を書いています！swapコンへの参加もぜひよろしくお願いいたします！みんなで強くなりましょう！
それでは、本編です！
【A問題】Anyway Takahashi
この問題は、言われたことをやるだけです。特に解説することはありません。Takahashiを出力することを忘れないようにしましょう。コードは以下です。
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using mint = modint998244353;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const double EPS = 1e-10;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int dx[8] = {1,1,1,0,0,-1,-1,-1};
const int dy[8] = {1,0,-1,1,-1,1,0,-1};
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define yes {puts("Yes"); return;}
# define no {puts("No"); return;}
# define dame {puts("-1"); return;}
# define yn {puts('Yes');} else{puts('No');}
# define ret(x) {cout << (x) << endl; return 0;}
# define ll long long
# define fi first
# define se second
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define vvi vector<vector<int>>
# define vvl vector<vector<long long>>
# define vvb vector<vector<bool>>
# define vpi vector<pair<int, int>>
# define vpl vector<pair<ll, ll>>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define rep(i,n) for(int i = 0; i < n; i++)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define all(obj) (obj).begin(), (obj).end()
# define rall(obj) (obj).rbegin(), (obj).rend()
# define _GLIBCXX_DEBUG
# define Pll pair<ll, ll>
# define P pair<int,int>
# define bit(x,i) (((x) >> (i)) & 1)
# define equals(a, b) (fabs((a) - (b)) < EPS) // 誤差を考慮した同値判定
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(vector<T>&v){stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v){if(v.size())o<<join(v);return o;}
template<typename T>ostream& operator<<(ostream&o,vector<vector<T>>&vv){if(vv.size())o<<join(vv);return o;}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int a,b,c,d;
cin >> a >> b >> c >> d;
cout << (a+b) * (c-d) << endl;
cout << "Takahashi" << endl;
}
【B問題】Rectangle Detection
この問題は、ある矩形区間の左上と右上の座標を1-indexedで出力する問題です。実装に少し迷う人もいたかもしれませんので、少しだけ。
左上の座標は、マス目を左上から1つずつ見ていって始めて、＃が出てきた座標をメモ、右下は最後に＃が出てきた座標をメモすればいいです。
コードは以下です。
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using mint = modint998244353;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const double EPS = 1e-10;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int dx[8] = {1,1,1,0,0,-1,-1,-1};
const int dy[8] = {1,0,-1,1,-1,1,0,-1};
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define yes {puts("Yes"); return;}
# define no {puts("No"); return;}
# define dame {puts("-1"); return;}
# define yn {puts('Yes');} else{puts('No');}
# define ret(x) {cout << (x) << endl; return 0;}
# define ll long long
# define fi first
# define se second
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define vvi vector<vector<int>>
# define vvl vector<vector<long long>>
# define vvb vector<vector<bool>>
# define vpi vector<pair<int, int>>
# define vpl vector<pair<ll, ll>>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define rep(i,n) for(int i = 0; i < n; i++)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define all(obj) (obj).begin(), (obj).end()
# define rall(obj) (obj).rbegin(), (obj).rend()
# define _GLIBCXX_DEBUG
# define Pll pair<ll, ll>
# define P pair<int,int>
# define bit(x,i) (((x) >> (i)) & 1)
# define equals(a, b) (fabs((a) - (b)) < EPS) // 誤差を考慮した同値判定
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(vector<T>&v){stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v){if(v.size())o<<join(v);return o;}
template<typename T>ostream& operator<<(ostream&o,vector<vector<T>>&vv){if(vv.size())o<<join(vv);return o;}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
vector<string> s(10);
rep(i,10) cin >> s[i];
bool fl = true;
int si, sj, ti, tj;
rep(i,10) {
rep(j,10) {
if(fl && s[i][j] == '#') {
si = i+1;
sj = j+1;
fl = false;
}
}
}
rep(i,10) {
rep(j,10) {
if(s[i][j] == '#') {
ti = i+1;
tj = j+1;
}
}
}
cout << si << " " << ti << endl;
cout << sj << " " << tj << endl;
}
【C問題】Submask
この問題は、再帰関数を使いましょう。頭が良い人は公式解説にあるbit演算出通してください。
再帰関数を使う方法を説明します。まず、与えられるNを二進数の文字列にします。具体的にはN=6の時、目的の文字列Sは'110'になります。
このSよりも小さい間、DFSを潜ります。具体的にはSのi桁目が0なら、作成している文字列に0を追加してDFSを潜る。Sのi桁目が1なら、作成している文字列に0を追加してDFSを潜った後、1つ戻って、目的の文字列に1を追加してDFSを潜る。これを繰り返して、作成している文字列がSと全く同じになった瞬間、DFSを終了すればいいです。 再帰関数の1つ戻って違う再帰に入ると言う感覚は、慣れが大きいので再帰関数を使う問題をたくさん解くことをお勧めします。僕のおすすめは、DFSのコードを解読して再帰関数を理解することです。話を戻して、コードは以下です。
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using mint = modint998244353;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const double EPS = 1e-10;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int dx[8] = {1,1,1,0,0,-1,-1,-1};
const int dy[8] = {1,0,-1,1,-1,1,0,-1};
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define yes {puts("Yes"); return;}
# define no {puts("No"); return;}
# define dame {puts("-1"); return;}
# define yn {puts('Yes');} else{puts('No');}
# define ret(x) {cout << (x) << endl; return 0;}
# define ll long long
# define fi first
# define se second
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define vvi vector<vector<int>>
# define vvl vector<vector<long long>>
# define vvb vector<vector<bool>>
# define vpi vector<pair<int, int>>
# define vpl vector<pair<ll, ll>>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define rep(i,n) for(int i = 0; i < n; i++)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define all(obj) (obj).begin(), (obj).end()
# define rall(obj) (obj).rbegin(), (obj).rend()
# define _GLIBCXX_DEBUG
# define Pll pair<ll, ll>
# define P pair<int,int>
# define bit(x,i) (((x) >> (i)) & 1)
# define equals(a, b) (fabs((a) - (b)) < EPS) // 誤差を考慮した同値判定
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(vector<T>&v){stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v){if(v.size())o<<join(v);return o;}
template<typename T>ostream& operator<<(ostream&o,vector<vector<T>>&vv){if(vv.size())o<<join(vv);return o;}
ll binary_pow(ll a, ll n) {
if(n == 0) return 1;
ll x = binary_pow(a,n/2);
x *= x;
if(n%2) x *= a;
return x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll n;
cin >> n;
string s = "";
for(int i = 0; i < 61; i++) {
if(bit(n,i)) s += '1';
else s += '0';
}
reverse(all(s));
string t;
vector<ll> ans;
auto convert = [&](string s) -> ll {
reverse(all(s));
int len = sz(s);
ll res = 0;
for(int i = 0; i < len; i++) {
res += (s[i]-'0') * binary_pow(2,i);
}
return res;
};
auto dfs = [&](auto& f, int keta, string s, string t) -> void {
if(keta == sz(s)) {
ans.push_back(convert(t));
return;
}
if(s[keta] == '0') {
f(f, keta+1, s, t+'0');
} else {
f(f, keta+1, s, t+'0');
f(f,keta+1, s, t+'1');
}
};
dfs(dfs,0,s,t);
for(auto a : ans) cout << a << endl;
}
【D問題】Do use hexagon grid
この問題は典型的なUnion-Findを使う問題です。問題文で指定された条件に従って、頂点をマージしていけばいいです。連結成分の数ですが、各連結成分のなかにリーダーとなる頂点を設けると、そのリーダーと自分自身が一致するのは、リーダー自身のみで一意に定まります。 すなわち、各連結成分のリーダーの数を数えれば、それすなわち連結成分の数です。コードは以下です。
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using mint = modint998244353;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const double EPS = 1e-10;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int dx[8] = {1,1,1,0,0,-1,-1,-1};
const int dy[8] = {1,0,-1,1,-1,1,0,-1};
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define yes {puts("Yes"); return;}
# define no {puts("No"); return;}
# define dame {puts("-1"); return;}
# define yn {puts('Yes');} else{puts('No');}
# define ret(x) {cout << (x) << endl; return 0;}
# define ll long long
# define fi first
# define se second
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define vvi vector<vector<int>>
# define vvl vector<vector<long long>>
# define vvb vector<vector<bool>>
# define vpi vector<pair<int, int>>
# define vpl vector<pair<ll, ll>>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define rep(i,n) for(int i = 0; i < n; i++)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define all(obj) (obj).begin(), (obj).end()
# define rall(obj) (obj).rbegin(), (obj).rend()
# define _GLIBCXX_DEBUG
# define Pll pair<ll, ll>
# define P pair<int,int>
# define bit(x,i) (((x) >> (i)) & 1)
# define equals(a, b) (fabs((a) - (b)) < EPS) // 誤差を考慮した同値判定
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(vector<T>&v){stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v){if(v.size())o<<join(v);return o;}
template<typename T>ostream& operator<<(ostream&o,vector<vector<T>>&vv){if(vv.size())o<<join(vv);return o;}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> x(n), y(n);
for(int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
--x[i]; --y[i];
}
dsu uf(n);
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
if(x[i] == x[j]-1 && y[i] == y[j]-1) uf.merge(i,j);
if(x[i] == x[j]-1 && y[i] == y[j]) uf.merge(i,j);
if(x[i] == x[j] && y[i] == y[j]-1) uf.merge(i,j);
if(x[i] == x[j] && y[i] == y[j]+1) uf.merge(i,j);
if(x[i] == x[j]+1 && y[i] == y[j]) uf.merge(i,j);
if(x[i] == x[j]+1 && y[i] == y[j]+1) uf.merge(i,j);
}
}
int ans = 0;
for(int i = 0; i < n; i++) {
if(i == uf.leader(i)) ans++;
}
cout << ans << endl;
}
【E問題】Last Rook
珍しいインタラクティブ問題です。実装は少し迷いますが、質問回数が20回と言うのが大ヒントですね。2の10乗が1024となり、これはNの制約と綺麗に一致します。これを縦横一回ずつ行えば、20回で質問は事足ります。と言うことで、二分探索を考えましょう。縦横一方を固定して、固定していない方を二分探索します。例えば、横を固定すると縦に対して二分探索します。縦の長さが10とすると、「真ん中の1~5のなかに何個のルークがありますか？」と聞いて、もし5個あるなら、前半5行内に目的の行は存在しないことがわかります。これを繰り返し、縦横同じことをやればいいです。コードは以下です。
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using mint = modint998244353;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const double EPS = 1e-10;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int dx[8] = {1,1,1,0,0,-1,-1,-1};
const int dy[8] = {1,0,-1,1,-1,1,0,-1};
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define yes {puts("Yes"); return;}
# define no {puts("No"); return;}
# define dame {puts("-1"); return;}
# define yn {puts('Yes');} else{puts('No');}
# define ret(x) {cout << (x) << endl; return 0;}
# define ll long long
# define fi first
# define se second
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define vvi vector<vector<int>>
# define vvl vector<vector<long long>>
# define vvb vector<vector<bool>>
# define vpi vector<pair<int, int>>
# define vpl vector<pair<ll, ll>>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define rep(i,n) for(int i = 0; i < n; i++)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define all(obj) (obj).begin(), (obj).end()
# define rall(obj) (obj).rbegin(), (obj).rend()
# define _GLIBCXX_DEBUG
# define Pll pair<ll, ll>
# define P pair<int,int>
# define bit(x,i) (((x) >> (i)) & 1)
# define equals(a, b) (fabs((a) - (b)) < EPS) // 誤差を考慮した同値判定
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(vector<T>&v){stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v){if(v.size())o<<join(v);return o;}
template<typename T>ostream& operator<<(ostream&o,vector<vector<T>>&vv){if(vv.size())o<<join(vv);return o;}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
while(1) {
ll ac = n+1, wa = 0;
while(ac-wa > 1) {
ll wj = (wa + ac) / 2;
cout << "?" << " " << 1 << " " << wj << " " << 1 << " " << n << endl;
int ans;
cin >> ans;
if(ans == -1) {
return 0;
}
if(ans == wj) wa = wj;
else ac = wj;
}
int h = ac;
ac = n+1, wa = 0;
while(ac-wa > 1) {
ll wj = (ac+wa)/2;
cout << "?" << " " << 1 << " " << n << " " << 1 << " " << wj << endl;
int ans;
cin >> ans;
if(ans == -1) {
return 0;
}
if(ans == wj) wa = wj;
else ac = wj;
}
int w = ac;
cout << "!" << " " << h << " " << w << endl;
return 0;
}
}
【終わりに】
今回はペナはありつつもA-Eまでは全完できました！復習ができているようで少しホッとしました。引き続きswapコンをやっていくので、ご参加よろしくお願いいたします！F問題の解説と言うか覚書と言うか、反省を書いた記事を上げているので、そちらも是非読んでください！今日はこれくらいにします！それでは！