Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

[入黄記事] 青い蕾が黄色の花を咲かせるまで

初めに

1t45E2OSGUTPOHp1621102904_1621102936.png

2021/05/15 に開催された マイナビプログラミングコンテスト2021 (AtCoder Beginner Contest 201) において, Performance 2274 を獲得した結果, Rating が 2006 になり, 黄色になりました.

1. 自分なりの心得

心得 1: 集中できないことが確定しているときはやらない

私自身, ある時期まではABC, ARC は毎回出場していました. しかし, ある時期をすぎると参戦しないことが増えました. 以下が実際の ABC/ARC の参戦記です.

日程 コンテスト 出場
03/28 (日) ARC 116 x
04/11 (日) ABC 198 o
04/17 (土) 第2回日本最強プログラマー学生選手権 o
04/18 (日) ARC 117 x
04/24 (土) ABC 199 (Sponsored by Panasonic) o
04/25 (日) AHC 002 o
05/01 (土) ZONeエナジープログラミングコンテスト "HELLO SPACE" o
05/08 (土) 京セラプログラミングコンテスト 2021 (ABC 200) x
05/09 (日) ARC 118 x
05/15 (土) マイナビプログラミングコンテスト 2021 (ABC 201) o

これはなぜでしょうか? 果たして, 参加していないコンテストの間はなにをしていたのでしょうか? この問題の答えは別の界隈のスケジュールにあります.

日程 コンテスト 出場 配信日程
03/28 (日) ARC 116 x 9th YEAR BIRTHDAY LIVE ~2期生ライブ~1
04/11 (日) ABC 198 o ----------
04/17 (土) JSC o ----------
04/18 (日) ARC 117 x ノギザカスキッツLIVE1
04/24 (土) ABC 199 o ----------
04/25 (日) AHC 002 o ----------
05/01 (土) ZONe o ----------
05/08 (土) ABC 200 x 9th YEAR BIRTHDAY LIVE ~4期生ライブ~
05/09 (日) ARC 118 x 9th YEAR BIRTHDAY LIVE ~3期生ライブ~
05/15 (土) ABC 201 o ----------

このように, 休んでいた日には乃木坂46の配信ライブがありました. 1 そして, これらの配信ライブには全て 21:00 からアフター配信があり, 私はこれを見ていました.

一応, 既に本配信を見ているので, 見ながらコンテストということも可能なのです. しかし, この配信を見るためにお金を払っているので, アフター配信を十分に楽しむことができず, しかも Rating が下がってしまったら, 元も子もなくなってしまうので, どちらか一方に集中すべきだと思い, 配信ライブの方を優先しました.

このように, 読者の皆さんも競プロ意外の趣味があったり, 趣味じゃなくても興味を持っているような事柄が発生したりします. ここで, もし日時がかぶってしまった場合, 趣味のことの頭が離れず, 集中できないままコンテストに参戦し, Rating が下がってしまったら, 悲しくなってしまうので, それだったらどちらか一方に集中した方がいいと思います. ただし, コンテストにでるときは思いっきり集中しましょう.

心得 2: 典型を見つける.

競技プログラミングは様々な問題があります. しかし, 何度も出題される要素があり, それらにはキーワードを持っている場合があります. たとえば,

  •  \cdots の最小値を得点とする. 得点の最大値を求めよ  \to 「得点として  X 点以上は可能か?」という判定問題を考え,  X について二分探索.
  • 順列に関する問題. ただし, 第  k 項までの情報はまとめることが可能  \to Bit-DP
  • グラフの頂点  u から頂点 v への移動における最短時間を求めよ.  \to グラフの最短路探索

などがあります. このような典型パターンをたくさん入れておくと, 似たような問題が出題されたときにすぐに対応できるようになります. また, 最近では典型90のようなコンテンツも登場し, 勉強がしやすくなったと思います. 典型は覚えておくと思考一気に進んだり, 場合によっては知らないと無理な問題もあるので, 上を目指すのであれば典型は覚えておくべきだと思います.

2. 新たに学んだこと

習得したこと

実は青色になった瞬間の装備と余り変わっていません. また, 追加された装備についても, また使ったことはありませんが, 一応載せておきます (★はライブラリーとして持っているものです).

アルゴリズム, テクニック

  • スライド最小値 (★)
  • ローリングハッシュ (★)
  • 双対セグメント木 (★)

データ構造

特になし

3. 解いた問題数

  • AtCoder: 1026問
    • 解いた問題の総得点: 308400 pts 2
      • 100 pts  \times 90/196
      • 200 pts  \times 167/213
      • 300 pts  \times 214/216
      • 400 pts  \times 184/189
      • 500 pts  \times 129/149
      • 600 pts  \times 80/149
      • 700 pts  \times 18/85
      • 800 pts  \times 4/65
  • yukicoder: 533問
  • AOI: 数問 (Verify 専用)
  • Library-Checker: 34問

4. 最後に

競プロで取り扱っている事柄はたくさんあるので, 勉強していることがすぐに出てくることはあまりないと思いますが, 名前は知っているのに, 後回しにして後悔しないように, 興味を持ったらその時に勉強することをおすすめします.

5. この記事に関する疑問

Q: なんで5月に黄色になったのに, この記事を12月に公開したのか?
A: その後のレートがこうなったから.

f:id:Kazun_kyopro:20211012002327p:plain

最後に


  1. 配信のうち, 半分がコント, 半分がライブです.

  2. 私は坂道シリーズのファンなのですが, この時期に土日の配信は乃木坂46だけであり, 櫻坂46と日向坂46はありませんでした.

  3. 1期生ライブは 03/29 (月) だったので, この表には登場しません.

  4. 一部のコンテストは有志コンテストなどの結果も含まれているので, 各得点毎の点数を足すと,  8000 pts 足りません.