アルゴリズムと数学 演習問題集
参加対象: All Rated対象: - ペナルティ: 5分
この問題集について
- この問題集は、「アルゴリズム×数学」が基礎からしっかり身につく本(E869120 が執筆)に対応した自動採点システムです。
- 全部で 104 問のプログラミング問題が収録されています。
- 基本的なアルゴリズムを扱う問題だけでなく、数学的知識・数学的考察を問う問題もあります。
本を読んでいない方に対する注意
- 本には「手計算問題」「プログラミング問題」合わせて全 200 問が掲載されていますが、この自動採点システムでは「プログラミング問題」しか扱っていません。
- このため、本を手に取っていない方にとっては、いくつかの重要な知識やテクニックに関する問題を扱っていないと感じるかもしれませんが、ご了承ください。
- なお、問題の解説は書籍本体に掲載されています。
目次(2 章:アルゴリズムのための数学の基本知識)
2.1 節|数の分類・文字式・2 進法
- 本文 2.1.3 項:001 - Print 5+N
- 本文 2.1.4 項:002 - Sum of 3 Integers
- 本文 2.1.5 項:003 - Sum of N Integers
- 節末問題 2.1.3:004 - Product of 3 Integers
2.2 節|基本的な演算と記号
- 節末問題 2.2.4:005 - Modulo 100
2.3 節|いろいろな関数
- 該当問題なし(すべて手計算問題または 1 つのケースについて答える問題)
2.4 節|計算回数を見積もろう ~全探索と二分探索~
- 本文 2.4.3 項:006 - Print 2N+3
- 本文 2.4.4 項:007 - Number of Multiples 1
- 本文 2.4.5 項:008 - Brute Force 1
- 本文 2.4.6 項:009 - Brute Force 2
2.5 節|その他の基本的な数学の知識
- 節末問題 2.5.3:010 - Factorial
- 節末問題 2.5.4:011 - Print Prime Numbers
目次(3 章:基本的なアルゴリズム)
3.1 節|素数判定法
- 本文 3.1.2 項:012 - Primality Test
- 本文 3.1.5 項:013 - Divisor Enumeration
- 節末問題 3.1.2:014 - Factorization
3.2 節|ユークリッドの互除法
- 本文 3.2.1 項:015 - Greatest Common Divisor
- 節末問題 3.2.2:016 - Greatest Common Divisor of N Integers
- 節末問題 3.2.3:017 - Least Common Multiple of N Integers
3.3 節|場合の数とアルゴリズム
- 本文 3.3.6 項:018 - Convenience Store 1
- 本文 3.3.7 項:019 - Choose Cards 1
- 本文 3.3.8 項:020 - Choose Cards 2
- 節末問題 3.3.3:021 - Combination Easy
- 節末問題 3.3.6:022 - Choose Cards 3
3.4 節|確率・期待値とアルゴリズム
- 本文 3.4.5 項:023 - Dice Expectation
- 本文 3.4.6 項:024 - Answer Exam Randomly
- 節末問題 3.4.3:025 - Jiro's Vacation
- 節末問題 3.4.4:026 - Coin Gacha
3.5 節|モンテカルロ法 ~統計的な考え方~
- 該当問題なし(すべて手計算問題または 1 つのケースについて答える問題)
3.6 節|ソートと再帰の考え方
- 節末問題 3.6.3:027 - Sorting
3.7 節|動的計画法 ~漸化式の利用~
- 本文 3.7.6 項:028 - Frog 1
- 本文 3.7.7 項:029 - Climb Stairs
- 本文 3.7.8 項:030 - Knapsack 1
- 節末問題 3.7.4:009 - Brute Force 2(2 回目)
- 節末問題 3.7.6:031 - Taro's Vacation
コラム 3|配列の二分探索
- コラム 3:032 - Binary Search
目次(4 章:発展的なアルゴリズム)
4.1 節|コンピュータで図形問題を ~計算幾何学~
- 本文 4.1.6 項:033 - Distance
- 節末問題 4.1.2:034 - Nearest Points
- 節末問題 4.1.3:035 - Two Circles
- 節末問題 4.1.4:036 - : (Colon)
- 節末問題 4.1.5:037 - Intersection
4.2 節|階差と累積和
- 本文 4.2.2 項:038 - How Many Guests?
- 本文 4.2.3 項:039 - Snowy Days
- 節末問題 4.2.1:040 - Travel
- 節末問題 4.2.2:041 - Convenience Store 2
4.3 節|ニュートン法 ~数値計算をやってみよう~
- 該当問題なし(すべて手計算問題または 1 つのケースについて答える問題)
4.4 節|エラトステネスのふるい
- 本文 4.4.1 項:011 - Print Prime Numbers(2 回目)
- 節末問題 4.4.3:042 - Sum of Divisors
4.5 節|グラフを使ったアルゴリズム
- 本文 4.5.6 項:043 - Is It Connected?
- 本文 4.5.7 項:044 - Shortest Path Problem
- 節末問題 4.5.5:045 - Easy Graph Problem
- 節末問題 4.5.6:046 - 幅優先探索
- 節末問題 4.5.7:047 - Bipartite Graph
- 節末問題 4.5.8:048 - Small Multiple
4.6 節|効率的な余りの計算
- 本文 4.6.6 項:049 - Fibonacci Easy (mod 1000000007)
- 本文 4.6.7 項:050 - Power
- 本文 4.6.8 項:051 - Combination Hard
- 節末問題 4.6.2:052 - Knight
- 節末問題 4.6.3:053 - Sum of 4^N
4.7 節|行列の累乗 ~フィボナッチ数列の高速計算~
- 本文 4.7.6 項:054 - Fibonacci Hard (mod 1000000000)
- 節末問題 4.7.2:055 - Recurrence Formula 1
- 節末問題 4.7.3:056 - Recurrence Formula 2
- 節末問題 4.7.4:057 - Domino Tiling
目次(5 章:問題解決のための数学的考察)
5.1 節|なぜ数学的考察が大切か
- 本文 5.1.1 項:058 - Move on Squares 1
5.2 節|規則性を考える
- 本文 5.2.1 項:059 - Power of Two
- 本文 5.2.2 項:060 - Stones Game 1
- 節末問題 5.2.2:061 - Stones Game 2
- 節末問題 5.2.3:062 - Teleporter
5.3 節|偶奇に着目する
- 本文 5.3.1 項:063 - Move on Squares 2
- 本文 5.3.2 項:064 - All Zero
- 節末問題 5.3.1:065 - Bishop
5.4 節|集合を上手く扱う
- 本文 5.4.2 項:066 - Three Cards
- 本文 5.4.5 項:067 - Cross Sum
- 節末問題 5.4.5:068 - Number of Multiples
5.5 節|ギリギリを考える
- 本文 5.5.1 項:069 - Product Max
- 本文 5.5.2 項:070 - Axis-Parallel Rectangle
- 節末問題 5.5.2:071 - Linear Programming
5.6 節|小問題に分解する
- 本文 5.6.2 項:072 - Max GCD 2x
- 節末問題 5.6.2:073 - Sum of Maximum
5.7 節|足された回数を考える
- 本文 5.7.3 項:074 - Sum of difference Easy
- 本文 5.7.5 項:075 - Pyramid
- 節末問題 5.7.3:076 - Sum of difference
- 節末問題 5.7.4:077 - Distance Sum
5.8 節|上界を考える
- 本文 5.8.3 項:078 - Difference Optimization 1
- 節末問題 5.8.2:079 - ModSum
- 節末問題 5.8.3:080 - Difference Optimization 2
5.9 節|次の手だけを考える ~貪欲法~
- 本文 5.9.1 項:081 - Bill Changing Problem
- 本文 5.9.2 項:082 - Interval Scheduling Problem
- 節末問題 5.9.2:083 - We Used to Sing a Song Together
5.10 節|その他の数学的考察
- 本文 5.10.1 項:084 - Sqrt Inequality
- 本文 5.10.4 項:085 - Two Conditions
- 本文 5.10.5 項:086 - Parentheses Check
- 節末問題 5.10.2:087 - Simple Math Easy
- 節末問題 5.10.3:088 - Simple Math
- 節末問題 5.10.5:089 - Log Inequality 2
- 節末問題 5.10.6:090 - Digit Product Equation
目次(最終章:最終確認問題)
- 最終確認問題 16:091 - How Many Ways?
- 最終確認問題 17:092 - Beautiful Rectangle
- 最終確認問題 18:093 - Large LCM
- 最終確認問題 19:094 - Maximum Value
- 最終確認問題 20:095 - Score Sum Queries
- 最終確認問題 22:096 - Cooking
- 最終確認問題 23:097 - Primes in an Interval
- 最終確認問題 24:098 - Polygon and Point
- 最終確認問題 25:099 - Tree Distance
- 最終確認問題 26:100 - Simulation of Chemicals
- 最終確認問題 27:101 - Don't be too close
- 最終確認問題 28:102 - Tricolor Pyramid
- 最終確認問題 29:103 - Circle Packing
- 最終確認問題 30:104 - Graph Master
謝辞
『「アルゴリズム×数学」が基礎からしっかり身につく本』のレビューに関わってくださった以下の 12 名の方々に感謝申し上げます。
- catupper、 kaage、 kaede2020、 kirimin、 kotamanegi、 PCTProbability、 physics0523、 sak、 sheyasutaka、 square1001、 tsukammo、 ygussany(敬称略)