2019-10-09

動的計画法をおさらいした

AtCoderのABC問題の解説を見ていたらBitDPを使う問題が出てきたのだが、
解説を見てもよくわからんので、動的計画法を基礎からやり直すことにした。
入門的な問題～ナップサック問題までPythonで実装したので記録しておく。
BitDPまでやろうと思ったのだがナップサック問題までで結構な量になってしまったのでそれはまたいつか。

1. Frog 1

問題文

N個の足場があります。足場には1, 2, …, Nと番号が振られています。
各i (1 ≤ i ≤ N)について、足場iの高さはhiです。
最初、足場1にカエルがいます。
カエルは次の行動を何回か繰り返し、足場Nまで辿り着こうとしています。

足場iにいるとき、足場i + 1またはi + 2へジャンプする。
このとき、ジャンプ先の足場をjとすると、コスト | hi − hj |を支払う。

カエルが足場Nに辿り着くまでに支払うコストの総和の最小値を求めてください。

制約

入力はすべて整数である。
2 ≤ N ≤ 10⁵
1 ≤ hi ≤ 10⁴

考え方

例としてn = 7、h = [2, 9, 4, 5, 1, 6, 10]の場合を考える。
問題文では足場の番号は1オリジンだが、配列のインデックスと合わせるため0オリジンで考える。
ここで、DP値を格納する配列dp を用意し、
dp[i]を、「i番目の足場に到達するためのコストの最小値」と定義する。

i = 0の場合

dp[0]は「0番目の足場に到達するためのコストの最小値」ということになる。
0番目の足場はスタート地点なので、辿り着くコストは0。
したがってdp[0] = 0 となる。

i	0	1	2	3	4	5	6
dp[i]	0

i = 1の場合

1番目の足場にたどり着くには、

0番目の足場からジャンプしてくる

1通りの方法しか存在しない。
したがって dp[1] = | h0 − h1 | = | 2 − 9 | = 7 となる。

i	0	1	2	3	4	5	6
dp[i]	0	7

i = 2の場合

2番目の足場にたどり着くには、

0番目の足場からジャンプしてくる
1番目の足場からジャンプしてくる

2通りの方法が存在する。
したがって dp[2]は | h0 − h1 | か | h0 − h2 |のうち小さい方となる。
この例では、| h0 − h2 | = 2 が最小。

i	0	1	2	3	4	5	6
dp[i]	0	7	2

最終結果

この繰り返しで、ゴールであるi = 6までを埋めたものが以下。

i	0	1	2	3	4	5	6
dp[i]	0	7	2	3	5	4	8

dp[6] = 8 は 6番目の足場に到達するためのコストの最小値 なので、答えは8。
このように、部分問題の計算結果を記録しながら最終的な答えを求めるアルゴリズムを「動的計画法」という。

実装

以下のように、DPテーブルの設定→初期化→初期条件→ループ→最終的な答えの出力というステップを踏むケースが多い。
最大値を求める場合は十分に小さい定数で、最小値を求める場合は十分に大きい定数で初期化する。
配列のindexと問題分の番号を混同しないように注意する。

# 柱の本数
n = 7
# 柱の高さ
h = [2, 9, 4, 5, 1, 6, 10]
# DPテーブル初期化値
INF = 1000000
# DPテーブル (dp[i]：i番目の柱に到達するためのコストの最小値)
dp = [INF for i in range(n)]

# 0番目の柱に到達するためのコストは0
dp[0] = 0

# dp[1]～dp[n-1]までループ
for i in range(1, n):
    # i = 1の場合、0番目の柱から1つ飛びで来るパターンしかない
    if (i <= 1):
        dp[i] = dp[i - 1] + abs(h[i - 1] - h[i])
    # それ以外の場合、1つ飛びパターンと2つ飛びパターンのうち小さい方が選ばれる
    else:
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]),
                    dp[i - 2] + abs(h[i - 2] - h[i]))

# 最終地点のDPテーブルの値が答えとなる
print(dp[n - 1])

2. Typical Stairs

問題文

N段の階段があります。高橋君は現在、上り口(0段目)にいます。
高橋君は一歩で1段か2段上ることができます。
ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？
総数を1,000,000,007で割った余りを求めてください。

制約

1 ≤ N ≤ 10⁵
0 ≤ M ≤ N − 1
1 ≤ a1 < a2< ... < aM ≤ N − 1

実装

