Tsuna lab

国の端っこで---しながら競技プログラミングなるものをしてみます

【随時更新】AtCoderで過去に詰まった発想・知識集

コンテストや精進中に使えそうな知見を得る度に追加していきます。正確性は保証しません。

文字列操作

・反転操作→反転している状態かどうかだけを記録し、実際には反転を行わない

・文頭, 文末に対する追加削除操作→listではなくdequeを用いると早い

・辞書順でK番目のものを求める→左の文字から決めていく

グリッド

・はみ出るか否かの処理→S[max(0,i-1) : min(W,i+2)]で if 文の省略

 

数列

・A-BがKの倍数→AをKで割ったあまりとBをKで割った余りが同じ

区間の和→累積和orいもす法

グラフ

・AからBにいけるか(無向グラフ)→UnionFindが使える

・2回の移動で~→真ん中の街を基準に考える

〇〇探索

・操作が難しいけど制約が小さい→全探索

・3変数の全探索だと間に合わない→式変形して2変数の全探索(整数条件に持ち込む)

・調べたいデータに単調性(昇順or降順)がある→二分探索

・二分探索したいデータがリストで与えられている→bisectの利用

・最大値の最小化→決め打ち二分探索

全般

・AからBを作れるか判定せよ→Bから逆の操作をしてAに出来るか考えてみる。

・2択(ある・なし)で管理がしたいとき→bitで管理

・bit管理下で複数の要素が条件を満たしているか調べたい→AND/ORの利用

・問題を解くのに不必要な情報の簡略化→bitでの管理/座標圧縮

・for文のループが遅い→前計算の検討