この記事は「プログラミングコンテストチャレンジブック第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()) #…
from collections import deque INF = 10 ** 8 def _01BFS(x, y, G): #始点sからの最短距離のリストを返す V = len(G) d = [INF for _ in range(V)] for i in range(4): d[calc(x, y, i)] = 0 que = deque([(calc(x, y, i), 0) for i in range(4)]) while qu…
こんにちは、クルトンです! この記事ではAtCoderの「AtCoder Beginner Contest 176」のE問題をPythonを使って解説します。問題のリンクを載せておきます。atcoder.jp 解法 解説 解説の補足 本解のサンプルコード 別解 別解のサンプルコード まとめ 解法 解…
こんにちは、クルトンです! この記事ではAtCoderの「AtCoder Beginner Contest 176」のD問題をPythonを使って解説します。問題のリンクを載せておきます。atcoder.jp 解法 解説 本解のサンプルコード サンプルコードの解説 まとめ 解法 解説が分かりやすか…
こんにちは、クルトンです! この記事ではAtCoderの「AtCoder Beginner Contest 176」のC問題をPythonを使って解説します。問題のリンクを載せておきます。atcoder.jp 解法 実装 サンプルコード まとめ 解法 「踏み台を込めて身長を比較したとき、自分より前…
こんにちは、クルトンです! この記事ではAtCoderの「AtCoder Beginner Contest 176」のB問題をPythonを使って解説します。問題のリンクを載せておきます。atcoder.jp 今回必要な知識 解法 超簡単な別解 まとめ 今回必要な知識 for文 if,else文 for文、if,el…
こんにちは、クルトンです! この記事ではAtCoderの「AtCoder Beginner Contest 176」のA問題をPythonを使って解説します。問題のリンクを載せておきます。atcoder.jp 今回必要な知識 入力の受け取り方 解法 まとめ 今回必要な知識 1行に複数の数字の入力が…
こんにちは、クルトンです! この記事ではAtCoderの「AtCoder Beginner Contest 175」のC問題をPythonを使って解説します。問題のリンクを載せておきます。atcoder.jp 解法 サンプルコード まとめ 解法 まず、左右対称性に注目するとのときとのときの答えが…
こんにちは、クルトンです! この記事ではAtCoderの「AtCoder Beginner Contest 175」のB問題をPythonを使って解説します。問題のリンクを載せておきます。atcoder.jp 今回必要な知識 入力の受け取り方 解法 まとめ 今回必要な知識 1行に複数の数字の入力が…
こんにちは、クルトンです! この記事ではAtCoderの「AtCoder Beginner Contest 175」のA問題をPythonを使って解説します。問題のリンクを載せておきます。atcoder.jp 今回必要な知識 数値の入力 解法 まとめ 今回必要な知識 input関数 if文, elif文, else文…
こんにちは、クルトンです! この記事ではAtCoderの「AtCoder Beginner Contest 174」のD問題をPythonを使って解説します。問題のリンクを載せておきます。atcoder.jp 解法 解説 本解のサンプルコード 別解 ふゆるさんのコード まとめ 解法 解説が分かりやす…
こんにちは、クルトンです! この記事ではAtCoderの「AtCoder Beginner Contest 174」のC問題をPythonを使って解説します。問題のリンクを載せておきます。atcoder.jp 解法 解説 オイラーの定理 サンプルコード まとめ 解法 解説が分かりやすかったので、解…
こんにちは、クルトンです! この記事ではAtCoderの「M-SOLUTIONS プロコンオープン 2020」のB問題をPythonを使って解説します。問題のリンクを載せておきます。atcoder.jp 今回必要な知識 入力の受け取り方 解法 まとめ 今回必要な知識 1行に複数の数字の入…
こんにちは、クルトンです! この記事ではAtCoderの「AtCoder Beginner Contest 174」のA問題をPythonを使って解説します。問題のリンクを載せておきます。atcoder.jp 今回必要な知識 数値の入力 解法 まとめ 今回必要な知識 input関数 if, else文 print関数…