Manuel1024の引きこもルーム

競プロ日記 Manuel1024

水コーダーになりました

はじめに

2020年11月8日のAtCoder Beginner Contest 182 – AtCoderで水コーダーになりました．折角なので色変記事を書きました．お読みいただけるとうれしいです．



レーティングの推移はこの通りです．2020年4月に緑コーダーへ復位してから，水コーダーになるまでに7ヶ月ほどかかりました．




精進の進捗はこの通りです．2020年3月頃からStreakを伸ばしてます．

改めて自己紹介

はじめましての人もいるかと思うので，自己紹介を．

  • ハンドルネーム：Manuel1024
  • 性別：男
  • 生息地：茨城県某所
  • 本業：学生（情報系）
  • 使用言語：C/C++, Python
  • 第三回アルゴリズム実技検定の成績：中級（64点）

現時点で保有しているスキルとライブラリ

使えるようになったもの，競プロで役立っているものを列挙します．

使えるようになったアルゴリズム・データ構造

資料を見なくても使える・できる

  • 全探索（bit全探索を含む）
  • 累積和・いもす法
  • 二分探索
  • 深さ優先探索
  • 幅優先探索
  • 最小公倍数・最大公約数の取り扱い
  • 素数判定・素因数分解・約数列挙
  • エラトステネスのふるい
  • 簡単な動的計画法
  • ダイクストラ法
  • UnionFind（簡単に実装できるもの）

資料を見ないと怪しい・自前ライブラリなどに頼っている

  • 繰り返し2乗法（べき乗の高速な計算）
  • 逆元の計算
  • 二項係数の計算
  • ワーシャルフロイド法
  • クラスカル法
  • 高速に動作するUnionFind
  • bitDP

整備したライブラリ

整備しても，最近は出番がないライブラリが多いです．

  • 逆元の計算・二項係数の計算・べき乗の高速な計算・ax+by=GCD(a, b)を満たすようなx, yの計算
  • UnionFind

水コーダーになるまでにやったこと

アルゴリズム・データ構造の習得

E869120氏の記事（レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 – Qiita）を参考にして各種アルゴリズム・データ構造を習得しました．
履修状況は下記の通りです．（ほとんど「現時点で保有しているスキルとライブラリ」の再掲ですが）

  • 全探索：多重ループの全探索とbit全探索は何も見なくてもできるようになりました．順列全探索は資料を見ないと（next_permutation()の使い方が）怪しいです．再帰関数を用いた全探索は実装に少し時間がかかることがあります．
  • 二分探索：いわゆる「めぐる式二分探索」を習得しました．実際には，ある問題について二分探索を適用できることに気づくところまでが難しいと思います．
  • 深さ優先探索：普段は再帰関数を用いて実装しています．
  • 幅優先探索：後述しますが，思い出深いアルゴリズムです．いつも心に幅優先探索
  • 動的計画法：ナップザックDPは習得しました．bitDPは一応確認しましたが，使いこなせるかは微妙です．区間DPはほとんど未履修の状態です．
  • ダイクストラ法：こちらは資料を見なくても実装できるようになりました．
  • ワーシャルフロイド法：こちらは資料を見ないと少し怪しいです．
  • クラスカル法：一応習得しました．
  • 高速な素数判定法：習得しました．資料を見なくても多分実装できます．
  • べき乗を高速に計算するアルゴリズム：習得しました．自前ライブラリを用意し，必要になったらコピペするだけで使えるようにしています．
  • 逆元を高速に計算するアルゴリズム：フェルマーの小定理を使うバージョンは習得しました．拡張ユークリッドの互除法を使うバージョンは頭からすっぽ抜けました．
  • 累積和・いもす法：習得しました．実装するときは添字の取り扱いに気を使う場面も多いです．
  • グラフ・木：データの持ち方として隣接リスト・隣接行列がありますが，両方習得しました．
  • UnionFind：経路圧縮のみの簡単なバージョンは何も見なくても実装できるようになりました．より高速に動作するバージョンは自前ライブラリに頼っています．

また，C++の標準ライブラリは以下のものを履修しました．

  • abs（絶対値計算）
  • sin/cos/tan（三角関数）
  • string（文字列）…一部の機能は資料を見ながらでないと怪しいです．
  • min/max（最小値/最大値）
  • reverse（配列中の要素の反転）
  • sort（配列中の要素の整列）
  • vector（可変長配列）
  • queue（普通のキュー）
  • priority_queue（優先度付きキュー）
  • map（連想配列・平衡二分探索木）…setやmultisetの代わりとしても使っています．大活躍です．
  • pair
  • next_permutation
  • （ライブラリではないですが）構造体の演算子オーバーロード…構造体の配列をソートしたり，構造体をpriority_queueに突っ込んだりするときには比較演算子のオーバーロードが必要となります．