正答を出すまでにTLEがいっぱい出た。
- 当初は「壊れた階段リスト」を持っていたが、dpを1で初期化して、壊れている階段の箇所にdp値(0)を初期条件として入力し、dp値の更新時に自分の値を係数として掛けることで「壊れた階段リスト」を使わないようにした。
- list.append() は極力使わないようにする。

# DPテーブル初期化値
INIT = 1
n, m = map(int, input().split())
# 初期化
dp = [INIT for i in range(n + 1)]
# 初期条件
for i in range(m):
    a = int(input())
    dp[a] = 0
# dp[2] ~ dp[n]までループ
for i in range(2, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) * dp[i]
 
print(dp[n] % 1000000007)

3. Vacation

問題文

明日から太郎君の夏休みが始まります。
太郎君は夏休みの計画を立てることにしました。
夏休みはN日からなります。
各i(1 ≤ i ≤ N)について、i日目には太郎君は次の活動のうちひとつを選んで行います。

A:海で泳ぐ。幸福度aiを得る。
B:山で虫取りをする。幸福度biを得る。
C:家で宿題をする。幸福度ciを得る。

太郎君は飽き性なので、2日以上連続で同じ活動を行うことはできません。
太郎君が得る幸福度の総和の最大値を求めてください。

制約

入力はすべて整数である。
1 ≤ N ≤ 10⁵
1 ≤ ai, bi, ci ≤ 10⁴

実装

今までのやり方では答えを出すことができない。
- 前日にどの活動を選択していたのかが一次元配列ではわからない
- よってi日目ではどの活動が選択可能なのかがわからない
dp[i][j] = i日目に活動jを選択した場合の幸福度の最大値 というように各活動を選択した場合を考慮する必要がある。
dpに添字を付け拡張することができるかを問う問題。

# 初期値
INF = 1000000
# 休みの日数
n = int(input())
# 満足度テーブル
t = [[int(i) for i in input().split()] for j in range(n)]
# 活動リスト(A = 0, B = 1, C = 2)
a = [0, 1, 2]
# DPテーブル
# dp[i][j]：
# i日目に活動jを選択した場合の幸福度の最大値
dp = [[-INF for i in range(3)] for j in range(n)]

# 初期条件(0日目の各活動の幸福度)
for j in range(3):
    dp[0][j] = t[0][j]

# dp[1][0]～dp[n-1][2]までループ
for i in range(1, n):
    for j in range(3):
        # 活動リストとjの差集合
        # ex) j = 0のときk = [1, 2]をとる
        k = list(set(a).difference(set([j])))
        # i日目の活動jの幸福度と、i-1日目のj以外の活動のうち幸福度が高い方を加算してdp[i][j]とする
        dp[i][j] = max(dp[i - 1][k[0]], dp[i - 1][k[1]]) + t[i][j]

# 最終日のdpテーブルのうち満足度が最大のものが答え
print(max(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]))

4. Knapsack 1

問題文

N個の品物があります。
品物には1,2,…,Nと番号が振られています。
各i(1 ≤ i ≤ N)について、品物iの重さはwiで、価値はviです。
太郎君は、N個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。
ナップサックの容量はWであり、持ち帰る品物の重さの総和はW以下でなければなりません。
太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

制約

入力はすべて整数である。 1 ≤ N ≤ 100
1 ≤ W ≤ 10⁵
1 ≤ wi ≤ W
1 ≤ vi ≤ 10⁹

実装

有名なナップサック問題。
部分和をDPテーブルの添字として利用できるか否かを問う。
難しかった……。0オリジンと1オリジンで頭が割れそうになる。

# 初期値
INIT = 0
# 品物の個数
n = 6
# 重量の上限
W = 15
# 重さリスト
arr_w = [6, 5, 6, 6, 3, 7]
# 価値リスト
arr_v = [5, 6, 4, 6, 5, 2]
# DPテーブル
# dp[i][w]
# i番目までの品物の中から重さwを超えないように選択した場合の価値の最大値
dp = [[INIT for i in range(W + 1)] for j in range(n + 1)]

# 初期条件
# 何も選ばない場合の価値は0
for i in range(W + 1):
    dp[0][i] = 0

# dp[1][0]～dp[n][W]までループ
for i in range(1, n + 1):
    for w in range(W + 1):
        # 品物を選ぶ場合
        if (w >= arr_w[i - 1]):
            dp[i][w] = max((dp[i - 1][w - arr_w[i - 1]] + arr_v[i - 1]),
                           dp[i - 1][w])
        # 品物を選ばない場合
        else:
            dp[i][w] = max(dp[i - 1][w], dp[i][w])

