| 
class SubstringReversal { public: vector <int> solve(string S) { vector<int>ans(2); int N=S.size(); string ref=S; sort(ALL(ref)); if(S==ref) { return ans; } int B=N-1; REP(i, N) if(S[i]!=ref[i]) {B=i;break;} ans[0]=ans[1]=B; if(B<N-1) { vector<pair<string, int> > w; RANGE(i, B, N) { string s = S.substr(B, i-B+1); reverse(ALL(s)); w.PB(MP(s+S.substr(i+1), i)); } sort(ALL(w)); ans[1]=w[0].second; } return ans; } };
| 
// たまにはマクロも #define ll long long #define VI vector<ll> #define PII pair<ll, ll> #define REP(i,n) for(int i=0,_n=(n);(i)<(int)_n;++i) #define ALL(c) (c).begin(), (c).end() #define MP(a, b) make_pair(a, b) // Dijkstra略 class DrivingPlans { public: int count(int N, vector <int> A, vector <int> B, vector <int> C) { int M = A.size(); Dijkstra d(N), r(N); REP(i, M) { d.add_edge(A[i]-1, B[i]-1, C[i]); d.add_edge(B[i]-1, A[i]-1, C[i]); } r=d; int co = d.run(0, N-1); r.run(N-1, 0); vector<PII> p(N); REP(i, N) p[i]=MP(d.V[i], i); sort(ALL(p)); VI ways(N); ways[0] = 1; REP(i, N) { int from = p[i].second; REP(j, d.G[from].size()) { int to=d.G[from][j].to; if(d.V[from] + d.G[from][j].cost + r.V[to] == co) { ways[to] += ways[from]; ways[to] %= 1000000009; REP(k, d.G[from].size()) if(d.G[from][k].cost==0) return -1; REP(k, d.G[to].size()) if(d.G[to][k].cost==0) return -1; } } } return ways[N-1]; } };
| 
class SumAndProductPuzzle { public: long long getSum(int A, int B) { const int N = 5000000; vector<bool> isp(N+1, true); RANGE(p, 2, sqrt(N+1)+2) if(isp[p])for(int q=p*2;q<N+1;q+=p) isp[q]=false; vector<int> cnt(N+1); // cnt[P] ... P=pq, 1≦p≦q のうち p+q-1が合成数なものの数 RANGE(p, 1, N+1) RANGE(q, p, N/p+1) if(!isp[p+q-1]) cnt[p*q]++; ll ans=0; RANGE(S, A, B+1) if(!isp[S-1] && cnt[S-1]==1) ans+=S; return ans; } };
| 
class UniformBoard { public: int getBoard(vector <string> B, int K) { int N=B.size(); int ans = 0; REP(sx, N) REP(sy, N) RANGE(ex, sx, N) RANGE(ey, sy, N) { int iE=0,iP=0,oE=0,oA=0; REP(x, N) REP(y, N) { if(sx<=x && x<=ex && sy<=y && y<=ey) { if(B[x][y]=='P') iP++; if(B[x][y]=='.') iE++; } else { if(B[x][y]=='A') oA++; if(B[x][y]=='.') oE++; } } //if(iE+iP<=oA && (iP==0 || oE>0) && iE+2*iP <= K) ans=max(ans, (ex-sx+1)*(ey-sy+1)); //だめ if(iE+iP<=oA && (iP==0 || iE+oE>0) && iE+2*iP <= K) ans=max(ans, (ex-sx+1)*(ey-sy+1)); } return ans; } };
| 
class BuildingRoutes { public: int build(vector <string> D, int T) { int N=D.size(); VVI d(N, VI(N)); VVI w(N, VI(N)); REP(i, N)REP(j,N)d[i][j]=w[i][j]=D[i][j]-'0'; REP(k,N)REP(i, N)REP(j,N) w[i][j]=min(w[i][j], w[i][k]+w[k][j]); ll ans = 0; REP(i, N)REP(j,N){ ll v=0; //(本文中とはi/ii, j/jjが逆) REP(ii, N)REP(jj,N) if(w[ii][i]+d[i][j]+w[j][jj]==w[ii][jj]) v++; if(v>=T) ans+=d[i][j]; } return ans; } };
