| 
■ ポイント1
|n1以下の集合 ∩ n2以下の集合| = Xect[n1][n2] |n1以下の集合以外 ∩ n2以下の集合| = size[Tree2][n2] - Xect[n1][n2] |n1以下の集合 ∩ n2以下の集合以外| = size[Tree1][n1] - Xect[n1][n2] |n1以下の集合以外 ∩ n2以下の集合以外| = (N - size[Tree1][n1]) - (size[Tree2][n2] - Xect[n1][n2]) n1以下以外 n2以下以外 0 1 2 2 3 n1以下 n2以下 3 4 0 1 4 のとき Xect[n1][n2] = |{4}| = 1 n1以下以外 ∩ n2以下 は? → 0 1 4 のうち 4 は Xect に入ってるので n1 以下にあるので "n1以下以外 ∩ n2以下" には含まれない。 → それ以外の 0 1 は n1 以下にはないはずなので n1 以下以外にあるはず→つまり n1以下以外 ∩ n2以下 に含まれる なので size[Tree2][n2] - Xect[n1][n2]
■ ポイント2
// 理解した後に書いたコード （ほぼそのままですね class TreesAnalysis { public: void dfs(int t, int idx, int prev, vector<VVI>& g, VVI& size, VVI& xect) { int N = xect.size(); size[t][idx]=1; REP(i, g[t][idx].size()) { int ci=g[t][idx][i]; if(ci==prev) continue; dfs(t, ci, idx, g, size, xect); size[t][idx]+=size[t][ci]; REP(j, N) xect[idx][j]+=xect[ci][j]; } } long long treeSimilarity(vector <int> T1, vector <int> T2) { int N=T1.size()+1; vector<VVI> g(2, VVI(N)); VVI size(2, VI(N)); VVI xect(N, VI(N)); REP(t, 2) REP(i, N-1) { int j=(t==0?T1:T2)[i]; g[t][i].PB(j); g[t][j].PB(i); } REP(i, N) xect[i][i]=1; REP(t, 2) { dfs(t, 0, -1, g, size, xect); REP(i, N) RANGE(j, i+1, N) swap(xect[i][j], xect[j][i]); } ll ans = 0; RANGE(i, 1, N) RANGE(j, 1, N) { int x=xect[i][j]; int a=size[0][i]; int b=size[1][j]; ll add = max(x, max(a-x, max(b-x, N-a-(b-x)))); ans += add*add; } return ans; } };
| 
class Family { public: string isFamily(vector <int> P1, vector <int> P2) { int N=P1.size(); VVI diff(N, VI()); REP(i, N) { if(P1[i]==-1) continue; diff[P1[i]].PB(P2[i]); diff[P2[i]].PB(P1[i]); } UnionFind uf(N); REP(i, N) { REP(j, diff[i].size()) { uf.Union(diff[i][0], diff[i][j]); } } REP(i, N) { REP(j, diff[i].size()) { if(uf.Find(i, diff[i][j])) return "Impossible"; } } return "Possible"; } };
| 
例: 1 2 4 12 24 の場合 額 1回で何枚までとれるか 1 1 2 1 4 2 12 1 24 ∞ 額 最大 1,2 回目に何枚とるか(例) 1 1 1,0 2 1 0,1 12 1 1,1 // ここまで (1+1)^2-1 == 3 種類以下ならOK 4 2 2,0 // ここまで (2+1)^2-1 == 8 種類以下ならOK 24 ∞ 3,0 // ここまで (大きな値+1)^2-1 種類以下ならOK
ll po(ll a, ll b) {
ll v=1;
REP(i, b) {
v*=a;
if(v>10000) return 10000; // 1, 2, 3, たくさん の精神
}
return v;
}
class ColorfulCoins {
public:
int minQueries(vector<long long> V) {
int N=V.size();
map<ll, ll> hi;
RANGE(i, 1, N) {
ll v = V[i]/V[i-1];
hi[v]++;
}
hi[1LL<<60]++;
cout<<hi<<endl;
RANGE(n, 1, N+1) {
ll used=0;
int ok=1;
FOR(e, hi) {
ll cap = po(e->first, n) - 1 - used;
// cout<<"C "<<cap<<" "<<e->first<<" "<<e->second<<endl;
if(cap < e->second) {ok=0;break;}
used += e->second;
}
if(ok) return n;
}
return -1;
}
};
| 
あとで
class MinimumSquare { public: long long minArea(vector <int> x, vector <int> y, int K) { int N=x.size(); vector<int> X(x); sort(ALL(X)); ll ans = 1LL<<60; //REP(x0, N) RANGE(x1, x0+1, N) { // だめじゃった REP(x0, N) RANGE(x1, x0, N) { ll W = abs(X[x0]-X[x1])+2; VI Y; REP(i, N) if(X[x0]<=x[i] && x[i]<=X[x1]) Y.PB(y[i]); sort(ALL(Y)); int M=Y.size(); REP(i, Y.size()) { if(i+K-1>=M) break; ll H = abs(Y[i]-Y[i+K-1])+2; ans = min(ans, max(W, H)); } } return ans*ans; } };
| 
class TaroFriends { public: int getNumber(vector <int> C, int X) { ll ans = 1<<30; REP(i, C.size()) { REP(j, 2) { int ok=1; ll lans = 0; ll left = C[i] + (j?-X:X); REP(k, C.size()) { if(left <= C[k]-X) lans=max(lans, abs(C[k]-X - left)); else if(left <= C[k]+X) lans=max(lans, abs(C[k]+X - left)); else ok=0; } if(ok) ans=min(ans, lans); } } return ans; } };