凡人が約5年かけて青コーダーになった話

競技プログラミング
Page content

入青しました

1/6 のコンテストにて、2019 年から実に 4 年半以上の月日をかけて入青しました。

うぇーい

自己紹介

色変記事には往々にして自己紹介が見られるので、例に洩れず書くことにします。

が、凡人です。当たり前です、天才は入青に約 5 年もかかりません。

  • 年齢: 28 歳
  • 出身: 岡山県の片田舎
    • 中学受験は当時存在すら知らず
  • 高校: 偏差値 50 の県立高校卒
  • 大学: 立命館大学卒(生命医科)
    • 修士は京大(生命科学)
  • 仕事: web 系のエンジニア
  • 競プロ開始時期: M2 の 3 月 (その前に少し paiza をやっていた時期あり)

専攻はプログラミングとの直接の関わりは一切なかったのですが、
実験の作業効率化のために B4 のころプログラミングを独学したところこれが中々面白く、今は IT 系のお仕事をやっています。

競プロ的な基礎スペックとしては、腐っても理系出身なので ABC の 序盤に耐えうる基礎学力があったのはアドバンテージだったと思います。

一方で、理系といえども所詮は偏差値 50 高校からの立命館、それも生物系ということで、
2 回生以降の大学数学はもちろん、受験数学においても難関大の 2 次試験や指導要領外の合同式や整数問題をろくに勉強しないまま今に至っています。
そのツケが回っているのか数学的な考察・式変形などを伴う ABC-EF、ARC-B あたりにはいまだにかなりの苦手意識がありますし、TL でたまに見かける形式的冪級数などはなーんにもわかっていません。

入青までに使ったアルゴリズム・データ構造について

998244353 回くらい擦られてるネタだと思うので今更ですが、自分目線でまとめておきます。
なにぶん入青に 4 年半以上かかってる人間の戯言なので、信憑性については言うまでもありません。あしからず。

E869120 さんの Qiita 記事をベースに整理

E869120 さんの Qiita 記事では黄色になるためのアルゴリズム・データ構造について書かれているので、
このうち自分が入青までに使った/使わなかったものを振り分けるような形で整理します。

(i) 中級編 2-1. 節に書かれている 12 個のアルゴリズムと 3 個のデータ構造

記事中には以下が記載されています。

  • 全探索
  • 二分探索
  • 深さ優先探索
  • 幅優先探索
  • 動的計画法
  • ダイクストラ法
  • ワーシャルフロイド法
  • クラスカル法
  • 高速な素数判定法
  • べき乗の高速な計算
  • 逆元の計算
  • 累積和・いもす法
  • グラフ理論
  • 木
  • Union-Find

これらは入青時点でも、例外なく全て必須でした。

ABC-EF にはこれらを想定解としつつも少し応用(前処理すれば二分探索できるとか DP の遷移や高速化を工夫するとか)をきかせたような問題が多いので、
ABC-D までの問題などを通じて上記のアルゴリズムに対する理解を深めておくことは非常に重要だと思います。

また、

「そのような(少し応用がきいた) EF が解けたり解けなかったりして青パフォを取ったり取らなかったりしつつ、失敗しても DE まではある程度早解きできているのでなんとか水下位パフォで耐える」

というのが停滞水コーダーのある種お決まりのパターンだというのは身をもって実感するところです。言うは易しですが、そうした EF の正答率を上げるのがおそらく入青に最も重要なのだと思います。

(ii) 中級編には書かれていないが蟻本には書かれている、11 個のアルゴリズム

記事中には以下が掲載されています。

  • 座標圧縮
  • 半分全列挙
  • 行列累乗
  • ダブリング
  • Grundy 数
  • Rolling Hash
  • 平方分割
  • 最大流
  • 最小カット
  • 二部グラフ判定
  • 二部マッチング

(i)と比較すると、入青までに使いこなせた試しが無いようなものも混じっているので、いくつかに分類します。

コンテストで使えたことがあるやつ

  • 座標圧縮

考え方は難しくない上に汎用性が高いので、とりあえず引き出しに入れておけばいい感じのやつです。
入水以前から知っていたり、自力で再発明した人も多そうです。

ごくごく単純な座圧を題材にしたものは ABC-C くらいに出ていたような気がしなくもないですが、
ABC-EF だともっぱら前処理に使われ、「座圧してからセグ木に載せる」みたいな形で何かと組み合わせて使われる印象です。
(とはいえ最近あまり使ってないような気もします。)

  • 半分全列挙

方針さえたてば比較的スムーズに考察が進むことが多く、基本的には全探索の延長で学習コストも低いため、やはり引き出しに入れておいて損はないやつです。
が、普通に出題すると「これ半分全列挙やるだけって問題文に書いてますよね」みたいな制約になるので、何かしらの捻りが加わった状態で出されがちな気がします。

自分はこの回でうまく刺さりました。

  • Rolling Hash

一度出題されて解けなかった際にクラス化して整備したものを、その数回あとのコンテストで使ったことがあります。
が、それ以降見た記憶はありません。実際に使用した回のコンテストでも別にロリハが想定ではなかったと思います。

