LoginSignup
2
3

More than 1 year has passed since last update.

@b150005

E869120本をSwiftで解く(問題1-35)

Last updated at Posted at 2022-06-01

📚 書籍情報

問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本

演習問題集(AtCoder)

アルゴリズムと数学 演習問題集

解説(公式)

E869120/math-algorithm-book/editorial

解答例

001 - Print 5+N

001 - Print 5+N
let numOrange: Int = Int(readLine()!)!
let sum: Int = numOrange + 5

print(sum)

002 - Sum of 3 Integers

002 - Sum of 3 Integers
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let sum: Int = nums.reduce(0, +)
print(sum)

003 - Sum of N Integers

003 - Sum of N Integers
_ = readLine()
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let sum: Int = nums.reduce(0, +)
print(sum)

004 - Product of 3 Integers

004 - Product of 3 Integers
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let p: Int = nums.reduce(1, *)
print(p)

005 - Modulo 100

005 - Modulo 100
_ = readLine()
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let sum: Int = nums.reduce(0, +)
print(sum % 100)

006 - Print 2N+3

定数時間(Constant Time) … 計算量が$ O(1) $となるアルゴリズムの実行時間

006 - Print 2N+3
let num: Int = Int(readLine()!)!
print(2 * num + 3)

007 - Number of Multiples 1

線形時間(Linear Time) … 計算量が$ O(N) $となるアルゴリズムの実行時間

007 - Number of Multiples 1
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }

var ans: Int = 0
for n in 1 ... nums[0] {
  if (n % nums[1] == 0 || n % nums[2] == 0) { ans += 1 }
}

print(ans)

008 - Brute Force 1

計算量 アルゴリズム
O(1) 点と直線の距離
O(log N) 基数変換
二分探索法
ユークリッドの互除法
繰り返し二乗法
O($ \sqrt{N}$) 素数判定法
O(N) 線形探索法
動的計画法
累積和
O(N log log N) エラトステネスの篩
O(N log N) マージソート
区間スケジューリング
O($ N^2 $) 選択ソート
O($ N^3 $) 行列の乗算
ワーシャルフロイド法
O($ 2^N $) 組合せ全探索
O(N!) 順列全探索
N log N $ \sqrt{N} $ N log N $ N^2 $ $ N^3 $ $ 2^N $ N!
$ 11 $ $ \approx 3 $ $ \approx 3 $ $ \approx 38 $ $ 121 $ $ 1331 $ $ 2048 $ $ < 10^9 $
$ 12 $ $ \approx 4 $ $ \approx 3 $ $ \approx 43 $ $ 144 $ $ 1728 $ $ 4096 $ $ > 10^9 $
$ 29 $ $ \approx 5 $ $ \approx 5 $ $ \approx 141 $ $ 841 $ $ 24389 $ $ < 10^9 $ $ > 10^{30} $
$ 30 $ $ \approx 5 $ $ \approx 5 $ $ \approx 147 $ $ 900 $ $ 27000 $ $ > 10^9 $ $ > 10^{32} $
$ 1000 $ $ \approx 10 $ $ \approx 32 $ $ \approx 9966 $ $ 10^6 $ $ 10^9 $ $ > 10^{301} $ $ > 10^{2567} $
$ 31622 $ $ \approx 15 $ $ \approx 178 $ $ \approx 472706 $ $ < 10^9 $ $ > 10^{13} $ $ > 10^{9519} $ $ > 10^{10^5} $
$ 31623 $ $ \approx 15 $ $ \approx 178 $ $ \approx 472722 $ $ > 10^9 $ $ > 10^{13} $ $ > 10^{9519} $ $ > 10^{10^5} $
$ 39620076 $ $ \approx 25 $ $ \approx 6294 $ $ < 10^9 $ $ > 10^{15} $ $ > 10^{22} $ $ > 10^{10^7} $ $ \infty $
$ 39620077 $ $ \approx 25 $ $ \approx 6294 $ $ > 10^9 $ $ > 10^{15} $ $ > 10^{22} $ $ > 10^{10^7} $ $ \infty $
$ 10^{18} $ $ \approx 60 $ $ 10^9 $ $ > 10^{19} $ $ 10^{36} $ $ 10^{54} $ $ \infty $ $ \infty $
$ 2^{10^9} $ $ 10^9 $ $ > 10^{13} $ $ > 10^{29} $ $ > 10^{54} $ $ > 10^{81} $ $ \infty $ $ \infty $
008 - Brute Force 1
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }

