Pythonで解くAtCoder版!蟻本(初級編)
競技プログラミングの参考書として有名なプログラミングコンテストチャレンジブック(通称 蟻本)で学習しています。
蟻本に出てくる例題はほぼPOJの問題でAtCoderの問題だったらいいのになって思っているとAtCoder 版!蟻本 (初級編)という記事を見つけました。
qiita.com
プログラミングの学習を行うときは実際にコードを書いて理解していくのが近道だと思います。
この記事で挙げられていた問題を解くことで蟻本を理解しようと取り組んだ内容をまとめていきます。
作成中の記事ばかりですが学習にあわせて記事を追加していきます m(_ _)m
目次
1 いざチャレンジ!でもその前に --- 準備編
1-1 プログラミングコンテストって何?
例題 1-1-1 (ハードルの上がった) くじびき <難問!!!!!>
ebisuke33.hatenablog.com
1-6 気楽にウォーミングアップ
例題 1-6-1 三角形
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
例題 1-6-2 Ants (POJ No.1852) (更新中)
2 基礎からスタート! --- 初級編
2-1 すべての基本 "全探索"
例題 2-1-1 部分和問題
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
例題 2-1-2 Lake Counting (POJ No.2386)
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
例題 2-1-3 迷路の最短路
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
例題 2-1-4 特殊な状態の列挙
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
2-2 猪突猛進! "貪欲法"
例題 2-2-1 硬貨の問題
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
例題 2-2-2 区間スケジューリング問題
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
例題 2-2-3 Best Cow Line (POJ No.3617)
例題 2-2-4 Saruman's Army (POJ No.3069)
例題 2-2-5 Fence Repair (POJ No.3253)
2-3 値を覚えて再利用 "動的計画法"(作成中)
例題 2-3-1 01ナップサック問題
例題 2-3-2 最長共通部分列問題
例題 2-3-3 個数制限なしナップサック問題
例題 2-3-4 01ナップサック問題その2
例題 2-3-5 個数制限付き部分和問題
例題 2-3-6 最長増加部分列問題
例題 2-3-7 分割数
例題 2-3-8 重複組合せ
2-3-α その他典型としてあると思う動的計画法(作成中)
例題 2-3-9 ゲーム DP
例題 2-3-10 区間 DP
例題 2-3-11 ツリー DP
例題 2-3-12 DAG DP
例題 2-3-13 グリッド DP
例題 2-3-14 ソートしてからナップサック DP
例題 2-3-15 部分文字列 DP
例題 2-3-16 挿入 DP
例題 2-3-17 連結性 DP
例題 2-3-18 きたまさ法
2-4 データを工夫して記憶する "データ構造"(作成中)
例題 2-4-1 Expedition (POJ No.2431)
ebisuke33.hatenablog.com
例題 2-4-2 二分探索木 (set, map の練習)
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
例題 2-4-3 食物連鎖 (POJ No.1182)
ebisuke33.hatenablog.com
2-5 あれもこれも実は "グラフ"(作成中)
例題 2-5-1 二部グラフ判定
例題 2-5-2 Roadblocks (POJ No.3255)
例題 2-5-3 Conscription (POJ No.3723)
例題 2-5-4 Layout (POJ No.3169)
例題 2-5-5 Warshall-Floyd を使う問題
ebisuke33.hatenablog.com
2-6 数学的な問題を解くコツ(作成中)
例題 2-6-1 線分上の格子点の個数
例題 2-6-2 双六
例題 2-6-3 素数判定
例題 2-6-4 素数の個数
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
例題 2-6-6 Carmichael Numbers (Uva No.10006)