| 
B[N], OP('-'か'+')[N] が与えられて、A[i] OP[i] A[i+1] = B[i], A[i]>0 であるとき、A[0]～A[N] として可能な値の組み合わせはいくつあるか答える問題。無限にあるなら -1 を返す。
↓ (passed in practice room)
// PII, VI の定義を変えて ll を使うようにしてある class ImportantSequence { public: PII f(int i, int op, ll v, vector <int>& B, string& OP) { if(i==0) return MP(op, v); op *= OP[i-1]=='-' ? 1 : -1; v *= (ll)(OP[i-1]=='-' ? 1 : -1); v += (ll)B[i-1]; return f(i-1, op, v, B, OP); } int getCount(vector <int> B, string OP) { VI lb, ub; REP(i, B.size()+1) { PII p = f(i, 1, 0, B, OP); if(p.first== 1) lb.PB(p.second); if(p.first==-1) ub.PB(p.second); } //cout<<lb<<endl; if(lb.size()==0 || ub.size()==0) return -1; ll l = *max_element(ALL(lb)); ll u = *min_element(ALL(ub)); //cout<<l<<endl; //cout<<u<<endl; //return (u-1)-(l+1)+1; // NG! return max((ll)0, (u-1)-(l+1)+1); } };
| 
ooo-- +-0 (Rank 51) 1640->1653
Round 3 と同時開催の Div2。
日本の上位陣スゲェと思いながらsystem testを見てた。
| 
int main() { int N; cin>>N; vector<PII> st(100010); vector<pair<PII, int> > ans(100010); int ansp=0; int anscount=0; int stp=0; REP(i, N) { int v; cin>>v; int push_pos=i; while(stp>0 && st[stp-1].second > v) { push_pos = st[stp-1].first; //cout<<"push_pos "<<push_pos<<endl; int prevH = max(v, stp-1>0 ? st[stp-2].second : 0); ans[ansp++] = MP(MP(st[stp-1].first+1, i), st[stp-1].second - prevH); anscount += st[stp-1].second - prevH; stp--; } if(stp==0) { if(v>0) st[stp++] = MP(push_pos, v); } else if(st[stp-1].second < v) { st[stp++] = MP(push_pos, v); } //REP(m, stp) cout<<st[m]<<" "; cout<<endl; } while(stp>0) { int prevH = stp-1>0 ? st[stp-2].second : 0; ans[ansp++] = MP(MP(st[stp-1].first+1, N), st[stp-1].second-prevH); anscount += st[stp-1].second-prevH; stp--; } cout<<anscount<<endl; REP(i, ansp) { REP(j, ans[i].second) { cout<<ans[i].first.first<<" "<<ans[i].first.second<<endl; } } return 0; }
| 
↓修正版(test pass in practice room)
class FoxAndKgram { public: int maxK(vector <int> len) { int N=len.size(); for(int k=50;k>=0;k--) { VI used(N); int ok=1; int L=0; //cout<<k<<endl; REP(i, N) { if(used[i]) continue; if(len[i]==k) {used[i]=1;L++;continue;} REP(j, N) { if(used[j]||i==j) continue; if(len[i]+len[j]+1==k) {used[i]=used[j]=1;L++;break;} } } ok &= L>=k; //cout<<ok<<endl; if(ok) return k; } return 0; } };
| 
↓修正版(test pass in practice room)
vector <int> WC; int SC; int N; map<PII, int> memo; class FoxAndDoraemon { public: // [i0, i1) int f(int i0, int i1) { PII key=MP(i0, i1); if(memo.count(key)) return memo[key]; int rest = i1-i0; if(rest<=0) return memo[key] = 0; if(rest==1) return memo[key] = WC[i0]; if(rest==2) return memo[key] = SC+max(WC[i0], WC[i0+1]); if(rest==3) return memo[key] = SC+max(WC[i0], SC+max/*min*/(WC[i0+1], WC[i0+2])); // >=4 int ans = 1000000; for(int i=1;i<rest;i++) { int c = SC+max(f(i0, i0+i), f(i0+i, i1)); ans = min(ans, c); } return memo[key] = ans; } int minTime(vector <int> _WC, int _SC) { sort(ALLR(_WC)); WC=_WC; SC=_SC; memo.clear(); N=WC.size(); int ans = f(0, N); return ans; } };
| 
文字列sのsubstringと文字列tのsubsequenceが一致するようなものの個数を求める問題。長さはどちらも5000以内。
あとでできてる人のコードや解説を見て。
dp[i][j] = s[i]で終わるsubstringとt[j]以前の文字列のsubsequenceのうち内容が一致するものの個数
とすると、dp[i][j]はt[j]以前のsubsequenceのうちt[j]を使う場合と使わない場合に分けて考えることができる。
t[j]を使わない場合、使わないということはt[j-1]以前の文字列に対するsubsequenceなのでdp[i][j-1]を加算
t[j]を使う場合、s[i]とt[j]を両方使うことになる。
s[i]!=t[j]のときは前に何がきても一致しないので加算なし
s[i]==t[j]のときは s[i-1] でおわるsubstringとt[j-1]以前のsubsequenceが一致すればよいのでdp[i-1][j-1]、
それに加えてs[i]とt[j]一文字だけの場合があるのでさらに1を加算。
というわけで式は
dp[i][j] = dp[i][j-1] + (s[i]==t[j] ? 1+dp[i-1][j-1] : 0)
となる
答えはsubstringが終わるすべての位置について足せばいいのでΣi dp[i][t.size-1]
.....と、言われると納得するけど思いつかんのだなぁ。
本番中はs[i]以前のsubstringとt[j]以前のsubsequenceでずっと考えてて、なんか4通りあるしさらに重複してそうとなってできなかった。
しばらく考えてできないときは状態をもっと分割してみて最後に足す、というアプローチが使えるかも。
(↓あとで通したやつ)
#define MOD 1000000007LL int main() { string A,B; cin>>A>>B; VVI dp(A.size()+1, VI(B.size()+1, 0)); for(int i=1; i<A.size()+1; i++) for(int j=1; j<B.size()+1; j++) { dp[i][j] = ((ll)dp[i][j-1] + (A[i-1]==B[j-1] ? 1+dp[i-1][j-1]:0)) % MOD; } ll ans = 0; REP(i, A.size()+1) ans = (ans+dp[i][B.size()])%MOD; cout<<ans<<endl; return 0; }
| 
#define INF 2000000000 class LessFoo { public: bool operator()(const PII& a, const PII& b) const { return a.first < b.first; } }; int main() { int N, M; cin>>N; vector<PII> A(N); int Axmin=INF, Axmax=-INF; REP(i, N) { cin>>A[i].first>>A[i].second; Axmin=min(Axmin, A[i].first); Axmax=max(Axmax, A[i].first); } cin>>M; vector<PII> B(M); int xmin=INF, xmax=-INF; REP(i, M) { cin>>B[i].first>>B[i].second; xmin=min(xmin, B[i].first); xmax=max(xmax, B[i].first); } if(xmin <= Axmin || Axmax <= xmax) { cout<<"NO"<<endl; return 0; } sort(ALL(B)); REP(i, N) { int x0 = A[i].first; int x1 = A[(i+1)%N].first; int y0 = A[i].second; int y1 = A[(i+1)%N].second; if(x0==x1) continue; int i0 = distance(B.begin(), lower_bound(ALL(B), MP(x0, -INF), LessFoo())); int i1 = distance(B.begin(), lower_bound(ALL(B), MP(x1, -INF), LessFoo())); //cout<<i<<" "<<A[i].first<<" "<<A[(i+1)%N].first<<" "<<i0<<" "<<i1<<endl; for(int i=i0;i<i1;i++) { double x = B[i].first; double y = B[i].second; if(!( y < ((double)y1-y0)/(x1-x0)*(x-x0)+y0 )) { cout<<"NO"<<endl; return 0; } } for(int i=i1;i<i0;i++) { double x = B[i].first; double y = B[i].second; //cout<<x<<" "<<y<<endl; //cout<<x0<<" "<<y0<<endl; //cout<<x1<<" "<<y1<<endl; //cout<<(y - y0)<<" "<<(y1-y0)*(x-x0)<<endl; if(!( y > ((double)y1-y0)/(x1-x0)*(x-x0)+y0 )) { cout<<"NO"<<endl; return 0; } } } cout<<"YES"<<endl; return 0; }
