| 
↓実装練習 (passed system test in practice room)
(...) #define VS vector<string> #define VI vector<ll> #define VVI vector<vector<ll> > #define VVVI vector<vector<vector<ll> > > #define REP(i,n) for(int i=0,_n=(n);(i)<(int)_n;++i) #define RANGE(i,a,b) for(int i=(int)a,_b=(int)(b);(i)<_b;++i) #define MOD 1000000007LL int W, H; VS rot(const VS& g) { VS o(W, string(H, '?')); REP(y, H) REP(x, W) o[W-1-x][y] = g[y][x]; return o; } VVVI dp; ll f(int y, int splitx, int co, const VS& g) { if(y==H) return co; if(dp[y][splitx][co]!=-1) return dp[y][splitx][co]; ll ans = 0; REP(ns, splitx+1) { int ok=1; RANGE(x, 0, ns) if(g[y][x]=='W') ok=0; RANGE(x, ns, W) if(g[y][x]=='B') ok=0; if(!ok) continue; ans += f(y+1, ns, co || (0<y && ns < splitx), g); ans %= MOD; } return dp[y][splitx][co]=ans; } ll all_(char notc, VS& g) { ll ok=1; REP(y, H) REP(x, W) if(g[y][x]==notc) ok=0; return ok; } class TwoConvexShapes { public: int countWays(vector <string> g) { W=g[0].size(); H=g.size(); ll ans = all_('B', g)+all_('W', g); REP(loop, 4) { W=g[0].size(); H=g.size(); dp = VVVI(H, VVI(W+1, VI(2, -1))); ll r = f(0, W, 0, g); cout<<r<<endl; ans += r; ans %= MOD; g = rot(g); } return ans; } };
| 
↓あとで (passed system test in practice room)
class FoxPaintingBalls { public: long long theMax(long long R, long long G, long long B, int N) { ll tot = (ll)N*(N+1)/2; ll to3 = tot/3; ll lo=0, hi=(R+G+B)/tot+1; while(lo+1<hi) { ll mid = (lo+hi)/2; ll r=R-mid*to3; ll g=G-mid*to3; ll b=B-mid*to3; //cout<<mid<<" "<<r<<" "<<g<<" "<<b<<endl; if(r>=0 && g>=0 && b>=0 && (tot%3 ? (mid <= (r+g+b)/(tot%3)) : 1)) lo=mid; else hi=mid; } return lo; } };
| 
class FoxAndFlowerShopDivOne { public: int theMaxFlowers(vector <string> F, int M) { int W=F[0].size(); int H=F.size(); // sum[y][x] is sum of [0, x) x [0, y) VVI sum(H+1, VI(W+1)); VVI dif(H+1, VI(W+1)); REP(x, W) REP(y, H) { sum[y+1][x+1] = (F[y][x]!='.' ? 1 : 0) + sum[y][x+1]+sum[y+1][x]-sum[y][x]; dif[y+1][x+1] = (F[y][x]=='L' ? 1 : (F[y][x]=='P' ? -1 : 0)) + dif[y][x+1]+dif[y+1][x]-dif[y][x]; } //cout<<sum<<endl; //cout<<dif<<endl; int ans = -1; REP(X, W) { map<int, int> hi0, hi1; // [0, X) x [0, H) for(int x0=0;x0<X;x0++) { for(int x1=x0;x1<X;x1++) { // [x0, x1] x [y0, y1] for(int y0=0;y0<H;y0++) { for(int y1=y0;y1<H;y1++) { int S = sum[y1+1][x1+1] - sum[y1+1][x0] - sum[y0][x1+1] + sum[y0][x0]; int D = dif[y1+1][x1+1] - dif[y1+1][x0] - dif[y0][x1+1] + dif[y0][x0]; hi0[D] = max(hi0[D], S); //cout<<MP(x0, MP(x1, MP(y0, y1)))<<" "<<S<<" "<<D<<endl; } } } } // [X, W) x [0, H) for(int x0=X;x0<W;x0++) { for(int x1=x0;x1<W;x1++) { // [x0, x1] x [y0, y1] for(int y0=0;y0<H;y0++) { for(int y1=y0;y1<H;y1++) { int S = sum[y1+1][x1+1] - sum[y1+1][x0] - sum[y0][x1+1] + sum[y0][x0]; int D = dif[y1+1][x1+1] - dif[y1+1][x0] - dif[y0][x1+1] + dif[y0][x0]; hi1[D] = max(hi1[D], S); } } } } FOR(e0, hi0) FOR(e1, hi1) if(abs(e0->first+e1->first)<=M) ans=max(ans, e0->second+e1->second); } REP(Y, H) { map<int, int> hi0, hi1; // [0, W) x [0, Y) for(int x0=0;x0<W;x0++) { for(int x1=x0;x1<W;x1++) { // [x0, x1] x [y0, y1] for(int y0=0;y0<Y;y0++) { for(int y1=y0;y1<Y;y1++) { int S = sum[y1+1][x1+1] - sum[y1+1][x0] - sum[y0][x1+1] + sum[y0][x0]; int D = dif[y1+1][x1+1] - dif[y1+1][x0] - dif[y0][x1+1] + dif[y0][x0]; hi0[D] = max(hi0[D], S); } } } } // [0, W) x [Y, H) for(int x0=0;x0<W;x0++) { for(int x1=x0;x1<W;x1++) { // [x0, x1] x [y0, y1] for(int y0=Y;y0<H;y0++) { for(int y1=y0;y1<H;y1++) { int S = sum[y1+1][x1+1] - sum[y1+1][x0] - sum[y0][x1+1] + sum[y0][x0]; int D = dif[y1+1][x1+1] - dif[y1+1][x0] - dif[y0][x1+1] + dif[y0][x0]; hi1[D] = max(hi1[D], S); } } } } FOR(e0, hi0) FOR(e1, hi1) if(abs(e0->first+e1->first)<=M) ans=max(ans, e0->second+e1->second); } return ans; } };
| 
class RotatingBot { public: int minArea(vector <int> M) { ll N=M.size(); if(N==1) return M[0]+1; if(N==2) return (M[0]+1)*(M[1]+1); if(N==3) return max(M[0]+1, M[2]+1)*(M[1]+1); ll W=max(M[0]+1, M[2]+1); ll H=max(M[1]+1, M[3]+1); ll sX = W-M[0]-1; ll sY = M[1]; VVI w(H+2, VI(W+2)); REP(x, W+2) w[0][x]=w[H+1][x]=1; REP(y, H+2) w[y][0]=w[y][W+1]=1; w[sY+1][sX+1]=1; int dx[4]={1,0,-1,0}; int dy[4]={0,-1,0,1}; REP(i, N) { int dir=i%4; REP(j, M[i]) { sX += dx[dir]; sY += dy[dir]; if(w[sY+1][sX+1]) return -1; w[sY+1][sX+1]=1; } if(i!=N-1 && w[sY+dy[dir]+1][sX+dx[dir]+1]==0) return -1; } return W*H; } };
| 
see
| 
ll ff(ll d) {
if(d==0) return 0;
if(d==1) return 1;
ll ans=1;
REP(i, d-2) ans*=10;
return ans;
}
ll ref(ll v) {
ll co=0;
for(int i=1;i<=v;i++) {
ll msd=i;
while(msd/10>0) {msd/=10;}
if(msd==i%10) co++;
}
return co;
}
ll f(ll v) {
if(v<10) return ref(v);
if(v==0) return 0;
ll msd=v, co=0;
while(msd/10>0) {msd/=10;co++;}
ll msdd=msd;
REP(i, co) msd*=10;
ll t=v, di=0;
while(t>0) {t/=10;di++;}
ll X = 0;
int xok=0;
{
ll mm = (v-msd)/10;
while(msd+(mm*10+msdd) > v && mm > 0) {
mm--;
}
X = msd+(mm*10+msdd);
if(X<=v) xok = 1;
}
ll vv= xok ? (X-msd)/10 +1 : 0;
ll lower=0;
REP(i, di) lower += 9*ff(i);
ll ans= vv+(msdd-1)*ff(di)+lower;
return ans;
}
int main() {
//REP(i, 10000) {
// ll ra=ref(i);
// ll fa=f(i);
// if(ra!=fa) {cout<<"ERR"<<i<<" "<<ra<<" "<<fa<<endl;return 0;}
//}
ll L,R;
while(cin>>L>>R) {
cout<<f(R)-f(L-1)<<endl;
}
return 0;
}
| 
#define INF (1LL<<60) int main() { ll N; while(cin>>N) { ll half=(N+1)/2; map<ll, ll> hi; map<ll, ll> hiF; VI F(N), B(N); REP(i, N) { cin>>F[i]>>B[i]; hi[F[i]]++; if(F[i]!=B[i]) hi[B[i]]++; hiF[F[i]]++; } //cout<<F<<B<<endl; //cout<<hi<<endl; VI cand; FOR(e, hi) { if(e->second >= half) cand.PB(e->first); } //cout<<cand<<endl; ll ans = INF; REP(i, cand.size()) { ll c = cand[i]; //ll rest = half - count(ALL(F), c); ll rest = half - hiF[c]; ans = min(ans, max(0LL, rest)); } cout<<(cand.size() ? ans : -1LL)<<endl; } return 0; }
| 
// N==3 ４２ ２１ ４のとこに置くと以下のように１が４つになる １０１ ０００ １０１ 右上の２のとこに置くと以下のように１が２つになる ０１０ ０００ ０１０ // N==4 ４４ ４４ // N==5 ４４２ ４４２ ２２１
// X==9 N==5 のばあい ４ ４ ２ ２ →4 4 2 2 じゃ 9 にならないので skip ４ ２ ４ ２ １ →4+4+1==9 なので N==5 で OK // X==3 N==5 のばあい ４ ４ ２ ２ →4 4 2 2 じゃ 3 にならないので skip ４ ２ ４ ２ １ →2+1==3 なので N==5 で OK
int main() { int X; while(cin>>X) { for(int n=1;;n++) { //cout<<n<<endl; { int x = X; int n4 = (n-1)*(n-1)/2; int n2 = ((n-1)/2 + ((n-1)&1))*2; int n1 = 0; //cout<<n4<<" "<<n2<<" "<<n1<<endl; while(n4-->0 && x>=4) x-=4; while(n2-->0 && x>=2) x-=2; while(n1-->0 && x>=1) x-=1; if(x==0) { cout<<2*n-1<<endl; break; } } { int x = X; int n4 = (n-1)*(n-1)/2 + ((n-1)*(n-1)&1); int n2 = (n-1)/2*2; int n1 = 1; //cout<<n4<<" "<<n2<<" "<<n1<<endl; while(n4-->0 && x>=4) x-=4; while(n2-->0 && x>=2) x-=2; while(n1-->0 && x>=1) x-=1; if(x==0) { cout<<2*n-1<<endl; break; } } } } return 0; }
| 
#define INF (1LL<<60) int main() { int N, M; while(cin>>N>>M) { VVI w(N, VI(M)); REP(y, N) REP(x, M) cin>>w[y][x]; VI cx(M); REP(x, M) REP(y, N) cx[x] += w[y][x]; VI cy(N); REP(y, N) REP(x, M) cy[y] += w[y][x]; ll minxv = INF, minx = 10000; REP(px, M+1) { ll a=0; REP(x, M) { ll d = ( x*4+2 - px*4 ); a += cx[x] * d * d; } if(a < minxv) { minxv = a; minx = px; } } ll minyv = INF, miny = 10000; REP(py, N+1) { ll a=0; REP(y, N) { ll d = ( y*4+2 - py*4 ); a += cy[y] * d * d; } if(a < minyv) { minyv = a; miny = py; } } cout<<minxv+minyv<<endl; cout<<miny<<" "<<minx<<endl; } return 0; }