AtCoder 水色になりました

AtCoder Beginner Contest 179」で水コーダーになりました.

f:id:mts1104:20200924002344p:plain

本記事はいわゆる色変記事ですが,「水色になるためにやったこと」などと偉そうに語るつもりはありません.自分は性格的に「再現性」「効率性」を重視して物事に取り組むところがあり,そういう観点で今まで取り組んできたことを一度しっかりまとめたいと思ったので,本記事の作成に至りました.

経験上,効率を最適化するとモチベーションが追いつかずに物事を辞めてしまう可能性が高くなるので,モチベーション維持にも配慮しながらコスパの良いやり方を日々模索しています.ですので,本記事の内容には堅実なところもあれば緩いところもあります.

半分くらいは自分のために書いていますが,本記事が誰かの役に立てば幸いです.

※本記事を短時間で読みたい方は「精進方法」だけを読むのがオススメです.

自己紹介

本記事を作成するにあたり,「再現性」という意味でも前提をしっかり示すべきだと思い,あまり本意ではなかったのですが競プロの実力に関係しそうな項目をできるだけ挙げました.

  • 社会人4年目(IT中小企業)
  • 名古屋大学大学院修士卒(物理)*1
  • プログラミング経験
    • 学生時代は研究で Fortran を最低限
    • 新人研修で2ヶ月間の基礎勉強
    • 社会人2年目から業務で Python *2
  • 数学*3
  • タイピング*6
    • 寿司打 10,000 円コース:14,600 円分お得
    • タイピング速度測定:打鍵数 287
  • ゲーム得意*7

競プロを始めたきっかけ

ここは備忘録も兼ねて詳細に書きます.

もともとは Kaggle をやろうと思い,情報収集も兼ねて Twitter を始めたのですが,残業が多くて肝心の Kaggle には本格的に手を出せずにいました(半分くらい言い訳です).そんなとき,一部の Kaggler が競プロ(≒AtCoder)をやっている姿を見かけて,競プロなら自分にも取り組みやすいのではないかと思い興味を持つようになりました.

2020年3月頃,新型コロナの影響で残業が減少傾向にあったため,時間的余裕が生まれました.Kaggle をやることをまず考えたのですが,興味が少し薄れていたこと,自分のスキルバランス的に競プロをやった方がいいと判断したこと *8 ,そして弊社の後輩(AtCoder 橙)*9 に影響されたこと,などによって競プロを始めることにしました.

高校生の時,楽しくて数学の問題ばかり解いていたことを思い出します.それくらい競プロは楽しいです.それゆえ「こんなに遊んでていいのか?」という謎の罪悪感をたまに感じます.

精進

精進量

精進量は多い方だと思います.今思えば,もう少し水〜青 diff に挑戦してもよかったなあと思います.精進グラフは既に青色です.

f:id:mts1104:20200925010249p:plain f:id:mts1104:20200925010300p:plain f:id:mts1104:20200925010310p:plain f:id:mts1104:20200925010359p:plain:h200

精進方法