var count: Int = 0
if (nums[0] < nums[1]) {
  for n in 1 ... nums[0] {
    count += (nums[1] - n >= nums[0]) ? nums[0] : nums[1] - n
  }
}
else {
  for n in 1 ... nums[1] - 1 {
    count += nums[1] - n
  }
}

print(count)

009 - Brute Force 2

動的計画法(Dynamic Programming; DP) … 部分問題の計算結果を記録しながら全体問題を解く手法

問題 概要 計算量
部分和問題 N個の要素 $ \{ A_1, A_2, A_3, .. , A_N \} $ を用いて総和を $ S $ にできるかどうか O(NS)
コイン問題 N種の硬貨 $ \{ A_1, A_2, A_3, .. , A_N \} $ を用いて合計 $ S $ 円支払う際に使用する硬貨の最小枚数 O(NS)
編集距離 文字列 $ S $ から一文字を削除・挿入・置換して文字列 $ T $ に書き換える場合の最小操作回数 O(|$ S $| |$ T $|)
重み付き区間スケジューリング問題 $ T_S $ から $ T_E $ までで $ M $ 円貰える仕事をいくつか行う場合の最大報酬金額 O($ N^2 $)
巡回セールスマン問題 全ての都市を一度ずつ訪問してから出発地に戻る場合の最小移動コスト O($ N^2 $$ 2^N $)
009 - Brute Force 2
let s: Int = readLine()!.split(separator: " ").map{ Int($0)! }[1]
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }.filter{ $0 <= s }

var isMakeable: [Bool] = [Bool](repeating: false, count: s + 1)
// 総和が0の場合は作成可能
isMakeable[0] = true

for num in nums {
  // 1つ前の要素の時点で作成可能な総和 + 現在の要素 = 現在の要素を使って作成可能な総和
  for makeableNum in (1 ... s).reversed()
    where (makeableNum - num >= 0 && isMakeable[makeableNum - num]) {
    isMakeable[makeableNum] = true
  }
}

print(isMakeable[s] == true ? "Yes" : "No")

010 - Factorial

010 - Factorial
let num: Int = Int(readLine()!)!

var answer: Int = 1
for i in 1 ... num {
  answer *= i
}

print(answer)

011 - Print Prime Numbers

エラトステネスの篩(Sieve of Eratosthenes) …

全ての合成数 $ C $ は $ 2 \leq d \leq \lfloor \sqrt{C} \rfloor $ を満たす正の約数 $ d $ が存在する

という定理のもと、$ \lfloor \sqrt{N} \rfloor $ 以下の非負整数 $ i $ で割り切れない数は素数とみなす、決定的素数判定法(Deterministic Primality Test)の一つ

証明
背理法を用いて上記の命題を示す。

任意の合成数 $ N $ の最小の約数を $ d\ (\ d > 0\ ,\ d \neq 1\ ) $ とすると、$$ d > \sqrt{N} $$ を満たす $ d $ が存在する、と仮定する。

このとき、$ k = \tfrac{N}{d} $ を満たす正の約数 $ k $ が存在するが、$$ k = \dfrac{N}{d} < \dfrac{N}{ \sqrt{N} }\ (\ = \sqrt{N}\ )\ < d $$ となり、$ d $ が合成数 $ N $ の最小の約数であることに矛盾する。

よって命題は真である。

エラトステネスの篩による素数判定
/// エラトステネスの篩を用いた素数判定(計算量: O(*√N*))
/// - parameter n: 素数判定を行う整数
/// - returns: nが素数である場合は`true`、素数でない場合は`false`
func isPrime(_ n: Int) -> Bool {
  if (n <= 1) { return false }
  
  var i: Int = 2
  while (i * i <= n) {
    if (n % i == 0) { return false }
    
    i += 1
  }
  
  return true
}
011 - Print Prime Numbers
let num: Int = Int(readLine()!)!
let answer: String = (1 ... num).filter{ isPrime($0) }.map{ String($0) }.joined(separator: " ")
print(answer)

012 - Primality Test

012 - Primality Test
let num: Int = Int(readLine()!)!
print(isPrime(num) ? "Yes" : "No")  // 011 - Print Prime Numbers を参照