なお、記事中のアルゴリズムでは挙げられていませんが、自分は関連する文字列アルゴリズムである Z algorithm や suffix array の方をあまり詳しく知りません。
ACL には Z algorithm が実装されているらしいので、可能であればそれらを使う方がいいと思います。

実装したことはあるけどコンテストで使えたことはないやつ

  • ダブリング
  • 行列累乗

コンテスト中に解けなかったので解説 AC したり、ダブリングしなくても周期性から解けちゃったり、必ずしも行列累乗は必須ではなく繰り返し二乗法の亜種で解けたり、みたいなパターンであんま使えてないです。
自分が使えてないだけで、入青までにきちんと使いこなしてレーティングに貢献させた人は割といそうです。

全然使ったことがないやつ

  • 平方分割

入青時のコンテストの F 問題が平方分割だったんですが、解けませんでした。

存在自体は知っていたんですが、全然使ったことなかったです。
単に区間和が欲しい場合などはセグ木でなんとかなるせいで過小評価されているせいです！！！(負け惜しみ)

  • Grundy 数
  • 最大流
  • 最小カット
  • 二部グラフ判定
  • 二部マッチング

全てまともに使った(使えた)記憶がないです。
(ここでの二部グラフ判定は二部グラフの性質などに着目した考察部分がセットにくる前提で取り上げられているものと思っています。dfs/bfs 系の問題として 2 色に塗り分けるだけならどっかでやってそうですが)

点数にして 600 点以上相当という印象で、これら 5 つについては入青になる上ではあまり気にしなくてもよさそうだという認識です。
もちろん黄色を目指す際には必要になってくるのでしょうし、前々から身につけていると上振れチャンスが狙えるとは思います。

(iii) 中級編には書かれていないが蟻本には書かれている 2 個のデータ構造

記事中触れられているものは以下の 2 つです。

  • Binary Indexed Tree (BIT)
  • セグメント木（※遅延評価セグメント木を含む）

めっちゃ使いました。とくにセグ木。

ただし、自分は遅延セグ木については伝播が単純なものしか扱えず、コンテスト中に通した問題は無い気がします。
(そもそも ABC で遅延セグ木を見かけるようになったのが割と最近っぽいです？)

普通のセグ木だけでもドラクエの船入手並に世界が広がるので、是非カバーしておきたいデータ構造です。使うだけなら比較的楽です。
なお、自分はソラで実装しろと言われてもできません。(ライブラリをぺたり)

まとめ

  • (i) 入水までに培ってきたアルゴリズム・データ構造は当然全部使うし、何ならその応用が一番重要そう
    • 結局のところ入青に重要な水-青下位 diff の多数派はそういう問題がち
  • (ii) ABC-EF 帯で(i)に無いアルゴリズムが出ることもある (ダブリング、半分全列挙、ロリハ等)
    • 入青ラインならそれらは知ってたり知らんかったりでも割となんとかなりそう
    • 入黄ラインになると話が別で、「1800 diff の典型を知らずに取りこぼすの、普通に激痛だろ」となるので結局全部要りそう
  • (iii) データ構造では、セグ木の習得が必須級

競プロとの付き合い方について

レーティングの推移を見ればわかりますが、 ほとんど毎週コンテストに出続けています。

「IQ サプリを毎週見てる」 とか、
「QuizKnock の動画が出たら毎回見てる」 とか、
「新聞の詰将棋やクロスワードを毎回解いてる」 とか、
そういう感じのノリでコンテストに参加していたら、いつの間にか 5 年近く経っていました。暇人か？？？

実に累計 300 回近くコンテストに参加 しています。暇人か？？？？？？？？？？？？？？？

その一方で、コンテスト以外では対して精進していません。


(AHC か何かの分で RPS が壊れてそう？)

300 回近く参加しているにもかかわらず AC 数は 1500 台です。「精進？rated 参加こそが精進だぜ HAHAHA」とでも言うべき付き合い方です。
(これ以外にも CodeForces やその他の事情により解いた問題がある程度ありますが、成長面ではあまり寄与していないように思います)

そもそも冷静に考えてみると、

  • 「問題を解くパズル的な面白さ ✕ レーティング変動のスリル」(競プロを楽しむこと)を主たる目的としてコンテストに参加すること

と、

  • 競技プログラミングなるものに文字通り競技として向き合い、体系的に勉強して努力すること

は両立しうる全く別のものであるはずです。後者は気が向いたときにやりつつ、前者を中心としてだらだらと競プロに向き合うこともまた一つの楽しみ方だといえると思います。

将棋指しの全員が奨励会を目指さなければならないわけでもありませんし、さしずめ縁台将棋ならぬ縁台競プロといったところでしょうか。


(カスのヒートマップ。平日の大半は AHC だと思う)

そして、そのような向き合い方をしているとそもそも禄に精進していないので「精進したのに伸びない」というメンタルの悪化が生じ得ません。
だからこそ 4 年半以上も続けてこられたのだと思います。

周囲の天才は一瞬で色変していきますが、今回の牛歩色変によって凡人なりに気楽に楽しみながら続けられてきたのだということを身をもって示せたかなと自負しています。

これからもだらだらと続けていきましょう。