COLOCON -Colopl programming contest 2018 C - すぬけそだて――ごはん――
問題ページ
C - すぬけそだて――ごはん――
この記事は解説ではなくクソポエムです。
考えたこと
- 互いに素とか言われたのでgcdとかlcmとかが頭に浮かぶ
- 制約が見たこと無い形をしている
- グラフを書いて互いに素じゃない頂点の間に辺を張ると最大独立集合みたいな雰囲気を感じる
- 枝刈り全探索すればワンチャン通るのではと思ったけど計算量怪しいしatcoderだしきれいな解法があると信じて考える
- 2の倍数、3の倍数、…、35の倍数の個数を調べて包除原理とか考えるけど無理
- a<=10, b<=10くらいまで実験してみたが何もわからない
残り20分とかでヤケクソで枝刈り全探索を書いたら普通に通った(は?)
偶数は1つしか使えないから奇数だけ全列挙すればいいの言われればそれはそうだった
反省
- 実装一瞬でフルフィードバックなんだしとりあえず投げろ
- 値の範囲を区切って一部だけ全列挙みたいなの何回か解いたことあるのに気づきすらしなかった
#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back #ifdef int const ll INF = (1LL<<60); #else const int INF = (1LL<<30); #endif const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; int a, b; VI g[40]; int func(int v, VI& used) { if(v == b) { if(!used[v-a]) return 2; else return 1; } int ret = 0; if(!used[v-a]) { VI n = {v-a}; for(int i: g[v-a]) if(!used[i]) n.PB(i); for(int i: n) used[i] = 1; ret += func(v+1, used); for(int i: n) used[i] = 0; } if(used[v-a]) { ret += func(v+1, used); } else { used[v-a] = 1; ret += func(v+1, used); used[v-a] = 0; } return ret; } signed main(void) { cin >> a >> b; FOR(i, a, b+1) { FOR(j, i+1, b+1) { if(i == j) continue; if(__gcd(i, j) != 1) { g[i-a].PB(j-a); g[j-a].PB(i-a); // cout << i << " " << j << endl; } } } VI used(b-a+1); REP(i, b-a+1) used[i] = 0; cout << func(a, used) << endl; return 0; }