この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-5 経路復元」(p.98) のコードをPythonで書き直したものとなっています。 入力 入力例 隣接リストを用いたコード（O(|V|^2)） 実行結果 入力 ダイクストラ法は負の辺があると使え…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-5 全点対最短路問題（ワーシャル-フロイド法）」(p.98) のコードをPythonで書き直したものとなっています。 入力 入力例1 入力例2 コード 実行結果 入力例1の場合 入力例2の場合…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-5 単一始点最短路問題２（ダイクストラ法）」(p.96) のコードをPythonで書き直したものとなっています。 入力 入力例 隣接リストを用いたコード（O(|V|^2)） 実行結果 優先度付…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-5 単一始点最短路問題１（ベルマンフォード法）」(p.95) のコードをPythonで書き直したものとなっています。 入力 入力例1 入力例2 負の閉路が無い場合のコード 実行結果 入力例…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-5 二部グラフ判定」(p.93) のコードをPythonで書き直したものとなっています。 入力 入力例 入力例1 入力例1 解答 入力 蟻本の入力例ではグラフが書かれていただけだったので、…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-5 隣接リスト」(p.91) のコードをPythonで書き直したものとなっています。 隣接リストのコード 例１ 隣接リストのコード 例１ MAX_V = 10 ** 8 G = [0] * MAX_V ''' 辺に属性が…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-4 食物連鎖（POJ 1182）」(p.85) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 100 7 1 2 2 2 1 2 1 101 1 2 3 1 3 5 1 2 3 3 3 1 5 解答 #…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-4 Union-Find木」(p.81) のコードをPythonで書き直したものとなっています。 Union-Find木の実装 コード 実行例 コード 実行結果 classを使ったUFTの実装 コード 実行例 コード …

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-4 二分探索木」(p.75) のコードをPythonで書き直したものとなっています。 二分探索木の実装 コード 実行例 コード 実行結果 プログラミング言語の標準ライブラリ 二分探索木の…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「Fence Repair（PKU 3253）」(p.75) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 3 8 5 8 解答 # 順位キュー（優先度付きキュー）をインポー…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-4 Expedition（POJ 2431）」(p.73) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 25 10 4 10 14 20 21 10 5 2 4 解答 C++のpriority_queue…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-4 プライオリティキューとヒープ」(p.71) のコードをPythonで書き直したものとなっています。 ヒープの実装例 PythonとC++の違い 標準ライブラリを使ったコード コード 実行結果…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-3 重複組み合わせ」(p.67) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 3 3 1 2 3 10000 解答 MAX_N = 1000 MAX_M = 1000 # 入力 n, m = m…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-3 分割数」(p.66) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 4 3 10000 解答 MAX_N = 1000 MAX_M = 1000 # 入力 n, m = map(int,input()…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-3 lower_bound」(p.65) のコードをPythonで書き直したものとなっています。 bisectモジュール コラムのコード bisectモジュール 二分探索をする際にPythonではbisectモジュール…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-3 最長増加部分列問題」(p.63) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 O(n^2)の解法 O(n log n)の解法 入力 入力例 5 4 2 3 1 5 解答 O(n^2)の解…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-3 個数制限付き部分和問題」(p.62) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 bool値を求めるDP（O(Σmi)） 情報量の多いDP（O(nK)） 入力 入力例 3 1…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-3 01 ナップサック問題その2」(p.60) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 4 5 2 1 3 2 3 2 4 2 解答 # 入力 n, W = map(int,input…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-3 個数制限なしナップサック問題」(p.58) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 三重ループによる解法（O(nW^2)） 二重ループによる解法（O(nW)…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-3 最長共通部分列問題」(p.56) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 4 4 abcd becd 解答 MAX_N = 1000 MAX_M = 1000 # 入力 n, m =…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-3 01 ナップサック問題」(p.52) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 再帰による愚直解（O(2^N)） メモ化再帰（O(nW)） 動的計画法(DP)（O(nW)…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-2 Fence Repair（POJ 3253）」(p.49) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 3 8 5 8 解答 # 入力 N = int(input()) L = list(map(in…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-2 Saruman's Army（POJ 3069）」(p.47) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 6 10 1 7 15 20 30 50 解答 N, R = map(int,input().s…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-2 Best Cow Line（POJ 3617）」(p.45) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 6 ACDBCB 解答 蟻本ではputcharで一文字ずつ出力してい…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-2 区間スケジューリング問題」(p.43) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 5 1 2 4 6 8 3 5 7 9 10 解答 MAX_N = 100000 # 入力 N …

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-2 硬貨の問題」(p.42) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 3 2 1 3 0 2 620 解答 # コインの金額 V = [1, 5, 10, 50, 100, 500] #…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-1 特殊な状態の列挙」(p.39) のコードをPythonで書き直したものとなっています。 PythonとC++の違い コード 実行例 サンプルコード 実行結果 PythonとC++の違い C++ではnext_per…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-1 Lake Counting（POJ No.2386）」(p.35) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 10 12 W........WW. .WWW.....WWW ....WW...WW. ...…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-1 迷路の最短路」(p.37) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 10 10 #S######.# ......#..# .#.##.##.# .#........ ##.##.#### ...…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-1 部分和問題」(p.34) のコードをPythonで書き直したものとなっています。 入力 入力例 再帰回数の上限 解答 入力 入力例 4 13 1 2 4 7 再帰回数の上限 Pythonでは再帰回数の上…