013 - Divisor Enumeration

エラトステネスの篩による正の約数の取得
/// エラトステネスの篩を用いて昇順の正の約数を取得する(計算量: O(*N* log *N*))
/// - parameter n: 正の約数を求める整数
/// - returns: 昇順に並べ替えられた正の約数の`[Int]`型配列
func getSortedDivisors(_ n: Int) -> [Int] {
  // 約数列挙のアルゴリズム自体の計算量はO(√N)
  var i: Int = 1
  var divisors: [Int] = [Int]()
  while (i * i <= n) {
    if (n % i == 0) {
      divisors.append(i)
      
      if (i * i != n) {
        divisors.append(n / i)
      }
    }
    
    i += 1
  }
  
  // Array#sorted()の計算量がO(N log N)
  return divisors.sorted()
}
013 - Divisor Enumeration
let num: Int = Int(readLine()!)!
let divisors: [Int] = getSortedDivisors(num)
divisors.forEach{ print($0) }

014 - Factorization

重複のない素因数の取得
/// 重複のない素因数を取得する(計算量: O(*N* log *N*))
/// - parameter n: 素因数を求める整数
/// - returns: 昇順に並べ替えられた重複のない素因数の`[Int]`型配列
func getUniquePrimeFactors(_ n: Int) -> [Int] {
  let divisors: [Int] = getSortedDivisors(n)
  
  return divisors.filter{ isPrime($0) }
}
全ての素因数の取得
/// 全ての素因数を取得する(計算量: O(*N* log *N*))
/// - parameter n: 素因数を求める整数
/// - returns: 昇順に並べ替えられた全ての素因数の`[Int]`型配列
func getAllPrimeFactors(_ n: Int) -> [Int] {
  let uniquePrimeFactors: [Int] = getUniquePrimeFactors(n)
  
  var num: Int = n
  var primeFactors: [Int] = [Int]()
  while (num != 1) {
    for p in uniquePrimeFactors where (num % p == 0) {
      primeFactors.append(p)
      num /= p
      break
    }
  }
  
  return primeFactors
}
014 - Factorization
let num: Int = Int(readLine()!)!
let primeFactors: [Int] = getAllPrimeFactors(num)
print(primeFactors.map{ String($0) }.joined(separator: " "))

015 - Greatest Common Divisor

ユークリッドの互除法(Euclidean Algorithm) …

2つの非負整数 $ p, q\ (\ p \geq q\ ) $ について、$$ (\ p \bmod q\ )\ +\ q \leq \dfrac{2}{3}\ (\ p + q\ ) $$ が常に成り立つ

という定理のもと、$ P \bmod Q\ = 0\ (\ P \geq Q\ ) $ となった際の $ Q $ が元の値 $ p, q $ の最大公約数とみなすアルゴリズム

証明
(i) $ p \leq 2q $
$ (\ p \bmod q\ ) = p - q $ より、(左辺) $ = p $
また、$ p \leq 2q $ について、$$ p \leq 2q \Leftrightarrow 3p \leq 2\ (\ p + q\ ) \Leftrightarrow p \leq \dfrac{2}{3}\ (\ p + q\ ) $$
(ii) $ p > 2q $
$ (\ p \bmod q\ ) = p - q $ より、(左辺) $ < 2q $ … ①
また、$ p > 2q $ について、$$ p > 2q \Leftrightarrow p + q > 3q \Leftrightarrow \dfrac{2}{3}\ (\ p + q\ ) > 2q … ②$$
①, ②より、(左辺) $ < \tfrac{2}{3} (\ p + q\ )$

(i), (ii)より命題は真である。

ユークリッドの互除法による最大公約数の取得
/// ユークリッドの互除法を用いて2つの整数の最大公約数を求める(計算量: O(log *N*))
/// - parameter num1: 最大公約数を求める整数
/// - parameter num2: 最大公約数を求める整数
/// - returns: `num1, num2`の最大公約数
func getGcd(_ num1: Int, _ num2: Int) -> Int {
  var (p, q): (Int, Int) = (num1, num2)
  while (p >= 1 && q >= 1) {
    if (p >= q) { p %= q }
    else { q %= p }
  }
  
  if (p >= q) { return p }
  else { return q }
}
ユークリッドの互除法による最大公約数の取得(再帰関数)
/// 再帰的にユークリッドの互除法を用いて2つの整数の最大公約数を取得する(計算量: O(log *N*))
/// - parameter num1: 最大公約数を求める整数
/// - parameter num2: 最大公約数を求める整数
/// - returns: `num1, num2`の最大公約数
func getGcdRecursively(_ num1: Int, _ num2: Int) -> Int {
  // ベースケース
  if (num2 == 0) { return num1 }
  return getGcdRecursively(num2, num1 % num2)
}
015 - Greatest Common Divisor
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
print(getGcd(nums[0], nums[1]))

