TERRYのブログ

最近は競技プログラミングにお熱。

Sponsored Link

トップ > 競プロ > AtCoderで青色になりました

AtCoderで青色になりました

競プロ AtCoder

優勝！！！！！！！！！！！！！！！！！！

誰？

詳しくは↓の入水記事に書きましたのでご興味あれば。 一言でまとめると機械系14歳社会人JCです。（は？） www.terry-u16.net

青になるまでにやったこと

データ構造・アルゴリズムを勉強する

勉強する、と言っておきながら水色になったときからそんなに使えるデータ構造・アルゴリズムは増えていません。これは個人的な感覚なのですが、水色と青とで要求される知識量はあまり大きく変わらないように思います。一応以下に新しく仕入れたデータ構造・アルゴリズムを列挙しますが、実戦で使う機会はさほど多くはありませんでした。*1

  • 区間DP
  • トポロジカルソート
  • ダブリング（最小共通祖先（LCA）問題とか）
  • 行列累乗
  • 平面走査
  • 文字列検索アルゴリズム
    • Z-Algorithm
    • KMP法
    • ローリングハッシュ
  • 包除原理
  • Grundy数

では水色と青とで何が違うかというと、「いかにこれらのデータ構造・アルゴリズムを使いこなせるか？」という点に尽きるのではないかと思います。青diffの問題は単にアルゴリズムを知っているだけでは解けなくて、「考察して一捻りしてあげると典型に落とし込める」というものが多いように感じています。*2

この典型に落とし込む考察力をどう養うか？というと、精進するしかないわけですね。精進しましょう。

精進する

結果からいきますね。どん！

f:id:terry_u16:20200822111202p:plain f:id:terry_u16:20200822111144p:plain f:id:terry_u16:20200822111229p:plain 画像はAtCoder ProblemsさんとAtCoder Scoresさんのものを使わせて頂きました。本当にいつもお世話になっております……！

精進グラフが綺麗な一次関数になっていますね。レーティングの方は一時期停滞してしまい、精進の結果が反映されるまで時間がかかってしまいましたが、気にすることなくコンスタントに精進を続けられたのは良かったのかなと思います。

自分は社会人なので、先が長くないできるだけ時間を効率的に使いたいなあという思いがあり、精進の進め方、効率の上げ方については意識するようにしていました。いろいろ試してみた結果、自分に合ってるなと思った取り組み方はこんな感じです。もちろん人によって最適な精進方法は違うと思いますので、あくまで参考程度に。

  1. 自分の実力の少し上くらいの問題を重点的に解く
  2. 解けた問題でもeditorialや解説記事を読む
  3. 1時間考えても分からなければ解説ACする
  4. 考察の過程を自分の言葉で言語化する

1.についてですが、競プロで良い成績を出す方針としては、

  • 早解き力を付けて安定感を上げる
  • 解ける難易度の上限を引き上げ爆発力を上げる

の2つがあると思っています。*3 1.はこのうち後者を目的としたものです。特にAtCoderはレート計算式の都合上、安定したレートを取るより大成功と破滅を繰り返した方がレートが高くなりやすいので、こちらの戦略の方が合ってるようにも思います。たまに大成功すると嬉しいですしね。その代わりCodeforcesではレートが一瞬で溶けたりしますが……。

2.については、「なんとなく」で通してしまう問題を潰したり、より良い別解を知ることができたりするのでオススメです。

3.は賛否両論あると思います。以前は「典型っぽい問題だったら解説を見る」という方針だったのですが、「見た目は典型っぽくないけど、考察の進め方が他にも応用できるような問題」が結構あることに気付いたので、最近はできることの幅を広げることを目的として解説ACするようにしています。アルゴリズムは名前が付いていることが多いのですが、考察過程は名前が付いていないことがほとんどで、検索等による知識習得が困難なので、問題に当たったときに取りこぼさず自分のものにしたいな、と考えています。*4

