Atcoder灰色の為のアルゴリズムノート【2/3】

前回に引き続きAtcoder灰色から茶色になるために必要な知識をまとめたノートを公開します。

目次

  • はじめに
  • 並び替え列挙
  • 組み合わせ列挙
  • おわりに

はじめに

今回は、「全列挙」において非常に役に立つitertoolsライブラリの紹介をします。並び替え列挙、組み合わせ列挙は一から書くとなると茶色以下の問題と比べると複雑で難しいので、ライブラリを利用することを強く勧めます。

非常に汎用性が高く、高難易度帯(緑、水diff)においてもこれらを用いる問題が出題されるので必須といっても過言ではないでしょう。

順列と組み合わせの違いについては以下の記事を参考にしてください。
順列と組み合わせの違いと見分け方!公式や練習問題

#1 -> TODO
#2 -> 本記事
#3 -> 近日公開

「補足」の項では、アルゴリズムを説明したpythonの公式ドキュメントを紹介します。余力があれば見てみてください。

並び替え列挙

ある配列から並び替えを生成して列挙します。

・ソースコード

import itertools

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

for per in itertools.permutations(A):
    print(per)

・入出力例

入力

1 1 2


出力

(1, 1, 2)
(1, 2, 1)
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
(2, 1, 1)

5行目をfor per in itertools.permutations(A,2):に変更した場合

入力

1 1 2 4

出力

(1, 1)
(1, 2)
(1, 4)
(1, 1)
(1, 2)
(1, 4)
(2, 1)
(2, 1)
(2, 4)
(4, 1)
(4, 1)
(4, 2)

・説明

記述の方法は以下の通りです。
tertools.permutations(p,r)

  • 第1引数: リスト
  • 第2引数: 並び替えの数(記述しない場合は要素の長さ)

nPr個の並び替えを昇順に列挙します。各要素を区別しているので、同じ数列を含むことに注意してください(重複ではありません)。
上の例ではそれぞれ3!(= 6 = 3 × 2 × 1)個、4P2 (= 12 = 4× 3) 個出力されます。

計算量はO(nPr)かかります。nが小さくてもnPrは非常に大きくなることに注意してください。Atcoderの問題では並び替えを列挙することも多くあり、その時の制約はN≦10の時が多いです。10! = 3,638,800 ≒ 3×10^6 であるので、定数倍等を考えると、これぐらいの制約が限界だと考えられます。

・問題例

C – Count Order(abc150) (diff422)
C – Graph Isomorphism (abc232) (diff685)

・補足

並び替え列挙の公式ドキュメントです。

itertools.permutations(iterabler=None)

組み合わせ列挙

ある配列から組み合わせを生成して列挙します。

・ソースコード

import itertools

A = list(map(int,input().split()))
for comb in itertools.combinations(A,2):
    print(comb)

・入出力例

入力

1 1 2

出力

(1, 1)
(1, 2)
(1, 2)

・説明

nCr個の組み合わせを昇順に列挙します。各要素を区別しているので、同じ数列を含むことに注意してください(重複ではありません)。

記述の方法は以下の通りです。
itertools.combination(p,r)

  • 第1引数: リスト
  • 第2引数: 組み合わせの数

計算量はO(nCr)かかります。これも順列同様nが小さくてもnCrが大きくなることがあります。

・問題例

C – Monotonically Increasing (ABC263) (diff298)
C – Make Takahashi Happy (ABC293) (diff431)

・補足

組み合わせ列挙の公式ドキュメントです。

itertools.combinations(iterabler)

おわりに

おまけ程度に今回紹介した並び替え列挙・組み合わせ列挙の高難易度の問題も紹介します。興味があれば解いてみてください。

D – Send More Money (ABC198) (diff1224)
D – Unique Username (ABC268) (diff 1309)

今回で灰色帯のアルゴリズムの紹介を終わりにしたいと思います。二分探索、動的計画法などの有名なアルゴリズムはかなり有名で多くの記事で書かれているのでここでは省きます。

第一回でも述べた通り、Atcoder灰色は「基礎的なプログラミング文法」をマスターすることが最重要です。沢山コーディングを経験してプログラミングに慣れて、プログラミングに対しての理解度を深めてください。
次回は早解きに関するtipsを紹介したいと思います。