Pythonで競プロ(N年前)

「Pythonで使う競プロ用チートシート」

基本的にPythonは重いので、通らない時はC++で同じコードを書けば通る

Python書きたい時は、pypy3で通すと良い

・入力

s = input()

s = list(input())

a = int(input())

x, y = map(int, input().split())

li = input().split()

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

li = input().split(’T’)

Input script 結果

abcde s=input() s='abcde'

5(1つだけ) a=int(input()) a=5

1 2 x,y = map(int,input().split()) x=1,y=2

n = int(input())

while True:

try:

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

except:

break;

listA = []

while True:

try:

listA.append(list(map(int, input().split())))

except:

break;

・出力

print(s)

print(s, end=‘’)

print(a/b)

print(“%lf”%(a/b))

printf(“%.1lf”%(a/b))

print(str(a/b) + “くらいかな”)

Input script OutPut

s<-'hogehoge' print(s) hogehoge\n

s<-'hogehoge' print(s,end='') hogehoge

a<-1,b<-2 print(a/b) 0.5\n

a<-1,b<-2 print("%lf" % (a/b)) 0.500000\n

a<-1,b<-2 print("%.1lf" % (a/b)) 0.5\n

a<-1,b<-2 print(str(a/b)+'くらいかな') 0.5くらいかな\n

・小数点表示

print(a)

print(“{:.6f}”.fortma(a))

print(“{:b}”.format(b))

a = 0.364364

b = 810

・ゼロ埋め・幅寄せ

print(“python”.ljust(15,’-’))

print(“python”.center(15,’-‘))

・二分探索

import bisect

listA.sort()

・文字列操作

・正規表現

import re

s='hoge6hoge21foo:bar'

「Pythonで競プロする時によく書くコード」

「Python入出力」

「Pythonで青になるまで気をつけること」

１、蟻本を解いていく

２、コンテストに出る

３、D問題埋めをする

４、強い人をAtCorder Problemsのライバルに

５、バチャコン参加

難しい問題でも、時間かけてACする

難しい問題にチャレンジしていくのが大切

気をつけること

・計算量を覚える

・ライブラリを覚える

・高速化

・Pypy3

・計算量を落とすテクニックを覚える

・Pythonでは無理な問題がある

「ライブラリ編」

1.sys

sys.exit()

条件分岐をすぐに終わらせられる

sys.stdin

入力が早くなる

文字列を使うときは注意する

sys.settrecursionlimit

Pythonでは再帰呼び出しの上限がデフォルトで1000回なのでこの上限を上げる

2.collections

collections.deque

デック

collections.defaultdict

普通の辞書と違って存在しないキーを参照してもエラーにならない

collections.Counter

個数カウント

3.itertools

itertools.accumulate

累積和が一発でできる

ものすごく早い

itertools.permutations, itertools.combinations

そこまで早くならないらしい

順列を全て列挙したり、組み合わせを全て列挙してくれる

4.operator

operator.itemgetter

座標などどのキーでソートするかを指定できる

5.bisect

bisect.bisect_left, bisect.bisect_right, bisect.bisect

二分探索

6.heapq

heapq.heappop, heapq.heappush

プライオリティキューのこと

計算量O(logN)で要素を挿入

計算量O(logN)で最小値を取り出す

ことができるデータ構造

7.fractions

fractions.gcd

最大公約数を出してくれる

8.math

math.ceil, math.floor

ceilは数字の切り上げ、floorは数字の切り下げ

math.sqrt

平方根を出してくれる

math.cos, math.sin, math.pi

cos, sin, π

9.copy

copy.deepcopy

普通にコピーしたら元の配列もコピーされちゃう

10.numpy, scipy, scikits

numpyで行列演算ができる

scipyでニュートン法が使える

scipyでワーシャルフロイド法

Pythonだと、powで繰り返し二乗法ができる

「競プロで使える！Python標準ライブラリ」

「計算量やメモリ量について」

「返り値」

「並列化オプション Numba」

アルゴリズム(Python)

本講義では情報科学の重要な基礎となっているアルゴリズムとデータ構造に関して学習します．具体的には，

* アルゴリズムとデータ構造に関する基礎知識を習得する

* Pythonを用いて代表的なアルゴリズム・データ構造を実装する

* 講義内で学習した内容を元に応用的なコーディング課題に取り組む

ことを目的としています．この講義を通して

* 代表的なアルゴリズムの考え方を理解する

* その考え方をコードに落とし込む力を養う

* 競技プログラミング等，様々なコーディング課題に取り組める知識を積み上げる

ことができるように授業が設計されています．

計算量，累積和，データ構造，探索，文字列探索，整列，動的計画法，整数に関係するアルゴリズム，BFS，DFS，グラフアルゴリズム，「難しい問題」

1 計算量

2 累積和、データ構造

3 探索

4 文字列照合

5 ソート

6 DP1

7 DP2

8 整数

9 BFS, DFS

10 グラフアルゴリズム(最短経路問題)

11 グラフアルゴリズム(最大流、最小費用流)

12 グラフアルゴリズム(二部グラフマッチング、最小全域木)

第1講

講義の動画、PDFは後から見れる

授業のURLはスプレッドシートで毎回異なる

第2講

計算量について

この講義では、頭で考えたことをコードに落とし込むことを学んでほしい

一般的なアルゴリズムの授業でカバーする内容に加えて競プロも少し意識した内容に変更！

