beet's soil

競プロのことなど

Codeforces Round #441 (Div. 1, by Moscow Team Olympiad)

ooo-- 2448pts 2106 -> 2098 (-8)
時間内にD通せてれば上がってたよなあ…

Dashboard - Codeforces Round #441 (Div. 1, by Moscow Team Olympiad) - Codeforces

【A. Classroom Watch】

概要

忘れた

解法

やる

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  int n;
  cin>>n;
  vector<int> ans;
  for(int i=0;i<min(1000000,n);i++){
    string s=to_string(n-i);
    int k=n-i;
    for(int j=0;j<(int)s.size();j++) k+=s[j]-'0';
    //cout<<i<<" "<<k<<endl;
    if(k==n) ans.push_back(n-i);
  }
  cout<<ans.size()<<endl;
  sort(ans.begin(),ans.end());
  for(int u:ans) cout<<u<<endl;
  return 0;
}
【B. Sorting the Coins】
概要

1行に並んだN枚のコインを1枚ずつひっくり返していく。各ステップごとに以下の操作を何回行うかを求める。
1. 左から右にコインを見ていく
2. 今見ているコインが裏向きで、その右にあるコインが表向きなら交換する。

解法

 [l,r) みたいに区間を持ってマージしていく。
setを使えば O(N \log N) でできる。

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n;
  cin>>n;
  typedef pair<int,int> P;
  set<P> sp;
  sp.insert(P(n+2,n+2));
  cout<<1;
  for(int i=0;i<n;i++){
    int k;
    cin>>k;
    P p(k,k+1);
    auto latte=sp.lower_bound(p);
    //cout<<latte->first<<" "<<latte->second<<endl;
    if(p.second==latte->first){
      p.second=latte->second;
      sp.erase(latte);
    }
    auto malta=--sp.lower_bound(p);
    //cout<<malta->first<<" "<<malta->second<<endl;
    if(malta->second==p.first){
      p.first=malta->first;
      sp.erase(malta);
    }
    sp.insert(p);
    if((----sp.end())->second==n+1){
      cout<<" "<<i+2-((----sp.end())->second-(----sp.end())->first);
    }else{
      cout<<" "<<i+2;
    }
    
    
    //cout<<(----sp.end())->first<<" "<<(----sp.end())->second<<endl;
    //cout<<sp.size()-1-((----sp.end())->second==n+1)<<endl;
  }
  cout<<endl;
  return 0;
}
【C. National Property】
概要

1 ~ m までの文字があり、それぞれ大文字と小文字がある。
小文字のみからなる辞書が与えられるので、いくつかの種類の文字を大文字にすることで、
矛盾がない辞書を作ることができるか判定し、できるなら一つ出力する。

解法

明らかに2-SATなので辺の貼り方を考える。
辞書の中で隣り合う単語同士のみ調べればいいのはそれはそう。
以下ではaをそのまま、!aを大文字にするとする。
愚直に前から見ていって文字が異なるところの文字をa,bとすると
a<bのとき !b->!a と a->b を張る(bを大文字にするならaも大文字にしないといけないので)
a>bのとき a->!a と !b->b を張る(必ずaを大文字にしbをそのままにしないといけないので)
あとは2SATの復元をする。kmjpさんのブログを参考にした。
kmjp.hatenablog.jp

#include<bits/stdc++.h>
using namespace std;
using Int = long long;

struct SCC{
  int n;
  vector<vector<int> > G,rG,T,C;
  vector<int> vs,used,cmp;
  SCC(){}
  SCC(int n_){init(n_);}
  void init(int n_){
    n=n_;
    for(int i=0;i<(int)G.size();i++) G[i].clear();
    for(int i=0;i<(int)rG.size();i++) rG[i].clear();
    for(int i=0;i<(int)T.size();i++) T[i].clear();
    G.clear();
    rG.clear();
    vs.clear();
    used.clear();
    cmp.clear();
    T.clear();
    
    G.resize(n);
    rG.resize(n);
    used.resize(n);
    cmp.resize(n);
  }
  
  void add_edge(int from,int to){
    G[from].push_back(to);
    rG[to].push_back(from);
  }
  
  void dfs(int v){
    used[v]=1;
    for(int i=0;i<(int)G[v].size();i++){
      if(!used[G[v][i]]) dfs(G[v][i]);
    }
    vs.push_back(v);
  }
  
  void rdfs(int v,int k){
    used[v]=1;
    cmp[v]=k;
    C[k].push_back(v);
    for(int i=0;i<(int)rG[v].size();i++){
      if(!used[rG[v][i]]) rdfs(rG[v][i],k);
    }
  }
  