Longest Streakの更新

AtCoder Problemsを利用して精進している方は多いかと思います．
私は2020年3月頃から毎日1AC以上するようにしました．毎日ACすることでLongest Streakの数字が伸びていくので，精進する上で励みになります．


（記事冒頭の画像を再掲）水コーダーになった地点で，Longest Streakは250daysに到達しました．今後もできるだけ伸ばしていきたいと思っています．

緑diff埋め・茶diff埋め

御存知の通り，水コーダーになるためには茶diffの問題を素早く解き切り，緑diffの問題も頑張ってACする必要があります．私は過去に一瞬だけ緑コーダーになった後，わずか1週間で茶コーダーに逆戻りしたという前科があります（詳細は後述）．そのときの反省を踏まえ，Longest Streakを更新していくときに茶diffや緑diffの問題を解き，解ける問題を増やしていくことにしました．

2020年3月は競プロに復帰したばかりなので茶diff埋めで競プロの問題を解く感覚を思い出し，4月に緑コーダーに復位した辺りからは緑diff埋めに移行しました．
茶diff埋め・緑diff埋め開始当初は解説ACもしていた記憶がありますが，途中からはできるだけ自力ACする方針に切り替えました．

緑diff埋めは中断期間を挟みながら2020年6月末～7月頭辺りまで継続しましたが，

  • 自力ACできる緑diffの問題が減ってきた
  • 本業の方に時間を割かないとマズイ状況になってしまった

こともあり，緑diff埋めは打ち切りました．

その後は8月中旬まで灰diffの問題をACしてStreakをつなぎました．そして夏休み突入により競プロに割く時間を確保できるようになったため，残りの茶diff問題を全部解くことにしました．
AtCoder ProblemsのTrophy機能では問題のdiffの色ごとのLongest Streakによるトロフィーが設定されていたので，茶diffの問題を1日1ACして（茶diffの問題についての）トロフィーをできる限り取りに行くことにしました．


（記事冒頭の画像を再掲）
その結果，10月末頃に茶diffの問題を全て解き切ることができました．

ABC182までの振り返り

自分語りパートです．私が競プロを始めてから水コーダーになるまでを振り返ります．

競プロ初参戦～入茶まで

私が競プロを始めたのは2019年3月です．情報系の学生が入学後しばらくしてから始めたパターンです．
そのため，基礎的なプログラミング（if文やfor文，配列，再帰関数など）はできる状態でのスタートでした．この頃はC言語（学校で習得）で参戦していました．
コンテスト初出場の前に，AtCoder Beginners Selection – AtCoderを何問か解きました．3月16日のAtCoder Grand Contest 031 – AtCoderが初出場のコンテストとなりました．（当時のAtCoder Grand Contestは，レーティングに関係なく全員がRated対象でした．）



AGC031ではWAを大量発生させましたが，それでもA問題を何とか通せました．初出場で緑パフォを出せたのは良かったと思います．
その後はABCで2完もしくは3完し，順当に茶パフォを出してレーティングを伸ばしました．



そして，私にとっては5回目のコンテストである問題 – Tenka1 Programmer Beginner Contest 2019で3完水パフォを達成し，茶コーダーになりました．

1度目の入緑

その後，令和ABC開幕などのイベントがありましたが概ね順調にレートを伸ばすことができました．
この頃は精進らしい精進をほとんどしていなかったので時々事故が起きてレートが溶けることもありましたが，それでもABCでは多くの回で緑パフォを出せました．
当時は基礎的なプログラミング＋累積和やしゃくとり法だけで緑パフォを出せる回が普通にあったと思います．



そして，2019年7月20日のAtCoder Beginner Contest 134 – AtCoderで緑コーダーになりました．AtCoder初出場が同年3月16日なので，だいたい4ヶ月で入緑できたことになります．

緑コーダー失陥と競プロの中断



しかし，7月27日のAtCoder Beginner Contest 135 – AtCoderでしくじり，わずか1週間で茶コーダーへ逆戻りすることになりました．無精進で早解きにより稼いだレートは，早解き失敗でみるみるうちに溶けていきます．
怒涛の7連続失敗でレートはだいぶさがってしまいました．本業が忙しくなったのもあり，AtCoder Grand Contest 039 – AtCoder（0完）出場後，しばらく競プロを中断しました…．