基本課題：全員できてほしい課題

Extra課題：頑張ればできる腕試し的課題

アルゴリズムの最低条件

有言実行時間で必ず止まる

止まったとき、正しい結果が得られる

気にしたいのは、いつ止まるのか

計算量

与えられたアルゴリズムがどの程度の時間的・メモリ的コストで実行できるのかの目安

具体的な時間やメモリ量を表すものではなく、必要なコストを判定量的に表す指標

時間感覚

オーダーの感覚

n = 10^6

O(n^2)：2.7時間

O(nlogn)：200ms

O(n)：10ms

空間計算量

単純にはメモリの消費量

時間計算量とトレードオフになりがち

その他の計算量・計算コスト

通信コストなど

テスト→問題を提出→試験を提出の順番

問題は一回提出するともう編集不可能になる

頻繁にテストケースを実行してデバッグすべき、これにより提出間際でのミスを防ぐことができる

これでコードが保存される

最初にimportされている

課題

全探索すればおわり

第3講

スライドで指定されたアルゴリズムじゃないと採点されない

コードを最初からやり直すには右上の歯車をクリックして書き直せる

extra課題はdeque、heapqなど使って良い

変更があるのは最初と最後だけなので、その差分だけ計算するようにすれば無駄を削減できる

これがしゃくとりほう？

累積和のその他の例

あるデータのうちAからBまでで該当するデータの数や和を問い合わせるクエリが大量に発生するなどのシナリオのときに有効

似たアルゴリズムとしてしゃくとり法がある

問題例「ランダムな整数が格納されている長さNの配列の中で、部分和がmになる連続した要素のうち、その長さが最小になるものを求めよ」

先ほどの問題と違い、長さが可変長

しゃくとり法の考え方

部分和を計算する左端、右端のindexを保持する変数を定義し、それぞれ0からスタートする

右端のindexを1つずつ増やしながら部分和を計算

決められた値を部分和が超えたら右端を増やすのをやめる

次に左端のindexを進めながら部分和を更新

決められた値を部分和を下回ったら左端のindexを増やすのをやめる

ぴったりmになったときは現在の部分和を構成する連続するようその長さを比較し、最短なら記録しておく

しゃくとり法の前提として、条件を満たしている区間の部分区間も条件を満たすというものがある

単純に言えば、単調増加するようなデータ列である必要がある

しゃくとり法は左端も右端もn回しか動かず、部分和の更新は定数回なので計算量はO(n)

なぜデータ構造を考えるか？

効率的にデータを取り出せることは計算量を削減する上で重要

データ構造自体がある種の処理を内包できるので追加の処理がいらない

今日紹介するデータ構造

・スタック

・キュー

・線型リスト

・ツリー

・ヒープ

スタック

上にどんどん積み重ねていく形でデータを保持する構造

LIFO(Last in , First out)

キュー

入った順に出ていく

enqueueは一番最後にくっつける

データを出すdequeueは一番先頭にあるデータを取り出す

実装

単純に実装するとdequeueするたびにデータ領域が動いてしまう

dequeueごとに全体をずらして先頭の位置をリセットするのは非現実的

リングバッファは円環状に見立てたバッファである

実装上はあらかじめ確保している領域の最後までいったらまた先頭に戻るように先頭と末尾のindexを変更する

最新のx個の情報を覚えておくみたいな使い方もできる

デック

キューの先頭と末尾のどちらからでもenqueue, dequeueできる

線型リスト

データと次のデータへのポインタを格納して数珠つなぎにできるようにしたデータ構造

要素の数の増減に応じて必要な分だけのメモリ量のみを消費するので空間計算量でメリットがある

リストを順に辿らないといけないので、データのアクセスに時間がかかる場合あり

何が嬉しいのかというと、要素の数だけ空間領域が必要になる

これが配列よりも利点

木構造

一番上の節点を根

一番したものを葉

あるノードからつながっている葉ノードに至るまでの最大エッジの数を高さという

根ノードからあるノードに至るまでに辿る必要があるエッジの数を深さという

二分木

各ノードが持つ子ノードの数が最大でも２つである木

構造が簡単なので実装も難しくない

完全二分木

全ての葉が同じ深さ & 全ての内部ノードの次数が2である二分木

ヒープ

親ノードは子ノードよりも常に同じか小さいという制約があるツリー

根ノードは常に最大値（最小値）になる

二分木を使った二分ヒープ

追加

空いている一番左に葉として追加

次に親と比較し、制約条件を満たすように順次入れ替える

削除

rootをとる

一番右端にいる葉をrootにする

子ノードと比較し、子ノードの方が小さい場合、より小さい方の子ノードと入れ替える

制約条件を満たすまで入れ替えを続ける

実装

二分ヒープは配列で実装できる

構造体を使う必要すらもない

計算量

追加も削除もO(logn)

優先度付きキュー

dequeueのときに優先度の高いものから順に出すキュー

優先度は要素自体の値で決められていることが多い

ヒープを使って実装することが多い

課題

やるだけ

第4講 探索

探索とは、あるデータ構造から目的とする値を持った要素を探し出すこと

線型探索

番兵を使うと定数倍高速化できる

二分探索

配列がソートされているという前提で、非常に高速に探索できる

昇順に並んでいる配列の中央に位置する値とキーを比較

O(logn)

配列のまま扱うならばソートが必須

データが出たり入ったりする場合に毎回ソートするのは面倒

そこで、データ構造で解決する

