ARC106参戦記

atcoder.jp

ARC106参戦記

2020年10月24日21:00-22:40に開催されたARC106に参戦しました。
１完１ペナ23:55秒でパフォーマンスは638。
レートは794から14下がって780になりました。

Contest Result - AtCoder

A問題

３のA乗と５のB乗の和で10e18以下の数Nをつくれるかを判定する問題です。
AとBはいずれも正の整数です。

考察

０は正の整数に含まれるかみたいな基本的なところで少し悩みました。
正の数とは０より大きな数をいうようなので含まれないのが正解でした。

AもBもそんなに大きくならなそうなので全探索で十分間に合いそうです。

最初にpowを使って実装したらWA。

WAしたコード

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

int main(){
  long long N;
  cin>>N;
  for(int i=1;i<40;i++){
    for(int j=1;j<26;j++){
      if(N==pow(3,i)+pow(5,j)){
        cout<<i<<" "<<j<<endl;
        return 0;
      }
    }
  }
  cout<<-1<<endl;
  return 0;
}

ためしに累乗のところだけやってみるとたしかにまずい。
オーバーフローしない範囲の数でも誤差がでます。

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

int main(){
  int n;
  cin >> n;
  long long ans=pow(5,n);
  cout<<ans<<endl;
  return 0;
}

入力

25

出力

298023223876953152

どうして１の位が５にならないのか，頭を抱えました。

powにはいろいろ罠があり注意して使わなければなりません。

powを使わずに実装しましたがこんどはオーバーフローが悩ましい。
多倍長で殴りました。

せっかく勉強したpythonに切り替えた方がスマートだったなとあとで思いました。

ACしたコード

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

#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
using Bint = mp::cpp_int;
using Real = mp::number<mp::cpp_dec_float<1024>>;

int main(){
  Bint N;
  cin>>N;
  for(int i=1;i<40;i++){    
    for(int j=1;j<26;j++){
       Bint temp1=1;
       Bint temp2=1;
      for(int k=1;k<=i;k++){
        temp1*=3;
      }
      for(int l=1;l<=j;l++){
        temp2*=5;
      }
      if(N==temp1+temp2){
        cout<<i<<" "<<j<<endl;
        return 0;
      }
    }
  }
  cout<<-1<<endl;
  return 0;
}
 

A問題ふりかえり

結局１８分ほどかけて１WAもありトータル２３分ほど。
提出したときの推定パフォは850ぐらいでした。

powの性質をしっかり理解できていれば10分で書けた問題かと思います。

powの罠についてのメモ

powの計算結果は浮動小数点型で出力され整数型にキャストするときに丸め誤差が発生するようです。
powの内部でlogを使うため小数部が発生するのだとか。

B問題

B - Values

単純無向グラフの頂点に配列Aの数字を割り振って，辺の両側の数字を＋１，－１する操作を０回以上繰り返して配列Bにできるかという問題です。

考察

最初は，端から順番にBに合うよう＋ーの操作を愚直に繰り返し，終点でつじつまがあうかどうかを判定する方法を思いつきました。単純グラフとはいえ分岐も考えられるので，トポロジカルソートをかけてソート順に作業することを思いつきましたが，きわめて複雑なことになりはまりました。

はたと気づいたのが，結局，数列の和を比較すれば最後の帳尻が合うかどうかわかる，ということです。
えいやっと出力してみたらなんとうまくいきそうな雰囲気でジャッジが走りますがWAするケースがでます。

オーバーフローが考えられるのでlong long型で書きなおしたけれどまだ４ケース残ります。
このあたりで時間切れでした。

終了後にTLを見て問題は連結グラフに限られないことがわかりました。

Union-Findをつかって分割し，それぞれのグラフ毎にAとBの和を比較すればよさそうです。

Union-Findは以前のABCの解説ででてきたライブラリのものを使いました。

最初，分割したあとのそれぞれのグラフのAとBの和を比較するコードを同じルートのものを拾うような形で愚直に書いたらTLEするケースがあり失敗。

TLEしたコード（部分）

  map<int,int>mp;
  for(int i=0;i<N;i++){
    //cout<<uf.root(i)<<endl;
    mp[uf.root(i)]++;
  }
  for(auto itr=mp.begin(); itr !=mp.end();itr++){
    long long suma=0;
    long long sumb=0;
    for(int i=0;i<N;i++){
      if(uf.root(i)==(itr->first)){
        suma+=A[i];
        sumb+=B[i];
      }
    }
      //cout<<itr->first<<" "<<suma<<" "<<sumb<<endl;
      if(suma==sumb){
        continue;
      }
      else{
        cout<<"No"<<endl;
        return 0;
      }
  }

和を出すところを一工夫してAC.

ACしたコード

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

long long suma[200100];
long long sumb[200100];

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
       //if(rx>ry) swap(rx,ry); 小さい方を根にする場合
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main(){
  int N,M;
  cin>>N>>M;
  long long  A[200100];
  long long B[200100];

  //入力

  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  for(int i=0;i<N;i++){
    cin>>B[i];
  }
  UnionFind uf(N);
  for(int i=0;i<M;i++){
    int a,b;
    cin>>a>>b;
    a--;
    b--;
    uf.unite(a,b);
  }
  
  map<int,int>mp;
  for(int i=0;i<N;i++){
    mp[uf.root(i)]++;
  }
  for(int i=0;i<N;i++){
    suma[uf.root(i)]+=A[i];
    sumb[uf.root(i)]+=B[i];
  }
  for(auto itr=mp.begin();itr !=mp.end();itr++){
    if(suma[itr->first] != sumb[itr->first]){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
  return 0;
}

反省など

今回はC問題以下はまったく手をつけられませんでした。
順位表見て怯えずにくらいつく姿勢も大切だと思いました。

緑手前あたりで停滞していますが，力はついている実感があります（当社比）。
冷える回もなんとか最低限の結果を出して激冷えは回避できています。

ここ半年ぐらい茶中位から緑中位くらいで足ふみしたり後退したりしている人がかなり多い印象があります。

その背景には競技者が全体にレベルアップしていることがあるのではないかと思います。大量に新規参入者がある時期には，新たな初心者の流入で茶から緑くらいのレベルのレーティングアップには追い風になるのに対し，現在は落ち着いた状況にあり，みんながそこそこ精進している中で中低位者冬の時代を迎えているように思います。

それでも抜け出していく人はあっという間に抜け出していきますし，水や青以上の人は毎回それなりのパフォーマンスを出しているので，レーティングそのものの信頼性はあると思います。

まだまだ面白く学べているので，このあたりはまだ私の落ち着き場所ではないと思います（ちょっと言ってみた）。
レート変化に一喜一憂せず精進を重ねて力をつけていきたいと思います。