35歳で競プロを始めて橙になるまでにやったこと

 

35歳から Python で競プロを始めて2年が経ちましたが、やっと AtCoder で橙になることができました！

 

f:id:Kiri8128:20201101002719p:plain

 

ふぁぼ、コメントもたくさん頂きありがとうございました。

 

RTA 途中経過

最初のRatedから青まで：3か月（Rated 7回）
青から黄色まで：7か月（Rated 17回）
黄色から橙まで：1年3か月（Rated 24回）

－－－－－

 

橙はだいぶ遠い存在という印象だったので、達成できて嬉しいです。

まだまだ上を目指していきたいと思いますが、ひとまずの区切りとしてこれまでにやったことなどを書いておきます。

 

 

スペック

  • 某京都大学というところで9年ほど *1 数学（代数学・代数幾何学）などをやっていた *2
  • 現在の昼間の仕事はアクチュアリー *3 。いわゆる業務プログラマーではない
  • 35歳で競プロを知って、そこから始めた
  • 結婚は何度か。子供は1人（子供の年齢 ≒ 競プロ歴）
  • 競プロを始める前のプログラム経験は、趣味で自分用のウェブサイトっぽいものを作ったりしてたのと、練習で高速素因数分解のアプリを作ってたぐらい *4 。業務では Excel の VBA を使ってたぐらい
  • 競プロで使っている言語は Python / PyPy （Python も競プロを始めるのとほぼ同時期に始めました）
  • 初等数学・パズル系は昔から割と好き *5
  • 大学時代は、塾講師・家庭教師のバイトをしてた *6

 

競プロer の中では、年齢高め・子持ち・Python ユーザー、あたりが特徴でしょうか *7。

 

 

やったこと

 

青になるまでにやったこと
  • 過去問
  • Python の文法の勉強 *8
  • 蟻本の前半ぐらいを流し読み（全部は読めてない）
  • BFS、DFS などの比較的簡単なアルゴリズムの勉強
  • ダイクストラなどグラフ関係は、知ってるけど使いこなせていないぐらい

この頃はすべてが新しいことばかりだったので、覚えるのが楽しかったですね。データ構造、アルゴリズム、問題の発想の仕方、解き方の典型、計算量の考え方など、吸収できるものはなるべく取り入れるようにしました。

 

黄色になるまでにやったこと
  • 過去問
  • アルゴリズム・データ構造の勉強（蟻本を読んだり、コンテストで出てきたものを復習したり）
  • 簡単なセグ木ぐらいまでは使えるようになってた
  • フローなどは知ってるけど実践では使えない

青ぐらいからはレートが上がりにくくなってきます。特に私の場合は、学習に偏りがあったせいか、パフォ変動が激しく失敗回で大きくレートを落とすことが多かったです。解けなかった問題で使われている考え方を復習するなどして、少しずつできる範囲を広げていきました。

 

橙になるまでにやったこと
  • ABC 埋め（これは黄色になった少し後に短期集中でやりました）
  • 適正難易度の埋め（まだ途中）
  • 他人の Submission との比較。特に同言語内で実行時間に差がある場合などに、自分のコードのどこが悪いかを特定する
  • 文字列関係のデータ構造
  • セグ木の抽象化、遅延セグ木、全方位木DPなど
  • Grundy 数（黄色後半になるまで知らなかった）
  • ACL （だいたい知ってたけど、 SCC とか CRT などはこのとき整備した）

 

黄色からは圧倒的に Rated コンテストが減りました。ある意味家庭とのバランスを取りやすくなったのは良かったですが、精進のモチベーションを保つのは難しいですね。

興味のあることや目標があると楽しく続けられるので、「〇〇を埋める」とか「〇〇（データ構造など）を履修する」とかの目標を見つけると精進が捗った気がします。 Twitter で議論されていることも、面白いアイデアなどはなるべく試すようにしていました。

 

 

オンサイト経験

 下記に参加しました。どちらもとても楽しかったです。

  • 第一回全国統一プログラミング王決定戦（日経コン）
  • DDCC2020

 

