水色になりましたので学びを整理します

はじめまして、ねてるくんと申します。

AtCoderを初めて約3ヶ月、ABC123で水色になれましたので今までの勉強内容を整理します。

f:id:neterukun_cd:20190414143925p:plain

 

 使用言語はPython3です。C++を勉強する予定は当面のところないです。

 

覚えたアルゴリズム

・深さ/幅優先探索（DFS/BFS）

グラフや2次元グリッド上を全探索したいときに利用します。実装には両端キューdequeによるスタック/キューを使います。再帰関数を用いた深さ優先探索もありますがコンテスト本番では実装できた記憶がないです（再帰関数が苦手です…）。

  

・貪欲法

ソートして前から/後ろから順番に考えていきます。難しい問題では、何を基準にソートすれば貪欲に解けるか分からなくなります。貪欲法のための勉強はあまりしませんでしたが、区間スケジューリング問題は知っておくと様々な問題で応用が効きました（区間の重なりが問題になるときによく使えます）。

  

・メモ化再帰、動的計画法（DP）

計算結果の再利用や、漸化式の作成によって計算量を落とせます。難しいです。「再帰の動作を正しく把握する」「状態を同一視してまとめる」というのがとても苦手です。DPまとめコンテストでナップサック問題、LCS、累積和によるDP高速化などを勉強しました。

 

・UnionFind

「2つのグループをまとめる」「2つの要素が同じグループに属するか調べる」をそれぞれO(logN)よりも小さい計算量で実行できます。グループは木構造で管理されます。

グループのまとめ方として、木の高さrankを基準にした実装、木の大きさsizeを基準にした実装がありますが、どちらの方法でも計算量は変わらないようです[要出典です]。昔はランクを用いて実装していましたが、ABC120-Dを経てサイズによる実装をライブラリ化しました。

 

・累積和

任意の区間の総和を求める計算量をO(N)→O(1)にできます。頻出だと思います。添字をバグらせがちですが、2次元累積和まで書けるようになりました。

 

・いもす法

区間クエリを足し合わせるやつを、O(QN)→O(Q+N)にできます。Qはクエリ数、Nは区間幅です。たまにつかいます。

 

・二分探索

探索対象に単調性がある場合（ソートされている、条件を満たす満たさないの境界が一つだけ存在するなどの場合）に探索に必要な計算量をO(N)→O(LogN)にできます。次の2つの場面でよく使いました。

  1. ソート済みリストから値を探したい。
  2. 解を探す問題に対して、解を仮定して判定問題として処理したい。

1に関してはbisectモジュールを使うと容易に実装できます。

一方、2の方が重要っぽくて、めぐる式二分探索と呼ばれている方法によって簡潔に実装できます。典型として蟻本に載ってる最小値の最大化、最大値の最小化、平均値の最大化などを学びました。実践では二分探索を使えることに気づけ無いことが多々あり、「単調性」を意識しておくことが重要な気がします。

 

・最短経路アルゴリズム

ワーシャルフロイドだけ書けるようになりました（forループを3回まわすだけで実装が簡単なので）。ベルマンフォード法は未勉強です。ダイクストラ法は勉強しましたが忘れてしまいました。ABCの範囲ならダイクストラを使わずにDFSで対応できる問題が多いように思えます。

 

・その他、思考停止でライブラリ化したもの

 素因数分解、最小公倍数、最大公約数、ユークリッドの互除法、逆元を用いた二項係数のmod計算

 

取り組んだこと 

・過去問をたくさん解く

文法練習としてABCのAB問題を解き、基本的なアルゴリズムを身につけるためにCD問題を解いてきました。最近はARC056以前のARCのAB問題に取り組んでいます。

f:id:neterukun_cd:20190414155504p:plain

4/14時点で解いた問題です

・できる限り解説を見ずに過去問を解く

初見の問題に対する考察力を上げたいお気持ちなので、できる限り解説は見ない方針で問題を解いています。解けない問題は基本後回しです。しかしこの方法だと、解けない問題が放置されるので、苦手が苦手のままになってしまいがちです…

 

・蟻本を買って流し読みする

蟻本を持っていると安心感があります。中級編の3-2までを一部飛ばしながら流し読みました。

 

・Twitterを見る

モチベーションの向上になります。コンテスト終わった後は、他の方がどういう方針で問題を解いてたか学べます。困ったときは、強い方からアドバイスを頂けます。本当にありがたいです…

 

・コンテストに出る

コンテストで解けなかった問題は記憶に残り定着します。目先のレートよりも今後に向けた大事な知見が得られる気がします。近々だとABC122-Dが本番で解けなくて悔しい思いをしました。

 

取り組まなかったこと

・解の正当性を証明する

問題を解くときに、それっぽい解放が生えたらテンションが上ってすぐ実装に取り掛かってしまいます。結果、実装中に「あっ、これ嘘解法じゃん…」となりがちなので良くないですね、はい。 

ところで、証明って難しいです。アルゴリズムと同様に、証明にも背理法や帰納法などの典型が存在すると思うのですが、典型の使い時が理解できてないです。練習あるのみでしょうか…？

 

・AtCoder以外でのコンテストに出場する

とはいうものの、最近はyukicoderにときどき参加しています。海外のコンテストには参加してません（生活リズムがバグりそうなのに加え、そもそも仕組みがよく分かってないので）。

 

・読みやすいコードを書く

コーディング規約という概念を知ったので今後はそれに倣ってコードを書いていきます。

 

最後に

今年中に青色相当の実力をつけることを目指して頑張ります。