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

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-1 キュー」(p.32) のコードをPythonで書き直したものとなっています。 PythonとC++の違い キューのコード Queue(キュー)を使ったコード list(リスト)を使ったコード deque(両端…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-1 スタック」(p.31) のコードをPythonで書き直したものとなっています。 PythonとC++の違い スタックのコード listを使ったコード deque(両端キュー)を使ったコード listとdeque…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「2-1 再帰関数」(p.30) のコードをPythonで書き直したものとなっています。 階乗を求めるコード フィボナッチ数列を求めるコード メモ探索(メモ化再帰)によってフィボナッチ数列を…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「ハードルが上がった「くじびき」」(p.25) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 二分探索とのアルゴリズム のアルゴリズム モジュールを使った解法…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「1-6 三角形」(p.21) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 別解 解法 別解のコード 関連記事 入力 入力例 5 2 3 4 5 10 解答 # 入力 n = int(input…

この記事のコンセプト 記事一覧 1 いざチャレンジ！でもその前に―準備編 1-1 プログラミングコンテストって何？ 1-6 気楽にウォーミングアップ 2 基礎からスタート！―初級編 2-1 すべての基本”全探索” 2-2 猪突猛進！”貪欲法” 2-3 値を覚えて再利用”動的計画…

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の 「1-1 くじびき」(p.8) のコードをPythonで書き直したものとなっています。 入力 入力例 解答 関連記事 入力 入力例 3 10 1 3 5 解答 MAX_N = 50 n, m = map(int,input().split()) #…