日経コンはエキジビションが楽しかった記憶があります。 DDCC2020 は時間が長かったのもあり、たくさんの方とお話しできました。

ところで、DDCC2019 も実は通過していたみたいですが、初心者すぎてメールに気付いてませんでした。

 

作問関係

黄色になってからは yukicoder で作問・テスターを何度かしました。

このあたりです。（まだやってない人はぜひやってみてください！）

 

作問は、解くのとはまた別の楽しさや難しさがありますね。一時期はとてもハマっていました。私の場合は Rated が少ない時期にやっていたので、良い気分転換にもなりました。ただ自分の Rating を上げることだけを考えると、普通に精進するのが効率が良い気はしますね。

 

作問・テスターをやるメリット
  • 出題した問題の考え方がその後のコンテストで出題されたのを多数見ています *9。似た問題が出題されたときは有利になるのは間違いないと思います。（これは運要素もありますが。）
  • 出題するときは、証明などもちゃんとする必要があります（それはそう）。普段のコンテストだと AC が出れば OK というスタンスになりがちなので、しっかり考える訓練にはなりました。
  • 愚直解とのチェックなどの仕組みも練習できます *10 。
  • 誤解のない問題文にする、正しくジャッジできるジャッジコードやテストケースを作る、なども楽しい作業でした。
  • テスターも勉強になりますね。普通の精進だとサボってしまうこともありますが、テスターを引き受けたら後には引けないので、少なくとも担当した問題については考察が捗るというのもあります。
  • 作問者とテスターで相談・議論することもあるので、他の人がどういう考え方をするのか、どういうスタンスで問題に取り組んでいるのかなどが分かったのも勉強になりました。 
  • 問題の作り方やジャッジの仕方がなんとなく分かるので、自分が参加するコンテストでも作問者の気持ちになって考えることでヒントが得られるかもしれません（たぶん）。

 

作問のコツ・気を付けた点
  • いくつか気を付けた点はありますが、一番は解く人が楽しめる面白い問題を作りたいという気持ちがありました。
  • なので問題として成立していても、面白いと思わなければ修正を考えたりボツにすることも多いです。*11
  • 実装の負荷だけの部分は省略したりとか、定数倍でなんとかなるようなものはなるべく排除したりとか、あとは問題文を理解しやすくする（別の解釈ができないようにする）というのも当たり前ですが注意していました。
  • 作問の方法は、解法から考える方法と、問題設定から考える方法があると思っています。
  • 問題設定から考える方が面白い問題になりやすい気がしています（最初に面白いと思える問題設定を考えれば良いので）。ただこの方法だと解けなくて出題できない可能性も高いです。いろんなパターンを試してみたり、逆に解ける条件から逆算する手もあると思います。

 

精進関係

レートを上げるのに一番大事なのは日々の精進だと思います。新しい知識や考え方を習得することで、将来のパフォーマンスの期待値を上げます。特に意識したのはこのあたりです。

 

1. 復習

コンテスト中にチャレンジしたけど解けなかった問題をちゃんと復習するのがとても大事です。これをやると伸びが速くなった気がします。

復習をするときは、次回似たような問題が出題されたときに、どうやったら思いつけるかを考えながらやると良いと思います。全く同じ問題が出ることはないですが、なるべく広い範囲の問題で応用できると嬉しいです。思いつくための「トリガー」をたくさん張り巡らせておくイメージでしょうか。

 

2. ABC 埋め

数をこなすのもやっぱり大事。特に適正レベルの問題や典型をたくさんやると実力は上がると思います。全然できてないですが。

ABC 埋めた宣言してからは、 ABC があるたびに全部通さないといけなくなりましたがそこはなんとか守っています。開催から概ね1週間以内ならセーフということにしてます。

 

ABC 埋めは虚無も多いのですが、いろんなパターンを履修できるので、「知らなくて解けなかった」みたいなのが減る気がします。そのせいか、この後は大きな失敗回が減った気がします。

 

 

3. 適正レベル埋め