基本的には過去問をひたすら解く方法で精進していました.

  • 基本方針

    • 過去問を解いて知らない知識は都度勉強
      • 参考書で勉強して過去問で演習,という教科書的なやり方はあまりやっていないです
    • 網羅性については量を確保することで対応
      • この記事を参考にしてバランスが悪くならないようには注意していました
    • 過去問の選び方は気分で決める
      • ここは割と自由にやっていました
      • 低 diff をたくさん解きたい日,高 diff をじっくり解きたい日,色々あると思います
      • 水 diff を1日1問解く,ということは少し意識していましたが,厳密には守れていません
    • 再現性を意識する
      • 過去問が解けず解説を見た場合「似た問題が出たとき解けるか?」を考えていました
      • 上手くいけば「典型的な考察過程」のようなものが抽象化できて自分のものにできます
      • 何も見えなかった場合,解説記事をたくさん読んで,何かヒントがないか探します
      • それでもピンとこなければ,とりあえず復習リストに入れて未来の自分に丸投げします
    • 効率性を意識する
      • 過去問が自力で解けた場合でも,解説は必ずチェックして無駄がなかったか確認します
      • もし無駄があったり想定解でなかったりした場合はなるべく解き直します
      • 他の人の実装をいくつか眺めて,盗めるものがあれば盗みます *10
  • AtCoder Problems

    • いつもお世話になっております
    • スポンサーになっていません,ごめんなさい
    • Virtual Contests
      • まとまった時間があるとき,気分転換したいときなどにオススメです
      • 自分の場合は早解きに自信があるので,コンテスト形式の練習は基本やらないです
    • Boot camp for Beginners
      • 全部埋めました
      • AGC-A などの diff 詐欺には注意が必要です *11
    • Recommendation (Moderate)
      • Boot camp を埋めてからはよく利用しています
  • AOJ

    • 螺旋本と合わせて勉強に使っています
    • いろいろなコースがあるので,気が向いたときにちまちま埋めています
  • 螺旋本

    • AtCoder を始めた当初に購入しました
    • AOJ と連携して学習でき,難しすぎることもないため,かなりオススメです
    • 通読はせずに興味のある章をつまみ食いしています(少し反省)
  • 蟻本

    • 緑コーダーになってから購入しましたが,全体的に難しいです
    • POJ が古いため,この記事などを参考に過去問を解いて練習します
    • 多くの競プロ er が蟻本で勉強しているので,遅れを取らないよう少しずつ読んでいます
  • ABC (AtCoder Beginner Contest)

    • 毎回参加することを徹底しており,ABC158 から1回も欠かさず参加し続けています
    • 解説放送
      • 自分はコンテスト後は相当疲れているので,解説放送を見ないで寝ます
      • 翌日以降に 1.25 倍速で見るのがオススメです
      • snuke さんが親切に色々教えてくれる絶好の機会なので,頑張って吸収します
      • C++ に移行してからは実装の時間にも注目するようになりました *12
  • 過去問精選 100 問

    • この記事のことです
    • ちゃんと100問解こうと思って最近取り組んでいます
    • ここに自作のチェックリストを置いているので,よろしければお使いください
  • 興味はあるが手を出していないこと

    • Codeforces, yukicoder
    • あさかつ・よるかつ
    • コンテスト前に「ぞい」とつぶやく

モチベーション維持

コンテストで大きく失敗したときだけだったと思いますが,競プロを辞めようと思ったことが過去に3回くらいありました.そのときに辞めずに続けられたのはなぜか,そもそも半年間ずっと続けられたのはなぜか,振り返ってみると自分の場合は下記が重要であると気が付きました.一応,重要度の高い順に書いています.

  • AtCoder 水色になりたいという強い気持ち
    • 結局これなのかなという気がします
    • 競プロを始めたときから,目標は茶色でも緑色でもなく「水色になること」でした
    • 「水色になれたらいいな」ではなく「水色になる」という気概で取り組んできました
  • Rated コンテストに毎回参加する
    • 一見矛盾しているようですが,今までの積み重ねが諦めない気持ちを支えてくれます
    • 「実力評価を受ける機会を定期的に設ける」ことは競プロに限らず勝負の世界では重要です
  • 仕事で残業しない
    • 割と重要だと思っているのですが,自分でコントロールすることは難しいです
  • 競争相手を見つける
    • 気になる人を見つけては AtCoder アカウントのお気に入り登録をしてます *13
    • 順位表を見て「この人に追いつきたい」「この人に負けたくない」と日々思ってます
  • 適切な睡眠を取る
    • 睡眠不足のとき,ちょっとしたことで心が揺れ動きやすいので,冷静さがやや失われます
    • 日々のパフォーマンスは精進の質ひいてはコンテスト結果に繋がるので気をつけたいものです

取り組み紹介

