競技プログラミングコンテストのお供

はじめに

をまとめました。コンテストのお供としてお使いいただけたら幸いです。

問題文をよく見る
- 問題文の誤読をしていないか確認しましょう。
- 制約条件をよく読みましょう。
  - あなたが棄却したアルゴリズムで十分間に合う可能性があります。
全探索について考察する
- 全探索の計算量を見積もりましょう。間に合う可能性があります。
- 簡単なケースの全探索を考えて、無駄な処理を発見しましょう。どうすれば効率よく探索できますか。
- 全探索を考えながら、問題を誤読していないか確認しましょう。
何かを固定する
- 何らかの要素（次元）が数個の場合は固定を考えます。
  - 端を固定する。
  - 三つの場合、中央を固定する。
逆からシミュレーションする
- 追加ではなく削除、削除ではなく追加。グラフ問題でよくある
書く
- サンプルケースやそれより小さいケースを自分で考えて、紙とペンを使って書きましょう。

1
2
3

10^7 余裕を持って間に合う
10^8 おそらく間に合う
10^9 非常にシンプルな処理でない限り厳しい

Pythonの場合、この数倍から10倍程度遅いと思っておけば良いでしょう。PyPyの場合、2,3倍程度で済むと思います。

こちらのページにまとめています

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】に沿う形でPythonで問題を解いています。各記事のコードをライブラリのように利用できるはずです。（間違い等あればTwitterまでご連絡ください。）

1	N = int(input())

1	a, b = map(int, input().split())

1	A = list(map(int, input().split()))

1	visited = [ [0]*M for _ in range(N) ]

1 2	def transpose(A): return [list(x) for x in zip(*A)]

1 2	from itertools import combinations for m1, m2 in combinations(range(M),2):

1 2	from itertools import product for p in product((0,1),repeat=R): # bit全探索

最後までご覧くださり、ありがとうございます！随時更新していきます！

改善点をドシドシお待ちしておりますので、お気軽にTwitterにご連絡ください。