AtCoder黄色になるまでにやったこと
競プロerのN_haraです。AtCoder Beginner Contest 211 において黄色コーダーとなりました。記念(あるいは備忘録)として以下、主にAtCoder青色達成から黄色到達までにやったことなどを振り返りたいと思います。
青色になるまでにやったことについてはこちらの記事に書いてあります。
以下、黄色達成時のデータです。
自分について
北海道大学M1のN_haraといいます。自分のプロフィールをまとめると
- 学科は情報系(学部も)
- 研究は機械学習とか
- 制作物はあまりない
- 競プロを始めたのは2018年8月～(現時点で3年弱)
です。主なプログラミング経験をまとめると、
となります。
黄色達成までにやったこと
1.コンテスト参加
主に以下のコンテスト(バーチャルコンテスト込み)に継続的に参加していました。
- AtCoder(ABC,ARC)
- サークル活動でのバーチャルコンテスト
また、イベントとして以下のものに参加していました。
以下、それぞれについて軽く振り返ってみます。
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にも気長に参加していこうと思います。
AtCoder青色になるまでにやったこと
記事を書くにあたって...
北大B4のN_haraです。
昨日行われたM-SOLUTIONS プロコンオープン 2020に参加し、レートが1600を超えAtCoder青色を達成しました。
今回は節目として、これまでに競プロでやったことをまとめてみたいと思います。
今までにやったこと
1.競プロを始める～AtCoder茶色まで
この頃はアルゴリズムに関する知識がほぼほぼ皆無であったので、とりあえず自力でも解けそうな問題を探して解いていました。やった内容としては、
- AtCoder Beginners Selection(ABS)
- (ABC042~の)ABCのA,B問題
がメインになっています。特にABSはたった10問でAtCoderの感覚がやんわりつかめるので、もしまだ埋めていない人は全部解いてみることをおすすめします。
アルゴリズムの知識として理解していたのは
- （計算量を減らした）全探索、貪欲法
くらいだったと思います。（現在だと、もっと要求レベルが高いと思います。）
2.AtCoder茶色～AtCoder水色まで
このあたりから（特に緑以降）アルゴリズムの勉強を少しずつ進めていきました。
やった内容としては、
- (ABC042~の)ABCのA,B問題すべて
- 上に加えて、C問題半分くらいと簡単めなD問題
になります。C問題、特にD問題以降は計算量を意識しないとACできないことが多いので、アルゴリズムの知識（&計算量のある程度の見積もり）が必要になります。
この頃にアルゴリズムの知識として新たに理解したのは
- bit全探索、順列全探索
- 二分探索
- 深さ優先探索(DFS),幅優先探索(BFS)
- （比較的易しい）動的計画法
- ベルマンフォード法
- ワーシャルフロイド法
- 高速な素数判定法
- べき乗、逆元の高速計算
- 累積和
です。
データ構造として、
- Union-Find
も勉強しました。
ダイクストラ法やクラスカル法はこの時点では勉強していませんでしたが、これが原因でコンテスト中に詰まることはなかったように思います。（もちろん勉強して使えるようになるのに越したことはないと思います。）
3.AtCoder水色～AtCoder青色まで
この頃になるとAtCoderのレートが伸び悩んできたのであまりレートを気にせずいろいろな問題に取り組むようになりました。
例えば、ABCの埋め具合は以下のようになりました。
ABCにはいわゆる「典型問題」が多く出題されており、問題を解いたり、あるいは解けず解説ACをしたりする中で知らなかった知識に出会うことが多々ありました。特にE問題埋めをしたときは並のF問題よりも難しい問題があり、1題1題に集中して取り組んでいました。
この時点で新しく勉強したアルゴリズムは
です。
このようなアルゴリズムを扱う問題を含め、とにかくいろいろな問題を解いていました。
レートが伸びない人へ
ここまで淡々と競プロでやってきたことを書きましたが、思うようにレートが伸びない人もいると思います（むしろ停滞期のない人のほうが少ないと思っています）。実際、僕自身も水色で1年ほど停滞していて、4か月間highestを更新できない時期もありました。以降、備忘録も兼ねて、自分がレートが伸びないときにやっていたことを振り返ってみたいと思います。
I.レートを上げる意識を持ちすぎない
AtCoderに限らず、レーティングのつく競プロのコンテストサイトではより高いレートを目指したくなると思います。コンテストの結果レートが上がれば、やはり嬉しくなります（多分）。しかし、思うようにレートが上がらないときもあります。「レートを上げる、〇色になる」という目標を掲げて競プロに取り組むのは大事ですが、強く意識しすぎるとかえってプレッシャーになったりします。
ではレートが伸びないときどうするかというと、問題を解きます。問題を解く際には、もしかしたら知らないアルゴリズムの知識が必要になるかもしれません。あるいは、既知のアルゴリズムだったとしても、自分の考えでは簡単に思いつかないような使い方をする場合もあります。そういった新しい問題に取り組み、ACすることで自分の考えの引き出しを増やすことができます。
こうして問題を解くことを繰り返していくと、「問題を解く」こと自体が楽しくなります。これは自分にとって難しい、解くのに苦労した問題ほど解けたときの嬉しさも上がります。レートが停滞したとき、レートを上げることに固執せず、「問題を解く」ことに楽しさを見出すことで競プロを楽しく続けられると思います。
II.自分の力量を把握する
自分の力量を把握する、というのは競技プログラミングに限らずいろんな分野で大切なことだと思います。レートが伸びなくなったら、直近数回のコンテスト結果を振り返ってみるとよいかもしれません。
例えば「ABCのE問題が解けた回が少ない」という人がいたとき、これは「D問題までで時間を取られすぎた」からなのか、それとも「時間はあっても解法を思いつけなかった」からなのか、ということを考えます。前者であれば簡単な問題を短時間で解けるようになり、後者であればまず時間をかけてでも難しい問題を解けるようになることを目標とするのがよさそうです。
この設定した目標によってコンテストでより上位になるにはどんな問題を解くのがよいかということが見えてきます。ほかにも、「ダイクストラ法を使った解き方が分からない」のであればダイクストラ法を利用する問題を練習し、「桁DPが苦手」であれば、桁DPの問題を解くのがいいと思います。
とにかくたくさん問題を解く、という精進の仕方もありです（実際その方がうまくいく人もいると思います）が、自分に足りないものは何か（知識か、解く速度か、発想か、など）、それを補うには何をしたらよいかということを考えて精進してみるのもいいと思います。
III.誰にでも冷え（停滞期）はある
これが一番大事だと思います。
Twitterなどで見かけるつよつよな青コーダーや黄コーダー（あるいはもっと上）の方々がいますが、その人達も今の段階になるまでに冷え、あるいは停滞期を経験しているはずです（初回からABCでパフォーマンス2400を出すような方もいますが...）。実際、あるコンテストの順位表から「レーティング変動」を「差分」の昇順で見てみると下のような感じになっています。
ここで言いたいのは「誰でもレートが冷えたり、うまくいかなかったりすることがある」ということです。自分が冷えたときに、「自分はダメなんだ」と抱え込まず、「誰だって冷える、次のコンテストで温まるためにしばらくはこの分野の問題を解こう」とポジティブに考えることが大事だと思います。
まとめ
記事を書くにあたり過去の自分のsubmitを見返しながら記事を書いていたのですが、Rated初参加のAGCで0完していたり、昔のコードの書き方が変だったりで見返してみると面白く、けれど同時に自分の成長を実感していました。
競プロはやはり楽しいですし、色変ツイートをするとたくさんいいねを貰って嬉しくなり、競プロ界隈あったけえなぁ、と日々感じています。これからも競プロは続けていきたいです（研究・・・）。
それではよい競プロライフを～。
DDCC2020参加記
1/25(土)に行われたDDCC2020（ディスカバリーチャンネルコードコンテスト）本戦に参加してきました。オンサイト自体は2回目ですが、やはりオンサイトは緊張しますね。今回も参加記を書いておこうと思います。
予選について
...とはいっても予選があったのが2か月前で、内容は覚えてません、割愛。
予選の配点は1-2-4-5-8-9で、自分は25で1-2-4の3完、751位でした。500が通せず本戦無理か...と思っていたら
DDCC新卒枠ボーダー、740位っぽい？
— Nはら (@N___hara) 2019年12月5日
(←751位)
ワンチャンある！
（実は日経コン予選の時も当初のボーダー224位に対し229位と、繰り下がりが狙えそうな位置にいました。予選通過チキンレースがあったら優勝しそう）
数日後...
DDCC予選通過しました！！👍👍 pic.twitter.com/YTEUqknbD7
— Nはら (@N___hara) 2019年12月10日
無事予選通過、日経コンに次いで2つ目のオンサイト出場が決定しました。やったね
（今度はちゃんと安全圏で予選通過するようにしたい）
本戦
コードコンテスト部門、0完
装置実装部門、0完
終
その後
本戦の内容については上記の通りなので、詳しい解説は他の参加者の方の参加記をご覧ください（丸投げ）
今回のDDCC2020本戦では、↓のシャツを貰いました。念願の初シャツGETです。
（去年は青色？だったっぽいです）
それとお昼の特別ビュッフェ、おいしかったです。（パスタ大量に食べたりチョコフォンデュしたりしてた）
コンテスト後、装置部門決勝進出者が再コーディングしている間にDISCOの社員さんに連れられ会社見学へ。ウエハーを切断する機械とか大きいプールとか社員寮とかいろいろなお話を聞きました。楽しい。
（写真を取り忘れたので、詳しくは他の参加者の方の参加記をご覧ください）（丸投げ*2）
それから装置実装部門決勝。非常にざっくりいうと「装置で水を運ぶ」というテーマですが、ほぼ最適解でどんどん水を運ぶ人や重力加速度を考慮して設計している人とかがいてすげぇとなってました。マラソン（競プロ）練習もしなきゃね。
懇親会。今回もいろんな人に会いました。名刺も配りました。
（名刺からフォローしてくださった方、ありがとうございます！）
北大生ともエンカできました。北大内で会うより先に東京で会いました、謎。
まとめ
オンサイトはいつ行っても楽しい。最高。また行きたい。（もちろん0完じゃなくて）
期末テストとレポート、耐えられるかなあ...（白目）
日経コン（第二回全国統一プログラミング王決定戦） 参加記
競技プログラミング界隈で、参加したコンテストについての感想や反省をまとめた「参加記」を書く人を多々見かけるので初オンサイト記念に自分も書いてみようと思います。（そもそもブログを書いたことがないのでところどころ駄文が見受けられる場合ががあります。それでもいい、という心の広い方のみお付き合いください。）
初オンサイトまでのいきさつ
1.11/09(土)に開かれた予選に参加した。
2.問題を解いていったら、なぜか700点問題を通した。
3.予選（国内）229位→繰り下げの続いた結果ギリギリで出場。
こういう感じにすると書くことがなくなるので、少しだけ予選（の問題）について。
A(100),B(300)はいつも通りくらいのペースで通して、残った問題は
C(600),D(600),E(700),F(1400)（残り100分程度）
この中で1問解ければいいやー、と考えた結果、
Fは論外（解けない）→Dはグラフ、得意じゃない→Cは解けそうなのにACできない
→E（消去法）。
（Eは見たところアルゴリズムの知識は必要そうではなくて、数学の要領でごり押せるとふんだのもある）
数値の選択方法を色々いじって（ついでに4WA出して）みるとできそうな方法がみつかり、無事AC。
コンテスト内外合わせても700通したことはなかったので、ほんとに鳥肌立ちました。びっくり。
こうして無事に初オンサイト出場。
本戦
本戦は会場独特な雰囲気？的なものがあってか緊張しまくり、タイプミスがそこそこ出る（普段は出ないとは言ってない）。
A(200)は最初に(i,j)のペアと(j,k)のペアを求めようと考えていたが、実装がうまく形にできず断念。その直後jを固定して(iの候補数)×(jの候補数）を数えて行けばよいことに気づく。
B(300)は方針がぱっと思いつかず考え込んでいたが、S2とS6をまず固定してS3S4S5の形がとれるかという方法ならいけるのでは、と思い実装。実行時間が危なめだけど通った。
D以降が800以上でしんどそうなのでC(600)に取りかかる。いろいろと試行錯誤するも
計算量がO(min(H,W)×HW)程度までしか落とせず、ここで終了。
結果は48分2完で170位でした。とりあえず大半の人が取れた問題はこぼさなかった、ということで一安心。(レート順位が199位/200人中なので変な気負いはなかった、緊張はしたけど)
懇親会
表彰式も終わり懇親会スタート。スタート時点で知り合い0の状態でどうしようかな、と思っていたが勇気を振り絞っていろいろな人に声をかけてみる。最終的に十数人くらいとは話せたので大満足。とても楽しかった。（とある方に「名刺あるといいかも」といわれ持って行ったのもよかった（結構好評だった）。アドバイスありがとうございます。）
結論
オンサイト、最高！！！
（1/25のDDCC本戦にも出られることになりました、対戦よろしくお願いします）
