この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「3-3 バブルソートの交換回数」(p.162) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 4 3 1 4 2 解答 # 入力 n = int(input()) a = list(map(i…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「3-3 BITの実装」(p.161) のコードをPythonで書き直したものとなっています。 蟻本のコード classを使ったコード 蟻本のコード # [1, n] n = int(input()) bit = [0] * (n + 1) def…

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

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「3-3 セグメント木によるRMQの実装」(p.155) のコードをPythonで書き直したものとなっています。 コード コード import sys sys.setrecursionlimit(4100000) MAX_N = 1 << 17 INT_M…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「3-2 領域の個数」(p.150) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 10 10 5 1 1 4 9 10 6 10 4 9 10 4 8 1 1 6 4 8 10 5 10 解答 from co…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「3-2 巨大ナップサック」(p.148) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 4 2 1 3 2 3 2 4 2 5 解答 from bisect import bisect_left INF…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「3-2 4 Values whose Sum is 0（POJ No.2785）」(p.147) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 6 -45 -41 -36 -36 26 -32 22 -27 53 30…

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

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「3-2 Fliptile（POJ No.3279）」(p.141) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 解答 # 隣接する…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「3-2 Face The Right Way（POJ No.3276）」(p.139) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 7 BBFBFBB 解答 MAX_N = 5000 # 入力 N = int…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「3-2 Subsequence（POJ No.3061）」(p.135) のコードをPythonで書き直したものとなっています。 入力 入力例1 入力例2 二分探索を用いた解答（O(n log n)） しゃくとり法を用いた解…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「3-1 平均最大化」(p.132) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 3 2 2 2 5 3 2 1 解答 INF = 10 ** 6 + 1 # 入力 n, k = map(int,inpu…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「3-1 Aggressive cows（POJ No.2456）」(p.131) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 5 3 1 2 8 4 9 解答 INF = 10 ** 9 + 1 # 入力 N…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「3-1 Cable master（POJ No.1064）」(p.129) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 入力 入力例 4 11 8.02 7.43 4.57 5.39 解答 import math INF = …

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「3-1 lower_bound」(p.128) のコードをPythonで書き直したものとなっています。 入力 入力例 蟻本のコード bisect_leftを使ったコード 入力 入力例 5 3 2 3 3 5 6 蟻本のコード # …

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-7 Millionaire（2008 APAC local onsites C）」(p.123) のコードをPythonで書き直したものとなっています。 入力 入力例1 入力例2 解答 入力 入力例1 1 500000 0.5 入力例2 3 60…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-7 Bribe the Prisoners（2009 Round 1C C）」(p.121) のコードをPythonで書き直したものとなっています。 入力 入力例1 入力例2 解答 入力 入力例1 8 1 3 入力例2 20 3 3 6 14 …

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-7 Crazy Rows（2009 Round2 A）」(p.119) のコードをPythonで書き直したものとなっています。 入力 入力例1 入力例2 入力例3 解答 入力 入力例1 2 10 11 入力例2 3 001 100 010 …

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-7 Minimum Scalar Product（2008 Round1A A）」(p.117) のコードをPythonで書き直したものとなっています。 入力 入力例1 入力例2 解答 入力 入力例1 3 1 3 -5 -2 4 1 入力例2 5…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-6 Carmichael Numbers（UVa No.10006）」(p.114) のコードをPythonで書き直したものとなっています。 入力 入力例1 入力例2 入力例3 2のべき乗の和として表す方法 再帰関数を使…

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

この記事は「プログラミングコンテストチャレンジブック第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)） 実行結果 優先度付きキューを使…