AtCoder 用リポジトリ

始め方

やりたい問題を見つけ、ルートディレクトリにて新しいコンテストディレクトリを作成する

acc new <contest-id>

各ディレクトリにて作業を行う
ローカルでテストを行う（ctrl + e）
テストが通れば、コードを提出する（ctrl + s）

オンボーディング

環境構築が終わったら、以下の URL のおすすめ問題を 1 日 1 つずつ解き始める。 https://qiita.com/drken/items/fd4e5e3630d0f5859067#%E7%AC%AC-1-%E5%95%8F--abc-086-a---product-100-%E7%82%B9

おすすめ問題を解き終わったら大会に参加しつつ、蟻本を進めていく。 https://qiita.com/drken/items/e77685614f3c6bf86f44

まだ全然、全探索の応用問題をサッと解くことができなかったので以下の問題集をやる https://qiita.com/e869120/items/25cb52ba47be0fd418d6#3-2-%E9%A0%86%E5%88%97%E5%85%A8%E6%8E%A2%E7%B4%A2

再帰関数を用いた方法についての解説は以下を参考に（練習問題もあるので時間がある時に解くと良さそう） https://qiita.com/drken/items/23a4f604fa3f505dd5ad

dfs の幾つかの例があるので、以下を参考にテンプレート化するのが良さそう。 https://franknyro.github.io/blog/archives/202005031749/

累積和についても勉強する https://qiita.com/drken/items/56a6b68edef8fc605821

しばらくは「競技プログラミングの鉄則」をやる https://atcoder.jp/contests/tessoku-book

参考

c++の基本的な型や関数: https://somachob.com/basic-cpp/

登場単語

全探索

その名の通り、for 文などで全て探索すること。

バケット法

B 問題ではバケット法といって、配列 num を用意しておいて、 num[i] := 値 i が何個あるかを判定する方法。一度 0 埋めした配列を用意し、そこに出現回数を入れていく方法。

Greedy 法 = 貪欲法

貪欲法は局所探索法と並んで近似アルゴリズムの最も基本的な考え方の一つである。

このアルゴリズムは問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、評価値の高い順に取り込んでいくことで解を得るという方法である。動的計画法と異なり保持する状態は常に一つであり、一度選択した要素を再考する事は無い。このため得られる解は最適解であるという保証は無いが部分問題の解法と単純なソートのみでプログラムを実装することが可能であり、多くの問題に対して多項式時間での近似アルゴリズムとなる。

問題を複数に分割する方法は特に組合せ最適化問題と相性が良い。問題によっては厳密解（最適解）を得られたりするものや最低限の精度保証（近似度）が算出可能なものもある。このため、現在でもしばしば同問題の研究に用いられている。

幅優先探索

参考: https://algo-method.com/descriptions/114 問題: abc325/c

深さ優先探索

https://qiita.com/e869120/items/25cb52ba47be0fd418d6#3-3-%E5%86%8D%E5%B8%B0%E9%96%A2%E6%95%B0%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E5%85%A8%E6%8E%A2%E7%B4%A2

ビットマスク（マスクビット）

ビットシフト演算子を利用してマスクする方法 https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361

bit 全探索

https://drken1215.hatenablog.com/entry/2019/12/14/171657

動的計画法

ランレングス圧縮

ランレングス圧縮とは連続したデータを(値,連続する個数)として圧縮する可逆的データ圧縮アルゴリズム

便利な関数

詳しくはこちら https://qiita.com/e869120/items/518297c6816adb67f9a5

next_permutation

順列全探索を簡単にやってくれる関数(0,1,2 -> 0,2,1 -> 1,0,2)

ryomaejii/atcoder