適正レベル埋めをまじめにやったのは、実はいいねの数だけ・・・をやったときぐらいかもしれません。このときは毎日の日課になっていたので集中して取り組めました。モチベーションのキープにもとても良かったです。

 

 

ABC 埋めなど、簡単目のところを埋めるのは失敗回を減らす効果がありますが、適正レベル（あるいは挑戦レベル）の埋めは大成功回を増やす効果があると思います。

  

4. ライブラリ整備

解けなかった問題や、初めて見た方法などがあれば、次に見たときにすぐに使えるようにライブラリを整備します。その際、他の人のコードをコピペするのではなく、（参考にはすることもありますが）自分で一から書くようにしていました。これによって使い方をより知れたり、自分が使いやすいようにカスタマイズできます。

今持っているライブラリは後述します。

 

コンテスト中の立ち回り

問題を解く順番など

以前は愚直に前から解いていたのですが、強い人が並列で考えているという例をいくつか聞いたので、最近は詰まったら並列っぽく考えるようにしています。以前は並列でやるとそのうち1問を解いたときに時間的に不利になる気がしていたのですが、案外ずっと同じ問題を考えるよりいろんな問題を行き来した方がアイデアが浮かぶことも多いので、効率も悪くないと思ってます。だいたいこんな感じ。

  • 基本は前から見て、簡単そうならすぐに解きます
  • 詰まったら一度順位表を見て落ち着きます
  • 超高難度以外の問題を眺めて、すぐに解けそうなものがあればそれを解きます
  • すぐに解けそうなものがなければ並列で（数分ごとに行ったり来たりしながら）考えて、解けそうになったものから集中的に考察して実装します
  • ちなみに、ある程度「これでいける！」ってなったら、細部を詰めてなくてもコードを書き始めます。詳細は print デバッグしながら詰めることが多いです。（と言いつつ、この方法はあまり良くないと思っています。）
  • あと No Sub 撤退はしないようにしています。そのためにも、いろんな作戦を考える前にまずは 1 Sub をします。 1 Sub すると集中力も上がる気がします。短期的には No Sub 戦略が期待値的には高いことも多いかもしれないですが、それで期待値が上がる人は伸びしろがない人（停滞状態の人）だと思っています。伸びしろが十分にあれば少しでも参加する方が上がりやすいので。
 
メモ

コンテスト中のメモは、ノートに手書きで書いています。

考察は絵や図が多いです。具体例の計算もノートに書くことが多いです。

途中で得たひらめきや考え方は、メモとして文字でも残します。場合分けやコーナーケースに気付いたら、その段階で分岐をノートにメモします。 *12

 

順位表

主に下記の目的で順位表を活用しています。

  • 問題で詰まったときに落ち着くために見る
  • 難易度判断のために正解者数を見る
  • 問題文がおかしい気がするときなど、本当に解けるの？という意味で全体の正解者の人数を見てみる
  • Python だときつくない？と思ったときに、 Python ユーザーの AC / ペナ状況を見る
  • 例えば C まで解けたときに、 D を解いた場合の順位と E を解いた場合の順位を比べて、期待パフォをなんとなく予測する
  • フレンド内で高難度を通している人がいた場合などに、この人がこの時間で解いてるなら自分も解けるかも、みたいな判断の参考にする
  • 知り合いや TL のみんなが頑張っているのを見て励みにする

 

ただし、少なくとも1問を解いてから（普通は前から解いていって詰まってから）順位表を見るようにしています。

ところで、コンテスト中にも順位表にパフォ・レートなどの予測をしてくれるユーザースクリプトがあると聞いたことがありますが、私は使っていません。たぶん気になって集中できなくなってしまいそうなので。

 

精神面のコントロール

頭を使うゲームなので、自分の精神面のコントロールも大事だと思っています。

 

冷静になること

問題が解けなくて慌ててしまったり、関係ない考察に時間を取られてしまったり、問題選択を極端にミスってしまったり、などは減らしたいです。緊張感を保ちながら、かつハマり過ぎたりしないように柔軟に立ち回るのが大事だと思います。 

 

瞑想・おまじない

