yn2011's blog

技術メモ

AtCoder 茶色になったので振り返りと茶色になるために必要だと思うことを書く

C++ AtCoder

最初に一言。茶色になるのは想像以上に大変だった。

tl;dr

  • C++ の学習と AtCoder のコンテスト参加を今年の 4 月頃から始めて、12 月に茶色になった
  • 茶色になるまでの振り返りと、現在（2020年）の AtCoder で茶色になるために必要だったことを書いていく

AtCoder をはじめる前の実力とかモチベーション

レート遷移

f:id:pokuwagata:20201223172800p:plain

開始 1ヶ月

  • A, B 問題は AC できることが多かった（WA することもあった）
  • レート補正もあったので参加すればするだけ順調にレートは伸びた
  • 意外と AC できて楽しい

開始 2ヶ月

  • レート 170 で停滞
  • 始めは相性の良いコンテストが続いていただけで、実際の実力はこれぐらいであることが判明。辛い。

f:id:pokuwagata:20201223173551p:plain

  • 多分これぐらいの時期に AtCoder の実行時間制限と計算量の見積もりを理解し始めた（それまでは勘）
  • あと WA するとペナルティ受けるらしいことを知った気がする

開始 3 ~ 4ヶ月

  • レート 300 まで成長
  • 一応精進はしていたが単純にコンテストの相性が良い回があってレートが上がった感じ
  • しかしここからが長い
  • 多分ようやく C++ の標準ライブラリの使い方に慣れてきた頃（pair は便利、sort はこう書けるのか等）
  • 精進は何を勘違いしたのか D 問題の練習してたと思う

開始 5 ~ 7ヶ月

  • レート 300前後を彷徨う
  • 精進しているにも関わらずむしろレートが下がる暗黒期
    • ABC 178 でパフォ 79 叩き出して泣きそうになってた。なんで初めてコンテスト参加したときより低いんだ？
  • コンテスト本番の実戦力の欠如もレートが安定しない原因だったと思う
    • A 問題で少し悩む -> 焦る -> B 問題で悩む -> 焦る -> (思考リソース枯渇）-> 死
  • このあたりで、自分はアルゴリズムの勉強する領域には達して無くて、 A~C 問題を大量に練習しなきゃいけないレベルなんだ、と自己認識を改めた（謙虚さが大事）
  • この頃ぐらいから数学的な思考みたいなものを取り戻し始めた感覚があった（大学受験以降は全然数学してなかった）

開始 8ヶ月~ 茶色

  • 過去のコンテストの演習を積んで、C 問題レベルまでを解くときに必要な知識とか注意点が分かってきた
  • レートが単調増加を始める
  • この時期は ABC よりも ARC が大量に開催されるようになっていて、ARC だと安定して 500~600 ぐらいのパフォーマンス出せたというのも大きい
    • 昔から処理能力が評価されるテストが苦手だったというのはありそう（センターより記述式が好きだった）
    • 正直今でも ABC は怖いです

やって良かったと思うこと

  • 過去の ABC コンテストを時間を計りながら解く（A~C 問題レベルを大量に解く）
  • 1.5 倍速で解説放送を見る
  • 解けなかった問題は何が自分に不足していたのか振り返って記録を残す
  • 解けなかった問題を繰り返し解く（Solve Later Again)
  • とりあえずコンテストには出場し続ける
  • 実装の方針が思いつかないときに検討することリストを自分なりに整理する

やらなくても良かったと思うこと

  • C++ を Web のチュートリアル と AOJ で学習（AtCoder のために学習するなら普通に AtCoder の問題解いた方が効率良い）
  • A ~ C 問題を安定して解答できないのに D 問題（茶 Diff ）で要求されるアルゴリズムの勉強をする（そのうち役に立つことは間違いないが、多分レートが上がらない間の精進が辛くなる）

茶色になるまでに必要そうなこと

C++ を使っていて灰色で停滞している人向け。他の言語は分からん。 多分高レートの人が書くと当然すぎて省略されたり、もう記憶になかったりすると思うような細かいことも書いていく。 ちなみに、多分最速で茶色目指すなら C++ より Python の方が良いと思った。C++ よりもオーバーフローや誤差を気にしなくても良いので...

場合分け

  • 考察の基本。数学でやるのと同じ。
  • 愚直に場合分けして整理するだけで O(1) で済むならそれが 1 番良い

全探索

  • 全探索で済む問題なら全探索一択（バグりにくい）
  • 下手な考察で全探索を回避しようとしない方がいい
  • bit 全探索が使えないかは心に留めておく。 n = 218 ぐらいなら全然間に合う。

n = 108 以内に収まらない場合の工夫

  • 問題の性質を活用することで単純な全探索を効率化する（探索対象や範囲を変更する）
    • 集合 A から全探索して集合 B を見つけるのではなく、集合 B として考えられる全事象を全探索するとか
      • 集合 B のパターンが限定的で、集合 A の判定が 少ない計算量で済むなら有効(ABC181 D)
    • 全探索？楽勝ｗｗｗ　みたいな感じに思いがちだが色々とパターンはあるので経験を積むのが大事

切り上げ

  • C++ は整数型同士の除算は切り捨て
  • a / b の切り上げをしたい場合は (a + b -1) / b

min と max

  • 使える場面を意識するとコードが見通しよくなる
  • a = max(a, 0) で a の最小値を保証したり、b = min(b, 30) b の最大値を保証したり

分布を使う

  • map 型の活用。最初の頃は意識しないと浮かんでこない発想だった。
  • ABC 172 C、ABC159 D、ABC 139 C

オーバーフロー

  • long long でも 約 9.2 * 1018 までしか扱えない
  • オーバーフローが式の途中でも発生しないように注意する（式変形も考慮する）
  • `for(ll i=1; i*i<=n; i++) で i = 109 を超えるような場合とかに注意

誤差

  • double 同士の計算は誤差がある
    • 7.29 * 100 = 728.999 みたいになることがある
    • ABC 169 B
  • double の仮数部は 約16桁 ( ARC 109 B でルートを取る場合に誤差）
  • 誤差許容の問題の場合の出力は、printf("%.12f", ans) ぐらいしておくと良い（ABC 126 C）

整数

  • 事前に学習してないと辛い
  • lcm、gcd、約数・素数列挙

ちょっとした変換

文字コードを加算・減算することで簡単に変換できる

  • 小文字 -> 大文字変換 printf("%c", t - 32);
  • 大文字 -> 小文字変換 printf("%c", t + 32);
  • 文字列 -> 数値 : '1' - '0' -> 1 に変換
  • 数値 -> 文字列 : to_string(1)

整数の切り出し

  • 上2桁、下2桁を切り出す
    • 1234 / 100 -> 12
    • 1234 % 100 -> 34
  • 順番に切り出す
int dx = 12345;
while(dx) {
  cout << dx % 10 << endl; // 5, 4, 3 ...
  dx /= 10;
}

その他

A ~ C 問題でもわりと頻出の考え方

  • 貪欲法
  • 累積和
  • 簡単な DP

今後について

  • 茶色になって区切りが良いのと、本業の学習にも注力したいので続けるか悩み中
    • 元々は趣味が欲しいと思って始めたことだが、本業でエンジニアやってて灰色で挫折しましたっていうのは悔しいみたいな感情にも突き動かされていたので茶色になって満足感が強い
  • でもコンテスト自体が良い脳トレとコーディング力の維持にはなっている感覚があってこの状態は保ちたいんだよな