yn2011's blog

技術メモ

AtCoder Beginner Contest に参加し始めた

AtCoder が毎週開催している AtCoder Beginner Contest (以下ABC)に参加するようになって 1ヶ月程度経ったので何かその辺りのことを書いておく。

今の成績

Rating 132 の灰色 f:id:pokuwagata:20200505212852p:plain

なぜやるか

  • 新しい趣味が欲しかった
  • 実装力の強化
  • 有給消化 + GW で25連休中のため比較的時間がある*1

始める前の実力

コンテストに関係しそうなやつだと

  • 競技プログラミング未経験
  • 高校数学は大体分かる(ただし整数問題は分からない*2)、大学の数学はほぼ忘れた
  • 電子・情報系の学部にいた。ただしコンピュータ・サイエンスはそんなに身に付いていない*3
    • 計算量・ビッグオー記法の概念・数学的な定義は何となく分かる
  • 業務でコード書くエンジニアとしての経験は3年ぐらい
    • C++ は書いたことない
    • 業務はフロントエンドを担当することも多く、複雑なアルゴリズムの実装が要求されたことはない

ABC 初参加前にやったこと

  • AtCoder に限らず、所謂競技プログラミングC++ が主流とのことだったので、まずは C++ の環境構築と学習から始めた(ちなみに、この選択は正しくて、ほぼ全てのAtCoder 関連の記事・解説放送、書籍は C++ を前提にしているので C++ やったことなくても学習した方が絶対効率よく学べる)

環境構築

VSCode の場合について書く。以下が揃えば良い感じに C++ でコンテストに参加できる。

code-runner (C++17 実行) の settings.json

  "code-runner.executorMap": {
    "cpp": "cd $dir && g++ -std=c++1z $fileName && ./a.out",
  },

AOJ ITP1 を解いた

自分の場合は C++ をまったく知らなかったので、レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編:競プロを始めよう】 でオススメされている通りに AOJ の ITP1コースを解いて練習しておくことにした。

愚直に9割ぐらい解いたんですが、注意点としては

  • 解答例は C++14 or 17 を見るようにする (標準ライブラリに慣れる)
  • ある程度プログラミング経験がある場合は全部やらなくていいと思う。 とりあえずA,B 問題に取り組んで解説放送聞いたり提出されたコードを読んだほうが実践的かも
  • ITP1 では標準入力の受け取りに慣れるのが1番大事かも

ABCに初めて参加した

自分はこの時点でA, B 問題までは解けた。コンテスト自体の知識は参加して覚えたほうが早い。(提出方法、問題の形式、誤答するとペナルティが発生する等)

スニペットを用意した

ABC の解説放送のライブコーディングで使われているスニペットを参考にした。自分の場合は start とタイプすると以下が挿入されるように設定している。

  "start-template": {
    "prefix": "start-template",
    "body": [
      "#include <bits/stdc++.h>",
      "#define rep(i,n) for(int i=0; i < (n); i++)",
      "#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)",
      "using namespace std;",
      "using ll = long long;",
      "",
      "int main() {",
      "  $0",
      "  return 0;",
      "}"
    ],
    "description": "basic"
  },

いちいちテンプレートファイルを準備して問題毎にコピーして新しく書き始めるよりも早いと思う。

コンテストで学んだこと

主に数値の取り扱い。Webアプリケーションを書いているだけだと意識することが少ない(気がする)

でもコンテストでは必須の知識だと思う。(A, B 問題でそこを狙ってくるテストケースや問題設定が多いので)

  • int (符号付き32bit 整数) の最大値は 231 -1 で、大体 2.14 * 109 で 、10桁
  • long int (符号付き64bit 整数)の最大値は 263 -1 で、大体 9.22 * 1018 で 、19桁
  • 除算は小数部切り捨て(例 5/2 = 2)
    • 切り上げする場合は (a+b-1) / b説明
  • 最終的な計算結果はオーバーフローしなくても計算途中の評価がオーバーフローすると駄目(例 a * b - ca * b がオーバーフロー)

あと、AtCoder のコンテストで C++ で解答する場合は計算機の性能は大体 108 step / sec ぐらいと想定すると良いみたいです。(例えば O(N) でも 1018 step だと 2sec 以内には絶対に収まらない)

ここに書いてた

今やっていること

週に4時間もコンテスト関連には時間使えていないと思う。土日にコンテストに参加して次のコンテストまでに解説放送聞いて実装してみたりぐらいが限界。

ABC に参加する

忘れない限りは毎週参加している。C, D問題は実戦で学ぶ感じになっている。C問題は慣れれば解けるようになってくる印象。実はそんなに高度なことを要求していないことが多い。

解説放送を聞く

神コンテンツ。これがなければ ABC 止めてたかも。模範解答自体はコンテスト終了と同時に公開されるが、大抵読んでも理解に時間がかかるか何も得られないので、最近は始めから解説放送を聞いている。(これは自分の読解力の問題もある)

D 問題以降は正直ちゃんとアルゴリズム等の実装経験積まないと対応できないことが明らかなんだけど、それをする時間をまとめて取れなさそうなので 解説放送に出てきたものから順に学んでいこうかと思っている。まあいつかは D で要求される範囲全部カバーできるようになるんじゃないかな...

今後の目標

  • コンテストに参加し続ける(後5回ぐらい参加で茶色になりそう)
  • C, D 問題の正答率を上げる
  • 楽しむ

*1:とはいえ次の業務で使う技術や知識のキャッチアップの方が優先なので、余暇を全て費やすことはできないが

*2:整数問題の対策が必要なのは当時は東大ぐらいだったのでやってない。今もそうかもだが

*3:C 言語でダイクストラとかバブルソートとか実装する演習があった記憶はある。当時は理解していた。今は実装は無理