| 
いろいろ考えたところ、貪欲法でいけそうとなったのでやってみたらうまくいった。
満足度が高い順に、消費期限の日から遡って飲む予定をできるだけいれて行く。すでに予定が入っている日はスキップする。
(なぜなら既に入っているコーヒーの満足度は入れようとしているものより満足度が同じか高いから。)
以上をやればいいが、largeの日数は単純にループで回してたら終わらないくらい多いので、連続する予定を日数に関係ないオーダーで記録する工夫が必要となる。
具体的には、空いてる日を「開始日と長さのリスト」で管理するようにして、そこに予定をまとまて入れるようにする。
空きリストが[(1,5)]なら1日目から5日分空いてるという状態。そこに4日目から前方向に2日分予定を入れると空きリストは[(1,2),(5,1)]となる。
一般的にはリストを後ろから見ていき、置けるところに置いてリストを更新していけばいい。オーダーはリストの長さになる。
1回の予定挿入でリストの要素数は高々1個増えるだけなので、リストの要素数は最大でもコーヒーの種類数程度。なので日数が1e18とかでも現実的な時間で計算できる。
予定を入れられた分だけ満足度を加算していって、全種類入れ終わったらそれが答え。
| 
ふつうにやると large の計算が終わらないので、なんか法則性があってO(N)にならないような方法があるんだろう
→とりあえずビットが全部たってる2**n-1とそれ以外で分けたらいいんじゃね？......という予想をしつつも証明できないのでまずはsmallをふつうにやる。
smallが通ったら、N以下の最大の2**n-1と残りでわけたときの合計ビット数を求めてみて、通った答えと一致してることを確認
→でdiffしたらおなじだったのでそれでlarge提出。なんとも危なっかしいやり方だけどまあいいや(笑)
証明は「2**n-1で分けるのが最適でない場合、ビットが全部立ってるとこから残りの方に移すとビットがもっと増えるはずだがそうはならない」みたいな感じでできそう。
立ってるビットを減らして他方にもってきたときに他方で2以上増えないといけないけど、0だったとこにもってきても1になるだけで合計は変わらないし、1だったとこにもってくると0になって良くて繰り上がって1になっても変わらないし繰り上がり方によってはどんどん減る方向にしかいかないので当初の分け方が最大。みたいな感じでしょうか。
| 
int main() { int T; cin>>T; //cout<<T<<endl; REP(t, T) { int R,C; cin>>R>>C; string v[R]; REP(y, R) { cin>>v[y]; } int ok=1; REP(y, R) { REP(x, C) { if(v[y][x]=='#') { if(y==R-1||x==C-1||v[y][x+1]!='#' || v[y+1][x]!='#' || v[y+1][x+1]!='#') { ok=0; goto END; } v[y][x]=v[y+1][x+1]='/'; v[y+1][x]=v[y][x+1]='\\'; } } } END:; cout<<"Case #"<<t+1<<":"<<endl; if(ok) { REP(y, R) { cout<<v[y]<<endl; } } else cout<<"Impossible"<<endl; } return 0; }
| 
int main() { int T; cin>>T; //cout<<T<<endl; REP(ttt, T) { ll L,t,N,C; cin>>L>>t>>N>>C; int v[N]; REP(i, C) cin>>v[i]; FOR(i, C, N) v[i]=v[i-C]; //REP(i, N) cout<<v[i]<<endl;; ll mintt = -1; if(L==0) { ll tt=0; REP(i, N) { tt+=v[i]*2; } //cout<<"tt "<<tt<<endl; if(mintt==-1 || tt<mintt) mintt=tt; } else if(L==1) { FOR(ba, 0, N) { // use in ba ll tt=0; REP(i, N) { if(i==ba) { if(t<=tt) tt+=v[i]; else if(t<tt+v[i]*2) tt+= (t-tt) + v[i]-(t-tt)/2; else tt+=v[i]*2; } else { tt+=v[i]*2; } } if(mintt==-1 || tt<mintt) mintt=tt; } } else { FOR(ba, 0, N-1) FOR(bb, ba, N) { // use in ba, bb ll tt=0; REP(i, N) { if(i==ba||i==bb) { if(t<=tt) tt+=v[i]; else if(t<tt+v[i]*2) tt+= (t-tt) + v[i]-(t-tt)/2; else tt+=v[i]*2; } else { tt+=v[i]*2; } } if(mintt==-1 || tt<mintt) mintt=tt; } } cout<<"Case #"<<ttt+1<<": "<<mintt<<endl; } return 0; }
| 
int main() { int T; cin>>T; //cout<<T<<endl; REP(t, T) { int N,L,H; cin>>N>>L>>H; int v[N]; REP(i, N) cin>>v[i]; int ok=0; int ans=0; FOR(f, L, H+1) { int lok=1; REP(i, N) { if(f<v[i]) { if(v[i]%f!=0) {lok=0; break;} } else if(f%v[i]!=0) {lok=0; break;} } if(lok) {ok=1; ans=f; break;} } if(ok) cout<<"Case #"<<t+1<<": "<<ans<<endl; else cout<<"Case #"<<t+1<<": NO"<<endl; } return 0; }
| 
int main() { int T; cin>>T; //cout<<T<<endl; REP(t, T) { int N; cin>>N; string sc[N]; double WP[N]; double OWP[N]; double OOWP[N]; CLR(WP); CLR(OWP); CLR(OOWP); REP(i, N){ cin>>sc[i]; } REP(i, N) { { int win=0, all=0; REP(j, N) { if(sc[i][j]!='.') { win += sc[i][j]=='1'; all++; } } WP[i] = (double)win/all; } { int _all=0; REP(j, N) { if(sc[i][j]!='.') { _all++; // calc wp of j except i int win=0, all=0; REP(k, N) { if(k==i) continue; if(sc[j][k]!='.') { win += sc[j][k]=='1'; all++; } } OWP[i] += (double)win/all; } } OWP[i] /= (double)_all; } } cout<<"Case #"<<t+1<<":"<<endl; REP(i, N) { int all=0; REP(j, N) { if(sc[i][j]!='.') { OOWP[i] += OWP[j]; all++; } } OOWP[i] /= all; double RPI = 0.25 * WP[i] + 0.50 * OWP[i] + 0.25 * OOWP[i]; cout<<RPI<<endl; } cout<<endl; } return 0; }
| 
| 
| 
（以下、long long に修正後のソース）
int gcd ( int a, int b ) { if(a<b) { int tmp=a; a=b; b=tmp; } int c; while ( a != 0 ) { c = a; a = b%a; b = c; } return b; } int main() { int T; cin>>T; //cout<<T<<endl; REP(t, T) { int ans = 1; int pd, pg, d=100, g=100, v; ll n; cin>>n>>pd>>pg; //cout<<n<<pd<<pg; v = gcd(d, pd); pd/=v; d/=v; v = gcd(g, pg); pg/=v; g/=v; //cout<<pd<<" "<<d<<" "<<pg<<" "<<g<<" "<<endl; //if(g<d) //{ // int a=d/g + 1; // g*=a; pg*=a; //} if((pd!=d&&pg==g)||(pd>0&&pg==0) || d>n) { cout<<"Case #"<<t+1<<": Broken"<<endl;; continue; } //cout<<pd<<" "<<d<<" "<<pg<<" "<<g<<" "<<endl; cout<<"Case #"<<t+1<<": Possible"<<endl;; } return 0; }
| 
int main() { int T; cin>>T; //cout<<T<<endl; REP(t, T) { int N, M; cin>>N>>M; string D[N]; string L[M]; REP(i, N) cin>>D[i]; REP(i, M) cin>>L[i]; //REP(i, N) cout<<D[i]<<endl; //REP(i, M) cout<<L[i]<<endl; cout<<"Case #"<<t+1<<":"; REP(Li, M) { int lose[N]; CLR(lose); REP(di, N) { // choose D[di] //cout<<"choose "<<D[di]<<endl; int ng[N]; int nng=0; CLR(ng); REP(i, N) { if(D[di].SZ != D[i].SZ) {ng[i]=1;nng++;} } if(nng==N-1) continue; // begin guess REP(li, 26) { int contains=0; REP(i, N) { if(ng[i]) continue; if(D[i].find(L[Li][li])!=D[i].npos) { contains=1; break; } } if(contains) { char guess = L[Li][li]; //cout<<"guess "<<guess<<endl; int revealed=0; REP(p, D[di].SZ) { if(D[di][p]==guess) {revealed=1;break;} } if(!revealed) lose[di]++; REP(i, N) { if(ng[i]) continue; REP(p, D[i].SZ) { if(D[di][p]==guess && D[i][p]!=guess || D[di][p]!=guess && D[i][p]==guess) {ng[i]=1;nng++;break;} } } if(nng==N-1) break; } } } int max = -1; int maxi = -1; REP(i, N) { //cout<<lose[i]<<endl; if(max<lose[i]) {max=lose[i];maxi=i;} } cout<<" "<<D[maxi]; } cout<<endl; } return 0; }
| 
int main() { int T; cin>>T; //cout<<T<<endl; REP(t, T) { int ans = 0; VVI d; d.PB(VI()); d.PB(VI()); int N; cin>>N; REP(i, N) { char col; int loc; cin>>col>>loc; //cout<<col<<loc<<endl; int ci = col=='O'?0:1; d[ci].PB(i); d[ci].PB(loc); } //cout<<d<<endl; int pi = 0; int ci[2]; int cur[2]; ci[0]=ci[1]=0; cur[0]=cur[1]=1; REP(step, 100*100) { int pushed = 0; int end = 1; REP(col, 2) { if(ci[col]>=d[col].size()/2) continue; end = 0; int p = d[col][ci[col]*2+0]; int loc = d[col][ci[col]*2+1]; if(cur[col]==loc) { if(pi==p) { //cout<<col<<" push "<<cur[col]<<endl; pushed=1; ci[col]++; } else { //cout<<col<<" stay"<<endl; } } else { int dir = loc - cur[col] > 0 ? 1 : -1; cur[col]+=dir; //cout<<col<<" move to "<<cur[col]<<endl; } } if(pushed) pi++; if(end) break; ans++; } cout<<"Case #"<<t+1<<": "<<ans<<endl;; } return 0; }
| 
（反省点）
int main() { int T; cin>>T; //cout<<T<<endl; REP(t, T) { vector<string> com; vector<string> del; string v; int nc, nd, nv; cin>>nc; REP(i, nc) { string tmp; cin>>tmp; com.PB(tmp); } cin>>nd; REP(i, nd) { string tmp; cin>>tmp; del.PB(tmp); } cin>>nv; cin>>v; //cout<<com<<del<<v<<endl; vector<char> w; REP(i, nv) { w.PB(v[i]); if(w.SZ>=2) REP(j, nc) { if(w[w.SZ-2]==com[j][0] && w[w.SZ-1]==com[j][1]) { w.pop_back(); w.pop_back(); w.PB(com[j][2]); } if(w[w.SZ-2]==com[j][1] && w[w.SZ-1]==com[j][0]) { w.pop_back(); w.pop_back(); w.PB(com[j][2]); } } if(w.SZ>=2) REP(j, nd) { if(w[w.SZ-1]==del[j][0]) REP(k, w.SZ-1) { if(w[k]==del[j][1]) { w.clear(); } } if(w[w.SZ-1]==del[j][1]) REP(k, w.SZ-1) { if(w[k]==del[j][0]) { w.clear(); } } } } cout<<"Case #"<<t+1<<": "<<w<<endl;; } return 0; }
| 
int main() { int T; cin>>T; //cout<<T<<endl; REP(t, T) { int n; cin>>n; VI c(n); int x=0; int sum=0; REP(i, n) { cin>>c[i]; x ^= c[i]; sum+=c[i]; } SORT(c); sum -= c[0]; //cout<<c<<endl; if(x==0) { cout<<"Case #"<<t+1<<": "<<sum<<endl; } else { cout<<"Case #"<<t+1<<": NO"<<endl; } } return 0; }
| 
（反省点）
（以下、間違ってますが掲載）
int main() { int T; cin>>T; //cout<<T<<endl; REP(t, T) { int n; int ans=0; cin>>n; VI d(n); REP(i, n) { cin>>d[i]; } cout<<d<<endl; int ans2=0; REP(i, n) { if(i+1!=d[i]) ans2++; } REP(i, n) { if(i+1!=d[i]) { int ti=-1; FOR(j, i+1, n) { if(d[j]==i+1) { ti=j; break; } } swap(d[i], d[ti]); ans+=2; //cout<<d<<endl; } } //cout<<d<<endl; cout<<"Case #"<<t+1<<": "<<ans<<".000000 "<<ans2<<endl; } return 0; }
| 
500回記念大会。
反省点
ソース（追記：要ログイン）
http://www.topcoder.com/stat?c=problem_solution&rm=307554&rd=14429&pm=11342&cr=22919543
追記：上記リンクが要ログインなのでこちらにもソースを貼っておきます。
こちらは最小票カウンタの初期値を 100 から 1000 に変えた版です（ｗ
他の方のソースや解説を見ると、「投票が終わるならば浮動票だけの人が１度でも最多票を獲得することはない」ということに気づくと短いコードになるみたいですね。。
実際書いてて「浮動票onlyの人が最多になるとその時点では確率M/Nだけど、固定票はその時点では確率1なので違っちゃってなんかまずいな」と思っていたのが、浮動票だけの人は結局は選ばれないということで納得です。
class MafiaGame { public: double probabilityToLose(int N, vector <int> de) { printf("%s %d\n", __FILE__, __LINE__); VI vul(N); VI vot(N); REP(i, N) vul[i]=1; vector<double> pro(N); REP(i, N) pro[i] = 1.0; int prev_n_vul = -1; int wdc = 0; do { cout<<"VUL "<<vul<<endl; int other = N-de.SZ; REP(i, N) vot[i]=0; REP(i, de.SZ) if(vul[de[i]]) { vot[de[i]]++; } else { other++; } cout<<"VOT "<<vot<<endl; cout<<"other "<<other<<endl; while(other>0) { cout<<"VO2 "<<vot<<endl; int min_vot = 1000; int min_cnt = 0; REP(i, N) if(vul[i] && vot[i]<min_vot) { min_vot=vot[i]; } REP(i, N) if(vul[i] && vot[i]==min_vot) min_cnt++; if(min_cnt<=other) { REP(i, N) if(vul[i] && vot[i]==min_vot) { vot[i]++; other--; } } else { // choose other/min_cnt double p = (double)other/min_cnt; REP(i, N) { if(other==0) break; if(vul[i] && vot[i]==min_vot) { pro[i] *= p; vot[i]++; other--; } } cout<<"PRO "<<pro<<endl; } } int n_vul = 0; int max_vot = 0; REP(i, N) if(vul[i] && max_vot < vot[i]) max_vot = vot[i]; REP(i, N) if(vul[i] && vot[i]==max_vot) n_vul++; cout<<"n_vul "<<n_vul<<endl; if(n_vul==prev_n_vul) return 0.0; prev_n_vul = n_vul; REP(i, N) vul[i] = vot[i]==max_vot ? 1 : 0; if(n_vul==1) break; if(wdc++>10) return -1.0; } while(1); double ans = 0.0; REP(i, N) if(vul[i] && ans<pro[i]) ans = pro[i]; return ans; }
