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