chacoderのブログ

競技プログラミングそのほか

トップ > ABC177 参戦記

ABC177 参戦記


2020.8.29 21:00-22:40に開催されたABC177に出場しました。

atcoder.jp

成績と簡単な感想

ABCEの４完　９９分４９秒　９ペナ　でパフォーマンスは１０５３、レーティングは前回７４５から＋３５で７８０となり、Highestを更新しました。

極端に簡単な問題がなくBCあたりに歯ごたえのある問題が入っているセットで早解きが苦手な私にはチャンスの回でした。もっともDの解法がすぐに見えず、Eに賭ける選択をしたのになかなかEが解けず苦戦しました。終了直前にEを通せたときは感激しました。

Eを通せてないとまたもや冷えていたところなので薄氷を踏む思いです。
まだまだ緑の実力に達していません。

f:id:chacoder:20200830100845p:plain

https://atcoder.jp/users/chacoder/history/share/abc177

A問題

シンプルな計算問題で簡単ですが丁寧に確認して提出しました。
１分５５秒。

B問題

部分文字列の不一致数を全探索でカウントする問題ですがB問題では相当難しい部類の問題だったと思います。
しかしdifを見ると125でみんな解けているので参加者全体のレベルが相当上がってきていることを実感します。

バグもなく一発でスムーズに書けました。
経過時間９分１０秒、本問の回答時間７分１５秒はかなり好調でした。

C問題

経過時間３２分３４秒。本問の回答時間２３分２４秒。
２ペナを叩きもたつきました。

最初に愚直解で提出しTLEを食いました。
出す前に考えなければいけません。

計算量を減らすのに最初に全部の和をとっておいて、引いていく方針を思いつきました。

long long ans=0;
  sum-=A[0];
  for(long long i=0;i<N-1;i++){
    ans+=A[i]*sum;
    ans%=1000000007;
    sum-=A[i+1];
  }

この方針は間違ってはいなかったのですが、提出するとオーバーフローしてWAがでました。
このオーバーフローの解消がどうしてもできず、最後は禁断の多倍長で殴って無理に通しました。
今は反省しています。

C問題のWAしたコード

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

int main(){
  long long N;
  cin>>N;
  long long A[200010];
  long long sum=0;
  for(long long i=0;i<N;i++){
    cin>>A[i];
    sum+=A[i];
  }
  sum%=1000000007;
  long long ans=0;
  sum-=A[0];
  for(long long i=0;i<N-1;i++){
    ans+=A[i]*sum;
    ans%=1000000007;
    sum-=A[i+1];
  }
  
  cout<<ans<<endl;
  return 0;
}

検討

改めて変数の値を丁寧に確認していくとA[i]が大きな値のときにmodをとって引き算すると負になることがわかりました。
これは考えてみると当たり前のことです。

modの引き算のときに負になったらmodを足す、というところができていませんでした。

足し算、掛け算は簡単ですが、引き算は負になったらmodを足す、割り算は逆元を掛けなければなりません。

書き直したコード

modの引き算のところを修正して無事にACしました。

#include <bits/stdc++.h>
using namespace std;
static const long long MOD=1000000007;

int main(){
  long long N;
  cin>>N;
  long long A[200010];
  long long sum=0;
  for(long long i=0;i<N;i++){
    cin>>A[i];
    sum+=A[i];
  }
  sum%=MOD;
  long long ans=0;
  sum-=A[0];
  if(sum<0){
    sum+=MOD;
  }
  for(long long i=0;i<N-1;i++){
    ans+=A[i]*sum;
    ans%=MOD;
    sum-=A[i+1];
    if(sum<0){
    sum+=MOD;
    }
  } 
  cout<<ans<<endl;
  return 0;
}

更に検討

解説で紹介されていたA[i]^2の方法はなるほどです。

また解説の解法でsumを足していく方法なら私の躓いた減算の罠に陥らなくて済みます。

D問題

コンテスト中はunion-findを使って一発で解けることに気づきませんでした。
５分ほど検討してうまい解法が思いつかずE問題に進みました。

確かに最大の友達グループのメンバーをそれぞれ別のグループに分ければ題意にこたえているのは見やすいところです。

union-findは知っていたしライブラリももっていたしコンテストで使ったこともありましたが、単に知っているのと適切な問題で適切な使い方ができるのとは距離があります。使いこなせて初めて自分のものになること、使いこなせる技術を増やしていくことを心がけます。

自分のライブラリーにはunion-findのサイズを出力する部分がなかったのでアップデートしておきたいと思います。

※　追記
　改めて解いて５分ほどでACできました。
　次は使えるはず。

E問題

最近はほぼ毎日水difレベルを解いており、多少の難しい問題も時間があれば解けるチャンスがあるはずだ、という気持ちになっています。

これまではコンテスト中には怖くてE問題あたりにはなかなか手が出せなかったのですが、今回はDの解法がすぐに見えなかったこともあり、E問題に賭けてみることにしました。

E - Coprime

問題は数列のセットが　①いずれの要素も互いに素か　②すべての要素の最大公約数が１か　③すべての要素の最大公約数が１でないか　を判別して回答する、というものです。

②、③はgcdを使って判別すればよいので簡単ですが①をどうするかが問題です。
要素数が最大１００万なのですべてのペアについてgcdを判別していくのでは到底間に合いません。

ちょうど最近数学ガール・フェルマーの最終定理（
https://www.amazon.co.jp/dp/4797345268/ref=cm_sw_r_tw_dp_x_hJWsFbA9JG4HC
）で互いに素とか素数指数表現とかを勉強したところでした。各要素について素因数分解してその要素をmapに入れて、要素数が２以上になったら約数が重複していると判別する、という方針を立てました。

最終的にこの方針で解けたのですが、素因数分解を高速に行うところでいろいろつまづいて時間がかかってしまいました。

素朴にやっても間に合うかと思ったのですがTLEします。
i*i<=Nまでを判定する方針とし、更にiは2以上の場合に奇数だけを判定する、先に互いに素でない要素を発見したらブレークする、などの対応をとって間に合いました。

特に先に互いに素でない要素を発見したらブレークする、というのは要素数が最大１００万ある中で素数は７万８０００個ほどなので大切なポイントかと思いました。

最後は平方数の場合にmapに２回入ってしまう問題に気づき、この部分を修正してクリアー。

書き上げて時計を見ると１０時３９分を回っています。
提出時間が１０時３９分４９秒。数秒のジャッジをへてACの表示がでた直後にコンテスト終了のお知らせがでました。

復習など

E問題はTLなどでエラトステネスの篩をつかった高速判定法に言及されていたので、ほかの方法も検討しておきたいと思います。

D問題は自力で一度といておきたいと思います。