016 - Greatest Common Divisor of N Integers

016 - Greatest Common Divisor of N Integers
_ = readLine()
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
// 初期値を最初の要素にする
let gcd: Int = nums.reduce(nums.first!, getGcd(_:_:))
print(gcd)

017 - Least Common Multiple of N Integers

ユークリッドの互除法による最小公倍数の取得
/// ユークリッドの互除法を用いて2つの整数の最小公倍数を取得する(計算量: O(log *N*))
/// - parameter num1: 最小公倍数を求める整数
/// - parameter num2: 最小公倍数を求める整数
/// - returns: `num1, num2`の最小公倍数
func getLcm(_ num1: Int, _ num2: Int) -> Int {
  let gcd: Int = getGcd(num1, num2)
  // 除算を先に行うことでInt型のオーバーフローを避ける
  return num1 / gcd * num2
}

乗算・除算の優先度は同じだが、除算を先に行うことでオーバーフローを避ける

017 - Least Common Multiple of N Integers
_ = readLine()
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
// 初期値を1にする
let lcm: Int = nums.reduce(1, getLcm(_:_:))
print(lcm)

018 - Convenience Store 1

018 - Convenience Store 1
_ = readLine()
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }

// 値段ごとの商品数を求める
var counts: [Int] = [Int](repeating: 0, count: 4)
nums.forEach{ counts[$0 / 100 - 1] += 1 }
print(counts[0] * counts[3] + counts[1] * counts[2])

019 - Choose Cards 1

019 - Choose Cards 1
_ = readLine()
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }

// 色ごとの枚数を求める
var counts: [Int] = [Int](repeating: 0, count: 3)
nums.forEach{ counts[$0 - 1] += 1 }
print(
  counts[0] * (counts[0] - 1) / 2
  + counts[1] * (counts[1] - 1) / 2
  + counts[2] * (counts[2] - 1) / 2
)

020 - Choose Cards 2

計算量が$ O(N^5) $のアルゴリズムであっても、$ N $ が十分に小さい場合は有効

020 - Choose Cards 2
_ = readLine()
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }

var count: Int = 0
for i in 0 ..< nums.count - 4 {
  for j in i + 1 ..< nums.count - 3 {
    for k in j + 1 ..< nums.count - 2 {
      for l in k + 1 ..< nums.count - 1 {
        for m in l + 1 ..< nums.count
          where (nums[i] + nums[j] + nums[k] + nums[l] + nums[m] == 1000) {
            count += 1
        }
      }
    }
  }
}

print(count)

021 - Combination Easy

順列の総数の取得
/// 順列の総数を取得する(計算量: O(*N*))
/// - parameter m: 全体の要素数
/// - parameter n: 抽出する要素数
/// - returns: *P(m, n)* の順列の総数
func getPermutation(_ m: Int, _ n: Int) -> Int {
  if (m < n) { return 0 }
  if (m == 0 || n == 0) { return 1 }
  
  var p: Int = 1
  for i in stride(from: m, through: (m - n + 1), by: -1) {
    p *= i
  }
  
  return p
}
組合せの総数の取得
/// 組合せの総数を取得する(計算量: O(*N*))
/// - parameter m: 全体の要素数
/// - parameter n: 抽出する要素数
/// - returns: *C(m, n)* の組合せの総数
func getCombination(_ m: Int, _ n: Int) -> Int {
  if (m < n) { return 0 }
  if (m == 0 || n == 0) { return 1 }
  
  var p: Int = getPermutation(m, n)
  for i in 1 ... n {
    p /= i
  }
  
  return p
}
021 - Combination Easy
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
print(getCombination(nums[0], nums[1]))

022 - Choose Cards 3

022 - Choose Cards 3
_ = readLine()
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }

// 値ごとの枚数を求める
let sum: Int = 100000
var counts: [Int] = [Int](repeating: 0, count: sum)
nums.forEach{ counts[$0] += 1 }

let halfCount: Int = counts[sum / 2]
var answer: Int = (halfCount % 2 == 0)
  ? halfCount / 2 * (halfCount - 1)
  : (halfCount - 1) / 2 * halfCount

for lth in 1 ..< (sum / 2) {
  answer += counts[lth] * counts[sum - lth]
}

print(answer)

023 - Dice Expectation

023 - Dice Expectation
let n: Double = Double(readLine()!)!
let blues: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let reds: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }

let sum: Int = blues.reduce(0, +) + reds.reduce(0, +)
print(Double(sum) / n)

024 - Answer Exam Randomly

024 - Answer Exam Randomly
let n: Int = Int(readLine()!)!
var questions: [[Double]] = [[Double]]()
for _ in 0 ..< n {
  questions.append(readLine()!.split(separator: " ").map{ Double($0)! })
}

var expectation: Double = 0
for question in questions {
  expectation += question[1] / question[0]
}

print(expectation)

025 - Jiro's Vacation

025 - Jiro's Vacation
_ = readLine()
let sum1_2: Int = readLine()!.split(separator: " ").map{ Int($0)! }.reduce(0, +)
let sum3_6: Int = readLine()!.split(separator: " ").map{ Int($0)! }.reduce(0, +)

print(Double(sum1_2 + sum3_6 * 2) / 3)

026 - Coin Gacha

026 - Coin Gacha
let n: Int = Int(readLine()!)!

var probability: Double = 0
for i in 1 ... n { probability += 1 / Double(i) }
probability *= Double(n)

print(probability)

027 - Sorting

種類 平均計算量 概要
クイック(Quick)ソート O(N log N) 要素の集合 $ A = \{ A_m \mid A_m < pivot \} $ と $ B = \{ B_n \mid pivot \leq B_n \} $に分割
マージ(Merge)ソート O(N log N) Merge操作が行われた要素の集合 $ A = \{ A_m \mid 1 \leq m \leq \frac{k}{2} \} $ と $ B = \{ B_n \mid \frac{k}{2} < n \leq k \} $ に対してMerge操作
ヒープ(Heap)ソート O(N log N) ヒープ構造化し、ルートの要素 $ A_{max} $ を抽出
計数(Bucket)ソート O(N+k) 値ごとの要素数を集計
選択(Selection)ソート O($ N^2 $) 要素 $ A_i $ と未ソート部分の最小値 $ A_{min} $ を交換
挿入(Insertion)ソート O($ N^2 $) 要素 $ A_i $ をソート済みの要素の集合 $ \{ A_k \mid 1 \leq k \leq i - 1 \} $ の適切な位置に挿入
バブル(Bubble)ソート O($ N^2 $) 隣り合う要素 $ A_{i-1},\ A_i $ の比較

Merge操作(Merge) … 列 $ A, B $ について、$ A $ の最小の要素 $ A_{min} $ と $ B $ の最小の要素 $ B_{min} $ を比較し、小さい方の値から並べること

マージソート
/// 2つの配列をマージする
/// - parameter left: 左半分の配列
/// - parameter right: 右半分の配列
/// - returns: `left, right`がマージされた`[Int]`型のソート済配列
func merge(_ left: [Int], _ right: [Int]) -> [Int] {
  var result: [Int] = [Int]()
  
  // Merge操作
  var (l, r): (Int, Int) = (0, 0)
  while (l < left.count || r < right.count) {
    // 左側の配列の値全てが走査済である場合は右側の配列から値を追加
    if (l == left.count) {
      result.append(right[r])
      r += 1
    }
    // 右側の配列の値全てが走査済である場合は左側の配列から値を追加
    else if (r == right.count) {
      result.append(left[l])
      l += 1
    }
    // 両方の配列の走査を終えていない場合は両方の配列の値同士を比較
    else {
      // 左側の配列の値の方が小さい場合
      if (left[l] <= right[r]) {
        result.append(left[l])
        l += 1
      }
      // 右側の配列の値の方が小さい場合
      else {
        result.append(right[r])
        r += 1
      }
    }
  }
  
  return result
}

