エイシングプログラミングコンテスト 2020 反省

atcoder.jp

結果

A, B, C 問題は 0 WA で AC した。D 問題は解けず。E, F 問題は見たけど解けそうにないと思ってすぐにあきらめた。

感想

~~D 問題が今もお手上げ状態。復習はだいぶ先になるかも。~~
復習しました（7/13）。

C 問題復習

問題概要

二つの条件

$1\leq x,y,z$
$x^2+y^2+z^2+xy+yz+zx=n$

を満たす整数の組 $(x,y,z)$ の数を求めよ。

解き方

$1\leq N\leq10^4$ なので、 $1$ ～ $N$ で3重ループを回すのはもちろん無理。でも問題文を見ると計算量を $O(^3/2)$ で回せばいいことに気が付ける。詳しくは以下のコード参照。

ACしたコード

#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  for(int ii=1;ii<=n;ii++){
    int ans=0;
  for(int i=1;6*i*i<=ii;i++){
    for(int j=i;3*j*j+2*i*j+i*i<=ii;j++){
      for(int k=j;i*i+j*j+k*k+i*j+j*k+k*i<=ii;k++){
        if(i*i+j*j+k*k+i*j+j*k+k*i==ii){
          if((i==j)&&(j==k)){
            ans+=1;
          }
          else if(((i==j)&&(j!=k))||((j==k)&&(j!=i))){
            ans+=3;
          }
          else ans+=6;
        }
      }
    }
  }
  cout <<ans<<endl;
  }
}

雑記

~~時間を見つけて D 問題を AC したい。~~

7月13日追記

本日 D 問題を復習した。AC したコードだけ載せておく。条件分岐の仕方にまだまだ甘いところがあるのではないかと思う。そこを洗練すればもっとコードが短くなるはず。
ところで整数 $x$ を二進数表記した時、各桁に $1$ が現れる回数をカウントする標準関数があるのをしらなかった。__builtin_count(x) というやつ。

ACしたコード

#include<bits/stdc++.h>
using namespace std;
using ll=int64_t;

int pcount(int x){
  return __builtin_popcount(x);
}

int f(int x){
  int ans=1;
  int tmp;
  if(x==0){
    return ans;
  }
  while(x){
    tmp=pcount(x);
    x%=tmp;
    ans++;
  }
  return ans;
}

int main(){
  int n;cin>>n;
  string s;cin>>s;
  reverse(s.begin(),s.end());
  int p1=0;
  int p2,p3;
  vector<int>amari2(n);
  vector<int>amari3(n);
  for(int i=0;i<n;i++){
    if(s.at(i)=='1'){
      p1++;
    }
  }
  p2=p1+1;
  p3=p1-1;
  if(p3!=0){
    for(int i=0;i<n;i++){
      if(i==0){
        amari2.at(i)=1%p2;
        amari3.at(i)=1%p3;
      }
      else{
        amari2.at(i)=amari2.at(i-1)*2%p2;
        amari3.at(i)=amari3.at(i-1)*2%p3;
      }
    }
  }
  else{
    for(int i=0;i<n;i++){
      if(i==0){
        amari2.at(i)=1%p2;
        amari3.at(i)=0;
      }
      else{
        amari2.at(i)=amari2.at(i-1)*2%p2;
        amari3.at(i)=0;
      }
    }
  }
  int x02=0;
  int x03=0;
  if(p2!=0&&p3!=0){
    for(int i=0;i<n;i++){
      if(s.at(i)=='1'){
        x02+=amari2.at(i);
        x02%=p2;
        x03+=amari3.at(i);
        x03%=p3;
      }
    }
  }
  else if(p2==0&&p3!=0){
    for(int i=0;i<n;i++){
      if(s.at(i)=='1'){
        x03+=amari3.at(i);
        x03%=p3;
      }
    }
    x02=0;
  }
  else if(p3==0&&p2!=0){
    for(int i=0;i<n;i++){
      if(s.at(i)=='1'){
        x02+=amari2.at(i);
        x02%=p2;
      }
    }
    x03=0;
  }
  for(int i=n-1;i>=0;i--){
    int x=0;
    if(s.at(i)=='1'){
      bool zero=true;
      for(int j=0;j<n;j++){
        if(j==i)continue;
        if(s.at(j)=='1'){
          zero=false;
          break;
        }
      }
      if(zero){
        cout <<0<<endl;
        continue;
      }
      x+=x03;
      x-=amari3.at(i);
      if(x<0){
        x+=p3;
      }
      x%=p3;
      if(x==0){
        cout <<1<<endl;
      }
      else{
        int anss=f(x);
        cout <<anss<<endl;
      }
    }
    else if(s.at(i)=='0'){
      x+=x02;
      x+=amari2.at(i);
      x%=p2;
      if(x==0){
        cout <<1<<endl;
      }
      else{
        int anss=f(x);
        cout <<anss<<endl;
      }
    }
  }
}

コードについて

以下の文章は問題文を読まないと意味不明だと思います。問題文は本記事冒頭のリンク先参照。
入力は莫大な数になることがあるので、愚直に余りをとるのは難しい。なので、掛け算は好きなタイミングで余りをとれることを利用して、あらかじめ $n=1$ ～ $N$ まで $2^n$ を $p$ で割った数を計算し配列に格納している。ここで $N$ は 2進数表記した時の入力の桁数、 $p$ は各桁に $1$ が現れる回数。
問題にしたがってビット反転した時に、 $p$ が $\pm 1$ しか変わらない。なのでビット反転した後の数字を $p\pm 1$ で割った値があらかじめ作っておいた配列を利用して $X_1%(p\pm 1$ が簡単に求められる。
各所で $0$ 除算を回避するための条件分岐を入れている。
ちなみに一度最初の数字が莫大でも、一度 $p$ で割ってしまえば小さな数字になるため、2回目からは愚直に計算すればいい。