競技プログラミング AtCoder茶までのチートシート

本投稿について

主にAtCoderで茶色までの、灰色でC問題で結構ぶつかるくらいの人向け。私も結構ぶつかるので、より明るい色から照らしてあげるような内容ではありませんのでご容赦ください。

これをそばにカンペとして置いておくとCに挑みやすいかな？という感じです。

計算量について

・10000000000はNG（10の5乗の2重ループ→10の10乗はだめ）
・625000000はOK（25000の2乗）
→10**9→1000000000までならワンループはいける？ そのあたり投稿主もよくわかっていません。

チートシート列挙

・余りを求める（%)

・1個を決め打ちする
3重ループになりそうなときの1つだけ決め打ちしてから全探索など

・バケットを検討する
l=n*[0]

・そっちで回さない
別視点での全探索の検討

・とりあえずリストはソートできないか？
ソートしないまま行うのではなく一旦ソートしたほうが処理が容易にならないか？

・途中結果のみを保持しておいて最後に連結する考え方
1個ずつ愚直に操作するとTLEになるケース

・実際のリスト、位置を記録したリストという2リスト体勢で実際のリストをいちいち検索する負荷をかけない作戦
[1,2,3...]という単純なリストで有効

・実際に移動させるとTLEになる場合は「移動した」という情報だけを別に持っておくことで計算量の削減になる

・dictを検討する
・Collections.Counter
・defaultdict

・itertoolsを検討する
・product（直積でパターン列挙、bit全探索にも）
・accumurate
・conbinations
・連長圧縮っぽい挙動のときにgroupbyの検討

・尺取り法っぽいときにdeque
・幅優先でもdeque

・常に変化するリストの最小値を求める場合はheapqが最速で最強

・bisectを検討する
リストの適切な位置に挿入したい場合

・math.comb

・math.dist
対角線の長さ（ユークリッド距離）

・2点が与えられたときに片方の点から片方の点への「移動」という考え方

・デフォで1や0やブーリアンFalse型のN個のリストを作って最終的にsumする手法
個数をカウントする場合に

・問題のタイトルにヒントがある
Prime：素数、Knight：将棋の桂馬 などなど

・図形問題で進行方向を取るときに方向の1か0の配列を用意する
右、下、左、上
[1,0,-1,0]
[0,1,0,-1]

・setの差集合、norの活用

・リストの転置（縦横逆）はzip関数と＊で簡単にできる
リンク
nkmk