/// 配列に対してマージソートを行う
/// - parameter list: マージソートを行う配列
/// - returns: マージソートされた`[Int]`型配列
func mergeSort(_ list: [Int]) -> [Int] {
  // 要素数が1以下の場合はソートの必要がない
  if (list.count <= 1) { return list }
  
  // 配列を分割(分割統治法)
  let (l, r): ([Int], [Int]) = (
    [Int](list[0 ..< list.count / 2]),
    [Int](list[list.count / 2 ..< list.count])
  )
  
  // Merge操作
  return merge(mergeSort(l), mergeSort(r))
}

例としてmergeSort([4,3,2])の処理の流れを説明する。

  1. mergeSort([4,3,2])を実行
  2. 分割統治によって、[4,3,2]を[4]と[3,2]の2つに分割
  3. mergeSort([4])を実行 → [4]を返却
  4. --- この時点でreturn merge(_:_:)の左半分が終了 ---
  5. mergeSort([3,2])を実行
  6. 分割統治によって、[3,2]を[3]と[2]の2つに分割
  7. mergeSort(3)を実行 → [3]を返却
  8. mergeSort(2)を実行 → [2]を返却
  9. --- この時点でreturn merge(_:_:)の右半分が終了 ---
  10. merge([3], [2])を実行 → [2,3]を返却
  11. merge([4], [2,3])を実行 → [2,3,4]を返却
027 - Sorting
_ = readLine()
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let sorted: [Int] = mergeSort(nums)
print(sorted.map{String($0)}.joined(separator: " "))

028 - Frog 1

028 - Frog 1
let n: Int = Int(readLine()!)!
let heights: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
var costs: [Int] = [Int]()
var (p, q): (Int, Int) = (0, 0)
for i in 0 ..< n {
  if (i == 0) { costs.append(0) }
  if (i == 1) { costs.append(abs(heights[i] - heights[i - 1])) }
  if (i >= 2) {
    // 1つ前の足場
    p = costs[i - 1] + abs(heights[i] - heights[i - 1])
    // 2つ前の足場
    q = costs[i - 2] + abs(heights[i] - heights[i - 2])
    costs.append(min(p, q))
  }
}

print(costs[n - 1])

029 - Climb Stairs

029 - Climb Stairs
let n: Int = Int(readLine()!)!
var counts: [Int] = [Int](repeating: 0, count: n + 1)
for i in 0 ... n {
  if (i <= 1) { counts[i] = 1 }
  else { counts[i] += counts[i - 1] + counts[i - 2] }
}

print(counts[n])

030 - Knapsack 1

030 - Knapsack 1
let input1: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, maxWeight): (Int, Int) = (input1[0], input1[1])
var values: [Int] = [Int](repeating: 0, count: maxWeight + 1)

// 商品を1つずつ走査
for _ in 0 ..< n {
  let input2: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
  let (weight, value): (Int, Int) = (input2[0], input2[1])
  
  // (新商品の重量weight) ≦ (設定重量w)であれば、重量の合計が設定重量wとなる
  // 「新商品を取らない、現時点での最適な取り方」と「新商品を取る、新たな取り方」を比較
  // ※ 値が再代入されたvaluesのインデックスwがループ処理の中で(w - weight)として再登場しないよう
  //   設定重量wは「重い順」で考える
  for w in (0 ... maxWeight).reversed() where (w - weight >= 0) {
    values[w] = max(values[w], values[w - weight] + value)
  }
}

print(values[maxWeight])

031 - Taro's Vacation

031 - Taro's Vacation
let n: Int = Int(readLine()!)!
let scores: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }

var maxScores: [Int] = [Int](repeating: 0, count: n + 1)
for d in 1 ... n {
  if (d == 1) { maxScores[d] = scores[d - 1] }
  else { maxScores[d] = max(maxScores[d - 1], maxScores[d - 2] + scores[d - 1]) }
}

print(maxScores[n])

032 - Binary Search

二分探索法(Binary Search) … ソート済の配列に対して、探索範囲の中央のインデックスとの値の比較を繰り返して値の存在を確認する手法

032 - Binary Search
let x: Int = readLine()!.split(separator: " ").map { Int($0)! }[1]
let nums: [Int] = readLine()!.split(separator: " ").map { Int($0)! }.sorted()

var (left, mid, right): (Int, Int, Int) = (1, 0, nums.count)
while (left <= right) {
  mid = (left + right) / 2
  
  if (nums[mid] == x) {
    print("Yes")
    return
  }
  else if (nums[mid] > x) { right = mid - 1 }
  else if (nums[mid] < x) { left = mid + 1 }
}

