Programming Contest Challenge Book プログラミングコンテストチャレンジブック

我是上个月的时候看到watashi大神写道要翻译这本书，才了解到的

本书作者是topcoder选手iwi与wata

然后在SHTSC结束时我就去买了本...

萌购团送的，但愿在APIO前能到货...

虽然还没拿到书，今天先翻译下目录内容吧...

目录内容来自作者blog

    1 いざチャレンジ！ でもその前に－－準備編
        1-1 プログラミングコンテストって何？ (什么是Programming Contest)
        1-2 どんなコンテストがあるの？　 (有些什么比赛)
            世界規模のコンテスト－－Google Code Jam（GCJ）　(世界规模的比赛，GCJ)
            上位ランクを目指せ！－－TopCoder　(冲刺高排名吧...TC)
            最も歴史のあるコンテスト－－ACM/ICPC　(最有历史的比赛，ACM/ICPC)
            中学・高校生向けの情報オリンピック－－JOI/IOI　(面向中学生的OI比赛)
            Web上で自動採点－－オンラインジャッジ　(网络上的在线赛)
        1-3 この本での進め方 (本书的写法)
            本書で扱う内容について　(涉及内容)
            使用する言語について　(使用语言)
            問題の扱いについて　(对待问题)
            プログラムについて (程序)
            さらなる練習方法　(提高自身的练习法)
        1-4 どうやって解答を提出するの？　(怎样交题)
            POJへの提出の仕方　(poj)
            GCJへの提出の仕方　(gcj)
        1-5 効率的なアルゴリズムを目指すには　(写出高效的算法)
            計算量って何だろう　(时间复杂度与计算量)
            実行時間について　(关于运行时间)
        1-6 気楽にウォーミングアップ　(warming up)
            まずは簡単な問題から　(最简单开始)
            POJの問題「Ants」　(poj的问题ants)
            ハードルが上がった「くじびき」　(难度更高的“抽签")

    2 基礎からスタート！－－初級編

        2-1 すべての基本“全探索”　(基本内容)
            再帰関数　(递归函数)
            スタック　(栈)
            キュー　(队列)
            深さ優先探索　(dfs)
            幅優先探索　(bfs)
            特殊な状態の列挙　(枚举全排列方法)
            枝刈り　(剪枝)
       2-2 猪突猛進！“貪欲法”　(猪突猛进！！贪心)
            硬貨の問題　(硬币问题)
            区間スケジューリング問題　(区间安排)
            Best Cow Line　
            Saruman's Army　
            Fence Repair　
        2-3 値を覚えて再利用“動的計画法”　(dp)
            探索のメモ化と動的計画法　(记忆化搜索)
            漸化式を工夫する　(在递推式上下工夫)
            計算問題に対するDP　(关于计算问题的dp)
        2-4 データを工夫して記憶する“データ構造”　(数据结构)
            木・二分木　(树，二叉树)
            プライオリティキューとヒープ　(priority queue 与heap)
            二分探索木　(BST)
            Union-Find木　(并查集)
        2-5 あれもこれも実は“グラフ” (一切皆图论)　
            グラフとは　(什么是图)
            グラフの表現　(图的存储方式)
            グラフの探索　(图的遍历)
            最短路問題　(最短路)
            最小全域木　(MST)
            練習問題　
        2-6 GCJの問題に挑戦してみよう（1）　
            Minimum Scalar Product　
            Crazy Rows　
            Bribe the Prisoners　
            Millionaire　

    3 ここで差がつく！－－中級編

        3-1 数学的な問題を解くコツ　(解决数学问题)
            ユークリッドの互除法　(欧几里德算法)
            素数に関する基本的なアルゴリズム　(关于素数的算法)
            余りの計算　(计算余数)
            べき乗を高速に計算する　(快速幂)
        3-2 値の検索だけじゃない！“二分探索”　(不仅仅只能查值的二分查找)
            ソート列から値を探す　(排序后数列中查值)
            解を仮定し可能か判定　(二分答案)
            最小値の最大化　(最小值的最大化)
            平均最大化　(平均值的最大化)
        3-3 厳選！ 頻出テクニック（1）(常用技术)　
            しゃくとり法　(不知道这是啥？)
            反転　(反转？)
            弾性衝突　(弹性冲突？)
            半分全列挙　(半分全列举？)
            座標圧縮　(坐标压缩？好吧这章我都不知是什么)
        3-4 さまざまなデータ構造を操ろう　(使用各种各样的数据结构)
            セグメント木　(线段树)
            Binary Indexed Treeとは　(树状数组)
            バケット法と平方分割　(分桶与分块)
        3-5 動的計画法を極める！　(更深入的dp)
            ビットDP　(SCDP)
            行列累乗　(矩阵优化dp)
            データ構造を用いて高速化　(配合数据结构提速)
        3-6 水を流して問題を解く“ネットワークフロー”　(网络流)
            最大流　(最大流)
            最小カット　(最小割)
            二部マッチング　(二分图匹配)
            一般マッチング　(一般图匹配)
            マッチング・辺カバー・安定集合・点カバー　(匹配，边覆盖，独立集，点覆盖)
            最小費用流　(费用流)
            練習問題　
        3-7 GCJの問題に挑戦してみよう（2）　
            Numbers　
            No Cheating　
            Stock Charts　
            Watering Plants　
            Number Sets　
            Wi-fi Towers

    4 さらに極める！－－上級編

        4-1 より複雑な数学的問題 (更复杂的数学问题)
            行列　(矩阵)
            modの世界　(模)
            数え上げ　(计数)
            対称性のある数え上げ　(根据对称性计数)
        4-2 ゲームの必勝法を編み出せ！(组合博弈的必胜法)　
            ゲームと必勝法　(ICG与必胜法)
            Nim　（Nim）
            Grundy数　(Grundy数)
        4-3 グラフマスターへの道　(走向图论大神)
            強連結成分分解　(拆scc)
            2-SAT　
            LCA　
        4-4 厳選！ 頻出テクニック（2）　
            スタックの利用　(栈的利用)
            デックの利用　(deque)
            LogStepDP　
        4-5 GCJの問題に挑戦してみよう（3）　
            Mine Layer　
            Year of More Code Jam　
            Football Team　
            Endless Knight　
            The Year of Code Jam　

    column
        スタック領域とヒープ領域　（栈容量&动态内存容量）
        アルゴリズムの証明　（算法证明）
        ハフマン符号　（哈夫曼编码）
        memset　
        全探索の書き方　（全排列写法）
        初期化　（初始化）
        いろいろなDP　（各种各样的dp）
        再利用の仕方　（再利用）
        lower_bound　
        平衡二分木　（平衡树）
        証明や法則などについて　（证明与法则）
        収束判定　（极限判定）
        集合の整数表現　（集合的正数表现，估计是SC）
        Sparse Table　
        領域木　（区域树）
        完全マッチングの個数　（完全匹配个数）
        もっと高速な漸化式の計算　（高速递推）
        さまざまなグラフに対する最大流　（面对不同图的最大流）
        高速なフローアルゴリズム　（高速网络流算法）
        さまざまなグラフに対する最小費用流　（面对不同图的费用流）
        計算誤差　（计算精度）
        多倍長演算 （高精度）

第二版追加
    3-6 平面・空間を扱う "計算幾何" （计算几何）
        幾何の基本（几何基础）
        ギリギリを考えよ （深入思考）
        平面走査 （扫描线）
        凸包とキャリパー法 （凸包与（后面那是什么法，搜了下查到的都显示是个测体内脂肪率的方法Orz））
        数値積分 （数值积分）
    4-5 工夫を凝らして賢く探索 （启发式搜索）
        枝刈り （剪枝）
        A* と IDA*
    4-6 分けて解いてまとめる! "分割統治法" （分治）
        列の分割統治法 （数列的分治）
        ツリーの分割統治法 （树分治）
        平面の分割統治法 （平面的分治）
    4-7 文字列を華麗に扱う （华丽地运用字符串）
        文字列に対する動的計画法 （字符串dp）
        文字列検索 （字符串查找）
        接尾辞配列 (Suffix Array) （后缀数组）

 

翻译时有些地方没太理解，然后是YY的。。。有错误请指出

不知这本书难度如何。。。等届时看了之后再写吧

（倒是学到了不少名词的日文名...）

updata：拿到书后看了下修正了几个错误