| 
1 2 3 1 2 3 3 1 2 3 1 2 2 3 1 2 3 1 ....
// 左上の 1 から DFS 開始 - 1 ? 2 - ? 1 ? - ↓ 1に戻ってきたけど2の隣なので1で良かった、結果オーライ！的な - 1 2 2 - 1 1 2 -
vector <string> B; VVI vis; ll ans; int N; class HexagonalBoard { public: void dfs(int x, int y, int col) { if(vis[y][x]) { if(vis[y][x]!=col) {ans=3;return;} return; } vis[y][x]=col; int dx[] = {-1,0,1,1,0,-1}; int dy[] = {0,-1,-1,0,1,1}; REP(i, 6) { int nx=x+dx[i]; int ny=y+dy[i]; if(0<=nx&&nx<N && 0<=ny&&ny<N && B[ny][nx]=='X') dfs(nx, ny, col==1?2:1); } } int minColors(vector <string> BB) { B=BB; N=B.size(); vis = VVI(N, VI(N)); ans = 0; REP(y, N) REP(x, N) { if(!vis[y][x] && B[y][x]=='X') dfs(x, y, 1); if(ans==3) return 3; } REP(y, N) REP(x, N) { ans=max(ans, vis[y][x]); } //cout<<w<<endl; return ans; } };
| 
class MayTheBestPetWin { public: int calc(vector <int> A, vector <int> B) { int N = A.size(); VI SUM(N); REP(i, N) SUM[i]=A[i]+B[i]; int sumA = accumulate(ALL(A), 0); int sumB = accumulate(ALL(B), 0); int maxK = 10000 * N * 2 + 500; VVI dp(2, VI(maxK)); int men=0; dp[men][0] = 1; REP(i, N) { REP(k, maxK) { if(dp[men][k]==0) continue; dp[1-men][k] = 1; dp[1-men][k + SUM[i]] = 1; assert(k + SUM[i] < maxK); } men ^= 1; } int ans = 1<<30; REP(k, maxK) { if(dp[men][k]) ans = min(ans, max(abs(sumA-k), abs(sumB-k))); } return ans; } };
| 
(あとで)
double dp[2][210][110][110]; int main() { //ios::sync_with_stdio(false); ll N, D; int tb[]={ 0, 0, 0, 1, 0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 1, 1, 1, 0, }; while(cin>>N>>D) { int p2=0, p3=0, p5=0; while(D%2==0) p2++,D/=2; while(D%3==0) p3++,D/=3; while(D%5==0) p5++,D/=5; if(D>1) { cout<<0<<endl; continue; } // cout<<p2<<" "<<p3<<" "<<p5<<endl; int men=0; REP(m, 2) REP(i, 210) REP(j, 110) REP(k, 110) dp[m][i][j][k]=0; dp[men][0][0][0] = 1; REP(I, N) { REP(i, 210) REP(j, 110) REP(k, 110) { if(dp[men][i][j][k]==0.0) continue; REP(me, 6) { int ni = i+tb[me*3+0]; int nj = j+tb[me*3+1]; int nk = k+tb[me*3+2]; if(ni<210 && nj<110 && nk<110) dp[1-men][ni][nj][nk] += dp[men][i][j][k] / 6.0; } } REP(i, 210) REP(j, 110) REP(k, 110) dp[men][i][j][k]=0; men ^= 1; // PRINT3(dp, 5, 5, 1); } double ans = 0; REP(i, 210) REP(j, 110) REP(k, 110) if(i>=p2 && j>=p3 && k>=p5) ans += dp[men][i][j][k]; cout<<ans<<endl; } return 0; }
| 
double f(double EP, double EQ) { return 1.0 / (1 + pow(10, (EQ-EP)/400)); } int main() { //ios::sync_with_stdio(false); ll K; while(cin>>K) { VI E(1<<K); REP(i, 1<<K) cin>>E[i]; vector<double> p(1<<K, 1), np(1<<K); REP(round, K) { int size = 1<<round; int games = (1<<K)/size/2; // cout<<"round: "<<size<<" "<<games<<endl; REP(game, games) { int asidx = game*size*2; int bsidx = game*size*2+size; REP(ai, size) { REP(bi, size) { double pawin = f(E[asidx+ai], E[bsidx+bi]); np[asidx+ai] += p[asidx+ai]*p[bsidx+bi]*pawin; np[bsidx+bi] += p[asidx+ai]*p[bsidx+bi]*(1-pawin); } } } // cout<<"np: "<<np<<endl; p = np; np = vector<double>(1<<K); } REP(i, 1<<K) cout<<p[i]<<endl; } return 0; }
| 
struct UnionFind { vector<int> data; UnionFind(int size) : data(size, -1) { } bool Union(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool Find(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; class GooseTattarrattatDiv1 { public: int getmin(string S) { UnionFind uf(26); int N=S.size(); REP(i, N/2) { uf.Union(S[i]-'a', S[N-1-i]-'a'); } map<int, int> vis; int ans = 0; REP(i, 26) { int root = uf.root(i); if(vis[root]) continue; vis[root]=1; string same; VI cnt; REP(j, 26) { if(root==uf.root(j)) { same+=string(1, 'a'+j); int ct=0; REP(k, N) if(S[k]=='a'+j) ct++; cnt.PB(ct); } } //cout<<string(1, 'a'+i)<<" "<<same<<" "<<cnt<<endl; if(same.size()==0) continue; sort(ALLR(cnt)); ans += accumulate(ALL(cnt), 0)-cnt[0]; } return ans; } };
| 
(あとで)
class GUMIAndSongsDiv1 { public: int maxSongs(vector <int> D, vector <int> tone, int T) { int N=D.size(); VVI dp(N, VI(N+1, 1<<30)); vector<PII> w; REP(i, N) w.PB(MP(tone[i], D[i])); sort(ALL(w)); REP(i, N) D[i]=w[i].second, tone[i]=w[i].first; REP(i, N) { dp[i][0] = 0; dp[i][1] = D[i]; RANGE(n, 2, N+1) { REP(j, i) { dp[i][n] = min(dp[i][n], dp[j][n-1] + D[i] + abs(tone[i]-tone[j])); } } } int ans = 0; REP(i, N) REP(n, N+1) if(dp[i][n]<=T) ans = max(ans, n); return ans; } };
| 
(あとで)
class TriangleXor { public: int theArea(int W) { long double ans = 0; REP(i, W+1) { long double h = i==0 ? 1 : 1-(long double)i/(i+W); long double K = i==0 ? 1 : 2*((i&1)?-1:1); ans += K * 0.5 * (W+1-i) * W * h; } return (int)ans; } };
