programming contest

Pythonのitertoolsでできる全列挙のまとめ

Pythonのitertoolsモジュールには、イテレーションに関する便利関数が多数用意されています。この記事では、その中でも競技プログラミングで全列挙に使える関数についてまとめます。Python 2.x, 3.xのどちらでも使えます。 Google Code JamのSmallでは全列挙…

ピタゴラス数を無限に生成する

先日久しぶりに参加したCodeforces Round #368 (Div. 2) - Codeforcesの C. Pythagorean Triples が面白かったのでご紹介します。 問題 「正の整数aが与えられる。三平方の定理 a2 + b2 = c2 を満たす残りの 正の整数b, cの組を一組答えよ。そのようなb, cの…

グラフのすべての2頂点間の最短路をワーシャルフロイド法で求める

ワーシャルフロイド法というのを使うと、グラフのすべての2頂点間の最短路を求められるらしい。蟻本を参考にして解いてみた。以下のグラフを例にとって、全点対の最短路を求める。 コードは以下。 #include <cstdio> #include <algorithm> #define REP(i,n) for(int i = 0; i < </algorithm></cstdio>…

C++で、重複順列を全列挙する

異なるn個のものから、重複を許してr個を取り出して列をつくることを、n個からr個とる重複順列という。これをC++で全列挙することを考える。例題として、1〜5の数字を使ってできる3桁の数字を全列挙することを考える。そのコードは以下の通り。 #include <iostream> #i</iostream>…