300億円欲しい

メジャーリーグのデータ解析します

AtCoderで緑色になるまでにやったこと

はじめに

ABC165でやっと緑色になりました。 f:id:gg_hatano:20200503132306p:plain

競技プログラミングを割とちゃんと始めてから、これまでにやってみたことを書いておきます。

初心者が陥りがちなポイントをまとめておけば、これから始める人に役立てるかなと思いました。

目次

環境の話

いろいろ揃っていて、いい時代ですね。本当に。

[環境] けんちょんさんその他、先人のみなさまの記事を読む

情報が充実しています。大変助かりました。

qiita.com qiita.com

10回くらい読みました。

qiita.com

この記事を読んで、とりあえず800問解こう！と思いました。あと350問(2020/05/02現在)です。

[環境] C++11の環境をつくる@macOS

仮想マシンで環境構築する用のスクリプトを置きました。 atcoder利用で戦う環境 · GitHub

便利に戦える様に、c++11以上を使って、bits/stdc++.hをインクルードしたくなります。

ローカルでやるには色々面倒でしたので、仮想マシンを使いました。

↑の内容を、vagrant 2.2.6 とvirtualbox6.0.4で動かしています。

VScodeでRemove Developしたりするといいと思います。

[環境] atcoder-toolsは便利なので使う

使いましょう。便利です。

[環境] atcoder problemsは楽しいので使う

f:id:gg_hatano:20200503133709p:plain

進捗が閲覧できて楽しいです。学校の勉強もこんな感じでやりたかった。 https://kenkoooo.com/atcoder/#/user/gghatano?userPageTab=Progress+Charts

[環境] atcoder problemsのバーチャルコンテストは楽しいので開催する

たのしい！！！自分でコンテストを立てれば、自分がまだ解いていない問題を、指定した難易度の問題からランダムに選んでくれます。超絶便利です。

参加する時間が他の人とずれていても、パフォーマンスの数字で競えるのも良いですね。

社内では、バーチャルコンテスト実施->リモート会議で時間を合わせて感想戦、を繰り返しています。強い人たちと直接話して、何を考えながら解いているのかを聞けると学びが多いです。

C++の話

こういうことを書き出すとキリがありませんが、3つだけ書いておきます。

[C++] 大きな桁の数字の扱いに注意する

普段の業務では、int, long, doubleくらいしか使っていなかったせいか、大きな桁に慣れていませんでした。積極的にlong longを使っています。

[C++] 出力する少数の桁に注意する

cout << setprecision(10); などとしておきましょう。 ちゃんと計算しても、欲しい精度で出力しないと正解できません。

[C++] powが遅いので自分で書く

TLEするので、↓を用意しました。標準で用意されたものが遅いってどういうことだ。

typedef long long ll;
ll mypow(ll x, ll n){
  if(n == 0)
    return 1;
 
  if(n % 2 == 0)
    return mpow(x * x, n / 2);
  else
    return x * mpow(x, n - 1);
}

他にも、long long用のgcdとか、mod(109+7)上での組み合わせとか、いろいろ準備しておくと戦いやすいです。

競技プログラミング特有(?)の話

[競プロ] まずは全探索する

最初はきれいな解法を探しがちでした。

最近は、まずは全探索前提で考える、ダメなら制約を見ながら工夫する、という手順で考えられるようになりました。

Atcoderの解説PDFもそういう流れで書いてあることが多いです。全探索最強です。

[競プロ] (a+b-1)/a する

こういう便利なものは知っておきましょう。

[競プロ] コーナーケースに気を付ける

おそらく、↓の問題の話です。アホですね。 atcoder.jp

Atcoderはテストケースが親切で、色々気づかせてくれます。 とはいえ、際どいケースはケアしないと爆死します。↓とか。気をつけます。 atcoder.jp

[競プロ] 速く解く練習をする

解ければいいやと思っていましたが、それだとレートが上がりません。

速く解くのは大事。

[競プロ] 過去の皆さんの実装を参考にする

これのことですね。

この記事のことだと思います。

アルゴリズムはわかっても、実装で詰まって進めないことがよくあります。今後もあります。 自分で考えるのと並行して、人の実装を参考にするようにしました。いろいろな工夫がつまっています。

さいごに

[競プロ] AtCoderはすごい

atcoder.jp ほぼ毎週、オンラインのコンテストを無料で開催して、教育的な問題と解説を準備してシステムを運用して...ってちょっと考えられません。

コロナ対応のStayHome生活は、Atcoderのおかげでかなり充実しています。

引き続きどうかよろしくお願いいたします。

メモ

企業コンで関われるといいな。社内に最適化マラソンマッチのネタがあるはず...