みなさん、こんにちは。第10回swapコンの振り返りを投稿します。
swapコンの詳細はこちら: https://qiita.com/swapman/items/62e9fedc2a3e39b9d28c
この記事では、自分が解けなかったF問題の解説を覚書として残したいと思います。それではいきましょう！
ABC262のリンク: https://atcoder.jp/contests/abc262
【解説を見る前の僕の考察と反省】
まずは赤の塗り方を決め打ちして、端点が異なる色で塗られた辺の本数をカウントすることを考えました。計算量がバカにならないので厳しいことにすぐに気づきます。でも頂点ごとに独立に考えることができたら嬉しいことがいっぱいありそうなので、その方針で考えていました。
方針として辺のカテゴライズの仕方は、端点を赤--赤、赤--青、青--青の3パターンしかなく、異なる色で塗られている辺の本数の偶奇は書くケースにおいて、0,1,0です。ここまでは言えてもそれ以上考察が進まず、タイムアウトでした。ぐぬぬ...
【解説を拝見してAC】
結論から言うとめっちゃ惜しかったです...。悔しすぎますね。ここからもう一段階の言い換えが必要です。先ほどのカテゴライズの方法は合っていて、このカテゴライズの仕方を言い換えます。**異なる色で塗られている辺の本数の偶奇は、赤の頂点の個数の偶奇に一致します。**これに気づければほとんど解けたようなものです。赤の頂点の塗り方を考えると、次数が奇数の頂点を偶数個(以下i個)選んで、次数が偶数個の頂点をk-i個選べばいいです。これはコンビネーションで解くことができますが、modを勝手に取りながらコンビネーションを計算してくれるライブラリがあると便利だと思います。結構使用頻度は高いので、作成しておくことをお勧めします。と言いながら僕はsnukeさんのをそのままパクったので、皆さんもぜひパクってください。パクって自分で解読して理解すればいいだけの話なので、どんどんパクればいいと思います。長期休みになったら上位勢のライブラリをC++の勉強がてら解読していくシリーズやってみたいです。ってことで、以下がACコードです。
#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 0;}
# define ll long long
# define fi first
# define se second
# 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;}
struct combination {
vector<mint> fact, ifact;
combination(int n):fact(n+1),ifact(n+1) {
assert(n < mod);
fact[0] = 1;
for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
ifact[n] = fact[n].inv();
for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[k]*ifact[n-k];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n,m,k;
cin >> n >> m >> k;
vector<int> deg(n);
rep(i,m) {
int u,v;
cin >> u >> v;
--u;--v;
deg[u]++;
deg[v]++;
}
vector<int> mod2deg(2);
rep(i,n) mod2deg[deg[i]%2]++;
combination c(220000);
mint ans = 0;
for(int i = 0; i <= n; i += 2) {
ans += c(mod2deg[1], i) * c(mod2deg[0], k-i);
}
cout << ans.val() << endl;
}
【終わりに】
青diffは難しいですね...。でも僕の持論として水色に上がるためには青diffをしっかり勉強するようにならないと上がれない気がしているので難しくても頑張り続けたいです。皆さんも一緒に頑張りましょう！それでは！