AtCoder 青色になりました

AtCoder Regular Contest 112」で青コーダーになりました.

f:id:mts1104:20210214105937p:plain

本記事はいわゆる色変記事です.あまり自慢にならないようになるべく客観的に書いたつもりです. 半分くらいは自分のために書いていますが,本記事が誰かの役に立てば幸いです.

水色達成時の記事に自己紹介を載せているので興味ある方はどうぞ.

精進

精進量

精進量はかなり多い方だと思います.下埋め優先なのでAC数が多いです.精進グラフは既に橙色です.

f:id:mts1104:20210214112229p:plain f:id:mts1104:20210214112232p:plain f:id:mts1104:20210214112238p:plain f:id:mts1104:20210214112235p:plain f:id:mts1104:20210214143453p:plain f:id:mts1104:20210214112257p:plain f:id:mts1104:20210214112254p:plain f:id:mts1104:20210214112252p:plain:h200

実力向上を実感した精進

水色〜青色の期間も過去問をひたすら解く方法で精進していましたが,その中でも実力向上を実感した精進を紹介します.個人差があると思いますので参考までに.

  • 過去問精選 100 問

    • 特に DP と累積和の問題セットが豊富で実力が付いたと思います.あくまで自分の印象ですが AtCoder でこのレベルの DP の問題はやや少ないと思うので,AOJ & JOI など他所の問題を利用して特定分野を補強することは重要だと思います.しかし,これだけでは青色コーダーを目指すレベルとしては不十分で,後述する EDPC・JOI などで更に補う必要があると思います
    • 記事中に「100 問全部解けたら、水色コーダーどころか青色コーダーくらいの実力が付くと思います」とありますが,これは約1年前に書かれた記述なので注意が必要です.今の界隈レベルではこれで青色コーダーというのは明らかに実力不足だと思いますが,水色コーダー相当の実力が養われることは間違いないと思います *1 *2
    • ここに自作のチェックリストを置いているので,よろしければお使いください
  • 令和ABC

    • 青色コーダーになるために「ABC 5完」は明らかに必要条件なので,特に ABC-E の過去問を解いて精進することはごく自然な発想だと思います.それだけでなく,ABC は典型問題がバランスよく出題されているので学習効果・網羅性ともに高く,やらない理由がないです
    • 年末にはこんなバチャを立てて ABC-E を総復習しました.確実に効果があったと思います *3
  • EDPC

    • なるべく早く埋めた方が良いです *4
    • 基本的に初見殺しなので解説 AC して1問ずつしっかり勉強する,という取り組み方で良いと思います.自分は現時点で W まで埋めています
    • 推定難易度についてはこのツイートが参考になります
    • EDPC に加えて TDPC も存在します(こちらはやや難しめ)
  • あさかつ・くじかつ

    • 早解き・復習・実装効率化・ライブラリ整理などを目的として参加していました
    • あさかつは制限時間が60分に削られてるので良い訓練になりました
    • 問題を解くことと同様に早解きにも「(1) 考察パート速度」「(2) 実装パート速度」があると思っていて,さらに後者には「(2-1) 考察結果を実装に落とし込む速度」「(2-2) タイピング速度 (+ライブラリ充実度)」「(2-3) デバッグ速度」があると思っています *5.このような区別を付けて自身の課題を明確に認識した上で参加すると効果が高くなるのではないかと思います *6
  • AOJ Courses Library

    • ライブラリ作成の機会になるような典型問題がたくさん用意されています
    • DSLGPL・DPL がオススメです.DSL ではセグ木・遅延セグ木の問題セットがあります
  • JOI

    • ABC-E 相当の問題数確保・DP 練習などを目的として取り組んでいました
    • 具体的には難易度 5〜7 あたりを埋めていました.ここにも言及があります
    • ABC-F 相当の練習として 7〜9 も埋めていく予定です
  • 蟻本

    • 蟻本の良さは散々語り尽されていますが,1点挙げるとすれば網羅性の高さだと思っています
    • 教養としてじっくり読むような感じで,気が向いた時に読み返していました
    • 誤植が結構あるので注意が必要です.ある意味で読解力も鍛えられます *7
    • 4-3・4-5・4-7・GCJ の節以外は一通り読んだと思います *8
  • 螺旋本

    • 蟻本より簡単で誤植も少ないので気軽に読めます
    • 本書を読みながら幾何ライブラリを整備していますが,AtCoder で幾何が滅多に出ないことは周知の事実であり,残念ながら本番で役立ったことは現時点で一度もないです *9

メンタルについて

精進について長々と前述しましたが,結局メンタルが一番重要だと自分は思っています.別記事に書く予定です.
(2021/2/17 22:50 追記)
競プロのメンタルについて記事を書きました.

mts1104.hatenablog.com

小ネタ

  • 緑時代に Python ---> C++ に乗り換えてから,月1回くらいは int 型のオーバーフローで痛い目に遭うようになりました.嫌な気持ちになるので,自分のテンプレート・ライブラリのほとんどの int 型を一掃して long long 型に変更しました.これによって「制約を確認して int 型か long long 型か決める」という作業も必要なくなりました *10

今後について

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

*1:もちろん,多くの問題を答えを見ずに解ける状態になったらの話です

*2:しれっと青diffと黄diffも入っているので全問制覇するのは大変です

*3:青diff以上の問題は解説ACが多かったので,何回か解き直さないと身に付かなかったです

*4:自分は ABC183-E・ABC184-D・ABC185-E・ABC187-E と立て続けに DP を落としたため,必要に迫られて EDPC を埋め始めました

*5:厳密には独立ではないです.例えば (2-1) が上手いと (2-2) の作業量自体が少なくなります

*6:自分は (2-2) > (2-3) >>> (1) > (2-1) という感じなので,あさかつ・くじかつ参加が (1) (2-1) の底上げに繋がったと実感しています

*7:自分の蟻本は赤字の書き込みで一杯です

*8:身に付いたとは言っていない

*9:ABC191-D は幾何というより誤差対処の問題だと思っています.許容誤差もないですし…

*10:AtCoder はメモリ制限が 1024 MB もありますし,int 型でないと TLE するケースにも遭遇したことはないです

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 を食らった経験があります…