beet's soil

競プロのことなど

SRM 708 Div1

翌日のプログの試験対策として出た(大嘘

【Easy- BalancedStrings】

概要
instability=similarityを満たすN個の文字列を構築する
ただし、
instability:= 連続する2文字で、種類が異なるものの数
similarity := N(N-1)/2個のペアに対して、同じ文字のペアの数の総和
とする。
解法
N<=26の時はaから順番に1文字ずつ埋めればinstability=similarity=0になる。
これ以降N>26の場合を考える。
実験してみると、instabilityに対してsimilarityが大きくなってしまうので、
instabilityを大きくする方法とsimilarityを小さくする方法を考える。
instabilityを大きくするにはuvuvuvuvuvuvuvのように二種類の文字を交互に並べればよい。
similarityを小さくするには1文字のものをなるべく均等に割り振ればよい。
99*10>15*14/2*6に気づけば勝ち。

vector <string> findAny(int N) {
    vector<string> v(N);
    if(N<=26){
      for(int i=0;i<N;i++) v[i]='a'+i;
      return v;
    }
    int tmp=0,cnt=N/6;
    char c='a'-1;
    for(int i=0;i<N-10;i++){
      if(i%cnt==0) c++;
      v[i]=c;
    }
    for(int i=0;i<N-10;i++)
      for(int j=i+1;j<N-10;j++)
	if(v[i]==v[j]) tmp++;
    
    for(int i=0;i<10;i++){
      char a='g'+i*2,b='g'+i*2+1;
      v[N-10+i]=a;
      while(tmp&&(int)v[N-10+i].size()<100){
	if(v[N-10+i].size()%2) v[N-10+i]+=b;
	else v[N-10+i]+=a;
	tmp--;
      }
    }
    return v;
  }

入力が100通りしかなかったのでローカルでセルフジャッジした(安心できる

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector <string> findAny(int N) {
  vector<string> v(N);
  if(N<=26){
    for(int i=0;i<N;i++) v[i]='a'+i;
    return v;
  }
  int tmp=0,cnt=N/6;
  char c='a'-1;
  for(int i=0;i<N-10;i++){
    if(i%cnt==0) c++;
    v[i]=c;
  }
  for(int i=0;i<N-10;i++)
    for(int j=i+1;j<N-10;j++)
      if(v[i]==v[j]) tmp++;
    
  for(int i=0;i<10;i++){
    char a='g'+i*2,b='g'+i*2+1;
    v[N-10+i]=a;
    while(tmp&&(int)v[N-10+i].size()<100){
      if(v[N-10+i].size()%2) v[N-10+i]+=b;
      else v[N-10+i]+=a;
      tmp--;
    }
  }
  return v;
}
int main(){
  for(int i=1;i<=100;i++){
    vector<string> v=findAny(i);
    assert((int)v.size()==i);
    int ins=0,sim=0;
    for(int j=0;j<i;j++){
      //cout<<v[j]<<endl;
      assert(v[j].size()<=100);
      assert(v[j].size());
      for(int k=0;k<(int)v[j].size();k++) assert(islower(v[j][k]));
      for(int k=0;k<(int)v[j].size()-1;k++) ins+=v[j][k]!=v[j][k+1];
      for(int k=j+1;k<i;k++)
	for(int x=0;x<(int)v[j].size();x++)
	  for(int y=0;y<(int)v[k].size();y++)
	    sim+=v[j][x]==v[k][y];
    }
    //cout<<i<<":"<<ins<<" "<<sim<<endl;
    assert(ins==sim);
  }
  return 0;
}
【全体】

o-- 136.13point 95th
1319 -> 1446 (+127) highest
もう一回easyを通せればyellowになりそう!すごーい!