| 
class UndoHistory { public: int minPresses(vector <string> L) { int ans = 0; REP(i, L.size()) { int lans = 1<<30; if(i>0 && L[i].find(L[i-1])==0) { // 前のをそのまま使う + 残りを打つ lans = L[i].size() - L[i-1].size(); } // 必要ならクリアしたあとに全部打つ lans = min<int>(lans, (i==0 ? 0 : 2) + L[i].size()); RANGE(j, 0, i) REP(k, L[j].size()+1) if(L[i].find(L[j].substr(0, k))==0) { // 履歴から呼び出したあとに全部打つ lans = min<int>(lans, 2 + L[i].size() - k); } ans += lans + 1; } return ans; } };
| 
#define INF (1LL<<30) class TheMountain { public: int minSum(int H, int W, vector <int> IY, vector <int> IX, vector <int> IE) { int ans=INF; VVI init(H+2, VI(W+2, 0)); VVI w[4]; REP(i, 4) w[i] = init; REP(i, IY.size()) init[IY[i]+1][IX[i]+1] = IE[i]; VVI dp[4]; REP(i, 4) dp[i] = VVI(H+2, VI(W+2, 0)); int sx[] = {0, W-1, 0, W-1}; int sy[] = {0, 0, H-1, H-1}; int dx[] = {1, -1, 1, -1}; int dy[] = {1, 1, -1, -1}; REP(dir, 4) { int Dx = dx[dir]; int Dy = dy[dir]; for(int y=sy[dir]; 0<=y && y<H; y+=Dy) for(int x=sx[dir]; 0<=x && x<W; x+=Dx) { w[dir][y +1][x +1] = -1; int v = max(init[y+1][x+1], max(w[dir][y +1][x-Dx +1], w[dir][y-Dy +1][x +1])+1); if((w[dir][y +1][x-Dx +1]!=-1 && w[dir][y-Dy +1][x +1]!=-1) && (init[y+1][x+1]==0 || init[y+1][x+1] == v)) { w[dir][y +1][x +1] = v; } dp[dir][y +1][x +1] = -1; int py = dp[dir][y-Dy +1][x +1]; int px = dp[dir][y +1][x-Dx +1]; int pxy = dp[dir][y-Dy +1][x-Dx +1]; if(!(w[dir][y +1][x +1]==-1 || px==-1 || py==-1 || pxy==-1)) { dp[dir][y +1][x +1] = w[dir][y +1][x +1] + py + px - pxy; } } } REP(ty, H) REP(tx, W) { VI wx(W), wy(H); int ok=1; RANGE(x, 0, tx+1) { int a=w[0][ty+1][x+1], b=w[2][ty+1][x+1]; wx[x]=max(wx[x], max(a, b)); if(min(a, b)==-1) ok=0; } RANGE(x, tx, W) { int a=w[1][ty+1][x+1], b=w[3][ty+1][x+1]; wx[x]=max(wx[x], max(a, b)); if(min(a, b)==-1) ok=0; } RANGE(y, 0, ty+1) { int a=w[0][y+1][tx+1], b=w[1][y+1][tx+1]; wy[y]=max(wy[y], max(a, b)); if(min(a, b)==-1) ok=0; } RANGE(y, ty, H) { int a=w[2][y+1][tx+1], b=w[3][y+1][tx+1]; wy[y]=max(wy[y], max(a, b)); if(min(a, b)==-1) ok=0; } if(!ok) continue; int wx_sum=0, wy_sum=0; REP(x, W) wx_sum += wx[x]; REP(y, H) wy_sum += wy[y]; int wxy = wx_sum + wy_sum - min(wx[tx], wy[ty]); int v0 = dp[0][ty-1 +1][tx-1 +1]; int v1 = dp[1][ty-1 +1][tx+1 +1]; int v2 = dp[2][ty+1 +1][tx-1 +1]; int v3 = dp[3][ty+1 +1][tx+1 +1]; if(v0==-1 || v1==-1 || v2==-1 || v3==-1) continue; int v4 = v0+v1+v2+v3; int lans = wxy + v4; ans = min(ans, lans); } return ans==INF ? -1 : ans; } };
| 
#define MAXN 10010 ll facts[MAXN]; ll inv_facts[MAXN]; static const ll MODVAL = 1000000007; ll MODADD(ll x, ll y) { return (x+y)%MODVAL; } ll MODSUB(ll x, ll y) { return (x-y+MODVAL)%MODVAL; } ll MODMUL(ll x, ll y) { return (x*y)%MODVAL; } ll MODPOW(ll x, ll e) { ll v = 1; for(;e;x=MODMUL(x,x),e>>=1) if(e&1) v = MODMUL(v, x); return v; } ll MODINV(ll x) { return MODPOW(x, MODVAL-2); } ll MODCOMB(ll n, ll r) { assert(0<=n && n<MAXN); assert(0<=r && r<=n); ll vv = MODMUL(facts[n], MODMUL(inv_facts[r], inv_facts[n-r])); return vv; } void gen_facts() { facts[0] = 1; inv_facts[0] = MODINV(facts[0]); RANGE(i, 1, MAXN) facts[i] = MODMUL(facts[i-1], i); RANGE(i, 1, MAXN) inv_facts[i] = MODMUL(inv_facts[i-1], MODINV(i)); REP(i, MAXN) assert(MODMUL(facts[i], inv_facts[i])==1); } int co=0; int W, H; void f(vector<string>& F, int D, int x, int y) { if(F[y][x]!='v') return; co++; F[y][x]='x'; REP(yy, H) REP(xx, W) { if(abs(yy-y)+abs(xx-x) <= D) { if(0<=xx && xx<W && 0<=yy && yy<H && F[yy][xx]=='v') { f(F, D, xx, yy); } } } } class GooseInZooDivOne { public: int count(vector <string> F, int D) { gen_facts(); H=F.size(); W=F[0].size(); int even=0, odd=0; int sum=0; int sumCo=0; REP(y, H) REP(x, W) if(F[y][x]=='v') sum++; REP(y, H) { REP(x, W) { if(F[y][x]=='v') { co=0; f(F, D, x, y); if(co&1) odd++; else even++; //cout<<"co "<<co<<endl; //cout<<F<<endl; sumCo+=co; } } } assert(sum==sumCo); cout<<even<<" "<<odd<<endl; ll ea = 1; REP(i, even) { ea = (ea * 2) % MODVAL; } ll oa = 0; for(int i=0;i<=odd;i+=2) { oa = (oa + MODCOMB(odd, i)) % MODVAL; } cout<<ea<<" "<<oa<<endl; return (((ea * oa) % MODVAL) - 1 + MODVAL) % MODVAL; } };
static const ll MODVAL = 1000000007; int co; int W, H; void f(vector<string>& F, int D, int x, int y) { if(F[y][x]!='v') return; F[y][x]='x'; co++; REP(yy, H) REP(xx, W) { if(abs(yy-y)+abs(xx-x) <= D) { if(0<=xx && xx<W && 0<=yy && yy<H && F[yy][xx]=='v') { f(F, D, xx, yy); } } } } class GooseInZooDivOne { public: int count(vector <string> F, int D) { H=F.size(); W=F[0].size(); int even=0, odd=0; REP(y, H) REP(x, W) { if(F[y][x]=='v') { co=0; f(F, D, x, y); if(co&1) odd++; else even++; } } ll ans = 1; REP(i, even + max(0, odd-1)) ans = (ans * 2) % MODVAL; return (ans - 1 + MODVAL) % MODVAL; } };
| 
class EllysRoomAssignmentsDiv1 { public: double getAverage(vector <string> RS) { string s; FOR(e, RS) s+=*e; VI w; stringstream ss(s); int v; while(ss>>v) w.PB(v); int me = w[0]; sort(ALLR(w)); //cout<<w<<endl; int N = w.size(); int ORE=0; REP(i, N) if(me==w[i]) ORE=i; int R = (N+19)/20; cout<<"R "<<R<<endl; cout<<"me "<<me<<endl; cout<<"ore "<<ORE<<endl; double ans = 0; double ext = 0; int p1 = N-N/R*R; double ooi = (double)p1 / R; cout<<"p1 "<<p1<<" "<<N/R<<" "<<endl; for(int i=0;i<N;i+=R) { int NUM = min(R, N-i); if(i/R==ORE/R) { ans += me; continue; } if(NUM==R) { REP(j, NUM) { ans += (double)w[i+j] / NUM; } } else { REP(j, NUM) { ext += (double)w[i+j] / NUM; } } } if((N-1)/R==ORE/R && p1) { return (ans+ext) / (N/R+1); } else { return (1.0-ooi) * ans / (N/R) + ooi * (ans+ext) / (N/R+1); } } };
| 
class TheNumberGame { public: string determineOutcome(int A, int B) { vector<string> w; // なにこれ stringstream ss, sb; sb<<B; ss<<A; string s=ss.str(); REP(i, 2) { if(i==1) reverse(ALL(s)); REP(sj, s.size()) { RANGE(ej, sj, s.size()) { // cout<<s.substr(sj, ej-sj+1)<<endl; if(s.substr(sj, ej-sj+1)==sb.str()) return "Manao wins"; } } } return "Manao loses"; } };
| 
// maximum 476ms in arena int cross(int N, int bit, int cur, int nxt) { // cur, nxt を結んだ線の両サイドに少なくとも１コ以上使用済みノードがあれば交差する int side0 = 0; for(int i=(cur+1)%N; i!=nxt; i=(i+1)%N) if(bit & 1<<i) side0=1; int side1 = 0; for(int i=(nxt+1)%N; i!=cur; i=(i+1)%N) if(bit & 1<<i) side1=1; return side0 && side1; } class PolygonTraversal { public: long long count(int N, vector <int> P) { int M = P.size(); REP(i, M) P[i]--; VVI dp(N, VI(1<<N)); int init_bit = 0; FOR(e, P) init_bit |= 1<<*e; dp[P.back()][init_bit] = 1; REP(bit, 1<<N) { REP(cur, N) { if((bit & 1<<cur)==0) continue; if(dp[cur][bit]==0) continue; REP(nxt, N) { if(bit & 1<<nxt) continue; int ok = cross(N, bit, cur, nxt); if(ok) dp[nxt][bit|1<<nxt] += dp[cur][bit]; } } } ll ans = 0; int bit = (1<<N)-1; REP(cur, N) { int nxt = P[0]; int ok = cross(N, bit, cur, nxt); if(ok) ans += dp[cur][bit]; } return ans; } };
// maximum 117ms in arena int crossB(int N, int bit, int cur, int nxt) { int a = min(cur, nxt); int b = max(cur, nxt); int mask0 = ((1<<b)-1) & ~((1<<(a+1))-1); // 0 0 0 b 1 1 1 a 0 0 0 int mask1 = ~((1<<(b+1))-1) | ((1<<a)-1); // 1 1 1 b 0 0 0 a 1 1 1 int ret = bit & mask0 && bit & mask1; return ret; }