二分探索木

二分探索木は挿入も探索もO(logn)

配列の要素がほぼ整列されている場合は非効率な木の形になってしまう

Treap

挿入の順番とは別に優先度を付与

要素としては二分木、優先度としては二分ヒープになるような構造を作る

優先度はランダムに付与されるので平衡に近くなる

一方に偏った木になるときに修正できないか？

ただしO(logn)で修正できることが条件である

１つの案として木の回転というものがある

木の回転にはポインタの付け替えが必要だが、これは定数回で終わる

平衡木

AVL木、B木、赤黒木、スプレー木などいろいろある

回転や多分木化、ノードに特別なラベルを導入してバランスを取ることを試みる

AVL木

平衡二分木の一種

ノードの挿入が行われるとき必要に応じて一回、二回の回転をおこない全ての部分木の左右の高さの差が一以下になるようにする

どういう回転にするかはバランスファクターで決めることができる

B木

多分木化を取り入れてバランス化をはかる

各ノードでの子ノードへの枝の数を最大mまで許す

これをm次のB木という

ハッシュ法

これまではデータの数が増えれば探索時間も増大する

ここで発想の転換をする

空間計算量を犠牲にして、時間計算量を稼ぐ

探索時間はO(1)、空間計算量はO(n)

与えられた値に対してある変換を行うことでその値を格納する場所を決定する

探索次にも同じ変換を利用して、その場所にある値と比較する

ハッシュの問題点として衝突が起こる

チェイン法は連結リストなどで追加する

オープンアドレス方は計算し直して開いているところを探す

pythonでいえば辞書である

第5講 文字列照合

あるテキストにおいて、所望の文字列が現れる場所を探し出す

力任せ法(Brute Force)

頭から順番にマッチしているかどうかを一文字ずつ確認する

マッチしなかったら１つ右に移動する

全一致か、最後まで行ったら終了

力任せ法の計算量は最悪でO(nl)

実際はそれほど悪くないことも多い

照合が失敗する場合、パターンの元の数文字であることが多く、使われている文字の種類が多くなればパターンのはじめの方で失敗する可能性がさらに高くなる

KMP法(Knuth-Morris-Pratt法)

照合が失敗した時点の状況（何文字目まで照合したか）に応じて、次の照合位置を変更

照合パターンの中に重複な並びが存在する場合には照合パターンのどこから再スタートするかが変わる

ただし、これは固定した情報なので、毎回計算していると非効率で、あらかじめ表を作っておき、照合中はそれを参照する

KMP法の事前準備

実際、KMP法は理論的にはよくできているアルゴリズムだが、性能向上はあまり望めない

BM法(Boyer-Moore法)

照合パターンの前からではなく、後ろから照合する

照合パターンに出てくる文字かどうか、出てくる場合どこに出てくるかに着目する

実用上は結構早く処理できる

工夫をすることで最悪のケースでもO(n+l)に計算量を落とせる

ラビン・カープ法(Rabin-Karp)法

これまでは文字を一文字ずつ見ていくという作業をしなければいけなかった

ここは、文字列の照合をハッシュ値の一致の問題へと変換する

この方法ではローリングハッシュというものを使う

ローリングハッシュ

これはa進数に変換していることと同じ

衝突して欲しくはないので与えられた文字列の種類以上の素数を使うことになる

ただし大きな値になるので剰余にしている

ハッシュの値が間違っていたら、２番目の文字からl+1番目までの部分文字列のハッシュを計算する

これを繰り返してハッシュ値がマッチすることを見つける

ただし、このハッシュの計算を毎回やっていたら結局O(l)の計算量になってしまいbrute forceと変わらん

ここで、変わらない部分を利用して、毎回ハッシュの計算することをローリングハッシュという

累積和みたいな話である

基数と除数をうまく選ぶのが腕の見せ所である

下手な値を選んでしまうと、衝突がめっちゃ起きる

第6講 ソート

ソートに関するライブラリは関数はどの言語でも大概充実しているのでそれを使えば良い

その中身を理解することが重要

内部と外部

ソート実行時に一時的に必要な記憶領域が元々のデータ量以上O(n)以上の場合、外部ソートという

一方、O(1)やO(logN)の一時的な記憶領域が必要なものは内部ソートという

安定と安定でない

同一の要素が複数ある場合、最初の並び順がソート完了後も保持されている場合、安定という

要素を飛び越えて入れ替えるようなアルゴリズムの場合、安定でなくなる

ボゴソート：超非効率ソート

ランダムにシャッフルしてたまたま完全にソートされている状態になるまで繰り返す

挿入ソート

与えられている配列のうち、頭からi番目まではソートされているとする

そのときにi+1番目の要素を入れる場所を順番にチェックして探す

バブルソート

シェイカーソート

ノームソート

今までに紹介したものは多少の差はあれどO(N^2)

なんとかしたい

与えられた配列をそのまま扱うのは無理がある

そういうときにアルゴリズム構成で考えるのは２パターン1

１処理で工夫する

2 データ構造で工夫する

最初は処理の工夫を考える

分割統治法

領域をすぐに処理できるレベルまで小分けにしてそこで処理する

それを順にくっつけていけば最終的に達成したゴールにたどり着く

クイックソートとマージソートを見ていく

クイックソート

配列の中から１つ値を選ぶ（枢軸という）

枢軸の選び方はいろいろある

グループ分けは半々になるのが嬉しい

