beet's soil

競プロのことなど

AtCoder Grand Contest 016

126th 2106 -> 2151 (+45) highest!!
4連続highest、だんだん怖くなってきた。

そろそろ1完だとレートが下がりそうなのでB->A->Cの順番で解いた。

【A - Shrinking】

強い心で考察をしないで愚直を書く。まあ26種試すんだろうなあという気持ちになるので試す。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  string s;
  cin>>s;
  int ans=s.size()-1;
  for(int i=0;i<26;i++){
    if(s.find((char)('a'+i))==string::npos) continue;
    string t=s;
    int tmp=0;
    while(1){
      bool flg=1;
      for(int j=0;j<(int)t.size();j++)
	flg&=t[j]==('a'+i);
      if(flg) break;
      tmp++;
      string u;
      for(int j=0;j<(int)t.size()-1;j++)
	if(t[j]==('a'+i)||t[j+1]==('a'+i)) u.push_back(('a'+i));
	else u.push_back(t[j]);
      t=u;
    }
    ans=min(ans,tmp);
  }
  cout<<ans<<endl;
  return 0;
}
【B - Colorful Hats】

がんばって場合分けするだけ。

少し考えると、
全体の色の数をCとしたときに、ある人について
・同じ色の人がいる場合はC色見えているはず
・同じ色の人がいない場合はC-1色見えているはず
ということがわかる。

以降x=max(a), y=min(a)とする。
まずx-y>1のときはどうやってもできないのでNo。
x==yのときは、全員同じ色の人がいる場合(x*2<=N)か、
全員ユニークな場合(x+1==N)だけYesで、他はNo。
残るx==y+1のときは、N人の中でa[i]==yの人が何人いるか数えて、
それらがユニークだと仮定した上で条件を満たせるかが答えになる。

#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 x=*max_element(a,a+n);
  int y=*min_element(a,a+n);
  if(x-y>1){
    cout<<"No"<<endl;
    return 0;
  }
  if(x==y){
    if(2*x<=n||n==x+1){
      cout<<"Yes"<<endl;
    }else{
      cout<<"No"<<endl;
    }
    return 0;
  }
  int cnt=0;
  for(int i=0;i<n;i++){
    if(a[i]==y) cnt++;
  }
  if(cnt>=x){
    cout<<"No"<<endl;
    return 0;
  }
  if((x-cnt)*2<=(n-cnt)) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}
【C - +/- Rectangle】

フィーリングで解いた(ア

まあサンプル1から1と-whで埋めるんだろうという気持ちになるので書くとWAが生える。
1 3 1 2みたいなコーナーがすぐ見つかるので1e9/(wh)と-1e9で埋める方針にすると通った。
念のためO(WHwh)で判定を書いたらTLEしてあばばってなったので累積和でO(WH)にした。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int H,W,h,w;
  cin>>H>>W>>h>>w;
  int a[H][W];
  memset(a,0,sizeof(a));

  int x=1000000000/(w*h);
  for(int i=0;i<H;i++)
    for(int j=0;j<W;j++)
      a[i][j]=x;

  for(int i=h-1;i<H;i+=h){
    for(int j=w-1;j<W;j+=w){
      a[i][j]=-(x*(h*w-1)+1);
    }
  }
  
  bool flg=1;
  int b[H+1][W+1];
  memset(b,0,sizeof(b));
  for(int i=0;i<H;i++)
    for(int j=0;j<W;j++)
      b[i+1][j+1]=b[i+1][j]+a[i][j];
  for(int i=0;i<H;i++)
    for(int j=0;j<=W;j++)
      b[i+1][j]+=b[i][j];
  
  for(int i=0;i<=H-h;i++){
    for(int j=0;j<=W-w;j++){
      int tmp=b[i+h][j+w]-b[i][j+w]-b[i+h][j]+b[i][j];
      flg&=tmp<0;
    }
  }

  int cnt=0;
  for(int i=0;i<H;i++)
    for(int j=0;j<W;j++)
      cnt+=a[i][j];

  if(!flg||cnt<=0){
    cout<<"No"<<endl;
    return 0;
  } 

  cout<<"Yes"<<endl;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(j) cout<<" ";
      cout<<a[i][j];
    }
    cout<<endl;
  }
  return 0;
}

Bはまあ運ゲーで一発で通ったのが奇跡って感じで、
Cは得意なタイプのロシアゲーだったので全体的に得意セットだったっぽい。
Dは後半のオイラーグラフが全然わからず。。。
Eをもう少しちゃんと読んでおくべきだったかなあという気もする。
ちゃんと復習しないとなあ…