print(dp[i][W])

参考

qiita.com

2019-10-07

「マスタリングTCP/IP」を読んだ (第2章)

技術書ネットワーク TCP/IP

第2章を読み終わった。
TCP/IPの階層モデルと通信例 はなかなか面白かった(小並感)

以下要約

第2章 TCP/IP基礎知識

TCP … Transmission Control Protocol
IP … Internet Protocol

TCP/IP登場の背景とその歴史

軍事利用のための分散型ネットワークを起源とし、大学、研究所間のネットワークとして生まれたARPANETを経て発展。割愛。

TCP/IPの標準化

TCP/IPとはIPを利用するために必要となる多くのプロトコル群の総称。
- IP, ICMP, TCP, UDP, TELNET, FTP, HTTP...

TCP/IPの標準化の特色

オープンである (標準化の議論に誰もが参加できる)
開発重視である (実際に通信ができることに重きが置かれる)

RFC (Request For Comments)

プロトコル標準化のためのドキュメント

TCP/IPの標準化の流れ、RFCの入手方法

割愛。

インターネットの基礎知識

インターネットの構造

インターネットは階層的な構造を持っている。
- 小さなネットワークの集合が組織のネットワーク、組織のネットワークの集合が地域のネットワーク…
各ネットワークは「バックボーン」と呼ばれる基幹ネットワークと、スタブと呼ばれる末端のネットワークから構成されている。
ネットワーク間はNOC (Network Operation Center)で接続される。
運用者や運用方針が異なるネットワークを対等に接続するポイントをIX (Internet Exchange)という。

ISPと地域ネット

インターネットに接続する際は、ISPや地域ネットに接続を依頼する必要がある。

TCP/IP プロトコルの階層モデル

OSI参照モデルとTCP/IPの階層モデルでは構造がやや異なる。
- OSI参照モデルは「通信に必要な機能は何か」という視点でモデル化されている。
- TCP/IPは「実装するにはどのようにプログラミングするか」という視点でモデル化されている。

OSI参照モデル	TCP/IP階層モデル
アプリケーション層	アプリケーション層
プレゼンテーション層	アプリケーション層
セッション層	アプリケーション層
トランスポート層	トランスポート層
ネットワーク層	インターネット層
データリンク層	ネットワークインターフェース層
物理層	(ハードウェア)

ハードウェア (物理層)

内容について規定がない。
- 通信媒体はケーブルでも無線でもよい。
- 信頼性、セキュリティ、帯域、遅延時間などについても制限なし。

ネットワークインターフェース層 (データリンク層)

データリンクを利用して通信をするためのインターフェースとなる。

インターネット層 (ネットワーク層)

IPプロトコル が使われる。
TCP/IP階層モデルでは、インターネット層とトランスポート層がホストのOSに組み込まれることを想定している。

IP (Internet Protocol)

ネットワークをまたいでパケットを配送するためのプロトコル。
識別子としてIPアドレスが使われる。
データリンクの特性を隠す役割もある。
データが到達しなかった場合も再送は行われない。

ICMP (Internet Control Message Protocol)

IPパケットが転送できなくなった場合に送信元に異常を知らせるためのプロトコル。

ARP (Address Resolution Protocol)

パケットの送り先の物理的なアドレス (MACアドレス)を IPアドレスから取得するプロトコル。

トランスポート層

アプリケーションプログラム間の通信を実現する。
ポート番号 を識別子としてどのプログラムとどのプログラムが通信しているのかを識別する。

TCP (Transmission Control Protocol)

コネクション型 で信頼性のあるプロトコル。
パケットの喪失や順番の入れ替わりにも対応できる。
制御のためのパケットのやり取りが多いため、転送データが少ない場合は無駄が多い。
一定間隔で規定量のデータを転送する通信などには向いていない。

UDP (User Datagram Protocol)

コネクションレス型 で信頼性のないプロトコル。
パケット到達のチェックが必要な場合、プログラム側での処理が必要となる。
少量データの通信や、ブロードキャスト、マルチキャストの通信に向いている。

アプリケーション層 (セッション層以上)

OSI参照モデルでいう「セッション層～アプリケーション層」の中で実現される。
TCP/IPアプリケーションの多くはクライアント／サーバーモデルで作られる。

WWW (World Wide Web)

サーバ・ブラウザ間でのプロトコルとしてHTTP (HyperText Transfer Protocol) が用いられる。
送信に用いられる主なデータフォーマットがHTML (HyperText Markup Language)。

