beet's soil

競プロのことなど

Codeforces Round #401 (Div. 2)

コンテスト多いなぁ

【A. Shell Game】

周期6なので18個if文を書く(ア

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n,x;
  cin>>n>>x;
  n%=6;
  if(n==0){
    cout<<x<<endl;
  }
  if(n==1){
    if(x==0) cout<<1<<endl;
    if(x==1) cout<<0<<endl;
    if(x==2) cout<<2<<endl;
  }
  if(n==2){
    if(x==0) cout<<1<<endl;
    if(x==1) cout<<2<<endl;
    if(x==2) cout<<0<<endl;
  }
  if(n==3){
    if(x==0) cout<<2<<endl;
    if(x==1) cout<<1<<endl;
    if(x==2) cout<<0<<endl;
  }
  if(n==4){
    if(x==0) cout<<2<<endl;
    if(x==1) cout<<0<<endl;
    if(x==2) cout<<1<<endl;
  }
  if(n==5){
    if(x==0) cout<<0<<endl;
    if(x==1) cout<<2<<endl;
    if(x==2) cout<<1<<endl;
  }
  return 0;
}
【B. Game of Credit Cards】

難しすぎるので二部マッチング。
上は負けない奴にエッジを張って全体から引く。
下は勝てる奴にエッジを張る。
二部マッチングはライブラリ参照。

int main(){
  int n;
  string s,t;
  cin>>n>>s>>t;
  V=n*2;

  
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(s[i]<=t[j]) add_edge(i,j+n);
  cout<<n-bipartite_matching()<<endl;
  
  for(int i=0;i<MAX_V;i++) G[i].clear();
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(s[i]<t[j]) add_edge(i,j+n);
  cout<<bipartite_matching()<<endl;
  
  return 0;
}
【C. Alyona and Spreadsheet】

尺取り+RUP。
冷静に考えて更新かかるのたかだかnm回なのでRUPいらなかった。
どこまで伸ばせるかを前計算で求めてクエリを処理する。
TLEがなぜか1秒で怖かったのでscanfに直してリサブしたけど必要なかった。うーん。
RUPはライブラリ参照。

signed main(){
  int n,m;
  scanf("%lld %lld",&n,&m);
  //cout<<n<<m<<endl;
  
  int a[n][m];
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      scanf("%lld",&a[i][j]); 

  RUP rup(n);
  for(int i=0;i<n;i++) rup.update(i,i+1,P(i,i));
  
  for(int j=0;j<m;j++){
    for(int i=0;i<n;i++){
      int k=i;
      while(k+1<n&&a[k][j]<=a[k+1][j]) k++;
      //cout<<i<<" "<<k<<endl;
      rup.update(i,k+1,P(k,k));
      i=k;
    }
  }
  
  int k;
  cin>>k;
  for(int i=0;i<k;i++){
    int l,r;
    cin>>l>>r;
    l--;r--;
    //cout<<l<<" "<<rup.query(l)<<" "<<r<<endl;
    if(rup.query(l)<r) puts("No");
    else puts("Yes");
  }
  
  return 0;
}
【D. Cloud of Hashtags】

下からやれば貪欲に決まるのでやる。
オーダーはちょっと考えるとO(Nsqrt(N))になるいつものだとわかる。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  cin.tie(0);
  int n;
  cin>>n;
  string s[n];
  for(int i=0;i<n;i++) cin>>s[i];
  int l[n];
  l[n-1]=s[n-1].length();
  for(int i=n-1;i>0;i--){
    l[i-1]=1;
    if(l[i]==1) continue;
    int a=s[i-1].length();
    for(int j=1;j<min(l[i],a);j++){
      if(s[i-1][j]<s[i][j]){
	l[i-1]=a;
	break;
      }
      if(s[i-1][j]>s[i][j]) break;
      l[i-1]=j+1;
    }
  }
  
  for(int i=0;i<n;i++){
    for(int j=0;j<l[i];j++) cout<<s[i][j];
    cout<<endl;
  }
  return 0;
}
【E. Hanoi Factory】

b,aの降順にソートすればDAGになりそうな感じがする。
範囲MAXと区間更新ができれば解けるのでRMQする。
RMQはライブラリ参照。

signed main(){
  int n;
  cin>>n;
  vector<int> v;
  vector<st> s(n);
  for(int i=0;i<n;i++){
    //scanf("%lld %lld %lld",&(s[i].a),&(s[i].b),&(s[i].h));
    cin>>s[i].a>>s[i].b>>s[i].h;
    v.push_back(s[i].a);
    v.push_back(s[i].b);
  }
  sort(s.begin(),s.end());
  sort(v.begin(),v.end());
  v.erase(unique(v.begin(),v.end()),v.end());
  map<int,int> m;
  int sz=v.size();
  for(int i=0;i<sz;i++) m[v[i]]=i;
  RMQ rmq(sz);
  for(int i=0;i<n;i++){
    //cout<<s[i].a<<" "<<s[i].b<<endl;
    int t=rmq.query(0,m[s[i].b]);
    rmq.update(m[s[i].a],t+s[i].h);
  }
  //for(int i=0;i<sz;i++) cout<<i<<":"<<rmq.query(i,i+1)<<endl;
  cout<<rmq.query(0,sz)<<endl;
  return 0;
}
【全体】

ooooo 5542points
1712 -> 1829 (+117)
Eで配列サイズ足りないのとオーバーフローで4WA生やしたのもったいなさすぎる。
いつもこのくらい問題読みやすければいいのになあ。