| 
// num of cells which value <= v ll n_upto(ll v) { ll ans = 0; while(v) { ans += v; v/=2; } return ans; } ll lb(int N, int K) { ll lo=0, hi=K; // n_upto(lo)<N<=n_upto(hi) while(lo+1<hi) { ll mid = (lo+hi)/2; if(N<=n_upto(mid)) hi=mid; else lo=mid; } return hi; } class KitayutaMart { public: int lastPrice(int N, int K) { ll countWithinK = n_upto(K); ll fillCount = N - countWithinK; ll fillLines = (fillCount + K - 1) / K; ll restCount = N - fillLines*K; return (modll(2)^fillLines) * lb(restCount, K); } };
| 
class AB { public: void check(string s, int N, int K) { assert(N==s.size()); REP(i, N) RANGE(j, i+1, N) if(s[i]=='A'&&s[j]=='B') K--; assert(K==0); } string createString(int N, int K) { REP(b, N+1) { int k = K; int a = N-b; map<int, int> bn; REP(i, a) { int take = min(k, b); bn[take]++; k-=take; } if(k==0) { string s; int ob=0; FOR(e, bn) { while(ob<e->first) { s+="B"; ob++; } REP(j, e->second) s+="A"; } assert(N==s.size()); reverse(ALL(s)); check(s, N, K); return s; } } return ""; } };
| 
↓
ぎゃぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁぁ #FHC
— こじ (@kojingharang) 2015, 1月 18↓
↓
↓
HackerCupのDやらかしてた．最小値から2つ目まで求めるので，部下が使っていないプレゼントの金額の2つ目まで調べないといけないのに，1つ目までしか調べていなかった…．制限時間緩いんだからもっとたくさん調べておくべきだった．
— laycrs (@laycrs) 2015, 1月 19↓
なぬ！！
— こじ (@kojingharang) 2015, 1月 19struct Node { ll minV, minSum, otherSum; Node() : minV(0), minSum(0), otherSum(0) {} }; struct Min2 { ll minK, min1, min2; Min2() : minK(1LL<<60), min1(1LL<<60), min2(1LL<<60) {} void add(ll k, ll v) { if(v<min1) { min2 = min1; min1 = v; minK = k; } else if(v<min2) { min2 = v; } } }; ll N; VVI g; Node nodes[200010]; VI unused2(int idx) { map<int, int> vs; REP(i, g[idx].size()) vs[ nodes[g[idx][i]].minV ] = 1; VI uns; int un = 1; FOR(e, vs) { while(un != e->first) { uns.PB(un); if(uns.size()==2) return uns; un++; } un = e->first+1; } uns.PB(un); uns.PB(un+1); return uns; } void f(int idx) { REP(i, g[idx].size()) f(g[idx][i]); VI un = unused2(idx); ll minSum = 0; map<ll, Node> m; REP(i, g[idx].size()) { auto& n = nodes[g[idx][i]]; Node& gr = m[n.minV]; gr.minV = n.minV; gr.minSum += n.minSum; gr.otherSum += n.otherSum; minSum += n.minSum; } Min2 mn; REP(i, 2) mn.add(un[i], un[i] + minSum); // ここ大事！ FOR(e, m) mn.add(e->first, e->first + minSum - e->second.minSum + e->second.otherSum); nodes[idx].minV = mn.minK; nodes[idx].minSum = mn.min1; nodes[idx].otherSum = mn.min2; } int main() { ios::sync_with_stdio(false); int Cases; cin>>Cases; REP(CaseID, Cases) { cin>>N; g = VVI(N+1); REP(i, N) { ll parent; cin>>parent; g[parent].PB(i+1); } f(1); ll ans = nodes[1].minSum; cout<<"Case #"<<CaseID+1<<": "<<ans<<endl; } return 0; }
| 
// Dijkstra省略 VI compress(VI v) { VI w; REP(i, v.size()) RANGE(r, -1, 2) w.PB(v[i]+r); sort(ALL(w)); w.erase(unique(ALL(w)), w.end()); return w; } VI toVI(vector<int> v) { VI w; REP(i, v.size()) w.PB(v[i]); return w; } class TheGridDivOne { public: int W, H; vector<string> m; int node(int x, int y) { return y*W + x; } int find(vector <int> X, vector <int> Y, int k) { VI vix = toVI(X); VI viy = toVI(Y); vix.PB(0); viy.PB(0); VI CX = compress(vix); VI CY = compress(viy); cout<<CX<<endl; cout<<CY<<endl; W = CX.size(); H = CY.size(); m = vector<string>(H, string(W, '.')); int sx, sy; REP(x, W) if(CX[x]==0) sx=x; REP(y, H) if(CY[y]==0) sy=y; REP(y, H) REP(x, W) REP(i, X.size()) { if(CX[x]==X[i] && CY[y]==Y[i]) m[y][x]='x'; } m[sy][sx] = 's'; cout<<m<<endl; Dijkstra d(W*H); int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; REP(y, H) REP(x, W) REP(dir, 4) { int nx=x+dx[dir]; int ny=y+dy[dir]; if(0<=nx && nx<W && 0<=ny && ny<H) { if(m[ny][nx]=='.') { ll cost = abs(CX[nx]-CX[x]) + abs(CY[ny]-CY[y]); d.add_edge(node(x, y), node(nx, ny), cost); } } } d.run(node(sx, sy), -1); ll ans = 0; REP(y, H) REP(x, W) if(d.V[node(x, y)]<=k) { ll nv = CX[x] + max<ll>(0, k-d.V[node(x, y)]); if(x<W-1) nv = min<ll>(nv, CX[x+1]-1); ans = max<ll>(ans, nv); } return ans; } };
| 
// struct Dijkstra は略 ll H, W; vector<string> m; vector<int> lx, ly, ldir; int inMap(int x, int y) { return 0<=x && x<W && 0<=y && y<H; } int isFence(int x, int y) { char c=m[y][x]; return c=='<' || c=='>' || c=='^' || c=='v' || c=='#'; } int dx[] = {0,1,0,-1}; // up right down left int dy[] = {-1,0,1,0}; // up right down left int alive(int x, int y, int phase) { REP(li, lx.size()) { int clx=lx[li]; int cly=ly[li]; int cldir=(ldir[li]+phase)%4; while(1) { if(clx==x && cly==y) return 0; //shoot clx+=dx[cldir]; cly+=dy[cldir]; if(!inMap(clx, cly)) break; if(isFence(clx, cly)) break; } } return 1; } int canMove(int x, int y, int phase, int dir) { int nx = x+dx[dir]; int ny = y+dy[dir]; if(!inMap(nx, ny)) return 0; if(isFence(x, y)) return 0; if(isFence(nx, ny)) return 0; if(!alive(nx, ny, (phase+1)%4)) return 0; return 1; } ll node(int x, int y, int phase) { assert(0<=x && x<W && 0<=y && y<H && 0<=phase && phase<4); return phase*H*W + x*H + y; } int main() { //ios::sync_with_stdio(false); int Cases; cin>>Cases; REP(CaseID, Cases) { cin>>H>>W; m = vector<string>(H); REP(y, H) cin>>m[y]; ll start; vector<ll> goals; lx.clear(); ly.clear(); ldir.clear(); REP(y, H) REP(x, W) { if(m[y][x]=='S') start = node(x, y, 0); if(m[y][x]=='G') { REP(p, 4) goals.PB(node(x, y, p)); } if(m[y][x]=='^') { lx.PB(x); ly.PB(y); ldir.PB(0); } if(m[y][x]=='>') { lx.PB(x); ly.PB(y); ldir.PB(1); } if(m[y][x]=='v') { lx.PB(x); ly.PB(y); ldir.PB(2); } if(m[y][x]=='<') { lx.PB(x); ly.PB(y); ldir.PB(3); } } // cout<<m<<endl; Dijkstra d(W*H*4); REP(y, H) REP(x, W) REP(p, 4) REP(dir, 4) { if(canMove(x, y, p, dir)) { int nx = x+dx[dir]; int ny = y+dy[dir]; d.add_edge(node(x, y, p), node(nx, ny, (p+1)%4), 1); } } d.run(start, -1); ll ans = 1LL<<60; REP(ni, W*H*4) { REP(gi, 4) if(d.V[goals[gi]] < (1<<30)) ans=min<ll>(ans, d.V[goals[gi]]); } if(ans==1LL<<60) { cout<<"Case #"<<CaseID+1<<": "<<"impossible"<<endl; } else { cout<<"Case #"<<CaseID+1<<": "<<ans<<endl; } // break; } return 0; }
| 
class ShoppingSurveyDiv1 { public: int minValue(int N, int K, vector <int> s) { int M=s.size(); ll lo=-1,hi=N; // hi -> OK while(lo+1<hi) { ll ans=(lo+hi)/2; // REP(ans, N+1) { map<ll, ll> co; co[0]=N-ans; REP(i, M) { map<ll, ll> add; ll rest = max<ll>(0, s[i]-ans); FOR(e, co) { if(rest==0) break; ll use = min<ll>(e->second, rest); // cout<<"use "<<use<<" for "<<e->first<<endl; e->second -= use; add[e->first+1] += use; rest-=use; } FOR(e, add) co[e->first]+=e->second; // cout<<i<<" "<<s[i]<<" "<<co<<endl; assert(rest==0); } int ok=1; FOR(e, co) if(e->first>=K) ok=0; if(ok) hi=ans; else lo=ans; } return hi; } };