Atcoder Beginner Contest D埋めしたので初心者向け学習法とか色々書く

f:id:inmir:20170722161554p:plain

 

今年の3月頃から競プロを始めましたが、ようやくABCのD(だけ)が埋まりましたので復習がてら色々書いてみます。

 

f:id:inmir:20170722164411p:plain

↑ 記念の初AC

 

 【やったこと】

・序盤

競プロの存在をAtCoderで知ったので、AtCoderの問題を解いていました。

for, if文ならかける程度の初心者でしたので、上の画像くらいA,B,C問題を解いていき(Cのいくつかくらいまでならfor,if文知識で解ける)、D問題を数問みて新たに勉強が必要だな、と感じました。

 

・中盤

蟻本を読みました。五日間くらいかけて(難しい所をとばしとばしで)中級編まで読みきって、その後AtCoderの問題を解きながら、やったことのあるアルゴリズムやデータ構造を見ながらでも書いてみるといった使い方でした。なんで蟻本の問題自体は解いてないです。でも解いた方が力になります。

「そんなん蟻本にも書いてなかったし(半ギレ)」→載ってる、というのを10回くらい繰り返しました。

 

・今とか

とりあえずコンテストを増やして、今はAtCoderTopCoder, Codeforcesに参加するようになりました。やっぱり実際のコンテストに出るのが一番楽しいし、問題を解くモチベーションが上がります。あと、普通にAtCoderの難易度は他と比べても遜色ないです。のでAtCoderに参加してるなら他のにもバンバン出た方がいいと思います。TopCoderはちょっと設定が面倒ですが、解説サイトは色々ありますし、CodeforcesAtCoderと同じ感じで登録するだけです。

蟻本は継続して読んでいます。最近あった「そんなん蟻本(略」はgrundy数でした。

 

【オススメ勉強法】

全くの初心者だった自分の経験から、もう一度競技プログラミングを始めるならこういう感じで学んだらいいんじゃないかという順です。教材はAtCoderとします。

 

ABC の A~Cくらいまで

⑴標準入力、出力が出来るようになる

⑵データ型(int, char, bool)、配列、for文、if文が書けるようになる

STLを使えるようにする(+計算時間を考える O(N) )

 C++ なら string , vector , set , map , priority_queue ...

 Javaなら String, ArrayList, LinkedList , HashSet , HashMap ...

などなど

 

 

1,2,3の順でABCのA,B,Cに対応している感じがします。本当か?

特に、競プロをしだすとアルゴリズムやデータ構造の方に目が行きがちになると思いますが、特に初心者のうちはしっかりとSTLの知識をつけた方がいいと思います。というかやっておかないと色々話になりませんでした...。

最初の内はおおまかにどんなことが出来るか、ということを勉強するといいと思います。慣れてきたら、コンテナクラスのランダムアクセス、追加・削除、検索といった計算時間も知っておくようにしましょう。ArrayListとLinkedListの違いくらい知っておきましょう(3時間くらいTLEに悩まされました)。

ちなみにC++STLを勉強するならこの辺がオススメです。(C++ 標準ライブラリ の項目)

C言語/C++ プログラミング 入門

 

ABC D

(1)アルゴリズム・データ構造をサッと勉強する

(2)問題を解く、分からなかったら復習する

(4)ライブラリを作る

 

問題を解きます。問題を解きましょう。後は問題を解くだけです。

問題を解きますが、特に初心者のうちはよく言われることですが、20分くらい考えて解けなかったら解説を見た方がいいと思います。

最初のアルゴリズムとデータ構造の勉強は、結構サッとやった方がいい気がします。真面目に実装とかやると滅入ります。ただ、何も知らずに問題を解こうとすると、全点対間最短距離問題(コードで精々2,3行)に1時間以上悩んだ挙句解説見て勝手にキレます。なのでサッと。

ちなみに、体感的にABC-D問題解くにあたって優先順位の高いデータ構造・アルゴリズム、テクニックは下の感じ。上の方が高い。

・DP

・累積和、imos法

・UnionFind木

・bit 関係 (選ぶ・選ばないの2択を全探索するときなど)

・mod 関係(フェルマーの小定理

・二分探索

 

DPは本当に色んなところで使いますので、最初に典型問題解くといいかも。

Typical DP Contest - Typical DP Contest | AtCoder

(本当にAtCoderさんは教材として優秀...)

それと、一回使ってライブラリにできそうなもの(segtree , dikstra , nCm mod p etc...)は一回やったら作っとくといいと思います。他の人のを借りてもいいけど、自分で実装した方が使いやすいし勉強になりますし、構造や処理をカプセル化する能力もつきます。

 

【現状】

f:id:inmir:20170722235319p:plain

割とザコいですがこんな感じです。ただDをたくさん解いてみて、後半になるほど実装力とか知識とか増えてきた実感があるので、最近右肩上がりを達成できるんじゃないかと思ってます。いつまで続くのか......

次はARCのA,Bかな...今年中にTopCoderのイエローを目指してます(言うは易し)。