普通はO(NlogN)だが中軸の選び方によってはO(N^2)

安定ではない

マージソート

与えられた配列を２分割していき、要素１個の配列まで小さくする

分割したもの同士をソートしながら結合して元の配列の大きさに戻す

クイックソートとマージソート

クイックソート

分割するときにざっくりソートする

結合するときは何も考えない

マージソート

分割するときは何も考えない

結合するときにソートする

なんとかしたい

与えられた配列をそのまま扱うのは無理がある

そういうときにアルゴリズム構成で考えるのは２パターン1

１処理で工夫する

2 データ構造で工夫する

次はデータ構造で工夫することを考える

ヒープソート

前に習ったヒープを用いる

与えられた配列を全部ヒープに押し込めた後、１つずつ取り出せば自動的にソートされている

ヒープソートの計算量はO(NlogN)

メリット：ヒープを使うので、データの出現パターンに影響を受けない、最悪でもO(NlogN)

デメリット：ヒープ処理の時間がかかるので、クイックソートより一般的には遅い、記憶領域O(N)が必要

ここまででO(NlogN)

条件をを限定して早くできないか？

バケットソート

整列したいデータのとりうる値がk種類である前提

あらかじめk種類のバケツを用意しておく

与えられた配列をバケツに振り分ける

振り分けた後、整列したい順序でバケツから順番に取り出す

バケツは可変長リストで実装

もし不安定でもよければ各ばけつに対応する値の出現回数のみを記録しておき、その情報をもとに出力すべき配列を作り出す

特にこの実装を係数ソートともいう

先の係数ソートでは出てくる要素とバケツに付随する値が一致しているがそうでなくても良い

バケットソートの計算量

配列の長さがn、出てくる要素の種類をkとすると、

メリット：早い！！

デメリット：強い制約が存在、とりうる種類が多い場合、空間計算量的に破損することも

パンケーキソート

n段のパンケーキをしたから大きい順に並べたい

ただし行える操作は上からi段目のパンケーキにフライ返しを入れて一気にひっくり返すことだけ

配列のprefixの回転のみ行える

最小で何回のソートでできるか？

これにより操作回数の上階が(5n+5)/3となることが知られている

第7講 DP1

動的計画法(Dynamic Programming)

DPの基本が身につくと色々な問題に取り組める（グラフ探索、パターンマッチング、文章間のdiffなど）

言葉は難しそうだが、考え方は簡単

Dynamic：複数の段階にわたり、時間的に変化する問題

Programming：最適な解を導出する方法という意味

フィボナッチ数列

普通の全探索は指数アルゴリズムである

DP

DPは以下の２つの条件を満たすようなアルゴリズムの総称

・小さい問題を解き、その結果を使ってより大きい問題を解く

・小さい問題の計算結果を再利用する

漸化式のような関係性にどう着目するかがポイントとなる

毎回同じことをやっているので、同じ計算を繰り返すのをやめたい

メモすれば良い

この方法のポイントは、わかっているものを保持しておき再計算を減らすところ

これがメモ化再帰

では、わかっているものから順に計算していっても良いのでは？

つまりFib(1)から辿れば重複する計算がない

これがいわゆるDP

質問

メモ化再帰では解けるが漸化式型では解けない、あるいはその逆みたいなケースってありますか？原理的には同じことをやっているような気がしますが

→基本的にどちらでも解けるが、どちらかが有利になるということがある

先ほどの計算速度比較表から考えるとメモ化再帰と漸化式方式では、基本的に漸化式方式の方が定数倍早いと考えて大丈夫ですか？

→場合による

計算量は同じだが、メモ化再帰はオーバーヘッド、漸化式方式では足し算と代入

最大値問題

配列に与えられた整数n個のうち、任意の個数取り出して和を計算する

このとき、和の最大値を求めよ

単純な全探索ではO(2^n)

漸化式のような関係性にどう着目するかがポイントとなる

Sk：１番目からk番目までの要素の最大の和

として、SkとSk+1の間の関係性を式で表現する

カエル飛び問題

カエルは足場iからi+1かi+2にジャンプできる

これも簡単

ナップサック問題

貪欲法ではだめ

漸化式的な関係性を探す

i番目の品物を考慮する直前までの状態、すなわち、knapsack(i-1, w)との関係性を考える

i番目の品物に起こりうるケースは以下の３つ

まずは単なる再帰のコードを書く

ここでメモ化再帰を行ってみる

二次元配列にしなくてもできる方法がある

どんどん辿っていくと最終的には初期状態に辿りつく

メモ化再帰と比較して、noteの行の大きさが1つ増える

DPの根本：最適性の原理

「最適な計画となるためには初期状態・条件に関係なく、残りの決定が最初の決定から生じた状態に対して最適な計画とならなくてはいけない」

「今の状態での最適解」 = 「今に至るまでの最適解」 + 「この時点での最適な選択」

これを順次繰り返すことによって、最終的に求めたい状態での最適解にたどり着く

メモ化再帰のnoteは計算されていないところがある

これが漸化式方式との違いである

課題

n = int(input())

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

h.insert(0, 0)

for i in range(3,len(h)):

n, w = map(int, input().split())

for i in range(n):

for i in range(w+1):

for i in range(1,n+1):

for j in range(w+1):

else:

第8講 DP2

DPは漸化式の関係さえ見つけてしまえば恐るるに足らない

DPはプログラミングの問題というよりは、DPテーブルの設計と操作を考えることが大切

