競技プログラミング - redultimate/utility GitHub Wiki

目次

テクニック

  • 数列の部分和が関係する場合は累積和を計算しておくことで計算を軽くする.
    • 特にこれを累積和で解くのは発想が天才すぎる. 二次元累積和を使う.
  • 複雑な場合わけが必要な場合, 必ず何か間違えている.
    • 大抵の場合例外処理でミスって, 後半だけうまくいかないとか, 1問だけWAとかになってしまう.
    • しかもdebugに時間を取られて全体の特典も下がってしまう.
  • 各桁の数値を足す場合は2つパターンがある.
    • 10で割りながらそのあまりを抜き出していく.
    • stringに変換して1つずつ抜き出し, 計算するときにintに戻す.
  • 10^9+7で割ったあまりを求める場合
    • 足し算, 引き算, 掛け算は各ステップごとにやる.
    • 複数同時にやらない.
    • 引き算する時は-のままになる可能性もあるので最後の処理に注意する (ABC130Eで最後それでひっかかった).
  • long long使う問題はよくあるので以下を使う.
    • ただし, llが関係するmin, max, absは使ってはいけない. やるなら自分で書く.
typedef long long ll;
  • 周期系の問題はmodを使うと簡単にできる場合が多い.
  • まずは全探索を考える.
  • 何かの操作をするときには, 「変わらないもの」を見つける. それがアルゴリズムの根幹になることが多い.
  • 変数定義はint mainの外に書こう. 特にEDPCのFの実装の時に, int mainの中に2次元配列の定義を書いたらセグって解決できなかった.
  • DPで使う, minかmaxを選ぶやつ. ここを参考にした.
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
  • XORについて
  • 答えが実数の場合.
    • 何も考えずに出力すると相対誤差の関係でWAになる.
    • 相対誤差が1e-9の場合は例えば以下のようにする必要がある.
#include<iomanip>
using namespace std;
cout << fixed << setprecision(10) << ans << endl;
  • 関数を定義する場合, 参照渡しにしないととても時間がかかってTLEになる. ABC119Dでそれがわからないためにアルゴリズムがあっていても全完逃した.

計算量

  • 参考
  • 必ず計算量を見積もる. 計算量を見積もらずにコードを書き始めない.
  • 10^9のループはやらない
    • arrayじゃなくてmapをとかを使って存在する値のみについてのループを考える.

60527.jpg

  • チートシート
    • 二分探索: O(logn)
    • マージソート: O(nlogn)
    • bit全探索: O(n2^n)
      • 動的計画法: O(nA)

参考

競技プログラミングサイト

競技プログラミング全般のブログなど

Advent calendar

便利ツール

Codeforces

解説ブログ

To do list

精進

復習してない問題

  • Tenka1 2019 D
    • テストといくつかは正解したが他の多くはWAで原因がわからない. 考え方は合っているはずなので実装か. 時間がかかるので一旦諦める.
  • グレイコード
    • AGC031C
  • 文字列DP
  • CF545Div2C
    • CF545CのTLEが解決できなった. 要復習.
  • ECD61Div2C
    • 解けそうで解けないこういうのを確実に解けるようにしたいと思ったECFであった. Cの復習をしよう.
  • CF542Div2D
  • AGC030B
  • AGC030D
  • NIKKEI-D
    • 初トポロジカルソート
    • ついでにトポロジカルソートの勉強する
  • AISing-D
    • 正確な実装力が試されるらしい. 定期的にやるといいかも.
  • AISing-E
    • どうやら珍しいDP問題らしい. EDPCが終わったらやってみよう.
  • KEYENCE-E
    • 最小全域木であることはわかったが, 計算量減らせず. 合わせて最小全域木の勉強もしておこう. 類題解いたり.

いま勉強の必要性を感じていること

反省

  • ABC120は心構えとして、今の僕の弱点として重要.
    • 調子に乗ってDから解いたけど, 通らなかった. 理由は1e5を超える数のかけ算をする時はかけ算の答えだけじゃなくて中身もlong longにする必要がある.
    • また, Cももうちょっと頭を使えば一瞬でできた. 最後の形を推定すること.
    • 必ずなんとかとして最大数の試験はサンプル以外にやること.
    • 全部解けたのに減点が30min以上というゴミみたいな感じになってしまった.
  • 見かけ倒しに注意しよう.
    • 例えばAGC031Aは文字列DPかと思って頑張ろうとしたが, 実際は中学受験算数であった.
  • ABC123Dも今の僕の弱点として重要.
    • 計算量的に何か工夫が必要となって, それ以降何も思いつかなかった.
    • 冷静に考えれば今まで習得したはずのツールでできるはずだった.
    • しかも, それを使わなくても最初の2つの和の上位K個を選んでくれば計算量は十分抑えられた. なぜ気づかなかったんだろう. それにこの問題が解けなかったせいでratingも下がってしまった. 本当に悔しい.
    • いろんな解法があるという点でもとても重要な問題.
  • Tenka1 2019も今の僕の弱点
    • 結局解けたが, Cで早とちりしてミスりまくって時間を浪費しまくった. ちゃんと考えれば一瞬だった. こういうので取りきれないとレートが下がってしまう. 上がらないのはまだいいが, 下がるのは許せない.
    • それにDも方針は合っていた.
    • ここら辺の300から600あたりを速く確実に解けるようにならないと停滞してしまう.
⚠️ **GitHub.com Fallback** ⚠️