この記事は「プログラミングコンテストチャレンジブック第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)） 実行結果 入力 ダイクストラ法は負の辺があると使え…