矢谷式DPの考え方

1 DPテーブル

2 DPテーブルを初期化する

3 DPテーブル上のあるせるに対して、１ステップの操作で他のどのセルから繊維できるかを調べる

4 3で分かったことをコードに落とし込む

コイン問題

DPテーブルの設計

DPテーブルのセル：求めたいもの

テーブルの行と列：セルの説明変数のとりうる「より小さな状態」を全部並べたもの

DPテーブルのセル：最小枚数

DPテーブルの行と列：f(支払う金額) = 最小枚数

初期状態をDPテーブルの追加する

例えば探索が始まる前状態など

操作のマッピング

１ステップ分で行える操作がDPテーブル上においてどのような操作に当たるのかを考える

iのセルに1ステップで到達してくるケースを考える

3パターンある

コード化

操作マッピングの遷移を式で表せば良い

１ステップのみを考えるのがポイント

最適性の原理に基づくのがDPなので！

２ステップ以上考えだすとわけわかんなくなる

部分和問題

DPテーブルの設計

DPテーブルのセル：和をSにできるかどうか

テーブルの行と列：f( nこの整数のprefix, S) = 和をSにできるかどうか

DPテーブルの初期化

数字が何もない状態ならとりうる部分和は0のみ

操作のマッピング

その数字を入れるか、入れないかの2通りの遷移が考えられる

コード化

どちらか一方でもTrueならTrueにすれば良い

セルの中身を変えることで他の問題にも対応することができる！

レーベンシュタイン距離

２つの文字列の差を表す距離

DPテーブルの設計

DPテーブルのセル：求めたいもの

テーブルの行と列：f(文字列1のprefix、文字列２のprefix) = 最小編集回数

DPテーブルの初期化

初期状態を追加する

操作のマッピング

斜めの線について、両方の文字が違う場合と同じ場合によって操作が異なる

操作は４パターンしかないが、それは３つの遷移で表される

ただし、斜めは２つの意味がある

もらうDPと配るDP

もらうDP

ある状態を１ステップ前の状態から計算する

配るDP

ある状態から1ステップ後の状態を計算する

矢谷式は全てもらうDP

3でDPテーブル上のアルセルに対して、1ステップの操作で他のどのセルへ繊維できるかを調べれば配るDPに変更することができる

子供に飴を配る問題

もらうDPと配るDPで計算量が違う場合がある

TLEしちゃうとき

配るからもらうへの変換を考える

その他、計算量を減らせそうなところを見る

DPテーブルの大きさを確認する

行や列があまりにも長すぎる場合には格納している値と入れ替えてみる

課題

n, w = map(int, input().split())

for i in range(n):

for i in range(n):

for j in range(n*200+1):

res = 0

for i in range(n*200+1):

print(res)

第9講 難しい問題と整数

巡回セールスマン問題

O(n!)

コンピュータにとって難しい問題は、効率的に解くアルゴリズムが知られていない問題を指す

本当はチューリングマシンなどの概念が必要になるが今回はこれをガン無視する

決定問題

ある入力に対してyesかnoの答えを求める問題

P問題とNP問題

P = Polynomial TIme Solvable

多項式時間で解くアルゴリズムが存在する判定問題

指数時間よりは時間がかからないものを指す

アルゴリズムの世界でいう優しい問題

NP = Non-deterministic Polynomial

出力がyesとなる証拠があった時、その証拠を確認する多項式時間のアルゴリズムが存在する判定問題

無限に並列計算できるなら動かしている中のある組み合わせがyesの出力のなることはあり得るので多項式時間で絶対に解けないというわけではない

P問題は必ずNP問題であるが、逆は成立しない

P問題：多項式時間で答えを出す方法がある

NP問題：多項式時間で答えを確認する方法がある

NPだけどPではない問題は難しい問題として扱われる

多項式時間帰着

ある問題から別の問題へ変換することが多項式時間で可能であること

帰着+問題Bを解くことで多項式時間で処理できる

NP完全

全てのNP問題を多項式時間帰着できるNP問題

NP問題の中で最も難しい問題

NP困難

多項式時間帰着でNP問題の１つに変換できる問題

決定問題でなくても良い

問題自身はNPに属していなくても良い

NP困難かつNPに属する問題はNP完全

NP完全、NP困難のときは、少しでもマシな方向に向かうことを考える

どんな問題が、NP完全、NP困難であるかを知っていればこの問題はやばそうというセンスを養うことができる

NP完全：充足可能性問題(SAT)

nこのboolean変数に対する論理式

NP完全：部分和問題

DPで解けるやん

M = 2^nのときは指数時間になってしまう

これは擬多項式時間アルゴリズムと呼ばれている

計算量の議論は入力がO(n)規模であることを前提としている、ここでMはこちらが勝手に決めることのできる数字なので、これを2^nと考えることもできる

多項式時間で帰着できるみたいなのは重要！

質問

「例えばO(logN)とO(N)以上で分けるなど、計算量を分類するなら他にもいろいろな分け方が考えられると思うのですが、指数と指数以外で２つに分けて考えるのには何か理論的な理由があるのでしょうか？」

→

オートマトンの話が考えられている

決定的か非決定的かの話になっている

Nがちょっと増えても良いのか、ダメなのかという話になっている

NP困難

スーパーマリオ

ステージの最初からゴールまで辿り着けるかどうか

ファミコンのゲームのいくつかは同様にNP困難であることが証明されている

