競プロ歴３か月の経験談

競技プログラミング

AtCoder最初の提出から３か月が経って（since 2018/07/12），ABCのA，B，C問題と300点問題を全部埋めたので，ブログを書きます．皆さんの参考になれば幸いです．

 

今までのレーティンです

 

 

 

競技プログラミングを知ったきっかけ

私は今年の４月から大学に入って，プログラミングを勉強し始めました．ラッキーなことに，大学では，競プロに一番（?）有利なC++を最初の言語として教えました．

入学して間もなく，掲示板から，「ACM-ICPCがあるよ」という広告を見て，とりあえず参加してみることにしました．ICPCを準備していたとき，「競技プログラミング」という単語（分野）を知り，興味を持ち始めました．

 

ICPC国内予選

ICPCでA問題とB問題をACすることができました．C問題は後々からしゃくとり法を使って，簡単にできることを知ったが，その時はまだアルゴリズムの知識を何も持ってなかったので（言い訳）できませんでした．

印象に残ったのは，A問題は試合開始５分くらいでできて，B問題は試合終了５分以内でできたことでした．ラスト５分でB問題を通したとき，心の中のドキドキと体の震えは試合が終わった後も続いていました．

 

順位は低かったけど，ICPCの経験から，競技プログラミングのスリルさと面白さを覚え，競技プログラミングを始めることにしました．

 

競技プログラミングを始めました

ネットでいろいろ調べていたら，satanicさんの記事（競技プログラミングを始めて1年が経ちました - sataniC++）を参考に，yukicoderとAtCoderを始めることにしました．

 

Phase I: yukicoder ★問題

その時，コンテスト形式に少し恐怖心を持っていたから，気軽にできるyukicoderの問題を埋めていた．最初は★問題をひたすら解きました．ちょうー暇でしたので，５日を使って★問題を全部埋めました．自立でできない問題があれば，他人のコードを読みました．★問題を埋めることによって，C++言語の基本的な使い方を習得しました．特に基本の基本であるSTLの使い方やコードを短く・簡潔に書く方法などは最短コードを読むことによって知りました．

 

 

★問題で必要なのは文字列操作の基本知識，基本的な数学の考え方と基本的なプログラム実装技術だと思います．

 

※そこで，競技プログラミングを始めて何がメリットがあったかというと，大学でのプログラミング系の授業はとても楽になりました．（いわゆる「地頭」を少し持っているのは否定しませんが，スラスラとコードを書けるようになるため，練習量も一つの大切な要素だと思います．）

 

Phase II: AtCoder Beginner Contest A，B問題

★を解き終わって，★☆問題に入りましたが，問題を解くスピードがドンと落ちてしまいました．なぜなら，★☆問題はすこし頭を使わないと解けない問題ばかりでしたからです．そこで，簡単な問題を求める私は，AtCoderのABC-A問題に手を伸ばしました．

 

 

そして，ヒマな私は半月くらいでA問題を全部埋めました．

さらに，夏休みに入って，より暇になった私は半月くらいでB問題を埋めました．

 

もちろん，A, B問題を埋める途中ABCもできる限り参加しました．運がよければ，C問題を解けるときもありました．

そして，B問題を埋める段階で，茶色になりました．

 

 

ここで，実力につながったのは，「難しい問題を考えること」だと思いました．B問題までできて，C問題ができないときはコンテスト後，解説や他人のコードを見て，C問題を理解しようとしました（どうしても無理な時も，潔く諦めることも大事）．そして，C問題ができて，D問題ができなかったときはD問題を理解しようとしていました．

難しい問題を理解しようとする時，今まで見たことのないアルゴリズムや考え方を知ることができます．後々難しい問題を攻略しようとしたときに，「以前似ているものを見たことがあるぞ！」と親近感を持って，抵抗感なく勉強することができると思います．

 

AtCoderは初心者に優しいサイトだと思います．ABCに典型的な問題が多く，「この問題を解いたら，このスキルが習得できる」という問題が多くみられます．A問題が入力と出力の問題，B問題は繰り返しや条件分岐を実装する問題が多いです．

 

Phase III: AtCoder Beginner Contest C問題

結果から言うと，C問題を埋めるのに，2か月くらい使いました．

B問題からC問題のギャップが深すぎると感じ，C問題が全然解けなくて，苦しんでいました．

 

しかし，C問題を通じて，自分が大きく成長したことも実感しました．新しいアルゴリズムを自立で実装してACしたときの心地よさは，また競プロを続ける糧にったと深く感じています．

 

 

C問題から，数学の問題（組み合わせ，mod関係，算数，数え上げ）やアルゴリズムの問題が出てきました．そして，実装面も（C++の場合），STL（map, vector），int以外の型（double, long long, pair）などを使うようになりました．

アルゴリズムは大体基礎的なものと教科書的の典型問題のレベルだと思います．以下のものをどんなものなのかを知り，典型の実装ができればC問題を制覇できると思います．

　　　DFS（深さ優先探索）

　　　BFS（幅優先探索）

　　　bit探索（すべての組み合わせを探索）

　　　累積和・いもす法

----------------------------------------------

昔の回（日本語タイトル時代の問題）では難しいアルゴリズムを扱っている問題もあるが，今の時代ではABC-D問題以上の難易度な気がします（まだ到達していないので，分かりません）

　　　DP（動的計画法）※昔のABCに１~2回しか出てないと思います

　　　フェルマーの小定理

　　　最短経路問題

 

【Twitter】

C問題を解くときに，Twitterで解法をツイートするようにしました．自分がどのようなアルゴリズムや方法でACしたかを記録することによって，知識を定着させました．

 

 
【アリ本】

そして，アリ本の最初の部分も読みました．難しくて，理解できませんでしたが，「このような考え方もあるよー」くらいの理解具合で大丈夫だと思います．そして，DPの部分になると，日本語も内容もさっぱりので，いったん放置しました．

結局，DPより前の知識を知っているとC問題は十分解けます．

そして，知識を定着するため，けんちょんさんの「AtCoder 版！蟻本 (初級編)」を参考に，DP以前の部分の問題を解きました．（その中に，400点以上の問題もありました）

 

【モチベーションを保つ方法】

心理面で，前文で述べたように，苦しんでいました．C問題が全然自立で解けず，解説や他人のコードを見ても理解できず，一つの問題をずっと考えて寝落ちて，夢の中でもその問題を考え続けた時期がありました．

そこで，Twitterの競プロerたちの精進ツイートを読んで，できる人たちのレートやAC問題数を見て，「ほかの人も頑張っているから」，「できる人はみんなそう苦しんできたから」，「問題を積み重ねるとできるようになる！」っと自分に言い続け，モチベーションを保てました．

 

 

そして，苦しいひと時を終え，9月のABC109ではじめてABCD全完しました．ABC111でABCとD問題部分点を取り，26位で，緑色になりました．

 

 

そして，現在

C問題を埋めた後，AGCのA問題（ABCのC問題と同じくらいの難易度）と，ARCのA問題を埋めました．体感難易度的にはABCのA~B問題くらいだと思います．C問題を全部埋めればこのくらいの問題は楽勝です．

現在，ARCのB(D)問題を埋めています．全部埋めたら，またほかの記事で経験を紹介したいと思います．

 

そして，9月からCodeForcesとTopCoderにも手を伸ばしましたが，CoderForcesとTopCoderの問題の傾向はまたそれぞれ違います．

 

これからも，レッドに向かって一生懸命頑張りたいと思います！