電子メール (E-Mail)

プロトコルとしてSMTP (Simple Mail Transfer Protocol) が用いられる。
送信できるデータ形式を拡張するMIME (Multipurpose Internet Mail Extensions)によって、様々な情報を送ることが可能。

ファイル転送

プロトコルとしてFTP (File Transfer Protocol)が用いられる。
バイナリモードとテキストモードを選択できる。
- テキストモードでは、改行コードが異なるOS間で自動的に改行コードを変換する。
ファイル転送指示のための制御コネクション と転送のためのデータコネクション を確立する。

遠隔ログイン

プロトコルとしてTELNET (TELetypewriter NETwork)、SSH (Secure SHell) が用いられる。

ネットワーク管理

プロトコルとしてSNMP (Simple Network Management Protocol) が用いられる。
SNMPを用いてネットワーク機器を管理するプログラムをマネージャ、管理される対象をエージェントという。
エージェントの各情報はMIB (Management Information Base)という構造体に格納される。

TCP/IPの階層モデルと通信例

電子メールの送受信を例にとる。
各階層でヘッダと呼ばれる情報が付加される。

1. アプリケーションの処理＜送信側＞

メール送信ボタンが押された段階で、本文等の符号化を行う。
TCPコネクションの確立の指示を行う。
TCPモジュール にデータを送信。

2. TCPモジュールの処理＜送信側＞

コネクションの確立／切断、データ送信等を行う。
渡されたデータにTCPのヘッダが付加される。以下の情報を含む。
- ポート番号 (送信元、受信先の識別子)
- シーケンス番号 (対象が何バイト目のデータか？)
- チェックサム (データが壊れていないことを保証)
IPモジュール にデータを送信。

3. IPモジュールの処理＜送信側＞

渡されたデータにIPのヘッダが付加される。以下の情報を含む。
- 宛先IPアドレス、送信元IPアドレス
- IPヘッダ以降のプロトコル (TCPかUDPか？)
経路制御表(ルーティングテーブル)を参照し、パケットを受け渡すルーターやホストを決定する。
ネットワークインターフェースのドライバにIPパケットを渡す。

4. ネットワークインターフェース(イーサネットドライバ)の処理＜送信側＞

渡されたデータにイーサネットのヘッダが付加される。以下の情報を含む。
- 宛先MACアドレス、送信元MACアドレス
- イーサネットタイプ (イーサネットヘッダ以降のプロトコル)
イーサネットパケットが物理層経由で送信先に配送される。
送信処理中にFCS (Frame Check Sequence)をパケットの最後に付加。
- ノイズなどによりパケットが破壊されたことを検出するためのもの

5. ネットワークインターフェース(イーサネットドライバ)の処理＜受信側＞

宛先MACアドレスが自分宛かどうかを調べる。自分宛でなければ破棄する。
イーサネットタイプを調べ、イーサネットプロトコルが運んでいるデータの種類を識別する。(この例ではIP)
IPを処理するルーチンにデータを渡す。
処理できないプロトコルの場合は破棄する。

6. IPモジュールの処理＜受信側＞

宛先IPアドレスが自分宛かどうかを調べる。
上位層のプロトコルを調べる。(この例ではTCP)
TCPを処理するルーチンにIPヘッダを除いたデータを渡す。

7. TCPモジュールの処理＜受信側＞

チェックサムを計算し、ヘッダやデータが壊れていないか調べる。
データを順番通り受信しているか調べる。
ポート番号を調べ、通信先アプリケーションを特定する。
データが届いていれば、送信ホストに「確認応答」を返す。
- 確認応答が届かない場合、送信ホストはデータを送り続ける。
ポート番号で識別したアプリケーションプログラムにデータを渡す。

8. アプリケーションの処理＜受信側＞

受信データを解析し、本文を受信する。
ハードディスク等にメッセージを格納する。
全てのメッセージを格納できた段階で、送信元アプリケーションに正常終了を伝える。

2019-10-07

「マスタリングTCP/IP」を読んだ (第1章)

技術書ネットワーク TCP/IP

仕事でTCP周りの処理を書くことが多い。
書くたびに体系的に学んどかないとまずいのではと思うので、名著と言われるこの本を買ってみた。
多分直接的に役に立つのは6章あたりなんだろうけど、知識の整理も兼ねて頭から読んでいく。

以下要約

第1章ネットワークの基礎知識

1-1 コンピュータネットワーク登場の背景

