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

beet's soil

競プロのことなど

AtCoder Grand Contest 010

課題がね、やばい(迫真

【A - Addition】

偶+偶=奇だと勘違いしてシミュレーションを書いてしまった。
odd%2で終わり。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int e=0,o=0;
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    if(a%2) o++;
    else e++; 
  }
  while(1){
    int a=e/2,b=o/2;
    //cout<<e<< " "<<o<<endl;
    e-=a*2;
    o-=b*2;
    e+=a+b;
    if(!a&&!b) break;
  }
  //cout<<e<< " "<<o<<endl;
  cout<<(e+o==1?"YES":"NO")<<endl;
  return 0;
}

【B - Boxes】

一番大きいやつに合わせて愚直にシミュレーションすれば良さそうなんだけど、
O(A/N)になってNが小さいとTLEする。
考察すると、

sum(a)/(n*(n+1)/2)で引く回数がわかる。
一回の操作で連続する項の一箇所だけ差が-(N-1)されて他は+1される。

ことからx回-(N-1)されたとすると
1*(sum(a)/(n*(n+1)/2)-1)-(N-1)*x=sum(a)/(n*(n+1)/2)-N*x=a[i+1]-a[i]
が成り立つことがわかるのであとは各iについて条件を満たすかどうか判定すればよい。
(あとなんやかんや条件は事前に弾いておく。)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n;
  cin>>n;
  ll a[n],b[n];
  for(ll i=0;i<n;i++) cin>>a[i];
  ll sum,mi=n*(n+1)/2;
  for(ll i=0;i<n;i++) sum+=a[i];
  if(sum%mi){
    cout<<"NO"<<endl;
    return 0;
  }
  bool ch=0;
  for(ll i=0;i<n;i++) ch|=!(sum/mi<=a[i]&&a[i]<=sum/mi*n);
  if(ch){
    cout<<"NO"<<endl;
    return 0;
  }
  ll cnt=0;
  bool ff=1;
  for(ll i=0;i<n;i++){
    b[i]=a[(i+1)%n]-a[i];
    if((sum/mi-b[i])%n){
      ff=0;break;
    }
    cnt+=(sum/mi-b[i])/n;
  }
  cout<<(ff&&cnt==sum/mi?"YES":"NO")<<endl;
  return 0;
}

【全体】

293rd 1900 -> 1899 (-1)
C解けそうだったからBもっと早く解けてればなあという気持ち。
自頭セットは疲れる、、(面白いけど)。