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

beet's soil

競プロのことなど

Codeforces Round #390 (Div. 2)

新年初コンテスト

【A. Lesha and array splitting】

何も考えずにDP+経路復元。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int n;
  cin>>n;
  int a[n],s[n+1];
  s[0]=0;
  for(int i=0;i<n;i++) cin>>a[i],s[i+1]=s[i]+a[i];
  if(s[n]){
    cout<<"YES"<<endl<<1<<endl<<1<<" "<<n<<endl;
    return 0;
  }
  bool dp[n+1];
  int pre[n+1];
  memset(dp,0,sizeof(dp));
  memset(pre,-1,sizeof(pre));
  dp[0]=1;
  for(int i=0;i<n;i++)
    for(int j=i+1;j<=n;j++)
      if(dp[i]&&(s[j]-s[i])) dp[j]=1,pre[j]=i;
  if(dp[n]){
    vector<int> v;
    int i=n;
    while(~i){
      v.push_back(i);
      i=pre[i];
    }
    cout<<"YES"<<endl;
    reverse(v.begin(),v.end());
    cout<<v.size()-1<<endl;
    for(int j=0;j<(int)v.size()-1;j++){
      cout<<v[j]+1<<" "<<v[j+1]<<endl;
    }
  }else cout<<"NO"<<endl;
  return 0;
}
【B. Ilya and tic-tac-toe game】

やるだけ。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int h=4,w=4;
  string s[h];
  for(int i=0;i<h;i++) cin>>s[i];
  bool f=0;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(s[i][j]!='.') continue;
      s[i][j]='x';
      for(int k=0;k<4;k++){
	f|=(s[k][0]=='x'&&s[k][1]=='x'&&s[k][2]=='x');
	f|=(s[k][1]=='x'&&s[k][2]=='x'&&s[k][3]=='x');
	f|=(s[0][k]=='x'&&s[1][k]=='x'&&s[2][k]=='x');
	f|=(s[1][k]=='x'&&s[2][k]=='x'&&s[3][k]=='x');
      }
      f|=(s[0][0]=='x'&&s[1][1]=='x'&&s[2][2]=='x');
      f|=(s[1][1]=='x'&&s[2][2]=='x'&&s[3][3]=='x');
      f|=(s[0][1]=='x'&&s[1][2]=='x'&&s[2][3]=='x');
      f|=(s[1][0]=='x'&&s[2][1]=='x'&&s[3][2]=='x');
      
      f|=(s[0][2]=='x'&&s[1][1]=='x'&&s[2][0]=='x');
      f|=(s[1][2]=='x'&&s[2][1]=='x'&&s[3][0]=='x');
      f|=(s[0][3]=='x'&&s[1][2]=='x'&&s[2][1]=='x');
      f|=(s[1][3]=='x'&&s[2][2]=='x'&&s[3][1]=='x');
      s[i][j]='.';
    }
  }
  cout<<(f?"YES":"NO")<<endl;
  return 0;
}
【C. Vladik and chat】

readforces2017って感じ。
"mention"の意味がわからなくてn分溶かした。
二つ以上離れているものは関係ないので候補が少ないものから貪欲に決めればいい。
構文解析パートが害悪。
used[n]をused[m]にしていて20分溶かした(つらい

#include<bits/stdc++.h>
using namespace std;
vector<string> split(const string &str, char sep){
  vector<string> v;
  stringstream ss(str);
  string buffer;
  while( getline(ss, buffer, sep) ) {
    v.push_back(buffer);
  }
  return v;
}
int s2i(string s){
  stringstream ss(s);
  int x;
  ss>>x;
  return x;
}
int main(){
  int T;
  string tmp;
  getline(cin,tmp);
  T=s2i(tmp);
  while(T--){
    getline(cin,tmp);
    int n,m;
    n=s2i(tmp);
    vector<string> name(n);
    map<string,int> ms;
    getline(cin,tmp);
    name=split(tmp,' ');
    for(int i=0;i<n;i++) ms[name[i]]=i;
    getline(cin,tmp);
    m=s2i(tmp);
    int who[m];
    memset(who,-1,sizeof(who));
    string chat[m],out[m];
    vector<string> v[m];
    for(int i=0;i<m;i++){
      getline(cin,chat[i]);
      out[i]=chat[i];
      for(int j=0;j<(int)chat[i].size();j++)
	if(!isalpha(chat[i][j])&&!isdigit(chat[i][j])) chat[i][j]=' ';

      v[i]=split(chat[i],' ');
      if(out[i][0]!='?'){
	who[i]=ms[v[i][0]];
	v[i].erase(v[i].begin());
      }
      /*//
      sort(v[i].begin(),v[i].end());
      v[i].erase(unique(v[i].begin(),v[i].end()),v[i].end());
      cout<<who[i]<<":";
      for(int j=0;j<(int)v[i].size();j++) cout<<v[i][j]<<" ";
      cout<<endl;
      //*/
    }
    while(1){
      int t=n,idx=-1;
      bool used[n];
      for(int i=0;i<m;i++){
	if(who[i]>=0) continue;
	memset(used,0,sizeof(used));
	if(i>0&&who[i-1]>=0) used[who[i-1]]=1; 
	if(i+1<m&&who[i+1]>=0) used[who[i+1]]=1; 
	for(int j=0;j<(int)v[i].size();j++){
	  if(ms.find(v[i][j])==ms.end()) continue;
	  used[ms[v[i][j]]]=1;
	}
	int r=0;
	for(int j=0;j<n;j++) r+=!used[j];
	if(idx<0||r<t){
	  t=r;
	  idx=i;
	}
      }
      if(t==0||idx<0) break;
      memset(used,0,sizeof(used));
      if(idx>0&&who[idx-1]>=0) used[who[idx-1]]=1; 
      if(idx+1<m&&who[idx+1]>=0) used[who[idx+1]]=1;
      for(int j=0;j<(int)v[idx].size();j++){
	if(ms.find(v[idx][j])==ms.end()) continue;
	used[ms[v[idx][j]]]=1;
      }
      for(int j=0;j<n;j++){
	if(used[j]) continue;
	//cout<<idx<<" "<<j<<endl;
	who[idx]=j;
	break;
      }
    }
    
    bool f=1;
    for(int i=0;i<m;i++) f&=who[i]>=0;
    if(f){
      for(int i=0;i<m;i++){
	cout<<name[who[i]]<<":";
	for(int j=0,x=0;j<(int)out[i].size();j++){
	  if(x) cout<<out[i][j];
	  x|=out[i][j]==':';
	}
	cout<<endl;
      }
    }else cout<<"Impossible"<<endl;
  }
  return 0;
}

ABに比べて難易度変わりすぎな気がした。

【全体】

1772 -> 1834 (+62) highest
一個もSystemTest落ちなくてびっくりした。
あとn回ぐらいでDiv1に上がれそう、、!!