LANとかWANとか、現代におけるネットワークの活用例とか。割愛。

1-2 コンピュータとネットワーク発展の7つの段階

1950年代…バッチ処理の時代
1960年代…TSS(タイムシェアリングシステム)の時代
1970年代…コンピュータ間通信の時代
1980年代…コンピュータネットワークの時代
1990年代…インターネット普及の時代
2000年代…インターネット技術中心の時代
2010年代…いつでもどこでも何にでもTCP/IPネットワークの時代

1-3 プロトコルとは

ネットワークを利用するための約束事をプロトコルという
プロトコルを体系的にまとめたものをネットワークアーキテクチャという
「TCP/IP」も様々なプロトコルの集合体である(IP, TCP, HTTP等)
大きなデータをパケットと呼ばれる単位に分割して送信する方法をパケット交換という
- 送信元がデータを分割し、ヘッダを付加し、パケットを作る
  ※ヘッダには自分のアドレス、宛先アドレス、データの番号等が書き込まれる
- 宛先ホストがヘッダを除き元のデータを再構築する

1-4 プロトコルは誰が決める？

TCP/IPはIFEF (Internet Engineer Task Force)にて標準化が行われている

1-5 プロトコルの階層化とOSI参照モデル

OSI参照モデル

ISO (International Organization for Standardization)が提唱した通信プロトコルの設計指標。
通信に必要な機能を7つに分け機能を分割することで、ネットワークプロトコルを単純化する。
下位層～上位層でサービスのやり取りをするときの約束事を「インターフェース」という。
通信相手の同一階層とやり取りするときの約束事を「プロトコル」という。

OSI参照モデルの7階層

アプリケーション層

特定のアプリケーションに特化したプロトコル。

プレゼンテーション層

機器固有のデータ形式をネットワーク共通のデータ形式に変換する。

セッション層

データ転送に関する管理を行う。
- コネクションの確立、切断、転送データの切れ目の設定など

1-6 OSI参照モデルによる通信処理の例

電子メールの送受信を例にとって各階層の処理を解説。割愛。

1-7 通信方式の種類

コネクション型とコネクションレス型

コネクション型

通信の前後に接続の確立と切断を行う。

コネクションレス型

接続の確立と切断がないため、送信側はいつでもデータを送ることができる。
受信側はデータが送られているか常に確認する必要がある。
コネクション型に比べ処理が単純なため、処理負荷軽減、低コスト化などのメリットが見込める。

回線交換とパケット交換

回線交換

従来の電話で利用されてきた。
交換機がデータの中継処理をする。
コネクションの確立から切断まで、回線は占有利用される。
コンピュータ間の回線速度が常に一定。

パケット交換

TCP/IPではこちらを採用。
パケット交換機(ルーター)によって通信回線が結ばれる。
データをパケットとして分割することで占有化の必要がなく、回線を効率的に利用できる。
混雑度によってパケットの到着時間が変動する。
ルーターのバッファが枯渇するとパケットが喪失して相手に届かなくなることがある。

通信相手の数による分類

ユニキャスト

1対1通信

ブロードキャスト

1対n通信
接続されている全てのホストに向けて発信する。

エニーキャスト

特定の複数台から最適な条件を持つ一台が選別され、その対象1つにのみ情報が送られる。

1-8 アドレスとは

アドレスの唯一性

1つのアドレスは通信相手の特定のために一意(ユニーク)であることが必要となる。

アドレスの階層性

アドレスの総数が多い場合に、検索を容易にするため階層性が必要となる。
IPアドレスは階層性を持っている。
- 「ネットワーク部」「ホスト部」の二つの部分からなる。
- 同じネットワーク部を持つものは同じ組織に属している
- 組織、プロバイダ、地域などで集約可能。

1-9 ネットワークの構成要素

通信媒体とデータリンク

利用するデータリンクの種類によって利用するケーブル類が異なる。

ネットワークインタフェース

NIC、ネットワークアダプタ、ネットワークカード、LANカードなどと呼ばれる。

リピーター

物理層でネットワークを延長する機器。

ブリッジ／レイヤ2スイッチ

データリンク層でネットワーク同士を接続する装置。
データリンクのフレームを認識してブリッジ内部に蓄積し、接続相手のセグメントに新たなフレームとして送出する。

ルーター／レイヤ3スイッチ

ネットワーク層の処理を行う。
ネットワーク間を接続して、パケットを中継する。

レイヤ4 - 7スイッチ

