N_haraのブログ

主に競技プログラミングの話を書きます（多分）

AtCoder黄色になるまでにやったこと

競プロ

競プロerのN_haraです。AtCoder Beginner Contest 211 において黄色コーダーとなりました。記念(あるいは備忘録)として以下、主にAtCoder青色達成から黄色到達までにやったことなどを振り返りたいと思います。

 

青色になるまでにやったことについてはこちらの記事に書いてあります。

n-hara.hatenablog.com

 

以下、黄色達成時のデータです。

f:id:N_hara:20210725001119p:plain

f:id:N_hara:20210725171937p:plain

f:id:N_hara:20210725171942p:plain

自分について

北海道大学M1のN_haraといいます。自分のプロフィールをまとめると

  • 学科は情報系(学部も)
  • 研究は機械学習とか
  • 制作物はあまりない
  • 競プロを始めたのは2018年8月～(現時点で3年弱)

です。主なプログラミング経験をまとめると、

  • C++:競プロで使っている。むしろ競プロでしか使っていない。
  • Python:研究で使っている。競プロでは使ったことはほとんどない。

となります。

 

黄色達成までにやったこと

1.コンテスト参加

主に以下のコンテスト(バーチャルコンテスト込み)に継続的に参加していました。

  • AtCoder(ABC,ARC)
  • サークル活動でのバーチャルコンテスト

 また、イベントとして以下のものに参加していました。

  • ICPC
  • WUPC2020
  • UTPC2020
  • PG BATTLE
  • Google Code Jam
  • 競プロ典型90問

以下、それぞれについて軽く振り返ってみます。

 

AtCoder→モチベーションの維持につながりました。コンテストに参加しなくなると一気に競プロの意欲が下がるので、なるべく出るようにしていました(卒論発表直前は、流石に出る回数を減らしていましたが...)。AGCは、たまに参加していました。

 

サークル活動でのバーチャルコンテスト→これもモチベーション維持に貢献しました。問題のチョイスが幅広く、いろいろな問題に触れられたこともよかったと思います。

 

ICPC→3人1チームで行う大学対抗プログラミングコンテストです。AtCoderではないですが、競プロのモチベ維持につながりました。チーム練がとても楽しかったです。

 

WUPC2020→ICPCのチームで参加しました。5時間コンテストはあまり経験がありませんでしたが、チームメイトと相談しながら考察を進めるのが楽しかったです。

 

UTPC2020→サークルのOBの方(黄コーダー2名)とチームを組み参加しました。自分は主に実装を担当していましたが、自分以外の2人の考察の速さに驚かされました。

 

PG BATTLE→これも競プロのモチベ維持につながりました。飛び賞もあるのでとても楽しめました。今年も参加予定です。

 

Google Code Jam→問題が面白いです。Qualification Roundをワイワイ話し合いながら解いていたのも楽しかったです。

 

競プロ典型90問→この影響はかなり大きかったと思います。1日1問というペースが程よく、典型知識を仕入れると同時に継続的に競プロをするモチベになっていました。

 

こうしてみると、やはりモチベーションの維持は一番大事だと感じています。レートを上げるだけでなく、さまざまな大会に参加して競プロの楽しさを認識できて良かったと思います。

 

2.精進

個人での精進としては、主に以下のことをやっていました。

  • ABC-F埋め
  • SpeedRun埋め

 

それぞれやってみた感想として、

 

ABC-F埋め→高度典型を身に着けること目標として開始しました。問題を頭の中に入れ、外出中に解法を考えるということをしていました。考察力も鍛えられた感覚がありました。

 

SpeedRun埋め→典型力の確認としてやっていました。典型知識で解けるといっても考察がある程度要求されるものもあり、自分にとっては程よい難易度でした。

 

という感じです。黄色になるまでの精進は、「典型知識、考察を習得する」ということをおおまかに意識していました。

 

3.知識

AtCoder青色達成以降は、以下のようなデータ構造とアルゴリズム、知識を身に付けました。

  • BIT(Binary Indexed Tree)
  • セグメント木(遅延評価セグメント木も)
  • 三分探索
  • Rolling Hash
  • 平方分割(クエリ平方分割)
  • 最大流、最小費用流
  • 行列累乗
  • LCA
  • 区間DP
  • 掃き出し法
  • 包除原理
  • クエリ先読み
  • オイラーツアー

 

4.その他

これまで上げた他には、サークルでの作問、online-judge-toolsの導入を行いました。

 

作問では、解法の正当性はもちろん、想定解以外の解き方や難易度の評価、問題分に不明瞭な点がないか、などに気を配る必要があります。問題を1問作るのにも時間がかかることがありますが、解き手とはまた違った面白さがあると感じています。

 

online-judge-toolsは、AtCoder等において入力例に対するテストなどを自動化する便利なシステムです。見間違いでのミスやテストケース入力の手間が減るため、コンテストや精進の際に使わせていただいています。

 

 これから

今後は、ICPCに向けてICPCなどの過去問埋めを再開していきたいと考えています。

また、AtCoder上では

  • ABC
  • ARC-A,B,C
  • 競プロ典型90問
  • PAST
  • EDPC
  • TDPC

あたりを埋めていきたいです。

 

今後のARC、また次回(2021/7/31)以降の8問構成ABCにも気長に参加していこうと思います。