print("No")

033 - Distance

内積・外積の定義
$ \vec{a} = (a_x, a_y), \vec{b} = (b_x, b_y) $ とし、$ \vec{a}, \vec{b} $ のなす角をθ ( $ 0 \leq θ \leq \tfrac{\pi}{2} $ ) とすると
内積 $ \vec{a} \cdot \vec{b} = a_x b_x + a_y b_y = |\ \vec{a}\ |\ |\ \vec{b}\ |\cos θ $
外積 $ |\ \vec{a} \times \vec{b}\ | = |\ a_x b_y - a_y b_x\ | = |\ \vec{a}\ |\ |\ \vec{b}\ |\sin θ $
※ 外積 $ |\ \vec{a} \times \vec{b}\ | $ は $ \vec{a}, \vec{b} $ によって作られる平行四辺形の面積に等しい

内積(inner product)について、以下の性質が成り立つ
$ \vec{a} \cdot \vec{b} > 0 \Leftrightarrow θ < \dfrac{\pi}{2} $
$ \vec{a} \cdot \vec{b} = 0 \Leftrightarrow θ = \dfrac{\pi}{2} $
$ \vec{a} \cdot \vec{b} < 0 \Leftrightarrow θ > \dfrac{\pi}{2} $

外積(outer product)について、以下の性質が成り立つ(右ねじの法則)
$ \vec{a} \times \vec{b} > 0 \Leftrightarrow $ $ \vec{a} $ を $ \vec{b} $ に対してなす角が小さい方向に回転させたとき、ねじはz座標の正の方向に進む
$ \vec{a} \times \vec{b} = 0 \Leftrightarrow $ $ \vec{a} $ と $ \vec{b} $ は平行
$ \vec{a} \times \vec{b} < 0 \Leftrightarrow $ $ \vec{a} $ を $ \vec{b} $ に対してなす角が小さい方向に回転させたとき、ねじはz座標の負の方向に進む

033 - Distance
import Foundation

let aInput: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let bInput: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let cInput: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }

// 点A, B, Cの座標
let (ax, ay): (Int, Int) = (aInput[0], aInput[1])
let (bx, by): (Int, Int) = (bInput[0], bInput[1])
let (cx, cy): (Int, Int) = (cInput[0], cInput[1])

// ベクトルの成分
let (BAx, BAy): (Int, Int) = (ax - bx, ay - by)
let (BCx, BCy): (Int, Int) = (cx - bx, cy - by)
let (CAx, CAy): (Int, Int) = (ax - cx, ay - cy)
let (CBx, CBy): (Int, Int) = (bx - cx, by - cy)

// ∠Bが90°より大きい ⇔ 点Aの最短は点B
var answer: Double = 0
if (BAx * BCx + BAy * BCy < 0) {
  answer = sqrt(Double(BAx * BAx + BAy * BAy))
}
// ∠Cが90°より大きい ⇔ 点Aの最短は点C
else if (CAx * CBx + CAy * CBy < 0) {
  answer = sqrt(Double(CAx * CAx + CAy * CAy))
}
// ∠B,Cが90°以下 ⇔ 点Aの最短は線分BC上の点
else {
  answer = Double(abs(CAx * CBy - CAy * CBx)) / sqrt(Double(BCx * BCx + BCy * BCy))
}

print(answer)

034 - Nearest Points