トランスポート層～アプリケーション層の情報に基づいて配送処理を行う。

ゲートウェイ

トランスポート層～アプリケーション層の階層で、データを変換して中継する。
互いに直接通信できない異なるプロトコル間の翻訳を行う。

1-10 現在のネットワークの姿

バックボーン／コア
- 輸送路
エッジ
- 出入口

2019-10-04

「プログラミングコンテストチャレンジブック」を読んだ (第1章～第2章)

技術書アルゴリズムデータ構造

アルゴリズム、データ構造の勉強がてら、「プログラミングコンテストチャレンジブック」の1、2章を読んだ。
7億年前に基本情報の勉強をしていた時に感じていた、結局のところこれ何に使うねん的な疑問が少し解消された気がする。(グラフとか)
2-3 動的計画法の漸化式の部分、2-5 グラフの利用例は難しく結構大雑把な理解になってしまったので、手を動かしながらもう一度読み返したい。
1,2章のプログラミング例の実装を真似て理解を深めるか、続きを読み進めるか悩んでいる。

以下要約

第1章準備編

オーダー

計算量は「何に比例するか」で考え、それをアルゴリズムのオーダーと呼ぶ。
- 例えばn回のループが4重になっていればO(n⁴)と表す
実行時間制限に収まるかどうかを調べるためには、オーダーの式に最大値を代入すればよい

二分探索

一度に候補の場所が半分になり、計算量はO(log n)(対数時間と呼ぶ)

第2章初級編

2-1　全探索

全探索

全ての可能性をしらみつぶしに調べること
ここでは 「深さ優先探索」「幅優先探索」 の2種類を扱う

再帰関数

再帰呼び出しは計算に時間がかかる
→呼び出し回数が指数的に広がるため
引数を渡した際の結果が一定の場合、1回計算したら配列等にメモしておくことで高速化できる(メモ化 、後述)

スタックとキュー

push (積む) と pop (取出す) という二つの操作ができる
スタックはLIFO、キューはFIFO

深さ優先探索 (Depth-First Search, DFS)

ある状態から始め、遷移できなくまで状態を進め、遷移できなくなったら１つ前に戻る
→再帰関数で簡単に書けることが多い

幅優先探索 (Breadth-First Search, BFS)

DFSと同じくある状態から始めてたどり着けるすべての状態を探索する。
はじめの状態に近いほうから検索する
→最短経路・最短手数 を求めるのに適している
同じ状態は一度しか通らないので計算量は O(状態数 * 遷移の仕方)

枝刈り

それ以上状態を遷移しても解が存在しないことが明らかな場合に
それ以上探索せず打ち切ることを枝刈りという。
- (ex) 合計がkとなる数の組み合わせを探す問題で途中で合計がkを超えてしまったとき、それ以上の探索は不要。

2-2　貪欲法

ルールに従ってその場での最善を繰り返すアルゴリズム設計技法
アルゴリズムが正しければシンプルかつ高速になることが多い
間違ったアルゴリズムを選ばないような注意が必要
辞書順比較を扱う問題などで有効なことが多い

2-3　動的計画法 (Dynamic Programming, DP)

ナップサック問題

重さと価値をw, vとするn個の品物があるとき、
重さの総和がWを超えないように選んだ時のvの総和の最大値を求める
各品物を入れる or 入れないで分岐しながら探索する愚直な方法ではO(2ⁿ)の時間がかかる
- この探索法には「i番目以降から重さがj以下になるように選ぶ」という探索を
  同じ引数に対して何度も行っているという問題がある
- 最初の計算時に結果を記録することで、2回目以降の計算を省略できる (メモ化)
ナップサック問題等におけるメモ化テーブルの値は漸化式になっている
- 再帰関数を書かなくても漸化式を直接用いて各項の値を検索することで、式がすっきりする

2-4　データ構造

「ヒープ」「二部探索木」「Union-Find木」を扱う。

定義

丸(○)をノード または節点と呼ぶ
線(ー)を辺と呼ぶ
ここで扱う木は 「根」 と呼ばれるノードを最も上に一つ持つ
各ノードはデータと、「子」 のノードを持つ
自身を「子」として持つノードを 「親」 と呼ぶ
親が同じノードを「兄弟」と呼ぶ
子を持たないノードを「葉」と呼ぶ

ヒープ

二分木
- 全てのノードについて子が2個以下である木
順位キュー (プライオリティーキュー)
- 次の操作ができるデータ構造
  - 数を追加する
  - 最小の数値を取り出す (値を取得し削除する)