コンテスト前に、集中力を高めるために瞑想をします。瞑想と言っても高度なことをする訳ではなく、軽く目を閉じて深呼吸するぐらいです。やりすぎて遅刻するとまずいので、呼吸の回数を数えています。私の場合15秒ぐらいで1回深呼吸できるので、1分前から始めると2～3回深呼吸すれば良いです。

あとこれは単におまじないみたいなものですが、コンテスト直前に目薬を差すことが多いです。緊張して目が乾くのを抑えるというのもありますが、コンテスト前に必ずやることを決めておくと、それがトリガーになって集中力を上げることができるかもしれません。

 

自分の実力を信じること

コンテスト中、挑戦する問題は「絶対解ける！」と信じて挑戦します。

 

ちなみにコンテスト時の飲食等は、お茶のみです。

栄養ドリンクを飲んだり、チョコレートを食べたりする人もいるようですが、いつもと同じ状態で臨むのが私には合ってる気がします。コンテスト中はとても集中した状態になるので、特別なアイテムがなくても集中が切れることはほとんどありません。

 

 

 

FAQ

Q: 競プロを始めたきっかけは？

A: 社内でやってる人が宣伝していて、聞いてみると面白そうだったので始めてみました。

 

Q: コーディング環境は？

A: Jupyter Notebook をブラウザで開いて使ってます。動作テストは簡単なのは手元でやりますが、入力が増えると paiza.io でテストしたりしています。処理時間が長くなりそうなのは PyPy が使える AtCoder のコードテストを使います。

 

Q: スニペットは何登録してる？

A: え、使ってないです。何それおいしいの？

 

Q: Python で参加するのはこだわりがあるの？今後も使い続ける予定？

A: 最初やったのがたまたま Python だったのでそのまま惰性で使っているというのが正直なところです。でもまあ使っていると愛着も湧いてくるので、すぐに変えようとは今のところ思っていません。文法も直感的できれいに書けるので、競プロに限らず書きやすい言語だと思っています。

私が始めたときは Python で上位の人が少なくて、参考にできるコードも少なくて困ったのですが、今は Python 使いの上位層も増えてきていますし、逆に他の Python ユーザーの方に少しでも参考になるコードを書いたり情報を発信できればと思っています。

実行速度が遅いと言われることもありますが、 AtCoder に限って言えば、 Python と PyPy を使えば私が解けるレベルで困ることはほぼないです *13。

 

Q: Numpy、 Cython などは使わないの？

A: 今のところ予定はないです。 PyPy で十分に対応できると思っています。

 

Q: 子供がいると精進つらくない？

A: 家庭があると調整が必要なのはそれはそうです。今のところコンテスト等に理解を示してくれているのでそこはありがたいです。精進は深夜にやることが多いので直接はあまりかぶらないですが、土日の夜のコンテストはややつらいこともあります。ただ子供・家庭に限らず、学生も社会人もみんな生活の中でやりくりして参加していると思うので、できる範囲でやるしかないのかなと思います。時間のやりくりという点では、自分の中ではこどふぉの優先順位はやや下げて、家庭や他の用事があればそっちを優先することにしています *14 。

 

Q: 仕事との両立はどうしてる？？

A: 上と似てますが、社会人なので業務時間中は仕事をせざるを得ないです。家庭と違うのは、こちらの努力でどうしようもないことも多いので、ある意味諦めがつきます。

 

生活を除いて、使える時間の中で頑張るというのは同じだと思います。

ひとつ救いなのは、社内にも競プロをやっている仲間がたくさんいるのはモチベーションの維持にもつながってありがたいです *15 。

社内にどれぐらいいるかとか、会社の特定をしたい人はこのあたりを見ると分かるかもしれないです。

 

両立という意味では、仕事（と家庭）が終わったら、夜遅くてもなるべく精進を少しはやるようにはしています。

どうしても仕事が忙しくてきつい時期は、精進を数日お休みすることもありますが、その点では自分を責めないようにしています。自分のペースで、できるときにやるのが良いと思います。

 

 