テンプレート・ライブラリ作成(Python

最初の頃は真っ白な状態から実装していましたが,入出力は何度も書いているうちに覚えてしまったので,割と初期の段階でテンプレートを作って効率化するようになりました.

Python のテンプレートは下記を使っていました.必要な入出力だけ残してあとはすべて消すという使い方です.

import sys

input = sys.stdin.readline


def main():
    N = int(input())
    S = input().rstrip()
    N, M = map(int, input().split())
    A = list(map(int, input().split()))



    print(" ".join(map(str, ans)))
    print(ans)


if __name__ == "__main__":
    main()

ライブラリについても精進の過程で少しずつ整備していきました. 他人のライブラリのコピペはせず,すべて自分で書いたものを使いたいと思っていたので, コツコツと整備していきました.ここはゲームで言えばやりこみ要素だと思います.

github.com

自作のめぐる式二分探索 Numba 実装は汎用的でオススメなのでよろしければ是非お使いください.ちなみに Numba 実装にしている理由は,めぐる式二分探索は関数呼び出しの都合上,Python でそのまま書くとかなり遅くなってしまうからです.

AtCoder 向け User Script の利用

界隈には ac-predictor などよく知られた User Script がたくさんあります.コンテスト中の立ち回りや日々の精進などで非常に活躍します.特にお世話になっているものを挙げたいと思います.順番は適当です.

  • AtCoderPerformanceColorizer
  • AtCoder Submission User Colorizer
  • AtCoderStandingsAnalysis
  • AtCoder Submission Status
  • AutoSubmissionsSettings.js
  • AtCoderResultNotifier
  • ac-predictor
  • AtCoder TestCase Extension

Python + Numba という選択

言語アップデートによって Python では Numba が使えるようになり,JIT で割と気軽に高速化できるようになりました.これは大変ありがたかったです.しかし,Numba は発展途上でできることは限られており,ある程度の勉強も必要です.「PyPy に頼らずに Python 一本でいくんだ」という強い気持ちがある方以外は PyPy を覚えるか C++ などの高速な言語への移行をオススメします.

自分は結構 Python固執愛着があったので Numba で対応する方向で頑張っていました.この記事や Numba リファレンスを繰り返し読んで使い方を身に着けていきました *14 .AOT には手を出していないです. *15

Numba に関する注意点はここに少しまとめているので,よろしければ参考にしてください(ほとんど悪口しか書いていませんが…).

ここからは Numba の話になりますが,個人的に嫌気が差していたのは,隣接リストがスマートに利用できずダイクストラ法の Numba 実装が上手くまとまらなかったことです.AtCoder で使えるバージョンの Numba では TypedList が実験的に導入されている一方で,普段 Python で使っている listreflected list として扱われ,reflected list のネスト(隣接リストなど)を関数に渡すと怒られます(関数内部では構成できる仕様です).かといって,Typed List のネストは配列アクセスが遅いらしく[要出典*16] ,割と詰んでいます.試行錯誤の末に,関数の外側で辺の情報を numpy.ndarray 形式で準備して関数に渡し,内部で隣接リストを作成するという苦肉の策を思いついて「何やってんだろうな」と思いながらも FIX としました.一応ここに成果物がありますが,こんなことをするなら PyPy を使ったほうが楽そうです.

この話題は下記記事に詳細があるので,詳しく知りたい方はそちらを参考にしてください.

ikatakos.com

online-judge-tools + atcoder-cli 導入

効率に拘るところがありながら「専用ツールに頼らず実力でレートを上げたい」という中途半端な美学によって導入を渋っていました.しかし,目の前にチャンスがぶら下がれば入念に準備したくなるのが人間というもの.自分のレートが 1195 で水色目前だったとき,ダメ押しのつもりで *17 導入しました.

導入後のコンテストは計4回(ABC176〜ABC179),結果を見る限り有意な変化は確認できませんが,テスト自動化の恩恵が大きく体感的にはトータルで5分くらい速くなっている気がします(パフォーマンス換算すると10〜20くらい?).自作テストケース追加が簡単なところも嬉しいです.submit は自分でコピペ提出した方が圧倒的に早いので使っていないです.

明らかにアドバンテージがあるので,特に理由がなければ導入することをオススメします.速度向上だけでなく,体力温存,ヒューマンエラー防止 *18 などの恩恵もありますし,日々の精進の効率も若干上がります.

Python から C++

8月22日,ABC176 の直後に Python を捨てて C++ を始めました.約1ヶ月前のことです.

レート 1195 で水色目前というときに D 問題「Wizard in Maze」で TLE に苦しみ,自分の実力不足も当然ありましたが Python (PyPy) の不利さも明確に感じました.かなりショックだったのでコンテスト後に今後について色々考えました.使用言語というのは,いわば競プロの問題と闘うためのパートナーのようなものだと思っていて,ポケモンで言えば最初に選んだ一匹みたいなものだと思っています.葛藤がありましたが,「水色になる」という目標を最優先するため,Python を捨てて C++ でやっていくことを決心しました.言い訳できないようにしたかったという思いもあります.

しばらくはレートが下がる可能性が高そうだったので怖かったですが,一心不乱に C++ を身に着けていきました.環境構築から始まり,APG4b やライブラリ整備などをやりつつ簡単な過去問を大量に解いて一気に慣らしていきました.ここは我ながらよく頑張ったと思います.

テンプレート・ライブラリ作成(C++

C++ のテンプレートは現在下記を使っています.なるべく Python と同じような感覚で使えるように,という思いを持って日々メンテしていたら,いつのまにか30行近くになっていました.入力のところで,変数宣言と cin を一行で書くのがお気に入りの書き方です.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// --------------------------------------------------------
#define FOR(i,l,r) for (int i = (l); i < (r); ++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define MIN(c) *min_element(ALL(c))
#define MAX(c) *max_element(ALL(c))
#define SUM(c) accumulate(ALL(c), 0)
#define SUMLL(c) accumulate(ALL(c), 0LL)
#define SZ(c) ((int)(c).size())
#define debug(x) cerr << #x << " = " << (x) << '\n';
using P = pair<int,int>;
using VP = vector<P>;
using VVP = vector<VP>;
using VS = vector<string>;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
using VVD = vector<VD>;
static const double EPS = 1e-10;
static const double PI  = acos(-1.0);
static const ll MOD = 1000000007;
// static const ll MOD = 998244353;
static const int INF = 1 << 30;
// static const ll INF = 1LL << 62;
// --------------------------------------------------------


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);

    int N; cin >> N;
    int N, M; cin >> N >> M;
    string S; cin >> S;
    VI A(N); REP(i,N) cin >> A[i];

    int ans = 0;
    cout << ans << '\n';

    return 0;
}