「解説を読んで次に出会ったときに解けるようにしておく」ではなく「解説ACする」としているのは、「分かったつもり」になることを避けるためです。解けなかった問題の解説がとても簡潔だったりするとなんとなく分かったつもりになって、実装する段階になって「あれ、ここどうやるんだ……？」となりがちなので、ACまでは持っていくようにしています。

4.については3.とも関連するのですが、ふわふわとした思考過程を他の問題にも適用できるよう自分なりに抽象化し、言語化することで、次に似たようなパターンが使える問題に出会ったときに迷いなく解けるようにしたいな、と思って実践しています。

とまあ偉そうに書きましたが、正直自分でも常にこれらを意識しながら精進できているかというと微妙なところがあります……。常に完璧を目指して精進すると疲れちゃうので、ときには肩の力を抜いて気楽に精進するのも大事かなと、自分に言い訳をしておきます。

話は変わりますが、AtCoderの過去問だけだと問題数に限りがあるので、埋まってきたなと感じたら海外コンテストサイトにも手を出すのが良いかと思います。中でもTopCoder SRMの問題は質が高く、同じ1問でも多くの学びが得られるためオススメです。こちらの記事の中でDiv.1 Easyの良問50問が紹介されているので、これを上から順に進めていました。

コンテストに出る

f:id:terry_u16:20200822113724p:plain f:id:terry_u16:20200822113814p:plain f:id:terry_u16:20200822113858p:plain

TopCoderのこの振動っぷりは何なんですかね……。

参加できるratedなコンテストはほとんど参加しました。なんといっても楽しいので。バーチャルコンテスト（以下バチャ）と比較しても、レーティングがかかっている分問題を解くときの集中力が違うように感じます。

今のところコンテストでのNo Sub*5はしたことがありません。一時的にレーティングが下がってしまったとしても、そのコンテストで何か得られるものがあったのであれば、実力はその分必ず付いているはずです。いずれレーティングは自分の実力に収束する*6ので、一時的な授業料を払うことを厭わず長い目で見た方が良いのかな、と考えています。もっとも破滅してレーティングが溶けるとめちゃくちゃ悔しいのですが……。

バチャを立てる

一日一回バチャを解く機会があると嬉しいなあと思ったので、諸先輩方をパクってに倣ってくじかつコンテストというバチャを立てました。 www.terry-u16.net

毎日同じ時間に参加すると自然と習慣となるので、続けるのも苦にならなくなりました。既に解いたことがある問題に当たっちゃうことも多いのですが、時間が決まっている分集中して解くようになったり、実力が近い人に負けて悔しい思いをしたり、バチャ後にTwitterでよりスマートな別解を知ったりと、いろいろとメリットが多いように感じています。個人的にはくじかつ以外にもどんどん自分たちに合ったバチャを立てる文化ができると嬉しいなあと思ったりしています。

時々TwitterでCodeforcesのバチャを立ててくれている人もいたため、見かけたら便乗して参加するようにしていました。AtCoderのバチャと比べ、初見の問題に当たることが多く、おかげさまでだいぶ力を付けることができたように感じます。

Twitterをする

ネタに見えますが、ネタです。

とはいえ少なからずメリットもあると思っています。やっぱり周りが自然と競プロをやる雰囲気になっているというのが大きいですね。みんなやってるし自分も精進するか、という気持ちにさせてくれます。その他にも、コンテスト後やバチャ後など、解法についての議論が盛り上がっていたりして、毎回ものすごく勉強させてもらいました。いつも絡んで下さっている方、本当にありがとうございます！

一方Twitterをすることによるデメリットは無限にあるのですが、中でもCodeforcesのコンテストが深夜に終わったあとも1時間以上TLを眺めながらダラダラしてしまい気付いたら午前3時、みたいなのはやめないといけないなと思っています……。でも居心地が良いのでついつい入り浸っちゃうんですよね……。

