はじめに
- コンテスト最中に頭に留めておきたいこと
- コピペで使えるコード(アルゴリズム、標準入力、イディオム、標準ライブラリ)
をまとめました。コンテストのお供としてお使いいただけたら幸いです。
頭に留めておきたいこと
解法が全く思い浮かばない
問題文をよく見る
- 問題文の誤読をしていないか確認しましょう。
- 制約条件をよく読みましょう。
- あなたが棄却したアルゴリズムで十分間に合う可能性があります。
全探索について考察する
- 全探索の計算量を見積もりましょう。間に合う可能性があります。
- 簡単なケースの全探索を考えて、無駄な処理を発見しましょう。どうすれば効率よく探索できますか。
- 全探索を考えながら、問題を誤読していないか確認しましょう。
何かを固定する
- 何らかの要素(次元)が数個の場合は固定を考えます。
- 端を固定する。
- 三つの場合、中央を固定する。
- 何らかの要素(次元)が数個の場合は固定を考えます。
逆からシミュレーションする
- 追加ではなく削除、削除ではなく追加。グラフ問題でよくある
書く
- サンプルケースやそれより小さいケースを自分で考えて、紙とペンを使って書きましょう。
ローカルでエラー
- エラー文をよく読む
- 配列外参照をしていないか
- タイプミスをしていないか
- テストケースを正しくコピペできているか
- 実行しているプログラムファイルは正しいか
サンプルは通るけどWA
- 嘘解法で書いていないか
- 自信がないのであれば、解法が正しいか検証をしましょう
- 入力される型の確認をしたか
- 整数か浮動小数点か
- 配列のサイズは十分か
- デバッグ用にと、不十分なサイズで確保していないか
- 特殊な値での確認はしたか
- 0, 負の値, 最大の値
- MODのタイミングは適切か
- 最後にもMODの計算しているか
- 精度は十分か
- 特に小数の出力
- 再帰関数の呼び出し回数は大丈夫か
その提出、ちょっと待った!
- printデバッグはきちんと消したか
- 言語選択を間違えていないか
- 提出する問題を間違えていないか
- 提出するコードを間違えていないか
- 軽微な修正だから・・と思ってテストし直すのをサボっていないか
計算量の目安
1 | 10^7 余裕を持って間に合う |
計算量オーダーの求め方を総整理! 〜 どこから log が出て来るか 〜より引用させていただきました。
Python
の場合、この数倍から10倍程度遅いと思っておけば良いでしょう。PyPy
の場合、2,3倍程度で済むと思います。
コピペで使えるコード
アルゴリズム一覧(Python)
こちらのページにまとめています
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】に沿う形でPythonで問題を解いています。各記事のコードをライブラリのように利用できるはずです。(間違い等あればTwitterまでご連絡ください。)
- 全探索:全列挙
- 全探索:工夫して通り数を減らす全列挙
- 全探索:ビット全探索
- 全探索:順列全探索
- 二分探索
- 深さ優先探索
- 幅優先探索
- 動的計画法:ナップザック DP
- ナップサックDPまたはその亜種
- 動的計画法:区間 DP
- 動的計画法:bit DP
- 動的計画法:その他
- 最短経路問題:ダイクストラ法
- 最短経路問題:ワーシャルフロイド法
- 最小全域木問題
- 高速な素数判定法
- 高速なべき乗計算
- 逆元を使う問題
- 累積和
- いもす法
- Union-Find
- その他のテクニック
- 圧縮
- 単純な幾何計算
- 実装問題
- 数学的な問題
標準入力
intを1つ
1 | N = int(input()) |
intを複数
1 | a, b = map(int, input().split()) |
intのlist
1 | A = list(map(int, input().split())) |
イディオム
二次元リストの初期化(M列N行)
1 | visited = [ [0]*M for _ in range(N) ] |
二次元リストの転値
1 | def transpose(A): |
標準ライブラリ
itertools.combinations
1 | from itertools import combinations |
itertools.combinations
1 | from itertools import product |
終わりに
最後までご覧くださり、ありがとうございます!随時更新していきます!
改善点をドシドシお待ちしておりますので、お気軽にTwitterにご連絡ください。
記事情報
- 投稿日:2020年5月21日
- 最終更新日:2020年5月21日