こんにちは, swapmanです。ABC126の解説を行います。
【A問題】Changing a Character
ループを回して, K番目のところを小文字に変えるだけです。ASCIIコードを見ると, 英小文字は同じアルファベットの大文字より, 32大きいことが分かるので, k番目の文字から32を引いてあげて, それを出力すればいいです。O(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 ret(x) {cout << (x) << endl; return;}
# define ll long long
# define fi first
# define se second
# define pb push_back
# define eb emplace_back
# define pob pop_back
# define GET_MACRO(_1, _2, _3, NAME, ...) NAME
# define _rep(i, n) _rep2(i, 0, n)
# define _rep2(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
# define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
# 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
inline void YesNo(bool f) { std::cout << (f? "Yes": "No") << std::endl; }
# 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;}
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vi = vc<int>; using vvi = vv<int>;
using vl = vc<ll>; using vvl = vv<ll>;
struct Solver {
void solve() {
int n,k;
cin >> n >> k;
string s;
cin >> s;
--k;
char c = s[k];
c += 32;
s[k] = c;
cout << s << endl;
}
};
int main() {
int ts = 1;
// scanf("%d", &ts);
rep(ti,ts) {
Solver solver;
solver.solve();
}
return 0;
}
【B問題】YYMM or MMYY
B問題は任意の文字列をどちらのフォーマットの可能性があるのかを判定してやる問題です。これを判定するには与えられた数列を前側と後側に分けて, これらが0以上99以下か1以上12以下かを見てあげればいいです。詳しい実装はコードを見てください。計算量はO(N)です。
#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 ret(x) {cout << (x) << endl; return;}
# define ll long long
# define fi first
# define se second
# define pb push_back
# define eb emplace_back
# define pob pop_back
# define GET_MACRO(_1, _2, _3, NAME, ...) NAME
# define _rep(i, n) _rep2(i, 0, n)
# define _rep2(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
# define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
# 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
inline void YesNo(bool f) { std::cout << (f? "Yes": "No") << std::endl; }
# 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;}
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vi = vc<int>; using vvi = vv<int>;
using vl = vc<ll>; using vvl = vv<ll>;
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;
}
struct Solver {
void solve() {
string s;
cin >> s;
string front, back;
rep(i,2) front += s[i];
rep(i,2,4) back += s[i];
bool yymm = false, mmyy = false;
int f = 0, b = 0;
reverse(all(front));
reverse(all(back));
rep(i,2) {
char c = front[i];
int nc = c-'0';
f += nc*binary_pow(10,i);
}
rep(i,2) {
char c = back[i];
int nc = c-'0';
b += nc*binary_pow(10,i);
}
if (1 <= f and f <= 12 and 0 <= b and b <= 99) mmyy = true;
if (0<=f and f<=99 and 1<=b and b<=12) yymm = true;
if (mmyy && yymm) cout << "AMBIGUOUS" << endl;
else if(!mmyy && !yymm) cout << "NA" << endl;
else if (mmyy && !yymm) cout << "MMYY" << endl;
else cout << "YYMM" << endl;
}
};
int main() {
int ts = 1;
// scanf("%d", &ts);
rep(ti,ts) {
Solver solver;
solver.solve();
}
return 0;
}
【C問題】Dice and Coin
snuke君がゲームに勝利するには, 得点が0になってはならないので一度もコインで裏が出ず, 得点がkを超えないような場合の数全ての確率を足したものになります。N面全ての目の出方を試すことを考えると, その目が出る確率は1/Nで, 得点がKを超えるまではコインが表を出続けるという1/2の確率を一生引く必要があります。これを愚直に趣味レーションしてもO(NlogK)となり, 十分高速にこの問題を解くことが出来ました。コードは以下のようになります。
#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 ret(x) {cout << (x) << endl; return;}
# define ll long long
# define fi first
# define se second
# define pb push_back
# define eb emplace_back
# define pob pop_back
# define GET_MACRO(_1, _2, _3, NAME, ...) NAME
# define _rep(i, n) _rep2(i, 0, n)
# define _rep2(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
# define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
# 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
inline void YesNo(bool f) { std::cout << (f? "Yes": "No") << std::endl; }
# 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;}
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vi = vc<int>; using vvi = vv<int>;
using vl = vc<ll>; using vvl = vv<ll>;
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;
}
struct Solver {
void solve() {
int n,k;
cin >> n >> k;
double ans = 0;
rep(s,1,n+1) {
double d = (double)1/n;
int now = s;
int cnt = 0;
while(now < k) {
now *= 2;
cnt++;
}
rep(i,cnt) d *= 0.5;
ans += d;
}
printf("%.10lf\n",ans);
}
};
int main() {
int ts = 1;
// scanf("%d", &ts);
rep(ti,ts) {
Solver solver;
solver.solve();
}
return 0;
}
【D問題】Even Relation
この問題は少し考察が必要です。まず条件として任意の2頂点を選ぶとき, これらの距離が偶数になっている必要がありますが, この条件に必要なのは各辺の長さwの値の偶奇のみであることに気づきます。これに気づくと任意の位置頂点からdfsをしてその距離が偶数になっているものだけを出力すればいいです。頂点数をN, 辺の数をMとすると, dfsの計算量はO(N+M)となり十分高速にこの問題を解くことが出来ました。コードは以下のようになります。
#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 ret(x) {cout << (x) << endl; return;}
# define ll long long
# define fi first
# define se second
# define pb push_back
# define eb emplace_back
# define pob pop_back
# define GET_MACRO(_1, _2, _3, NAME, ...) NAME
# define _rep(i, n) _rep2(i, 0, n)
# define _rep2(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
# define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
# 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
inline void YesNo(bool f) { std::cout << (f? "Yes": "No") << std::endl; }
# 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;}
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vi = vc<int>; using vvi = vv<int>;
using vl = vc<ll>; using vvl = vv<ll>;
struct Edge {
int to, co;
Edge(int to, int co) : to(to), co(co) {};
};
struct Solver {
void solve() {
int n;
cin >> n;
vv<Edge> to(n);
rep(i,n-1) {
int u,v,w;
cin >> u >> v >> w;
--u;--v;
w %= 2;
to[u].eb(v,w);
to[v].eb(u,w);
}
vi dist(n);
auto dfs = [&](auto& dfs, int v, int d, int p=-1) -> void {
dist[v] = d;
for(auto [u,w] : to[v]) {
if(u == p) continue;
dist[u] = d+w;
dfs(dfs,u,d+w,v);
}
};
dfs(dfs,0,0);
for(auto& d : dist) d %= 2;
cout << dist << endl;
}
};
int main() {
int ts = 1;
// scanf("%d", &ts);
rep(ti,ts) {
Solver solver;
solver.solve();
}
return 0;
}
【E問題】1 or 2
この問題も少し考察が必要ですが, 手元で実験してみると意外に気付けると思います。
まず, (A[x]+A[y]+z) %2 = 0であるので, zの偶奇が(A[x]+A[y])の偶奇を決定することが分かります。Aとしてあり得る数は, 1か2しかないですが, これは1か0と考えても同じことであることに気づきます。ここまでわかれば後は実験すればいいでしょう。
Sample 2で実験するのが一番良いと思うので, これを用いて説明します。まずはSample 2を式として書いてみます。
・A[1] + A[2] = 1
・ A[2] + A[3] = 0
・A[1] + A[3] = 1
・ A[4] + A[5] = 0
・ A[5] + A[6] = 1
このように書き起こしてみると上3つのケースはどれか, A[1], A[2], A[3]いずれかの偶奇が決定されれば残り全ての要素の偶奇が一意に決まることが分かります。これは下2つのケースについても同様です。すなわち各要素についてUnion-Findをしたときの連結成分数がこの問題の答えになっていることが分かります。Union-Findの計算量はアッカーマン関数の逆数になるので, 十分高速に動くアルゴリズムです。各式についてこれを評価しますが, 高々O(NlogN)くらいで, この問題を解くことが出来ました。
コードは以下のようになります。
#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 ret(x) {cout << (x) << endl; return;}
# define ll long long
# define fi first
# define se second
# define pb push_back
# define eb emplace_back
# define pob pop_back
# define GET_MACRO(_1, _2, _3, NAME, ...) NAME
# define _rep(i, n) _rep2(i, 0, n)
# define _rep2(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
# define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
# 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
inline void YesNo(bool f) { std::cout << (f? "Yes": "No") << std::endl; }
# 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;}
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vi = vc<int>; using vvi = vv<int>;
using vl = vc<ll>; using vvl = vv<ll>;
struct Solver {
void solve() {
int n,m;
cin >> n >> m;
vi x(m),y(m),z(m);
rep(i,m) cin >> x[i] >> y[i] >> z[i];
dsu uf(n+1);
vc<bool> seen(n+1);
rep(i,m) uf.merge(x[i], y[i]);
int ans = 0;
rep(i,1,n+1) if(i == uf.leader(i)) ans++;
printf("%d\n",ans);
}
};
int main() {
int ts = 1;
// scanf("%d", &ts);
rep(ti,ts) {
Solver solver;
solver.solve();
}
return 0;
}
【F問題】XOR Matching
この問題はXORにどれだけ詳しいかによって解法を思いつく速さが変わると思います。
まずはXORの基本的な性質から整理します。まず同じ値同士でXORをとる, すなわちR^R = 0です。また, XOR演算のみを組み合わせた場合, 交換則が成り立ちます。すなわち, A^B^C = C^A^Bです。これさえわかればこの問題を解くことが出来ます。
数列Aには同じ数を2ずつ含める必要があるので, 数列A全体のXORの値は0になります。
これ等の性質を利用すると, 同じ数で挟まれた区間内のXORの値をKにするには0,1,2,3,......a,b,c,K,c,b,a.....3,2,1,K 数列を並べ替えればいいことが分かります。こうしてやれば問題の条件を満たすことが出来ます。しかしコーナーケースには気を付けましょう。一つ目のコーナーケースはK >=2^Mの場合です。XORの重要な性質の一つとして, 桁数がXOR演算によって増加することはあり得ないです。数列Aの中には高々2^(M-1)までしか存在しないので, K >=2^Mのケースは存在しないことが分かります。
最後に(m = 1, k = 1), (m = 1, k= 0)の場合もコーナーケースです。上記で説明した通りに数列を並び替えるとうまくいきません。Sample 2, 3がこれに当たります。(m = 0, k = 0)のケースにおいては(0,0)と置けばいいですが, 何も記述しないと多分落ちるので気を付けましょう。 計算量は実装にもよりますが, 僕はdequeを使ったので,O((2^M)log(2^M))で解くことが出来ました。コードは以下のようになります。
#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 ret(x) {cout << (x) << endl; return;}
# define ll long long
# define fi first
# define se second
# define pb push_back
# define eb emplace_back
# define pob pop_back
# define GET_MACRO(_1, _2, _3, NAME, ...) NAME
# define _rep(i, n) _rep2(i, 0, n)
# define _rep2(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
# define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
# 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
inline void YesNo(bool f) { std::cout << (f? "Yes": "No") << std::endl; }
# 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;}
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vi = vc<int>; using vvi = vv<int>;
using vl = vc<ll>; using vvl = vv<ll>;
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;
}
struct Solver {
void solve() {
int m,k;
cin >> m >> k;
if (m == 1 && k == 1) ret(-1);
if (k >= binary_pow(2,m)) ret(-1);
if (m == 1 && k == 0) { ret("0 1 1 0");}
if (m == 0 && k == 0) { ret("0 0"); }
deque<ll> q;
q.eb(k);
rep(i,1ll<<m) {
if(i == k) continue;
q.eb(i);
q.emplace_front(i);
}
q.eb(k);
rep(i,sz(q)) {
cout << q[i] << " ";
}
cout << endl;
}
};
int main() {
int ts = 1;
// scanf("%d", &ts);
rep(ti,ts) {
Solver solver;
solver.solve();
}
return 0;
}
【終わりに】
Fは難しかったですが, それ以外は割と典型かなとのも思います。最近のABCとは傾向が少し違いますが面白かったです。