問題 計算量 概要
最近点対問題 O(N log N) N個の点のうち、最近接の2点間の距離
凸包の構築 O(N log N) N個の点を全て含む多角形の最小面積
ボロノイ図の作成 O(N log N) N個の母点それぞれに対して最近接な領域
美術館問題 O(N log N) N頂点の多角形状をとる美術館の全領域を監視するために必要な監視カメラの最小台数
分割統治法を用いた最近点対の距離(の2乗)の取得
/// x座標でソート済の点群に対して、最近接の2点間の距離の2乗を取得する(計算量: O(*N* log *N*))
/// - parameter xSortedPoints: x座標の値でソートされた`[[Int]]`型の点群
/// - returns: `xSortedPoints`内での最近接の2点間の距離の2乗
func getNearestSquaredDistance(_ xSortedPoints: [[Int]]) -> Int {
  /*
   点が1つしかない場合:
   (最短距離の2乗) = Int.max
   */
  if (xSortedPoints.count == 1) { return Int.max }
  
  /*
   点が2つ以上ある場合:
   (最短距離の2乗) = min(同領域内のx, y座標が近接する2点間の最短距離の2乗,
   他領域同士のx, y座標が近接する2点間の最短距離の2乗)
   */
  let mid: Int = xSortedPoints.count / 2
  let midX: Int = xSortedPoints[mid][0]
  
  // x座標を基準とした点の分割 → 少なくともx座標が近接した点同士でしか比較しない
  var nearerSquaredDistance: Int = min(
    getNearestSquaredDistance([[Int]](xSortedPoints[0 ..< mid])),
    getNearestSquaredDistance([[Int]](xSortedPoints[mid ..< xSortedPoints.count]))
  )
  
  // x座標が近接した点同士のうち、y座標も近接している点同士の距離(の2乗)を求める
  let ySortedPoints: [[Int]] = xSortedPoints.sorted{ $0[1] < $1[1] }
  for i in 0 ..< (ySortedPoints.count - 1) {
    // 基準点Aは、x座標が中央値である点Bとのx座標の距離が最短距離未満である必要がある
    let midDx: Int = ySortedPoints[i][0] - midX
    if (midDx * midDx >= nearerSquaredDistance) { continue }
    
    for j in (i + 1) ..< ySortedPoints.count {
      // 基準点Aとのy座標の距離dyが最短距離以上となった時点で、
      // 以降の要素と基準点Aのy座標の距離はdy以上であることが確定しているため次の基準点の走査に移る
      let dy: Int = ySortedPoints[i][1] - ySortedPoints[j][1]
      let squaredDy: Int = dy * dy
      if (squaredDy >= nearerSquaredDistance) { break }
      
      let dx: Int = ySortedPoints[i][0] - ySortedPoints[j][0]
      let squaredDx: Int = dx * dx
      nearerSquaredDistance = min(nearerSquaredDistance, squaredDx + squaredDy)
    }
  }
  
  return nearerSquaredDistance
}
034 - Nearest Points
let n: Int = Int(readLine()!)!
var points: [[Int]] = [[Int]]()
for _ in 0 ..< n {
  points.append(readLine()!.split(separator: " ").map{ Int($0)! })
}

// x座標順にソート
points.sort{ $0[0] < $1[0] }

let nearestSquaredDistance: Int = getNearestSquaredDistance(points)
print(sqrt(Double(nearestSquaredDistance)))

035 - Two Circles

中心座標と半径がそれぞれ $ (x_1, y_1, r_1), (x_2, y_2, r_2) $ となる2つの円の位置関係は、2つの円の半径 $ r_1, r_2 $ と中心間の距離 $ d $ の関係によって分類できる

位置関係 半径と中心間の距離
離れている $ d > r_1 + r_2 $
外接 $ d = r_1 + r_2 $
2点で交わる $ (\ d < r_1 + r_2\ ) $ $ \land $ $ (\ d > |\ r_1 - r_2\ |\ ) $
内接 $ d = |\ r_1 - r_2\ | $
内部に存在 $ d < |\ r_1 - r_2\ | $
035 - Two Circles
let circle1: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (x1, y1, r1): (Int, Int, Int) = (circle1[0], circle1[1], circle1[2])
let circle2: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (x2, y2, r2): (Int, Int, Int) = (circle2[0], circle2[1], circle2[2])

let squaredDx: Int = (x1 - x2) * (x1 - x2)
let squaredDy: Int = (y1 - y2) * (y1 - y2)
let d: Double = sqrt(Double(squaredDx + squaredDy))
let rSum: Double = Double(r1 + r2)
let dr: Double = Double(abs(r1 - r2))
switch d {
  // 一方の円が他方の円を完全に含み、2つの円は接していない
  case let d where (d < dr): print("1")
  // 一方の円が他方の円を完全に含み、2つの円は接している
  case let d where (d == dr): print("2")
  // 2つの円が互いに交差する
  case let d where (d < rSum && d > dr): print("3")
  // 2つの円の内部に共通部分は存在しないが、2つの円は接している
  case let d where (d == rSum): print("4")
  // 2つの円の内部に共通部分は存在せず、2つの円は接していない
  case let d where (d > rSum): print("5")
  default: break
}
2
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
3