  int build(){
    fill(used.begin(),used.end(),0);
    vs.clear();
    for(int v=0;v<n;v++){
      if(!used[v]) dfs(v);
    }
    fill(used.begin(),used.end(),0);
    int k=0;
    for(int i=vs.size()-1;i>=0;i--){
      if(!used[vs[i]]){
	T.push_back(vector<int>());
	C.push_back(vector<int>());
	rdfs(vs[i],k++);
      }
    }
    for(int i=0;i<n;i++)
      for(int u:G[i])
	if(cmp[i]!=cmp[u])
	  T[cmp[i]].push_back(cmp[u]);
    for(int i=0;i<k;i++){
      sort(T[i].begin(),T[i].end());
      T[i].erase(unique(T[i].begin(),T[i].end()),T[i].end());
    }
    return k;
  }
};

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n,m;
  cin>>n>>m;
  vector<vector<int> > G(n);
  for(int i=0;i<n;i++){
    int k;
    cin>>k;
    G[i].resize(k);
    for(int j=0;j<k;j++){
      cin>>G[i][j];
      G[i][j]--;
    }
  }
  SCC scc(m*2);
  auto add_edge=[&](vector<int> &a,vector<int> &b){
    int x=min(a.size(),b.size());
    int i;
    for(i=0;i<x;i++){
      if(a[i]==b[i]) continue;
      if(a[i]<b[i]){
	scc.add_edge(m+b[i],m+a[i]);
	scc.add_edge(a[i],b[i]);
      }else{
	scc.add_edge(a[i],m+a[i]);
	scc.add_edge(m+b[i],b[i]);
      }
      break;
    }
    if(i==x){
      if(a.size()>b.size()){
	cout<<"No"<<endl;
	exit(0);
      }
    }
  };
  for(int i=0;i<n-1;i++)
    add_edge(G[i],G[i+1]);
  
  scc.build();
  auto cmp=scc.cmp;
  for(int i=0;i<m;i++){
    //cout<<cmp[i]<<" "<<cmp[m+i]<<endl;
    if(cmp[i]==cmp[m+i]){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
  
  vector<int> ans;
  for(int i=0;i<m;i++)
    if(cmp[i]<cmp[m+i]) ans.push_back(i);
  
  cout<<ans.size()<<endl;
  for(int i=0;i<(int)ans.size();i++){
    if(i) cout<<" ";
    cout<<ans[i]+1;
  }
  cout<<endl;
  return 0;
}
【D. High Cry】

コンテスト終わって10分後くらいに書き終わった。時間内に通したかった。

概要

i番目の高さがa[i]であるようなn個の尾根がある。
 1 \le l \lt r \le n となるようなl,rの組のうち、以下の条件を満たすものの数を求める。
 a[i] \lt K (l \le i \le r) 、ただし、 K = a[l] \ or \  a[l+1] \ or \  ... \ or \  a[r] (bitwise) 。

解法

こういうのはなんか最大から置いていく気持ちになる。
最大値Xを挟んだ区間について考えると、Xで立っていないbitが立っている要素を含むことが必要十分条件だとわかる。
Xを挟んだ区間を数え上げたあと、 [l, p) , p, [p+1, r) みたいに区間を分割していくことで重複を除いて数え上げられる。
同じ値が複数ある場合もなんかいい感じになる。
区間の最大値のindexを求めるのはセグ木でできて、立っていないbitを調べるのは O(\log X \log n) でできるので解ける。
setでlower_boundしたらTLEしたのでvectorにしたら通った。(定数倍改善ゲーやめて(TLE厳しくない?ないね))

#include<bits/stdc++.h>
using namespace std;
using Int = long long;

template <typename T,typename E>
struct SegmentTree{
  typedef function<T(T,T)> F;
  typedef function<T(T,E)> G;
  Int n;
  F f;
  G g;
  T d1;
  E d0;
  vector<T> dat;
  SegmentTree(Int n_,F f,G g,T d1,
	      vector<T> v=vector<T>()):
    f(f),g(g),d1(d1){
    init(n_);
    if(n_==(Int)v.size()) build(n_,v);
  }
  void init(Int n_){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1,d1);
  }
  void build(Int n_, vector<T> v){
    for(Int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(Int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  void update(Int k,E a){
    k+=n-1;
    dat[k]=g(dat[k],a);
    while(k>0){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
  T query(Int a,Int b,Int k,Int l,Int r){
    if(r<=a||b<=l) return d1;
    if(a<=l&&r<=b) return dat[k];
    T vl=query(a,b,k*2+1,l,(l+r)/2);
    T vr=query(a,b,k*2+2,(l+r)/2,r);
    return f(vl,vr);
  }
  T query(Int a,Int b){
    return query(a,b,0,0,n);
  }
};


signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  Int n;
  cin>>n;
  //scanf("%lld",&n);
  vector<Int> x(n);
  //for(Int i=0;i<n;i++) scanf("%lld",&x[i]);
  for(Int i=0;i<n;i++) cin>>x[i];
  typedef pair<Int,Int> P;
  vector<P> vp(n);
  vector<Int> s[32];
  for(Int j=0;j<32;j++){
    s[j].push_back(-1);
  }
  for(Int i=0;i<n;i++){
    vp[i]=P(x[i],i);
    for(Int j=0;j<32;j++){
      if((x[i]>>j)&1) s[j].push_back(i);
    }
  }
  
  for(Int j=0;j<32;j++){
    s[j].push_back(n);
  }
  SegmentTree<P,P> ushi(n,
			[](P a,P b){return a.first>b.first?a:b;},
			[](P a,P b){return a;},
			P(-1,-1),
			vp);
  Int ans=0;
  queue<P> q;
  q.push(P(0,n));
  while(!q.empty()){
    P pp=q.front();q.pop();
    Int l=pp.first,r=pp.second;
    if(l==r) continue;
    Int p=ushi.query(l,r).second;
    Int a=l-1,b=r;
    for(Int j=0;j<32;j++){
      if((x[p]>>j)&1) continue;
      {
	Int k=*--lower_bound(s[j].begin(),s[j].end(),p);
        a=max(a,k);
      }
      {
	Int k=*upper_bound(s[j].begin(),s[j].end(),p);
        b=min(b,k);
      }
    }
    Int A=p-(a+1);
    Int B=b-(p+1);
    Int C=(p-l)-A;
    Int D=(r-(p+1))-B;
    //cout<<l<<" "<<p<<" "<<r<<endl;
    //cout<<A<<" "<<B<<" "<<C<<" "<<D<<endl;
    ans+=(B+1)*C+(A+1)*D+C*D;
    //cout<<(B+1)*C+(A+1)*D+C*D<<endl;
    q.push(P(l,p));
    q.push(P(p+1,r));
  }

  cout<<ans<<endl;
  //printf("%lld\n",ans);
  return 0;
}

あー黄色になりたかった