競技プログラミングで2年ほどでやったこと

ここまで競技プログラミングプログラミングでやってきたことを日記風にまとめておきます

また、競技プログラミングに参加しようかと考えている人向けに後半に何をやるべきか書いたので、時間のない人は、そこだけ見てください

競技プログラミングとの出会い・paizaランクA取得まで

私の競技プログラミングの出会いは、部活でC言語講習での部員からの紹介です。

ここでpaizaさんのコード・ガールコレクション(https://paiza.jp/cgc)を知り、ここでPythonを習いました。

また、暇があるときにこれらの実践でプログラミングスキルチェックに挑戦して、D,C,Bランクとステップアップしていきました。

当時は問題に応じて、CとPythonを変えていました。

その後、エンジニアでも恋がしたい！〜転職初日にぶつかった女の子が同僚だった件〜 | paizaオンラインハッカソン（POH）(https://paiza.jp/poh/enkoi)などのプログラムエンタメに取り組み、その中で尺取り法を習得しました。

そして、2019年の2月にAランクを取得しました

やったこと

  • paizaのスキルチェック問題のAランクをクリアする (Aランクの問題を1問、想定解答時間以内(多くは2時間以内)に提出し、おおむねすべてのテストケースに正答する)
  • paizaの想定paizaランクB以上対象のプログラムエンタメに挑戦し、何らかのアルゴリズムを身に着ける

習得したアルゴリズム・データ構造など

  • 尺取り法
  • C言語の基本構文(if,for,while,配列,入出力)
  • 計算量の見積もり
  • 標準入力から文字列を受け取る方法
  • 数字とアスキー文字との関係

atcoder参戦 ~ 茶コーダーまで

その時は、paizaのスキルチェックSランクをとってから参戦しようと考えましたがSランク問題がなかなか解けず、埒が明かないと判断して、6月にatcoderに参戦しました。

その時に、直大さんのブログ(https://chokudai.hatenablog.com/entry/2019/02/11/155904)によると、エンジニアとしてもある程度の安心感がある緑コーダを目標にしました。

当時は、ABCが6問体制になってから間もなかったため、初めてのコンテストまでにABC127,128のA,B,C問題を解きましたが、ABC128のCが解けず不安になりました。

そうして、ABC129でデビューをしました。

その時にA,B問題は解けましたが、C問題で時間切れ、その問題の解説を見たら、DPを使う問題で、その時からDPに因縁を持っていました。

(当時のコンテスト成績表)

atcoder.jp

その次の週、ARCクラスの企業コンテストに参戦しました。

このコンテストではA問しか解けず、レートが下がると思っていたが、まさかの茶perfでびっくりしました。

また、翌日のABCでは、先週のABCと違ってスムーズに進み、特にC問題で考察中心の問題が出て、びっくりしました。 また、D問題で尺取り法を使う問題が解けて、パフォーマンスももう少しで水色の1164でうれしかったです。

今後もABCはほぼ毎回参加し、A,B問題が解けて、C問題が解けるか解けないかのレベルでした。

また、途中にあったAGCに参加したが(当時は灰コーダでも参加できた)、1問も解けず、そのことがきっかけでAGCには出ないと決めました。

そして、2019年07月のABC135で茶コーダになりましたが、その時に解けなかったD問題で、今度もDPだ!と思ったら、今度は桁でDPをとるものでした...

(その時のコンテスト成績表)

atcoder.jp

やったこと

  • ABCに毎週参加する
  • 時間があったときにABCのA,B問題を解く

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

特になし

茶コーダー　~ 緑コーダー　まで

これまで2度もDPに阻まれたのをきっかけにEducational DP ContestのE問題までを解きました。

しかし、ABC141のD問題で、優先度付きキューを使う問題が出て、それがC言語では提供されていないことがきっかけで、 そこで競技プログラミングでC言語、さらにはPythonも捨て、C++一本で競技プログラミングに取り込むことを決めました。

まもなく、部活でのコンテストの最後の追い込みで半月間、競技プログラミングに触れられない日々が続きました。

そして、部活でのコンテスト終了後、C++になれるため、APG4bを解き、C++のライブラリに少しずつ慣れていきました。

このころから、精進の手段として、Atcoder ProblemsのRecommendationを使うようになり、有志が開くバーチャルコンテストに参加するようになりました。

このころから、アルゴリズムなどをライブラリにまとめ、コードを書くときに、すぐ引き出せるように整備しました。

あるとき、ABCのD問題で自分では互角だと思っていて、解けた問題のdiffを見たら、青diffで驚き、それと同時にここから自分の可能性を信じるようになりました。

しかし、グラフの問題は大の苦手で、気づいた瞬間、避けていました。その一方で、その判断が吉となり、結果として、水perfを取ると同時に、目標が水コーダーに変わりました。

しかし、それではいずれ足かせになると思い、Webの記事などで幅優先探索、深さ優先探索を習得し、グラフに慣れました。

あるときのABCでこれまでかけたはずのDPが書けなくなり、これがきっかけでC++でEDPCを解き直しました。

2020年02月のABC154で緑コーダーになりましたが、ここでも(事実上の)桁DPに阻まれました。

(その時のコンテスト成績表)

atcoder.jp

やったこと

  • ABCに毎週参加する
  • 時間があったときにAtcoder ProblemsのRecommendationにある問題を解く
  • バーチャルコンテストに参加する

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

緑コーダー ~ 水コーダー　まで

ここら辺から1年近く、毎日1問は新規ACをするようになりました。

また、2月の終わりからe869120さんのレッドコーダーが教える、競プロ・AtCoder上達のガイドライン(https://qiita.com/e869120/items/eb50fdaece12be418faa)の分野別　初中級者が解くべき過去問精選 100 問を解くようになりました。

さらに、コロナによる休校+遠隔授業も重なり、競技プログラミングに専念できるようになり5月ごろには、9割前後をACしました。

ここで、panasonic2020のC問題(https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_c)などの浮動小数点の誤差に注意する問題が多くなり、苦戦しました。

また、4月から、バチャであさかつ・よるかつ/くじかつに参加するようになり、これによって、時間内にどう立ち回るかを鍛えられました。

このバチャは序盤に相対的に解いていない灰diffが出るため、ステークを重ねやすくなりましたが、すでに解いていた問題の場合、日が変わるまでに解けない可能性が高いため、バチャ前にステークを重ねるようにしました。

おまけに、解けない問題に出会える機会が増えたため、解説を読んで、手が届きそうならば、実装するというのをするようになり、ダブリングなどをこの方法で習得しました。

また、PASTが無料で受けられるのを聞き、第三回 アルゴリズム実技検定に挑戦しました。

(当時のツイート)

それに先立ち、第1回と2回目の過去問に挑戦したところ、セグメント木を使えるかどうかが中級への鍵だと考え、セグメント木を勉強しました。

本番では、セグメント木こそは使わなかったが、時間を配分を間違い、これが解けたら中級だと思って解いたら、すでに中級が確定していたなどのハプニングがありましたが、最後から3番目の問題の複数のアルゴリズムを使って解く問題が解けて、実力の向上を感じました。(ちなみにあと一問解けてたら上級でした)

ここら辺から、問題を解く時に、似たような問題を思い出し、その思い出をだとって解いたりするようになりました。

2020年の6月当たりからABC170のD問題などで(https://atcoder.jp/contests/abc170/tasks/abc170_d)エラトステネスの篩を使う問題が出てきたのを感じ、エラトステネスの篩を習得しました。

2020年の8月から、コンテスト後に解説を書き始めました。解説を書く時に気を付けたのは次の3つです。

  • できるだけ速く解く
  • わかった問題は、どのように考えて、どのような方法で解くか
  • できなかった問題は、どこまでできたか、どこでつまずいたかを書く

2020年9月にACLが導入されました。

2020年12月のABC185でE問題のDPが解け、初めての全完&水コーダになりました。

やったこと

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

  • 答えに貢献する量から答えを求める
  • セグメント木
  • エラトステネスの篩
  • 二部探索
  • 区間DP
  • bitDP
  • ダイクストラ法
  • ワーシャルフロイド法
  • プリム法・クラシカル法
  • mod109+7での除算
  • グラフの取り扱い(隣接行列・隣接リストへの変換)
  • Disjoint Set (Union Find)
  • 半分全列挙
  • imos法
  • ダブリング
  • 座標圧縮
  • 木の直径

水コーダー ~ 現在

ABC189のE問題で初めてアフィン変換を知りました。

また、2021年5月のABCクラスの企業コンで青diffだと思って解いたF問題が黄diffになり、初めての黄perfを取りました。

また、その解法で、論理回路のベイチの図を使ったため、学業も競技プログラミングの役に立つと感じました。

遅延評価付きセグメントのライブラリを作るように

ABCが8問体制になったころから、学業に時間をとられ、精進はできていませんが、ABCトーナメントに参加し、対象となるABCには出ています。

現在は青コーダーを目指して頑張っています

やったこと

とくになし

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

  • 遅延評価付きセグメント木

  • アフィン変換

(ここからは用語は知っているが、実装はできないアルゴリズムたちです)

  • 高速ゼータ変換
  • 行列累乗
  • きたまさ法
  • 拡張ダイクストラ法
  • 中国剰余定理
  • 最大流・最小カット
  • 全方位木DP

これから参加する人が上達するために

~灰コーダ

まずは、一つの言語でif,for,while文などの基本構文を習得しましょう。

私のお勧めはpaizaさんのコードガールこれくしょん(https://paiza.jp/entertainment)などで一通りクリアしたのち、スキルチェックでCランク問題を3問程度クリアです。C++なら、APG4B(https://atcoder.jp/contests/apg4b)もお勧めです

~茶コーダー

ABCのA~C問題を解いて、Atcoderに慣れましょう。ABS(https://atcoder.jp/contests/abs)がお勧めです

また、計算量に関する知識と全探索を身につけましょう。 e869120さんが書いた「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】」の全探索の問題 (https://qiita.com/e869120/items/f1c6f98364d1443148b3#%E5%85%A8%E6%8E%A2%E7%B4%A2%E3%81%AE%E5%95%8F%E9%A1%8C)がお勧めです。

また、計算量に関する知識に関連して、disjoint-setや、調和級数になるループ、エラトステネスの篩を習得するのをお勧めです。

また、ここら辺から、自分がどうやって解いたか、もしくは、どこまでは考えついたかを書き起こしておくことをお勧めします。

~緑コーダー~水コーダー

ここからになると、レートを上げる方法は大きく分けて2通りの道があります。

  1. 問題を速く解く
  2. 問題を多く解く

1はレートを安定させるのに役立ちます。自分と同じか一つ下の色の問題を解くのがお勧めです。 2は高いレートを取るのに役立ちます。分野別の学習はe869120さんの「レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】」 分野別　初中級者が解くべき過去問精選 100 問(https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F)やアルゴ式(https://algo-method.com/)がお勧めです。アルゴリズムのverifyには、aize online judge(https://onlinejudge.u-aizu.ac.jp/home)もお勧めです。 アルゴリズムの引き出す力の習得には、競プロ典型 90 問(https://atcoder.jp/contests/typical90)がおすすめです。

1,2共通で時間があるときにバチャに出ましょう。私のお勧めは毎日21時から行われるくじかつです。