ヒープ とは
- プライオリティーキューの操作を二分木を用いて効率的に実現するデータ構造
ヒープの仕組み
- 必ず子の数字は親の数字より大きい
- 上から下へ、左から右へ順にノードが詰まっている
ヒープの計算量
- 追加、最小値取り出しの操作には木の深さに比例した時間がかかる (つまりO(log n) )

二分探索木

二分探索木 は次のような操作が効率的に行えるデータ構造である
- 数値を追加する
- ある数値が含まれているか調べる
- ある数値を削除する
二分探索木の仕組み
- 左の子以下の数はすべて自分の数より小さく、
  右の子以下の数はすべて自分の数より大きくなるように管理する
数の探索
- 根から子に向かって、大きければ右、小さければ左と進んでいけば見つかる
数の追加
- 根から子に向かって数の探索と同様に進めば本来あるべき場所がわかるので、そこに追加する
数の削除
- 削除したいノードが左の子を持っていなければ右の子を持ってくる
- 削除したいノードの左の子が右の子を持っていなければ左の子を持ってくる
- どちらでもなければ、左の子以下で最大のノードを削除したいノードの位置に持ってくる

Union-Find木

グループ分けを管理するデータ構造。以下の操作が行える
- 要素aと要素bが同じグループに属すかどうか調べる
- 要素aと要素bのグループを併合する
Union-Find木も木を使って表現され、1つの木が1つのグループを表す
- ただし二分木とは限らないし、親子関係も重要ではない
併合
- 片方の木の根からもう片方の木の根に辺を張る
判定
- 要素aと要素bが同じグループに属すかどうか調べるには、木の根を見る
  同じ根にたどり着けば同一グループとみなすことができる
実装時の注意
- 木のデータに偏りが発生すれば計算量が膨大になってしまう
  →そのため、偏りが発生しないような工夫が必要となる
  - 併合の際、高さの低いものを高いものの根に張る
  - 縮約
Union-Find木の計算量
- 上記の工夫を行えば非常に高速
  - n要素のUnion-Find木に対する一度の操作は O(α(n) )
    α(n)とはアッカーマン関数の逆関数で、O(log(n))よりも高速

2-5　グラフ

グラフの定義

頂点と辺からなる。
頂点は「対象」、辺は「対象どうしの結びつき」を表す
頂点の集合V、辺の集合EからなるグラフをG(V, E)と表す
2点u, vを結ぶ辺をe(u, v)と表す

グラフの種類

有向グラフ … 辺に向きがあるグラフ
無向グラフ … 辺に向きがないグラフ

重み

辺には様々な属性がつくことがあり、代表的なものに重みがある。

無向グラフの用語

2頂点の間に辺があるとき、2つの頂点は「隣接している」という
隣接している頂点の列をパスという
始点と終点が同じパスを閉路という
任意の2頂点間にパスが存在するグラフを連結グラフという
頂点につながっている辺の数をその頂点の次数という
閉路を持たない連結グラフを「木」という
- 木は辺の数が頂点数 - 1になる
連結でないグラフで閉路を持たないものを「森」という

有効グラフの用語

有効グラフで閉路を持たないものを「DAG (Directed Acyclic Graph)」という
- DAGの頂点の間には順序関係を与えることができる
各頂点に番号を付け、頂点viからvjに向かって辺があるとき、i < jが成り立つような番号の付け方を
トポロジカル順序という
トポロジカル順序に従い頂点を左から右に並び替えると(トポロジカルソート)全ての辺は左から右に向かう
- このような順序をつけることでDAGの問題をDPを用いて解けるようになることがある。

グラフの表現

グラフをデータとして表現する方法に、「隣接行列」「隣接リスト」がある

隣接行列

頂点の個数 * 頂点の個数の二次元配列gでグラフを表現する。

無向グラフの場合

「頂点iと頂点jが結ばれているか？」という情報で事足りる
→結ばれていればg[i][j]、g[j][i]の値を1にすればいい

有向グラフの場合

「頂点iから頂点jに向かう辺があるか？」という情報があればよい
→向かう辺があれば二次元配列g[i][j]の値を1にする
- 無効グラフのケースと違い、g[i][j] = g[j][i]とは限らない

重み付きグラフの場合

g[i][j]の値を辺の重みにする
辺がないときは十分に大きな定数INFを定義し、g[i][j] = INFとする

隣接行列の欠点

常にO(頂点の個数 ^ 2)のメモリを消費する
多重辺や自己ループがある場合の表現が難しい

