読者です 読者をやめる 読者になる 読者になる

beet's soil

競プロのことなど

AtCoder Grand Contest 013

139th 1944 -> 1986 (+42) highest!!
今週で黄色に上がりたい(フラグ
AB速解きできたのでよかったんですが2時間以上かけてC通せないのダメ。
Cがコドフォに同名で同じ内容の問題があってえぇってなった。

【A - Sorted Arrays】

数列が与えられる。いくつかの部分列に分けてそれぞれが単調非減少もしくは単調非増加になるようにする。
最小でいくつの部分列に分ける必要があるかを求める。

貪欲やるだけ。罠があるかと思ったけどそんなこともなかった。O(N).

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  int ans=0;
  for(int i=0;i<n;i++){
    ans++;
    while(i+1<n&&a[i]==a[i+1]) i++;
    if(i==n-1) break;
    if(a[i]<a[i+1]){
      while(i+1<n&&a[i]<=a[i+1]) i++;
    }else{
      while(i+1<n&&a[i]>=a[i+1]) i++;
    }
  }
  cout<<ans<<endl;
  return 0;
}
【B - Hamiltonish Path】

N頂点M辺の単純グラフが与えられる。次の3つの条件を満たすパスを1つ求める。
1. 2つ以上の頂点が含まれる。
2. 同じ頂点を二度通らない。
3. 端点と直接繋がっているすべての頂点がパスに含まれる

適当に2点決めて貪欲に伸ばしていけばいい。
まだ含まれていない頂点があるなら伸ばして、ないなら条件を満たしているので終了。
O(MsqrtN)くらいかと思ったけど冷静に考えるとO(N+M).

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> G[114514];
signed main(){
  int n,m;
  cin>>n>>m;
  int a[m],b[m];
  for(int i=0;i<m;i++) cin>>a[i]>>b[i];
  for(int i=0;i<m;i++){
    a[i]--;b[i]--;
    G[a[i]].push_back(b[i]);
    G[b[i]].push_back(a[i]);
  }
  list<int> l;
  l.push_back(a[0]);
  l.push_back(b[0]);
  bool used[n];
  memset(used,0,sizeof(used));
  used[a[0]]=1;
  used[b[0]]=1;
  while(1){
    int x=l.front(),y=l.back();
    //cout<<x<<" "<<y<<endl;
    bool ff=1;
    for(int i=0;i<(int)G[x].size();i++){
      if(used[G[x][i]]) continue;
      used[G[x][i]]=1;
      ff=0;
      l.push_front(G[x][i]);
      break;
    }
    for(int i=0;i<(int)G[y].size();i++){
      if(used[G[y][i]]) continue;
      used[G[y][i]]=1;
      ff=0;
      l.push_back(G[y][i]);
      break;
    }
    if(ff) break;
  }
  int k=l.size();
  cout<<k<<endl;
  bool f=0;
  for(auto it=l.begin();it!=l.end();++it){
    if(f) cout<<" ";
    cout<<(*it)+1;
    f=1;
  }
  cout<<endl;
  return 0;
}
【C - Ants on a Circle】

長さLの円周上にN匹の蟻がいる。各蟻は向きを持っており、別の蟻とぶつかると反転する。
T秒後の各蟻の位置を求める。

蟻本に載ってるやつの拡張版。すり抜ける考察と順番が変わらない考察ができれば、
あとは一匹でも位置がわかれば解ける。
本番中はO(N)シミュレーションを頑張っていたけど解けなかった。
各蟻とすれ違う時に右回りなら番号が1増え、左回りなら番号が1減ると考えるとO(N)で番号と位置がわかる。
ソートがボトルネックでO(NlogN).

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
signed main(){
  int n,l,t;
  cin>>n>>l>>t;
  int x[n],w[n];
  for(int i=0;i<n;i++) cin>>x[i]>>w[i];
  {
    bool f=1;
    for(int i=0;i<n-1;i++) f&=w[i]==w[i+1];
    if(f){
      int y[n];
      for(int i=0;i<n;i++){
	if(w[i]==1) y[i]=(x[i]+t)%l;
	else y[i]=(x[i]-t+(t/l+1)*l)%l;
	cout<<y[i]<<endl;
      }
      return 0;
    }
  }

  
  int y[n];
  for(int i=0;i<n;i++){
    if(w[i]==1) y[i]=(x[i]+t)%l;
    else y[i]=(x[i]-t+(t/l+1)*l)%l;
  }
  int pos=y[0];
  sort(y,y+n);
  
  int p=0;
  for(int i=1;i<n;i++){
    if(w[0]==w[i]) continue;
    if(w[0]==1){
      int q=0;
      if(2*t>=(x[i]-x[0])) q=(2*t-(x[i]-x[0]))/l+1;
      (p+=q)%=n;
    }else{
      int q=0;
      if(2*t>=(x[0]+l-x[i]%l)) q=(2*t-(x[0]+l-x[i]%l))/l+1;
      (p+=n-q)%=n;
    }
  }
  map<int,vector<int> > m;
  for(int i=0;i<n;i++)
    if(w[0]==1) m[y[i]].insert(m[y[i]].begin(),i);
    else m[y[i]].push_back(i);
  
  //cout<<m[pos][0]<<" "<<p<<endl;
  for(int i=0;i<n;i++) cout<<y[(m[pos][0]+i+n-p)%n]<<endl;
  return 0;
}

周りがみんな黄色くなっていって焦りを感じる。
実力をもっとつけたい。