NP完全、NP困難

以上の問題の多くは「組み合わせ最適化問題」と呼ばれるカテゴリに入る

「XXXをうまく選んでYYになるか」などのような問題は雲行きが怪しい可能性あり

巡回セールスマン問題もDPでO(2^n*n^2)に落とせる

近似アルゴリズムでいく方針に切り替える

様々な方法が知られており、問題ごとに特化したアルゴリズムも存在する

整数

最大公約数、最小公倍数

ユークリッドの互除法

拡張ユークリッドの互除法

一次不定方程式の整数解の１つを求める

素数判定

(d, n/d)が必ずペアになっており、その最大値は√nなので、計算量はP(√n)である

素数数え上げ

エラトステネスのふるい

素因数分解

冪乗

繰り返し自乗法

剰余で答えを出す

割り算以外は普通にやれば良い

フェルマーの小定理

逆元

これで順列の計算ができる

まとめ

「難しい問題」

NP問題、 NP完全、 NP困難

整数関連

ユークリッドの互除法、素数判定、エラトステネスのふるい、繰り返し自乗法、剰余の世界での四則演算

第10講 BFS, DFS

質問

「巡回セールスマン問題がn^2*2^nで解けるので任意のNP問題はn^2*2^nで解けると言えるか」

→P,NP,NP完全、NP困難は問題の相対的な困難さをクラス分けしたものであり、アルゴリズムの計算量の議論を直接行うものではないので計算量に関してはまた別の議論が必要

NP困難 = 任意のNP問題から多項式時間で帰着できる問題

木はグラフの一種

グラフを表すのは隣接リストと隣接行列

有効グラフの隣接リストは各要素が各頂点の接続先を表す

有向グラフの隣接リストはつながっている向きのみ値を持つ

無向、コスト付きの隣接リストは、(接続先、コスト)という構造体をリストに入れる

無向グラフでコストがあるのは、隣接行列にコストを入れれば良い



今回のテーマはグラフの探索

BFSとDFS

BFS

キューを使って実装

DFS

スタックを使って実装、もしくは再帰

例でDを見つけたとき、まだ訪問していないところを見つけたとき最後に見つけたものから見つけたとする、ここは実装の違いである

BFSとDFSはキュートスタックの違いだけである

再帰の方が簡単

BFSとDFSの計算量

隣接行列のときO(V^2)

隣接リストのときO(V+E)

メモリ消費量はBFSの方が大きくなりがち

BFS、DFSを行うと、通った辺の順番を基に木ができる

BFS、DFSを応用できる問題

ノードAとノードBの接続関係に関する問題

セルを順に塗りつぶしていく問題

BFSが得意な問題

最小回のステップ（辺のコスト一定）、最短距離などを求めるもの

BFSは開始ノードから接続しているノードに対して１つずつステップを増やして探索するので、目標とするノードが見つかった時点で最短距離がわかる

一方、DFSでは全ての経路をチェックしないと最短かどうかがわからない

DFSが得意な問題

・橋の検出

橋 = 切ってしまうとグラフ全体が非連結になる、あるいは連結成分の数が増える辺

DFS木でlowlinkという指標を考える

DFS木で探索で通らなかった辺を追加する（後退辺）

lowlinkの値をDFS木の木の葉ノードから更新していく

・関節点の検出

・二重辺連結成分分解

lowlinkのようにノードや辺に対してそれらの状態を表す変数を定義してそれらの関係性を見ることでグラフの性質を見極めることはこれからもでてくる

追加で定義される変数がどういう意味を持っているかを理解しながらグラフのアルゴリズムを理解することが大切

課題

from collections import deque

n, m, s, t = map(int, input().split())

edges = [[] for _ in range(n)]

for i in range(m):

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

def bfs(edges, start, end):

waiting = deque()

waiting.append(v)

while len(waiting):

cur_node = waiting.popleft()

if(end == cur_node):

print("Yes")

return 

waiting.append(i)

print("No")

bfs(edges, s-1, t-1)

from collections import deque

h, w = map(int, input().split())

sy, sx = map(int, input().split())

gy, gx = map(int, input().split())

def bfs(board, graph, sy, sx, gy, gx):

while waiting:

y, x = waiting.popleft()

new_y, new_x = y+i, x+j

print(bfs(board, graph, sy-1, sx-1, gy-1, gx-1))

第11講 グラフ1

最短路問題：与えられたグラフの辺には一定値でないコストが予め設定されている

コストが一定値ならBFSで良い、コストは負であることもある

最短経路問題の種類

２頂点対最短経路問題：特定の２つのノード間の最短経路を求める

単一始点最短経路問題：ある始点ノードから他の全部のノードへの最短経路を求める

全点対最短経路問題：すべての２ノード間の最短経路を求める

２頂点対最短経路問題は単一始点最短経路問題のアルゴリズムを利用して解くのが一般的なので、まずは単一始点最短経路問題を解くアルゴリズムについて見ていく

最短経路をよく見ると「最短経路の部分経路も最短経路」という重要な性質がある

これは背理法で証明できる

これは最適性の原理である

あるノードまでの最短経路はその１つ前までのノードのうち、最短でつながるものだけを取り出せば良いので、各ノードにいままでの最短経路の情報を保持しておけばよい

ダイクストラ法

まだ距離が完全に確定していないノードのうち、最短の距離になっているノードiを選ぶ

ノードiにつながっているノードの距離を更新する