Q: 年齢的に精進厳しくない？もっと早くから競プロをやっていたと思う？

A: たしかにもっと早く始めてればもっと成長できたのかもというのは思わなくはないです。でも知らなかった *16 からしょうがないです。私の場合、20代前半、20代後半、30代前半、30代後半と、それぞれ趣味・生活・職場・家族など全く違うものになってきていますが、どの時期もわりと楽しんでいます。少なくとも30代後半期は競プロが大きな楽しみのひとつになっているのは間違いなくて、それだけでとても満足です。

年齢の有利不利で言うと、私の場合、年を取って明らかに衰えたのは、紙の上での計算力です *17 。ただその他の部分では大きく不利になっていることはないと思っています。逆に有利な点としては、初等代数学などは一通り学んだあとに始められたのでその部分では詰まりにくかったというのは少しあるかもしれません *18。

競プロの成績はコンテストの結果がすべてなので、年齢関係なく平等に楽しめるゲームとも言えると思います。その意味ではむしろ高年齢帯でも参入しやすいのかもしれません。若い方に負けないように頑張りたいと思います。

 

Q: 今後の精進の予定は？

A: 正直、簡単にできることはある程度やってしまった感があり、ここからさらにレートを伸ばすのはこれまでより格段に難しくなると思っています。ただここで満足してしまったら成長は見込めないので、自分に足りていないところを強化していきたいと思います。例えば

  • 埋め（特に橙 Diff 前後が全然埋まってない）
  • 考え方の整理（いつもノリや感覚で解いてるので、体系的に考えられるようになりたい）
  • 正確性（立式や証明をせず、なんとなくコードを書き始めてしまうので、添え字なども含めてちゃんと理解してから書き始めると精度が上がるのかなとかは思っています）
  • 高難度のアルゴリズムの履修（直近で困ったのだと、高速ゼータ変換・メビウス変換や 3^n DP など。あと指数型母関数というのも最近知りましたが、今後履修予定です）
  • 考察・実装のスピードアップ（今の実力だと、スムーズに解けてももう1問解くのは時間的にきついことが多い）

あたりはまだ全然できていないので、少しずつやっていきたいと思っています。

 

 

 

おまけ－ライブラリ

普段使っているライブラリのリストです。▲は黄色になってから整備したもの。■は使ったことがない、または出ても使える気がしないやつ。

 

ライブラリは他人のコピペはあまりしたくないので、参考にすることはあっても、なるべく自分で書くようにしています。

 

 

（一般）
  • 階乗の前計算
  • 行列累乗
  • 小数 → 分数
  • Mod P → 分数
  • Permutation ↔ ID
  • ▲ 自作乱数
  • ▲ popcount, popcount_parity *19
  • ▲ 多倍長整数の平方根、 N 乗根
  • ▲ 01 Vector Space
  • ▲ 可変長ループ *20
  • ▲ スライド最小値
  • ▲ CRT *21
  • ■ 最長回文半径
  • ■ Tonelli_Shanks
  • ■ Li Chao Tree （簡単なやつ）

 

（素数関係）

 

素因数分解はポラード・ローで乱択 O(N1/4) のやつ *23。素数判定はミラー・ラビン。素数列挙はエラトステネス。

 

（畳み込み関係）

 

（文字列関係）
  • Z Algorithm
  • KMP
  • SA-IS

ロリハはライブラリになってないので、毎回手で書いてる。

 

（グラフ関係）
  • BFS
  • Union Find
  • ■ 部分永続 Union Find
  • 木のトポロジカルソート
  • ▲ 最小全域木
  • 木の最遠点・重心
  • ■ 2部グラフ判定
  • Dijkstra
  • ■ ワーシャル・フロイド
  • ■ ベルマン・フォード
  • LCA（ダブリング、Tarjan）
  • Euler Tour
  • ▲ 全方位木DP *26
  • ▲ SCC
  • ■ 区間に辺を貼る一般的なテク
  • ■ HL分解 *27

 

木の問題は基本的にトポソして解く *28。木以外のライブラリはいまいちで、DAGのトポソすらない（ライブラリ整備したときには木しか考えてなかったので）。

 