ライブラリは Python で作ったものを移植して作っていきました.あと最近に modint を理解しながら実装しました.今後も ACL は使用せず自分で実装したコードを使っていきたいと考えています.

github.com

今後について

「2021年3月までに青色になる」を目標に引き続き精進します.まずは水パフォ以上を安定させたいです.

*1:情報系の講義はほとんど受けていませんでした

*2:社会人1年目は無をしていました

*3:整数問題が苦手なのでトータルで少し有利,くらいの自己評価です

*4:本番は1ミスでした

*5:二次試験で大問丸々落としました…

*6:このレベルなら結構役に立ってると思います

*7:関係ないかもしれませんが…

*8:結果的にこの判断は正しく,競プロで培った高速化ノウハウが業務で役立ちました

*9:なぜ弊社に橙がいるのでしょう…笑

*10:Python では定数倍高速化のためによくやっていましたが,C++ ではほぼやっていないです

*11:激ムズの灰 diff とかあります

*12:最近は Python で解説されることもありますね

*13:現在,62アカウントをお気に入り登録しています.アクティブユーザは10〜20人くらいです.

*14:Numba は業務でも役に立ったので良かったです

*15:そこまでするなら PyPy で書いたほうがスマートかなと思っていました

*16:Numba GitHub Issues のどこかに書いてあったと思います

*17:残念ながら結果は奮いませんでしたが…

*18:過去にサンプルの出力を見間違えて WA を食らった経験があります…