更新が終わると、ノードiを確定済みとする、この時点でノードiまでの最短距離は確定となる

変数：ノードxからyにいく距離、ノードxの現在までの最短距離

初期化：開始ノードは0、それ以外は無限大

1 各ノードの最短距離を表す変数を十分大きな数字で初期化する

2 開始ノードからスタート、距離0

3 直接つながっているノードに対して、接続する辺の距離を参照し、そのノードの現時点での最短距離を記録

4 開始ノードは処理が終わったので確定とする

5 つぎに、最短距離が初期されたときは違う値になっていて、かつ最短距離が確定されていないノードのうち、現時点で最短距離が最も小さいものを選び出す

6 直接つながっているノードに対して、接続する辺の距離を参照し、その辺を使うことでそのノードの現時点での最短距離を更新できる場合は更新する

7 このノードを確定とする、以下5,6を繰り返す

予め最短距離を持つ未確定のノードがすぐわかるようなデータ構造で記録できないか→ヒープ使えばええやん！

これで現在までの最短距離で優先度がつけられる

負の距離が存在し、負になる閉路が存在するときは最短距離が定義できない

ベルマンフォード法

負の経路があっても計算可能

全ての辺に対して計算を毎回行う

負の閉路があっても検知可能　

SPFA

基本の考えはベルマンフォードに同じだが、毎回全部の辺をチェックすることを避けることで高速化を測る

ノードiに更新がなければそこから直接つながっているノードに対するdistの更新は必要ない

負の辺がないランダムなノードでは実験的にはO(E)ぐらいになるらしいが、厳密に証明はされていないらしい



ワーシャルフロイド法

２つのノードの全ての組み合わせに対して、最短経路を導出するアルゴリズム

どの順番でループを回さないといけないかを考える

まとめ

単一始点最短経路問題

ダイクストラ

ベルマンフォード

SPFA

全点対最短経路問題

ワーシャル・フロイド

課題

n, m ,s = map(int, input().split())

edges_list = [[] for _ in range(n)]

for i in range(m):

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

inf = 10**9

def dijkstra(n, edges_list):

while True:

tmp_min_dist = inf

cur_node = -1

for i in range(n):

cur_node = i

if cur_node == -1: break

for i in range(n):

else:

print("INF")

dijkstra(n, edges_list)

n, m = map(int, input().split())

inf = 10**9

for _ in range(m):

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

for k in range(n):

for i in range(n):

for j in range(n):

q = int(input())

for i in range(q):

u, v = map(int, input().split())

else:

print("INF")

第12講 グラフ2

グラフの上に流れ（フロー）が存在する

物資の最大流通可能量を求めたり、最大スループットを求めたり、

sourceとsink

始点からフローが生まれ、終点ではフローがなくなる

始点と終点のーど以外ではフローが増減しない

今回は１つずつ存在することを仮定する

最大流問題

あるノードから別のノードへの流量の最大値を求める

貪欲法

今ある選択肢のうち何か１つ選んで次に進む

そしてそれ以降はこの状況のことは振り返らない

貪欲法は必ずしも最適解を導出できるとは限らない

見つけた経路において流せるだけ流すということを全ての経路でDFSでやる

これでもとまった解は18だが、実際は20

貪欲法と最適解を引き算すると、マイナスの経路が出てきて、これを逆にすることで、貪欲法では考慮できなかった経路が浮き出る！

ファード・ファルカーソン法

基本は貪欲法と同じく、DFSやBFSで開始ノードから終了ノードまで流せるだけ流す

ただし、経路の探索においてノード間を逆にたどるような仮想的な経路を考慮する

逆方向の容量も更新する

s-tカットとフローの関係

グラフのカット

最大流・最小カット

最小カット

最小費用流

プライマル・デュアル法

第13講 グラフ3

今回は

・二部グラフマッチング

・最小全域木

・まとめ

二部グラフマッチング

二部グラフ

頂点集合を２つの部分集合に分割でき、各集合内の頂点同士の間には辺がないグラフ

ペア組に使える

二部グラフマッチング

二部グラフにおいてノード間を繋ぐ組み合わせを解く

答えは必ずしも１つではない

複数のノードにつながることを許したり、ある決められたペアの数を達成するなど、様々なケースがある

今回はメジャーな

・二部グラフ最大マッチング

・重みつき二部グラフ最大マッチング

について紹介する

最大マッチングとはペアの数を最大にする辺の組み合わせの１つである

最大マッチングになる辺の組み合わせが見つかったとき、残る辺の数は最大

これを最大流問題に置き換えて考える

辺の容量を1として左のグループから右のグループに流れる流量が最大になる辺の組み合わせを考える

仮想的な開始ノードS、終了ノードTを考えて、SからTへの最大流量を求める

Sから向かう辺、Tに向かうへんも容量を1にすることでペアになることを保証する

フォード・ファルカーソン法などにより最大流となる経路の組み合わせを求める

重みつき二部グラフの最大マッチング問題

左右のグループをつなぐ辺の重みの総和を最大にする

どの２辺も共通のノードを持たない

数字が大きいほどペアになりたい度がより高いことを表す

個人レベルでは必ずしも最大にならない

これを最大費用流問題に置き換えて肝g萎える

辺の重みを負にして、辺のコストとみたてる

元々の重みが大きければ大きいほど辺のコストは小さくなる

全ての辺の容積は1

二部グラフのマッチング問題