隣接リスト

「隣接する頂点のリスト」を持つことでグラフを表現する
O(頂点の個数 + 辺の個数)のメモリしか消費しない

グラフの利用例

グラフの彩色問題
最短路問題 (頻出)
単一始点最短路問題 (ベルマンフォード法)
- 始点を固定したときに他の全ての頂点との間の最短路を求める問題
単一始点最短路問題 (ダイクストラ法)
全点対最短路問題 (ワーシャル-フロイド法)
経路復元
最小全域木

2-6　数学的な問題を解くコツ

ユークリッドの互除法

概要

最大公約数を求めるアルゴリズム
自然数a, bの最大公約数を求める関数をgcd(a, b)とすると、
gcd(a, b) = gcd(b, a % b)が成り立つ

ユークリッドの互除法の計算量

O(log max(a, b))

素数判定

整数nの約数はn未満なので、2～n-1までの整数で割り切れるかどうかを試せば素数かどうか判定できる
ここでnが約数dを持ったとするとn/dもnの約数なので、min(d, n/d) <= √n
よって2～√nまでの整数を試すだけで十分である
同様に素因数分解、約数列挙もO(√n)で行える

エラトステネスの篩(ふるい)

概要

多くの整数を素数判定する際に用いる
2以上n以下の整数をすべて書き出すと、その中の最小である2は素数である
→2の倍数をすべて取り除くと、残りの中で最小である3は素数である
→3の倍数をすべて取り除くと、残りの中で最小であるmは素数である
→mの倍数をすべて取り除くと…　という操作を繰り返し素数を列挙する

エラトステネスの篩の計算量

O(log log n)程度

べき乗を高速に計算する

繰り返し二乗法

2-7

問題集なので省略

1. Frog 1

問題文

制約

考え方

i = 0の場合

i = 1の場合

i = 2の場合

最終結果

実装

2. Typical Stairs

問題文

制約

実装

3. Vacation

問題文

制約

実装

4. Knapsack 1

問題文

制約

実装

参考

第2章 TCP/IP基礎知識

TCP/IP登場の背景とその歴史

TCP/IPの標準化

TCP/IPの標準化の特色

RFC (Request For Comments)

TCP/IPの標準化の流れ、RFCの入手方法

インターネットの基礎知識

インターネットの構造

ISPと地域ネット

TCP/IPプロトコルの階層モデル

ハードウェア (物理層)

ネットワークインターフェース層 (データリンク層)

インターネット層 (ネットワーク層)

IP (Internet Protocol)

ICMP (Internet Control Message Protocol)

ARP (Address Resolution Protocol)

TCP (Transmission Control Protocol)

UDP (User Datagram Protocol)

アプリケーション層 (セッション層以上)

WWW (World Wide Web)

電子メール (E-Mail)

ファイル転送

遠隔ログイン

ネットワーク管理

TCP/IPの階層モデルと通信例

1. アプリケーションの処理＜送信側＞

2. TCPモジュールの処理＜送信側＞

3. IPモジュールの処理＜送信側＞

4. ネットワークインターフェース(イーサネットドライバ)の処理＜送信側＞

5. ネットワークインターフェース(イーサネットドライバ)の処理＜受信側＞

6. IPモジュールの処理＜受信側＞

7. TCPモジュールの処理＜受信側＞

8. アプリケーションの処理＜受信側＞

第1章 ネットワークの基礎知識

1-1 コンピュータネットワーク登場の背景

1-2 コンピュータとネットワーク発展の7つの段階

1-3 プロトコルとは

1-4 プロトコルは誰が決める？

1-5 プロトコルの階層化とOSI参照モデル

OSI参照モデルの7階層

アプリケーション層

プレゼンテーション層

セッション層

1-6 OSI参照モデルによる通信処理の例

1-7 通信方式の種類

コネクション型とコネクションレス型

コネクション型

コネクションレス型

回線交換とパケット交換

パケット交換

通信相手の数による分類

ユニキャスト

ブロードキャスト

エニーキャスト

1-8 アドレスとは

アドレスの唯一性

アドレスの階層性

1-9 ネットワークの構成要素

TCP/IP プロトコルの階層モデル

第1章ネットワークの基礎知識

第1章準備編

第2章初級編

2-1　全探索

2-2　貪欲法

2-3　動的計画法 (Dynamic Programming, DP)

2-4　データ構造

2-5　グラフ

2-6　数学的な問題を解くコツ