みなさん、こんにちは。ABC270のA-E問題の解説を書いていきます。
F問題の解説は、こちらに書いています。 リンク: https://qiita.com/swapman/items/dc1ce48bc9c0389e1434
僕は毎日夜21時からswapコンというバーチャルコンテストを開いており、そこで解けた問題と、解けなかった問題を分けて解説を書いています！swapコンへの参加もぜひよろしくお願いいたします！みんなで強くなりましょう！
それでは、本編です！
ABC270のリンク: https://atcoder.jp/contests/abc270
【A問題】1-2-4 Test
これAにしてはむずいと思います。よく考えると、これって2進数になっていますね。すぬけ君は高橋君と青木君のどちらかが解けた問題を解ける設定なので、高橋君と青木君の点数のORを取ればいいですね。コードは以下です。
#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;
cin >> a >> b;
cout << a|b << endl;
}
【B問題】Hammer
これも難しいです。まずX,Y,Zの3点の場所が決まっていないのはやりづらいので、ゴールであるXの位置を原点より右に固定します。するとゴールに到達できるかは、ハンマーを拾えるかどうかのみに依存することになります。場合分けは以下のようになります。
・ゴールが壁より先に現れるか、壁がゴールとは真反対の方向にある場合は、ハンマーを拾わずそのままゴールに向かえば良い。
・壁の方がゴールより先に現れるが、その道中にハンマーが存在する場合もそのままゴールに向かえば良い。
・上のパターン以外でハンマーが原点より右に現れるなら、到達不可。
・それ以外は一度ハンマーを拾いに帰ってからゴールに向かうえばよい。
コードは以下です。
#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 x,y,z;
cin >> x >> y >> z;
if(x < 0) {
x *= -1;
y *= -1;
z *= -1;
}
if(x < y || y < 0) {
cout << x << endl;
return 0;
}
else {
if(0 < z && z < y) {
cout << x << endl;
} else if(0 < z) {
cout << -1 << endl;
} else {
cout << abs(z*2) + abs(x) << endl;
}
}
}
【C問題】Simple path
この問題が一番楽に解ける気がします。本番はBFSで解きましたが、DFSの方が楽なのでそちらで実装しました。
イメージとしては、目標とする頂点を見つけるまで、木を潜り続けます。見つけたら「見つかったよ！」という意味を込めて、Trueをreturnさせます。Trueが帰ってくるということは、今潜っているDFSの道の上にターゲットのものがあることを意味します。あとはその道順をvectorかなんかに保存しておけばいいです。コードは以下です。
#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,x,y;
cin >> n >> x >> y;
--x;--y;
vector<vector<int>> to(n);
rep(i,n-1) {
int u,v;
cin >> u >> v;
--u;--v;
to[u].push_back(v);
to[v].push_back(u);
}
vector<int> ans;
auto dfs = [&](auto& f, int v, int t, int p = -1) -> bool {
if(v == t) {
ans.push_back(v+1);
return true;
}
for(int u : to[v]) {
if(u == p) continue;
if(f(f,u,t,v)) {
ans.push_back(v+1);
return true;
}
}
return false;
};
dfs(dfs,x,y);
reverse(all(ans));
cout << ans << endl;
}
一応、BFSのコードも載せておきます。イメージとしては、それぞれの頂点に距離を書き込んでいき、ターゲットの頂点の距離を見にいきます。
ターゲットの頂点の親の距離は、ターゲットに書かれている距離-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 MX = 200005;
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
const int di[8] = {1,1,1,0,0,-1,-1,-1};
const int dj[8] = {1,0,-1,1,-1,1,0,-1};
int getint(){int x; scanf("%d",&x);return x;}
# 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 be begin
# define en end
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define S sort
# define N next_permutation
# define rep(i,n) for(int i = 0; i < n; i++)
# define rrep(i,a,b) for(int i = a; i < b; i++)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define drep(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>
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;}
vector<vector<int>> to;
vector<int> ans;
int n,x,y;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> x >> y;
--x;--y;
to.resize(n);
rep(i,n-1) {
int u,v;
cin >> u >> v;
--u;--v;
to[u].push_back(v);
to[v].push_back(u);
}
vector<int> dist(n, INF);
queue<int> q;
auto push = [&](int v, int d) {
if(dist[v] != INF) return;
dist[v] = d;
q.push(v);
};
push(x,0);
while(sz(q)) {
int v = q.front(); q.pop();
int d = dist[v];
for(auto u : to[v]) push(u,d+1);
}
int now = y;
while(now != x) {
ans.push_back(now);
int d = dist[now];
for(auto nx : to[now]) if(dist[nx] == d-1) {
now = nx;
break;
}
}
ans.push_back(x);
reverse(ALL(ans));
rep(i,sz(ans)) cout << ans[i]+1 << endl;
【D問題】Stones
このコンテストの中で一番強敵です。DPであることに気づくのが難しいですし、DPをどう組むかの過程も難しいと思います。
結論から言うと、dp[i][j]:i番手から始めて、高橋君が取得できる石の個数の最大値 とすればいいです。これはまだいいのですが、漸化式が難しいです。高橋君は、自分の獲得できる石の個数を最大化したい、青木君は高橋君が獲得する石の個数を最小化したい。これが難しいです。
0番手を高橋君、1番手を青木君とすると、漸化式は次のようになります。今カードを取る人の枚数をx枚とすると,
//高橋君の場合
dp[0][i] = max(dp[1][i-x]+x, dp[i][0]);
//青木君の場合
dp[1][i] = min(dp[0][i-x], dp[1][i]);
コードは以下です。
#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,k;
cin >> n >> k;
vector<int> a(k);
for(int i = 0; i < k; i++) cin >> a[i];
vector dp(2, vector<int>(n+1));
//dp[i][j]:手番iから始めて石の個数がj個の時、高橋くんが取ることのできる石の最大個数
// dp[0][0] = 0;
// dp[0][1] = 0;
for(int i = 0; i <= n; i++) {
{//takahashi
int now = 0;
for(int x : a) {
if(i-x >= 0) now = max(now, dp[1][i-x]+x);
}
dp[0][i] = now;
}
{//aoki
int now = INF;
for(int x : a) {
if(i-x >= 0) now = min(now, dp[0][i-x]);
}
dp[1][i] = now;
}
dp[0][0] = 0;
dp[1][0] = 0;
}
cout << dp[0][n] << endl;
}
【E問題】Apple Baskets on Circle
この問題を見ると、周期性が関係してきそうですが、0になったところを飛ばすのが厄介です。でも大体何周回せるかをわかれば、あとはシュミレーションできそうなので、何周回せるかを考えましょう。この答えを二分探索で決めうちしてやれば比較的簡単に解けそうです。
コードは以下です。
#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);
ll n,k;
cin >> n >> k;
vector<ll> a(n);
rep(i,n) cin >> a[i];
ll ac = -1, wa = LINF;
auto f = [&](ll x) -> bool {
ll cnt = 0;
rep(i,n) cnt += min(a[i],x);
return cnt <= k;
};
while(wa-ac > 1) {
ll wj = (ac+wa)/2;
if(f(wj)) ac = wj;
else wa = wj;
}
ll cnt = k;
rep(i,n) {
cnt -= min(ac,a[i]);
a[i] -= min(ac, a[i]);
}
ll now = 0;
while(1) {
if(cnt == 0) {
cout << a << endl;
return 0;
}
if(a[now] == 0) {
now++;
continue;
} else {
a[now]--;
cnt--;
now++;
}
}
}
【終わりに】
ここまで読んでくださってありがとうございます。F問題の記事は別にあげますので、ぜひ読んでください。swapコンへの参加もよろしくお願いします！それでは！