全体最適を目指すアルゴリズムとなる

全体最適のために場合によっては大きく不利益を被る個人がでてくることがある

お互いに現在よりも好ましい組が存在しないような方法もある（安定マッチング、ゲール・シャプレイのアルゴリズム）

最小全域木

全域木

グラフにおいて、全ての頂点がつながっている木

最小全域木

全域木の中で辺のコストの総和が最小になるもの

「複数の建物を有線のネットワークで接続するとき、コストを最小にするよう線を引きたい」という問題に答えられる

求め方

・辺ベースのアプローチ：クラスカル法

存在する辺を距離の短い順に並べて順に入れていき、閉路ができないことが確認できた場合はつい怪σ、全部の辺をチェックしたら終了

・ノードベースのアプローチ：プリム法

既に到達した頂点の集合からまだ到達していない頂点の集合への辺のうち、距離が最短のものを追加し、全ノードが繋がったら終了

クラスカル法

1 全ての辺を距離の短い順にソート

2 一番距離の短い辺からソート

3 今までにできた木に辺を追加したとき、閉路が新しくできないことを確認する、できない場合、この辺を最小全域木についか

4 全ての辺をチェックするまで3を繰り返す

実装

「存在する辺を距離の短い順に並べて」：これはソートするだけ

「閉路ができないことを確認できた場合は追加し」：これはどうやって効率的に実現できるか？辺を足すごとに毎回グラフを辿るのは非現実的

Union-Find木

要素を素集合に分割して管理するデータ構造

Union：２つの集合をマージする

Find：ある要素がどの集合にいるかを見つける、同じグループである=同じ根であるなので、根ノードを返す

実装

長さNの配列を用意

配列に親ノードのindexを入れる

自分が子ノードの場合は自分自身のindexを入れる

この値を辿っていけば最終的に根ノードに行き着く

効率化

1 Unite時に木の高さが高い方にマージ

2 根を調べたときに、直接根につながるようにつなぎ変える

計算量はlogよりも増加しない関数であり、定数倍とみなして扱われることもある

プリム法

1 最初のノードを１つ選び、訪問済にする

2 そのノードにつながっている全ての辺を取り、最小全域木の候補の辺に入れる

3 最小全域木の後方の辺の中から接続先のノードが未訪問である最短の距離の辺を選ぶ

4 選んだ辺を最小全域きに入れ、その接続先にあるノードを訪問済みにする

5 4で新しく訪問したノードからさらにその先につながっている辺のうち、接続先のノードが未訪問の全ての辺を最小全域木の候補に入れる

6 以降、全ノードが訪問済みになるまで2~4を繰り返す

計算量

隣接行列 + 最短の辺の単純な探索 O(V^3)

隣接リスト + 最短の辺の単純な探索 O(EV)

ダイクストラ法のようにデータ構造を工夫することで高速化できる

まとめ

今までいろんな問題を解いてきた

データ構造、累積和

探索

文字列探索

整列

DP

整数

BFS, DFS, 橋の検出

グラフ(最短経路、最大流、最小費用流、二部ブラフ、最小全域木)

何ができるのか？

ElasticPlay：視聴時間を指定できる動画再生インタフェース

早送りと取捨選択を組み合わせたビデオの加速再生、ユーザは何秒でビデオを見終えたいか、を設定するだけで自動的に再生方針を決定する

動画を音声がある部分とそうでない部分に分け、さらに重要度を推定し、より低い部分は削除、音声がない部分はより高速に早送りするようにして、ユーザが指定した再生時間に合わせた再生方法を自動的に生成



CodeGlass：GitHubのプルリクエストを活用したコード断片のインタラクティブな調査支援システム

1 時系列順、実装内容に関する情報が多い順、開発背景に関する情報が多い順に関連するプルリクエストをソート可能

2 各プルリクエストの概要情報

3 選択されたコード断片と一致する可能性があるコード断片が過去のバージョンで複数ある場合にはそのバージョンにおけるソースコードへのリンクが表示

4 プルリクエストの詳細情報、実装内容に分類される文章は緑色で、開発背景に分類される文章は青色で表示される

RealCode：GItHub上にある実コード変更をプログラミング課題に転用するシステム

問題文：Issueの説明文

コードの解答例：実際のコード変更

解答の説明文：Pull Request内の説明文

存在するPull Requestを利用して実世界のコード変更をプログラミング課題として利用

実開発を体験できるプログラミング課題を提供できる可能性を確認

アルゴリズムの知識は計算理論に限らず、信号処理、データ処理、ソフトウェア工学、HCIなどいろんな場面で役立つ

課題

class UnionFind:

def __init__(self, n):

def get_root(self, i):

return i

else:

def unite(self, i, j):

root_i = self.get_root(i)

root_j = self.get_root(j)

if root_i != root_j:

else:

def is_in_group(self, i, j):

if self.get_root(i) == self.get_root(j):

return True

else:

return False

def kruskal(V, e_list):

e_cost_sorted = []

for e in e_list:

e_cost_sorted.sort()

uf_tree = UnionFind(V)

ans = 0

mst = []

for e in e_cost_sorted:

mst.sort()

print(ans)

n, m = map(int, input().split())

e_list = []

for _ in range(m):

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

e_list.append(e)

kruskal(n, e_list)

Facebook Coding Interview





all based on fundamental algorithms









アルゴリズムの計算量を見積もれるように、EASY

英語は勉強しとけ

Python, C++, Java