競プロ再開～緑コーダー復位まで



2020年の2月頃には本業の方も落ち着き，競プロに割く時間を確保できるようになったので競プロを再開しました．コンテスト出場を再開したのはは2月16日のAtCoder Beginner Contest 155 – AtCoderです．ここからしばらくは茶色上位～緑色下位パフォーマンス（＋AGC0完による灰パフォ）が続き，レートはあまり動きませんでした．
この頃は茶diff埋めやレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 – Qiitaの再履修をしていました．
競プロでの使用言語をC言語からC++に乗り換えたのもこの頃です．C++入門 AtCoder Programming Guide for beginners (APG4b) – AtCoderなどを活用し，C++を使えるように訓練しました．
コロナ禍で学校の春休みが増えたので，7割怠け3割精進くらいの感覚で精進していました．

流れが変わったのはAtCoder Beginner Contest 161 – AtCoderです．
幅優先探索でD – Lunlun NumberをACして4完早解きに成功し，久しぶりに水パフォを出せました．この回で色変チャンスをつかみ，次のABCでも緑色上位パフォを出せたので入緑に成功．緑コーダーに復位しました．

緑コーダー防衛戦～入水へ



緑コーダーに復位した後，ABC164, 165で2連続茶パフォを出して再び茶コーダーへ逆戻りのピンチが到来しましたが，ABC166では何とか緑パフォを確保し，緑コーダーの地位は何とか防衛できました．
AtCoder Beginner Contest 168 – AtCoderではD問題までの早解きで水パフォを確保し，1年以上ぶりにパフォーマンスの最高値を更新しました．
AtCoder Beginner Contest 170 – AtCoderでは初めてE問題(E – Smart Infants)をACし，レーティング4桁台突入＆パフォーマンスの最高値更新を達成．その後はABCでE問題が緑diffになる回が増えたこともあり，E問題もある程度ACできるようになりました．
レーティングが4桁台に突入し，E問題を解ける回が増えてからは徐々に水コーダー入りを意識するようになりました．



HHKB プログラミングコンテスト 2020 – AtCoderで入水目前のところまでレーティングを上げましたが，ARCでの早解き失敗＆レーティング低下やAtCoder Beginner Contest 181 – AtCoderでの失敗＆レーティング低下により，足踏み状態が続きました．しかしAtCoder Beginner Contest 182 – AtCoderではかつてないスピードでE問題までACし，入水＆初めての青パフォを達成できました！

思い出深い出来事

ABC128で灰パフォ

AtCoder Beginner Contest 128 – AtCoderでまさかの1完灰パフォを出してしまったのは，今でもよく覚えています．AGC0完以外で灰パフォを出してしまったのは，後にも先にもこの回だけです．以下言い訳

  • 当時はC言語で参戦しており，ソートなどの基本的な操作も自前ライブラリに頼らざるを得なかった
  • 数字をソートするライブラリは用意していたが，文字列をソートするライブラリは用意していなかった
  • 文字列ソートの自前実装という想定外の課題が登場し，焦って自滅した

ABC161でD問題をAC

AtCoder Beginner Contest 161 – AtCoderでD – Lunlun NumberをACできたときはとても嬉しかったです．私は根付き木に対する幅優先探索でこの問題をACしましたが，中には気合の10重ループでACした人もいたらしく，驚きました．いつかこの問題の解説記事を書きたいですね．

ともあれ，この問題をACできたことで久しぶりに水パフォを出すことができ，レーティングが伸びない状態を打破できました．この回だけで入緑とはいきませんでしたが，緑コーダー復位のきっかけをくれたのは間違いなくこの回です．

ABC170でE問題をAC

AtCoder Beginner Contest 170 – AtCoderでは初めてE問題(E – Smart Infants)をACできました．std::mapを使ってひたすらゴリ押ししていく解法ではありましたが，これまで解けなかったE問題を解けたときは大変嬉しかったです．レーティング4桁台突入＆パフォーマンスの最高値更新も同時に達成できたので，ABC170も思い出深いですね．

おわりに

時間はかかりましたが，水コーダーになれてとても嬉しいです．当面の目標は，

  • 水コーダー維持
  • ABCでE問題をより高確率で解けるようにする
  • ARCでも水パフォを出せるようにする

の3点ですね．いずれは青コーダーを目指したいものです．

最後までお読みいただき，誠にありがとうございました．

参考にした記事

色変記事を書くときに，先人たちの色変記事を参考にさせていただきました．参考にした記事を列挙します．