心構えとか

レーティングについて

レーティング、気になりますよね。上がってモチベになっているうちは良いのですが、大失敗してレートが溶けると下手したらトラウマになってしまいがちです。そこまで行かなくとも、コンテスト前はレートを気にしてどうしても緊張してしまう……というのはあるあるだと思います。

音ゲーなどでも常々感じていたことなのですが、一番大事なのは今自分の実力がどの程度かという点であって、段位やレーティングはあくまで実力をある一面から計測した指標に過ぎないと捉えると少し気持ちが楽になるように思います。上でも書きましたが、レーティングが下がったからといって自分自身の実力が下がっているわけではありません。コンテスト結果に一喜一憂することはとても健全なことですし、それが競プロの面白さの一因にもなっているのですが、思い詰めてレーティングが足枷になるようだったら一旦忘れちゃった方が良いのかもしれません。

ちなみに最近は成功したら喜び、失敗したらネタにしてどっちもおいしい！みたいなのをやっています。

ただあんまりやり過ぎると色変反復芸人になりかねないので、負けた悔しさはうまいことバネに変換していきたいところです。あと微冷えだとネタにするにも微妙でつらい気持ちになりがち……。

周りとの比較について

競プロは自分の実力*7がレーティングという数値にダイレクトに反映されるネトゲなので、つい周りと比較してしまいがちです。無限時間かけても手が届かなさそうな人を見たり、後から始めた人に抜かれてしまったりすると凹んでしまう、ということは非常によくあります。

ですがちょっと待ってください。インターネットの功罪と言いますか、ネットによりつよつよな化け物たちが無限に観測できるようになってしまったので感覚が麻痺しがちなのですが、そもそも茶色の段階で上位50%なのです。*8 緑で上位30%、水色に至っては上位15%です。それもAtCoderに登録するような競プロが好きな人々の中で。Twitter等で化け物を日常的に見ていると「普通」の感覚が容易に狂いがちなのですが、化け物と人間を比較しないように気を付けると良いかなと思います。人によってバックグラウンドも全く違いますしね。

（2020/08/26追記：どうやら現在は茶色で上位34.3%、緑で上位19.9%、水で上位9.8%らしいです。半色以上ズレてません？レーティングのデフレが著しい……。）

話は変わりますが、ここ最近競プロ界隈をフォローし始めて、中学生・高校生の段階から競プロをやっている人が多いことを知り、とても驚きました。彼ら・彼女らがこれから成長して次の世代を担っていくと思うととても楽しみでなりません。若さは正義ですね……羨まし……あっ、いや、ぼくもJCでした。

おわりに

こんな長い記事をここまで読んだの！？本当に！？どうもありがとうございます……！サラッと書いて上げるつもりが思いのほか長くなってしまいました……。

一年くらいかけて黄色になれればいいなあと思っています。これからも仲良くしてくれると嬉しいです。

*1:とはいえ、新しいアルゴリズムを勉強したりデータ構造ライブラリを整備したりするのはやっぱり楽しいです。

*2:解いたサンプル数が少ないのですが、黄diffとなるとこれが二捻り三捻りくらいに増えるような印象です。

*3:既に無限人に言及されていますね？

*4:時々「これは解けなきゃダメだった……」みたいな問題もあり、そういうときは悔しさのあまり床を転げ回ったりしますが……。

*5:解答を提出してもレーティングが下がりそうなときに、敢えて提出しないことでunrated扱いとしレーティング下落を避ける戦略。

*6:黄以上だとratedなコンテストの回数が一気に減っちゃうので厳しい面はありますが、青までならほぼ毎週コンテストがあるのでリカバリーはしやすいと思います。

*7:運もだいぶ絡みますが……。

*8:参加回数によるレーティング補正があるので灰色が多くなりがちという点はありますが、それを差し引いても決して低いレベルではないです。そもそも最近の茶diffは普通に難しい……。