この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-6 素数の個数」(p.111) のコードをPythonで書き直したものとなっています。 入力 入力例1 入力例2 解答 入力 入力例1 11 入力例2 1000000 解答 MAX_N = 10 ** 6 prime = [None] …

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-6 素数判定」(p.110) のコードをPythonで書き直したものとなっています。 入力 入力例 素数判定（O(√n)） 実行結果 約数の列挙（O(√n)） 実行結果 素因数分解（O(√n)） 実行結果…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-6 双六」(p.108) のコードをPythonで書き直したものとなっています。 入力 入力例 拡張ユークリッドの互除法 解答 入力 入力例 4 11 拡張ユークリッドの互除法 def extgcd(a, b)…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-6 線分上の格子点の個数」(p.107) のコードをPythonで書き直したものとなっています。 入力 入力例 最大公約数を求める関数 解答 入力 入力例 1 11 5 3 最大公約数を求める関数 …

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-5 Layout（POJ No.3169）」(p.104) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 4 2 1 1 3 10 2 4 20 2 3 3 解答 import sys MAX_N = 1000…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-5 Conscription（POJ No.3723）」(p.103) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 5 5 8 4 3 6831 1 3 4583 0 0 6592 0 1 3063 3 3 49…

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

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-5 最小全域木問題２（クラスカル法）」(p.101) のコードをPythonで書き直したものとなっています。 入力 入力例 コード 実行結果 入力 入力例 7 9 0 1 2 0 4 10 1 2 1 1 3 3 1 5…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-5 最小全域木問題１（プリム法）」(p.100) のコードをPythonで書き直したものとなっています。 入力 入力例 蟻本に載っているコード（O(|V|^2)） 実行結果 優先度付きキューを使…

この記事は「プログラミングコンテストチャレンジブック第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)…