（セグ木関係）
  • BIT
  • セグ木
  • ▲ 遅延セグ木
  • ▲ 双対セグ木
  • ■ Beats *29

 

セグ木関係は、最初は用途（「1点更新区間 max 取得」とか）毎に作っていたけど、最近は抽象化したやつを使い回してることが多い。

あと最近は Monoid Check 機能とかも入れてる *30。

 

（ゲーム関係）

 

（フロー関係）
  • Max Flow
  • ■ Min Cost Flow

 

Min Cost Flow はちゃんとできてないので Python の Networkx を使うことが多い。

 

（平衡二分木もどき）
  • 例の平衡二分木もどき *32

バグがあると指摘されてからまだ修正できてない気がする。

赤黒木はずいぶん前にやろうとしたけど作りかけで止まってる。

 

（その他）

 

 

 

*1:特に意味はないですが、 7+2=9 という式を書いておきます

*2:できるとは言ってない

*3:現在は決算関係の部門で、8人ぐらいのチームのマネージャーをしてます

*4:ポラード・ローを使うやつです。アンドロイド限定だけど、「素数電卓」で検索してね

*5:数オリ勢ほどではないです。数オリは存在もよく知らずでした

*6:なので高校数学の最盛期は、大学に入ってからだと思います

*7:年齢で言うと、この記事の執筆時点で AtCoder に登録されている中では橙以上で国内最年長みたいです。年上だと偉いとかいう訳では全くないので、みなさん気軽に仲良くしてください

*8:Python の文法は、主に他人の Submission を見ながら少しずつ覚えた感じです。体系立てて勉強はしていないので、感覚でやっているところも多いです。

*9:一番見たのは Typical Game Contest のB（とF）の考え方。木の上の山の後半の考え方も何度かありました。

*10: Rated コンテストでも使えると良いのですが、今はあまりうまく使えていないと思います

*11:「面白い」の基準は割と主観だったりしますが

*12:こんな感じで if 文の分岐をメモしておくようにしてから、コーナーケースでミスることが減った気がします

*13:赤になろうとするとどうかはまだ分かりませんが、おそらくこれがボトルネックになることはないと思っています

*14:今後は ABC は少し優先度が下がるかもです

*15:Unrated の ABC に出続けるのも、社内で出ている人が多いからというのも大きいです

*16:というか私が学生のときは競プロ自体そもそもなかった？

*17:これは大学入試、それから入学後に家庭教師・塾講師をしていたときが最盛期でした。その後何年も触っていないと正確さ、スピードともに大きく下がっていました。これも長いことやってなかったのが原因なので、年のせいというのは必ずしも正しくないかもですが

*18:例えば mod の逆元や乗法群なども自然に理解できたのは一般の中高生よりは有利だったかもしれません。とはいえ競プロをやる中高生は環論・体論ぐらい余裕で履修していたりするので驚きますが

*19:16 bit 用、 64 bit 用、 65535 bit 用など、ビット長ごとに使い分けています

*20:i 番目のループ変数の終了条件を指定してループ

*21:ACL にあったやつ

*22:これ

*23:これ

*24:これ

*25:任意 mod と言っても、素数3つ使うやつです。競プロで出てくる畳み込みは、要素の最大値が 10^9 程度、要素数が最大 10^6 程度なので、 10^24 程度まであれば十分です。これは 10^9 程度の素数を3つ使えば十分です。ちなみに、必要な最大整数を与えると、その3乗根ぐらいの NTT Friendly な素数の情報を返す関数も作っています。

*26:こんな感じ

*27:log が2つ付くと聞いてあまり使ってない

*28:こんな感じ

*29:某問題のテスターをしたときに、 Beats なら貼るだけじゃない？と思って試してみたときに使っただけ

*30:結合則や作用の条件などを満たさないと教えてくれます

*31:遷移を入れると Grundy 数のリストが出てくるようにしています

*32:これ

*33:初回からのパフォーマンスのリストを入れるとレート推移を返す