ARC062 E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer
解法
立方体の上の面と底面を決めると残りの側面に来る面の色配置は一意に定まる。色の配置がvのタイルが何枚あるか？という情報を計算しておけば何通りあるかは求めることができる。C(N,2)通りを全通り試すことで答えが求まる。
ただし、回転等をしっかり考慮してダブらないように数え上げるのが大変。まずタイルを回転することで得られる4通りの色配置に対して辞書順で最小となる並べ方を基準とすることでダブって数えないようにする。各タイルに対して回転で同じ色配置になるようなことがあるかどうかで場合分けしておく。これによって回転で同じ色配置ができるパターンが何通りあるか求められる。
- 回転して同じ色配置が出てくることがない
- 180度回転で同じ配置になる(点対称)
- 90度回転で同じ配置になる(全て同じ色)
上の面のタイルをi番目、底面をj番目に固定する。立方体の上下反転で同じになるものを数えないためi<jと条件をつける。上の面は辞書順最小のもの一つに固定し底面は回転4通りを試す。側面に必要なパネル4枚を列挙し、各色配置に対して何通りの置き方が存在しているのかを求め掛けていく。
N<-400で3乗通るしタイル3枚固定する半分全列挙？とか考えてたけど2枚固定でよかった
細かいところ詰めるのが大変、こういう実装をちゃんとできるようにしていきたい…
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #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() 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<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<typename T> istream& operator >> (istream& is, vector<T>& vec){ for(T& x: vec) {is >> x;} return is; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; // 回転の4通りのうち辞書順で最小のものを返す だぶって数えるのを防ぐ vector<int> getmin(vector<int> v) { vector<int> ret(v); REP(i, 3) { rotate(v.begin(), v.begin()+1, v.end()); chmin(ret, v); } return ret; } // n0枚、n1枚、n2枚でpanel枚を埋める方法が何通り？ ll dfs(ll panel, ll n0, ll n1, ll n2) { if(panel == 0) return 1; ll ret = 0; if(n0) ret += n0*dfs(panel-1, n0-1, n1, n2); if(n1) ret += 2*n1*dfs(panel-1, n0, n1-1, n2); if(n2) ret += 4*n2*dfs(panel-1, n0, n1, n2-1); return ret; } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n; cin >> n; // 0→回転して同じになるものはない // 1→180度回転で同じになる(対角が同じ) // 2→90度回転でも同じ(全部同じ) vector<ll> r(n); map<vector<int>, int> cnt[3]; vector<vector<int>> a(n, vector<int>(4)); REP(i, n) { REP(j, 4) cin >> a[i][j]; a[i] = getmin(a[i]); if(a[i][0] == a[i][2] && a[i][1] == a[i][3]) { r[i] = 1; if(a[i][0] == a[i][1]) r[i] = 2; } cnt[r[i]][a[i]]++; } ll ret = 0; // 上をi番目のパネルに REP(i, n) { // i番目のパネルの分を消す これが側面に来るとだぶるので再度足すことはしない cnt[r[i]][a[i]]--; // 底をj番目のパネルに FOR(j, i+1, n) { // j番目のパネルの分を消す こっちはループの最後で再度足す cnt[r[j]][a[j]]--; // 底面を4通りに回転させる REP(k, 4) { // 側面に必要なパネル4枚を列挙 map<vector<int>, int> mp; mp[getmin({a[i][1], a[i][0], a[j][1], a[j][0]})]++; mp[getmin({a[i][2], a[i][1], a[j][0], a[j][3]})]++; mp[getmin({a[i][3], a[i][2], a[j][3], a[j][2]})]++; mp[getmin({a[i][0], a[i][3], a[j][2], a[j][1]})]++; // 側面に置く方法が何通りあるか ll t = 1; for(auto p: mp) { t *= dfs(p.second, cnt[0][p.first], cnt[1][p.first], cnt[2][p.first]); if(t == 0) break; } ret += t; // 底のパネルを回転 rotate(a[j].begin(), a[j].begin()+1, a[j].end()); } cnt[r[j]][a[j]]++; } } cout << ret << endl; return 0; }
