競技プログラム（AtCoder）の精進まとめと復習用リスト

最初に、このブログはレーティングが黒色の状態から書き始めているので初心者レベルの記事で、自分用に情報をまとめるものです。

この記事ではAtCoderの過去問を解いていき、新しく学びのあった問題に関して記録を残します。コンテスト前の復習を効率化するために、問題とTIPのペアを記述します。手法とは別に実装がスムーズにできなかったもののリストも作成します。

記述してある問題はすべてＡＢＣのものです。

〇ABC163～ABC126に関して

C. Count Order：順列の作成 

C. HonestOrUnkind2：ｂｉｔ全探索

C. Green Bin：文字列（ｓｔｒｉｎｇ）に対するソートとｍａｐの組み合わせ。

C. Traveling Salesman around Lake：数列が円の場合のイメージの補強。

C. Sum of gcd of Tuples (Easy)：最大公約数の性質とユークリッドの互除法

C. Snack：LCM（最小公倍数）の求め方と実装。

以下、歯切れ悪く実装してしまった問題。手法云々でなく、再度チャレンジして実装に慣れたい。

C. Guess The Number

C. Welcome to AtCoder 

C. Next Prime （簡単に通せたが、解説で一部不明点あり、Youtubeをみる）

＃ABC136～ABC126は半年以上前（４／２４現在）に解いているのでもう一度解きなおして、ここに情報をまとめる。しかし、その前にD問題に着手する。

D. Megalomania：vector<pair<int,int>> に対するソートとデータアクセス。（first,secondの優先順位で昇順になる）

D. Dice in Line：期待値の簡単な性質。累積和の扱い。

D. Banned K：大きな数同士の計算は long long で扱う法が良い。組み合わせ計算の関数をint にしてバグらせていた。問題の論理は簡単。

D. RGB Triplets ：問題の条件を分割して考える。捜査対象が多い場合、対象の補集合を考えるとループの数が下がる場合がある。j-i != k-j  ⇒ k=2j-i は汎用性がありそう。

D. String Formation：deque コンテナの利用。先頭へのpushがvectorなどに比べて高速。reverse(deq.begin(),deq.end()) での要素の並べ替えも便利であった。問題分はよく読むこと。

D. Prediction and Restriction：RGB Triplets とほぼ同様の問題なので、すぐに解けた。（この問題を行っておけば、RGB Triplets も解けると思うが、両方ともdiffが700程度なのを考えると、まじめに過去問を解いている人数は思っているより少ないのかもしれない。）

D. Triangles：二分探索を利用。lower_bound(a,b,x) （ab間でx以上）とupper_bound(a,b,x) （ab間でxより大きい）はvectorに対する探索を簡単に実施できるので使いこなせるようにしておく。返り値のイテレータは、イテレータ同士の演算でスカラに変換可能。また単調増加／減少の値から何かを探す際はすぐに二分探索を疑う。

D.Ki：深さ優先探索（DFS）と累積和の考え方を用いて解くと簡単。DFSの実装は簡単だが、コンテストでスムーズに実装できなさそうなので反復する。

D. Knight：おおよそ理解しているが、最後のコンビネーションのmodをとるところが

今一つ理解できていない。フェルマーの小定理など利用する。理論はあとにしてまずはAtCoderが解説で作成したライブラリを利用して計算できるようにした。

D.Integer Cards：最終的な状態がどうなるかだけを考えて、その状態に対する集計を行う。比較的容易。map（コンテナ） を逆から捜査する場合、rbegin() から rend() までをfor ループに指定すればよい。イテレータをデクリメントするのでなく、インクリメントすることに注意する。

D.Preparing Boses：基本的には配列を逆から処理することに気が付いたら終わり。異常系の-1出力は、存在しないことにコンテスト中に気が付かないとそれに対応するケースを考えてしまいそう。なんとなく、ないと気が付いたら一度提出してみるのもありかもしれない。

TBC ...