| 
// 予定 struct Entry { ll s, e, type; }; int main() { int test_cases; cin>>test_cases; ll A,B, s, e; REP(ttt, test_cases) { cin>>A>>B; ll ra = 720, rb = 720; // のこり割当時間 ll fr = 1440; // どっちに割り当ててもノーペナな枠 vector<Entry> es; REP(i, A) { cin>>s>>e; ra -= e-s; fr -= e-s; es.push_back(Entry{s, e, 1}); } REP(i, B) { cin>>s>>e; rb -= e-s; fr -= e-s; es.push_back(Entry{s, e, -1}); } VI pa, pb; // dur ll N = 1440; sort(ALL(es), [](const Entry& a, const Entry& b){return a.s<b.s;}); ll ans = 0; ll M = es.size(); REP(i, M) { ll ni = (i+1)%M; if(es[i].e%N != es[ni].s%N) { // すきまはっけん if(es[i].type == es[ni].type) { ll dur = (es[ni].s-es[i].e+N)%N; if(es[i].type==1) pa.PB(dur); if(es[i].type==-1) pb.PB(dur); } } if(es[i].type!=es[ni].type) ans++; } sort(ALL(pa)); sort(ALL(pb)); REP(i, pa.size()) fr -= pa[i]; REP(i, pb.size()) fr -= pb[i]; // ペナルティ回避 REP(i, pa.size()) { ll use = min(ra, pa[i]); ra -= use; pa[i]-=use; } REP(i, pb.size()) { ll use = min(rb, pb[i]); rb -= use; pb[i]-=use; } // ノーペナ消費 { ll use = min(ra, fr); ra -= use; fr -= use; } { ll use = min(rb, fr); rb -= use; fr -= use; } // ペナルティ REP(i, pb.size()) { ll use = min(ra, pb[i]); if(use) ans+=2; ra -= use; } REP(i, pa.size()) { ll use = min(rb, pa[i]); if(use) ans+=2; rb -= use; } assert(ra==0); assert(rb==0); cout<<"Case #"<<ttt+1<<": "<<ans<<endl; } return 0; }
| 
VI rot(const VI& a, char d) { int lr = d=='L' ? -1 : 1; int N = a.size(); VI rv(N); REP(i, N) rv[i] = a[(i+lr+N)%N]+a[i]; return rv; } VI rotN(const VI& a, string d) { VI rv(a); for(auto c : d) rv = rot(rv, c); return rv; } VI shiftL(const VI& a) { int N = a.size(); VI rv(N); REP(i, N) rv[i] = a[(i+1)%N]; return rv; } class LR { public: string construct(vector<long long> s, vector<long long> t) { ll ss = accumulate(ALL(s), 0LL); ll st = accumulate(ALL(t), 0LL); if(ss>st) return "No solution"; if(ss==st) { return s==t ? "" : "No solution"; } if(ss==0) return "No solution"; int cnt = 0; { bool ok = false; while(ss<=st) { if(ss==st) { ok=true; break; } ss*=2; cnt++; } if(!ok) return "No solution"; } VI w(s); REP(i, cnt) { w = rot(w, 'L'); } bool ok = false; int R = 0; REP(i, s.size()) { if(w==t) { ok = true; break; } w = shiftL(w); R++; } if(ok && R<=cnt) { string ans(cnt, 'L'); REP(i, R) ans[i] = 'R'; assert(t==rotN(s, ans)); return ans; } return "No solution"; } };
| 
// simplex 法バージョン // 新たな盤面を計算する部分だけ抜粋 vector<string> solve(const vector<string>& w) { int N = w.size(); int pre = 0; REP(y, N) REP(x, N) if(w[y][x]!='.') pre++; int vars = 4*N*N; int cs = N*N + pre + 2*N + 2*(2*N-1); Mat m(cs, Vec(vars)); Vec b(cs); Vec c(vars); int base = 0; { // .+xo int score[4] = {0, 1, 1, 2}; REP(i, N*N) { REP(j, 4) m[base][4*i+j] = 1; b[base] = 1; REP(j, 4) c[4*base+j] = score[j]; base++; } } // pre { REP(y, N) REP(x, N) { int idx = y*N+x; if(w[y][x]=='+') { // must be + or o m[base][idx*4+1] = -1; m[base][idx*4+3] = -1; b[base] = -1; base++; } if(w[y][x]=='x') { // must be x or o m[base][idx*4+2] = -1; m[base][idx*4+3] = -1; b[base] = -1; base++; } if(w[y][x]=='o') { // must be o m[base][idx*4+3] = -1; b[base] = -1; base++; } } } // たて Σxo <= 1 { REP(x, N) { REP(y, N) { int idx = y*N+x; m[base][idx*4+2] = 1; m[base][idx*4+3] = 1; } b[base] = 1; base++; } } // よこ Σxo <= 1 { REP(y, N) { REP(x, N) { int idx = y*N+x; m[base][idx*4+2] = 1; m[base][idx*4+3] = 1; } b[base] = 1; base++; } } // ななめ Σ+o <= 1 { REP(k, 2*N-1) { REP(y, N) { REP(x, N) { if(x+y==k) { int idx = y*N+x; m[base][idx*4+1] = 1; m[base][idx*4+3] = 1; } } } b[base] = 1; base++; REP(y, N) { REP(x, N) { if((N-1-x)+y==k) { int idx = y*N+x; m[base][idx*4+1] = 1; m[base][idx*4+3] = 1; } } } b[base] = 1; base++; } } auto p = simplex(m, b, c); auto vs = p.second; auto rv = w; REP(y, N) REP(x, N) { rv[y][x] = '.'; ll sum = 0; REP(i, 4) sum += (ll)vs[(y*N+x)*4+i]; assert(sum==1); if(vs[(y*N+x)*4+0]) rv[y][x] = '.'; if(vs[(y*N+x)*4+1]) rv[y][x] = '+'; if(vs[(y*N+x)*4+2]) rv[y][x] = 'x'; if(vs[(y*N+x)*4+3]) rv[y][x] = 'o'; } return rv; }
// 新たな盤面を計算する部分だけ抜粋 vector<string> solve2(const vector<string>& w) { int N = w.size(); vector<string> xs(N, string(N, '.')); vector<string> ps(N, string(N, '.')); vector<string> rv(N, string(N, '.')); // put x { REP(y, N) REP(x, N) if(w[y][x]=='x' || w[y][x]=='o') xs[y][x] = 'x'; vector<bool> Ys(N), Xs(N); REP(y, N) REP(x, N) if(xs[y][x]=='x') Ys[y]=Xs[x]=true; while(1) { REP(y, N) REP(x, N) if(xs[y][x]=='.' && !Xs[x] && !Ys[y]) { xs[y][x] = 'x'; Ys[y]=Xs[x]=true; } if(count(ALL(Xs), true)==N && count(ALL(Xs), true)==N) break; } } // put + { REP(y, N) REP(x, N) if(w[y][x]=='+' || w[y][x]=='o') ps[y][x] = '+'; bipartite_matching bm((2*N-1)*2); VVI edges(2*N-1, VI(2*N-1)); vector<bool> usedD0(2*N-1), usedD1(2*N-1); REP(y, N) REP(x, N) if(ps[y][x]=='+') { int d0 = x+y; int d1 = N-1-x+y; usedD0[d0] = 1; usedD1[d1] = 1; } REP(y, N) REP(x, N) { int d0 = x+y; int d1 = N-1-x+y; if(!usedD0[d0] && !usedD1[d1]) { edges[d0][d1] = 1; } } REP(d0, 2*N-1) REP(d1, 2*N-1) { if(edges[d0][d1]) bm.add_edge(d0, 2*N-1+d1); } int matched=bm.run(); REP(i, 2*N-1) if(bm.match[i]!=-1) { // x+y int d0 = i; // (N-1-x)+y int d1 = bm.match[i]-(2*N-1); // d0+d1 = N-1+2y int y = (d0+d1-N+1)/2; int x = d0-y; ps[y][x] = '+'; } } REP(y, N) REP(x, N) { rv[y][x] = xs[y][x]; if(ps[y][x]=='+') rv[y][x] = rv[y][x]=='x' ? 'o' : '+'; } return rv; }
| 
あとで
class PolygonRotation { public: double getVolume(vector <int> x, vector <int> y) { int N = x.size(); int mid; REP(i, N) if(x[i]==0) mid=i; vector<P> l, r, all; REP(i, N) { if(i<=mid) { r.PB(P{(double)x[i], (double)y[i]}); } if(i>=mid) { l.PB(P{(double)-x[i], (double)y[i]}); } } l.PB(P{(double)-x[0], (double)y[0]}); vector<double> ys(ALL(y)); REP(i, l.size()-1) REP(j, r.size()-1) { auto rv = intersection(l[i], l[i+1], r[j], r[j+1]); if(rv.first) { ys.PB(rv.second.y); } } sort(ALL(ys)); vector<double> xs(ys.size()); REP(i, ys.size()) { // find max x for ys[i] double y = ys[i]; for(auto& e : {l, r}) { REP(j, e.size()-1) { double ra = (y - e[j].y) / (e[j+1].y-e[j].y); if(0 <= ra && ra <= 1) { xs[i] = max(xs[i], e[j].x + ra * (e[j+1].x-e[j].x)); } } } } double ans = 0; REP(i, ys.size()-1) { double h = ys[i+1]-ys[i]; double r1 = xs[i]; double r2 = xs[i+1]; ans += M_PI*h/3.0*(r1*r1+r1*r2+r2*r2); } return ans; } };
| 
SRM708 500の上位陣のコードを見て何でこれで解けるんだろうとしばらく考えてたら分かった気がする。
— 暇人の名は (@kojingharang) 2017年2月11日
特に後半がナゾだったが回文中で固定文字に対応する文字は重複なくN通りあるから足せば良いのかと気付いたところなう。
class PalindromicSubseq { public: int solve(string s) { ll N = s.size(); // dp1[i][j] ... [i, j] 内での回文の個数 vector<vector<modll>> dp1(N, vector<modll>(N)); // dp2[i][j] ... [0, i), (j, N) 内での回文の個数 vector<vector<modll>> dp2(N, vector<modll>(N)); RANGE(L, 0, N+1) REP(i, N-L+1) { int j = i+L-1; if(L==0) { if(0<=j && i<N) dp1[i][j] = 1; // empty } else { modll v = 0; // s[i] を採用しない場合 (s[j]は採用するしないどちらも含む) if(i+1<N) v += dp1[i+1][j]; // s[j] を採用しない場合 (s[i]は採用するしないどちらも含む) if(0<=j-1) v += dp1[i][j-1]; // s[i], s[j] 両方採用しない場合が 2 回数えられている分を減らす if(0<=j-1 && i+1<N) v -= dp1[i+1][j-1]; if(s[i]==s[j]) { // s[i], s[j] を採用できる。採用するとその内側の組み合わせ総数だけ増える if(0<=j-1 && i+1<N) v += dp1[i+1][j-1]; } dp1[i][j] = v; } } for(int L=N;L>=1;L--) REP(i, N-L+1) { int j = i+L-1; if(L==N) { dp2[i][j] = 1; // empty } else { modll v = 0; // 同様 if(0<=i-1) v += dp2[i-1][j]; if(j+1<N) v += dp2[i][j+1]; if(0<=i-1 && j+1<N) { v -= dp2[i-1][j+1]; if(s[i-1]==s[j+1]) { // s[i-1], s[j+1] を採用できる。採用するとその外側の組み合わせ総数だけ増える v += dp2[i-1][j+1]; } } dp2[i][j] = v; } } ll ans = 0; REP(i, N) { modll X = 0; REP(j, N) { if(s[i]==s[j]) { ll I=i, J=j; if(I>J) swap(I, J); // ここでは I, J がどちらも採用され I, J が回文にて対応関係にある。 // 内側は [I+1, J-1] 内の回文の個数 // 外側は [0, I), (J, N) 内の回文の個数 // これらの積が "I, J がどちらも採用され回文にて I, J が対応関係にある" 場合の組み合わせ総数。 X += (I+1<=J-1 ? dp1[I+1][J-1] : modll(1)) * dp2[I][J]; } } ans ^= modll(i+1LL)*X; } return ans; } };
