| 
// [i][j][k] ... M[I], I in [0, i] の範囲で, ;で終わってる顔文字が j コ, ;_+ な顔文字が k コあるような状態の個数 modll dp[202][202][202]; class BearCries { public: int count(string M) { CLEAR(dp, 0); int N=M.size(); dp[0][0][0]=1; REP(i, N) REP(j, N) REP(k, N) { auto cur = dp[i][j][k]; if(M[i]==';') { dp[i+1][j+1][k] += cur; // 新規 ; if(k-1>=0) dp[i+1][j][k-1] += cur*modll(k); // ;_+ -> ;_+; (k コある) } else { dp[i+1][j][k] += cur*modll(k); // ;_+ -> ;_+ (k コある) if(j-1>=0) dp[i+1][j-1][k+1] += cur*modll(j); // ; -> ;_+ (j コある) } } return dp[N][0][0]; } };
| 
struct Pos { int x, y; bool operator<(const Pos v) const { return x*1000+y < v.x*1000+v.y; } bool operator==(const Pos v) const { return x==v.x && y==v.y; } }; std::ostream& operator<<(std::ostream& os, const Pos& v) { os << "("<<v.x<<", "<<v.y<<") "; return os; } struct Pat { Pos ref; vector<Pos> pos; }; class Coversta { public: int place(vector <string> a, vector <int> X, vector <int> Y) { int W=a.size(), H=a[0].size(); int N=X.size(); VVI one(W, VI(H)); vector<Pat> pat; map<PII, int> ng; REP(x, W) REP(y, H) REP(i, N) { if(IN_RANGE(x+X[i], 0, W) && IN_RANGE(y+Y[i], 0, H)) { one[x][y]+=a[x+X[i]][y+Y[i]]-'0'; } } REP(i, N) REP(j, N) if(i!=j) { // i-j int dx = X[i]-X[j]; int dy = Y[i]-Y[j]; auto key = MP(dx, dy); if(ng.count(key)) continue; if(dx==0 && dy==0) continue; ng[key] = 1; vector<Pos> v; REP(k, N) v.PB(Pos{X[k], Y[k]}); REP(k, N) v.PB(Pos{X[k]+dx, Y[k]+dy}); sort(ALL(v)); v.erase(unique(ALL(v)), v.end()); pat.PB({Pos{dx, dy}, v}); } REP(i, pat.size()) { // cout<<pat[i].ref<<" -> "<<pat[i].pos<<endl; // cout<<pat[i].ref.x<<" "<<pat[i].ref.y<<endl; } ll ans = 0; REP(pi, pat.size()) { auto& p = pat[pi]; REP(x0, W) REP(y0, H) { int xx = x0+p.ref.x; int yy = y0+p.ref.y; if(IN_RANGE(xx, 0, W) && IN_RANGE(yy, 0, H)) { ll lans = 0; REP(i, p.pos.size()) { int ex = x0 + p.pos[i].x; int ey = y0 + p.pos[i].y; if(IN_RANGE(ex, 0, W) && IN_RANGE(ey, 0, H)) { lans += a[ex][ey]-'0'; } } ans = max(ans, lans); } } } // cout<<"one "<<one<<endl; REP(x0, W) REP(y0, H) REP(x1, W) REP(y1, H) if(!(x0==x1 && y0==y1)) { int dx = x0-x1; int dy = y0-y1; PII k = MP(dx, dy); if(!ng.count(k)) { // cout<<x0<<" "<<y0<<" "<<x1<<" "<<y1<<" -> "<<one[x0][y0]+one[x1][y1]<<endl; ans = max(ans, one[x0][y0]+one[x1][y1]); } } return ans; } };
| 
class ApplesAndOrangesEasy { public: int maximumApples(int N, int K, vector <int> info) { VI w(N), sum(N); // sum of [i-K+1, i] REP(i, info.size()) w[info[i]-1]=1; REP(i, N) RANGE(j, max(0, i-K+1), i+1) sum[i]+=w[j]; ll ans=info.size(); REP(i, N) if(!w[i]) { bool ok=true; RANGE(j, i, min(N, i+K)) if(sum[j]>=K/2) ok=false; if(!ok) continue; ans++; RANGE(j, i, min(N, i+K)) sum[j]++; } return ans; } };
| 
int main() { int test_cases; cin>>test_cases; ll N, D, H, M; string s; REP(ttt, test_cases) { cin>>N; vector<PII> w; REP(i, N) { cin>>D>>H>>M; REP(j, H) w.PB(MP(M+j, D)); } sort(ALL(w)); ll ft = w[0].first * (360 + 360-w[0].second); ll st = w[1].first * (360-w[1].second); ll ans = st>=ft ? 1 : 0; cout<<"Case #"<<ttt+1<<": "<<ans<<endl; } return 0; }
(追記)
int main() { int test_cases; cin>>test_cases; ll N, D, H, M; string s; REP(ttt, test_cases) { cin>>N; priority_queue<pair<ll, pair<ll, ll>>> q; ll all = 0; REP(i, N) { cin>>D>>H>>M; REP(j, H) q.push(MP(-(M+j)*(360-D), MP(-1, (M+j)*360))); all+=H; } ll ans = 1LL<<60; ll cur=all; while(q.size() && cur < all*2) { ll t = -q.top().first; ll dn = q.top().second.first; ll dur = q.top().second.second; q.pop(); cur+=dn; q.push(MP(-(t+dur), MP(1, dur))); if(t != -q.top().first) { ans = min(ans, cur); } } ans = min(ans, cur); cout<<"Case #"<<ttt+1<<": "<<ans<<endl; } return 0; }
| 
■■■■■ ■□■□■ ■■■■■ 5x3, N=13→答え14 ■□■□■ □■□■□ ■□■□■ ↑これ前提で9個目以降を□に置いて行くと答え15になってしまう □■□■□ ■□■□■ □■□■□ ↑こっちだと14
int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; char m[10010][10010]; // 無駄 ll large(ll W, ll H, ll N) { if(W>H) swap(W, H); // W<=H ll ans = 1LL<<60; REP(eo, 2) { ll NN=N; VI n(5); CLEAR(m, 0); REP(y,H)REP(x,W) if((x+y)%2==eo) m[y+1][x+1]=1; REP(y,H)REP(x,W) { int co=0; REP(dir, 4) if(m[y+dy[dir]+1][x+dx[dir]+1]) co++; n[co]++; } ll lans = 0; REP(i, 5) { ll use = min(NN, n[i]); lans += use * i; NN -= use; } if(NN) cout<<"ERR "<<W<<" "<<H<<" "<<N<<" eo "<<eo<<endl; assert(NN==0); ans = min(ans, lans); } return ans; } int main() { int test_cases; cin>>test_cases; ll W,H,N; string s; REP(ttt, test_cases) { cin>>H>>W>>N; ll ans = large(W, H, N); cout<<"Case #"<<ttt+1<<": "<<ans<<endl; } return 0; }
766 G++ -O2 Bs.cpp && ./a.out < a.txt 767 G++ -O2 Bs.cpp && ./a.out < a.txt 768 G++ -O2 Bs.cpp && ./a.out < B-small-attempt0.in > try_bs.txt 769 diff b try_bs.txt ← small解と一致確認、よかった 770 G++ -O2 BsRef.cpp && ./a.out < B-small-attempt0.in > b ← b が古くなってたら困るので念のため small 解の出力を更新しておこう 771 diff b try_bs.txt ← small解と一致確認、よかった 772 G++ -O2 BsRef.cpp && ./a.out < B-large.in > obl.txt ← largeをsmallコードで実行! ROCK! (Bus error) 773 G++ -O2 BsRef.cpp && ./a.out < B-large.in > obl.txt ← (Bus error) (つд⊂)ｺﾞｼｺﾞｼ 774 G++ -O2 BsRef.cpp && ./a.out < B-large.in > obl.txt ← (Bus error) ...??? 775 gdb ./a.out < B-large.in > obl.txt ← -bash: gdb: command not found (カッコわるい) 776 G++ -O2 BsRef.cpp && ./a.out < a.txt 777 G++ -O2 BsRef.cpp && ./a.out < a.txt 778 G++ -O2 BsRef.cpp && ./a.out < a.txt ← cout<<"ok"<<endl; を入れてどこまで実行できてるか見るなど 779 G++ -O2 BsRef.cpp && ./a.out < a.txt 780 G++ -O2 BsRef.cpp && ./a.out < a.txt 781 G++ -O2 BsRef.cpp && ./a.out < a.txt 782 G++ -O2 Bs.cpp && ./a.out < a.txt ← やっと気づいた(´・ω・｀) 783 G++ -O2 Bs.cpp && ./a.out < a.txt 784 G++ -O2 Bs.cpp && ./a.out < B-large.in ← 動くじゃ〜ん 785 G++ -O2 Bs.cpp && ./a.out < B-large.in > obl.txt 786 G++ -O2 Bs.cpp && ./a.out < B-small-attempt0.in > try_bs.txt 787 diff b try_bs.txt ← 念のため念のためsmall解と一致確認、よかった
