E869120本をSwiftで解く(問題58-90)

📚 書籍情報

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

演習問題集(AtCoder)

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

解説(公式)

E869120/math-algorithm-book/editorial

解答例

058 - Move on Squares 1

参考: 競技プログラミングで解法を思いつくための典型的な考え方

058 - Move on Squares 1

let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, x, y): (Int, Int, Int) = (input[0], input[1], input[2])

// |x| + |y| ≦ n かつ |x + y|とnの偶奇が一致 であれば到達可能
let isReachable: Bool = (abs(x) + abs(y) <= n && abs(x + y) % 2 == n % 2) ? true : false
if (isReachable == true) { print("Yes") }
else { print("No") }

059 - Power of Two

059 - Power of Two

let n: Int = Int(readLine()!)!

// 2^nの一の位は{2, 4, 8, 6}の繰り返し
let units: [Int] = [6, 2, 4, 8]
print(units[n % 4])

060 - Stones Game 1

060 - Stones Game 1

let n: Int = Int(readLine()!)!

if (n % 4 == 0) {
  print("Second")
}
else {
  print("First")
}

061 - Stones Game 2

$ n $個の石が残っている状態における現在手番のプレイヤーの勝敗を表にすると、以下のようになる。

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	L	W	L	W	W	W	L	W	W	W	W	W	W	W	L

上記の結果から、以下の規則性を見出せる。

$ n = 2^k - 1\ (k \geq 1) $ のときにのみ、現在手番のプレイヤーは負ける

あとは法則が全ての非負整数$ k $において成り立つことを証明すればよい。

$ k = 1 \Leftrightarrow n = 1 $ のとき、現在手番のプレイヤー(以下、$ A $とする)は負ける。

$ k = m \Leftrightarrow n = 2^m - 1\ (m \geq 1) $ のとき、$ A $が負けると仮定する。

ここで、$ k = m+1 \Leftrightarrow n = 2^{m+1} - 1 $ のときに$ A $を勝たせる場合、次に手番のプレイヤー(以下、$ B $とする)が負ける状態を作るため$ A $は$ 2^m $個の石を取ればよいが、$ n = 2^{m+1} - 1 $の状態で$ A $が取れる石の個数$ a $は、条件より次のように表される。

1 \leq a \leq \frac{2^{m+1} - 1}{2} = 2^m - \frac{1}{2} \\
\Leftrightarrow
1 \leq a \leq 2^m - 1\ (m \geq 1)

よって、$ k = m+1 $ の場合もAは負ける。
上記のことから、数学的帰納法より命題は真である。

061 - Stones Game 2

let n: Int = Int(readLine()!)!

var (isWinnable, isOne): (Bool, Bool) = (false, true)
// 2進数表記の2^m - 1は2^0の位から順に1が続き、2^kの位で0が初めて登場すると以降の位で1は登場しない
for i in 0 ... 60 {
  if (isOne == true) {
    if (n & (1 << i) == 0) { isOne = false }
  }
  else {
    // 2^m - 1でない場合は先手必勝
    if (n & (1 << i) != 0) { isWinnable = true }
  }
}

if (isWinnable == true) {
  print("First")
}
else {
  print("Second")
}

062 - Teleporter

062 - Teleporter

let k: Int = readLine()!.split(separator: " ").map{ Int($0)! }[1]
var destinations: [Int] = [0]
readLine()!.split(separator: " ").forEach{ destinations.append(Int($0)!) }

var visitedCount: [Int] = [Int](repeating: 0, count: destinations.count)

// 最初の街1は到達済とする
visitedCount[1] += 1
var (notLoops, loops): ([Int], [Int]) = ([1] ,[Int]())

var next: Int = destinations[1]
while (true) {
  // 未到達の街であればループ対象外
  if (visitedCount[next] == 0) {
    notLoops.append(next)
    visitedCount[next] += 1
    next = destinations[next]
  }
  // 到達済の街であればループ対象なので、初回のループにのみ注目
  else if (visitedCount[next] == 1) {
    loops.append(next)
    visitedCount[next] += 1
    next = destinations[next]
  }
  // 2回目以降のループは注目しない
  else { break }
}

// kがループになる前の移動回数である場合
if (k < notLoops.count) {
  print(notLoops[k])
}
// kがループになった後の移動回数である場合
else {
  print(loops[(k - notLoops.count) % loops.count])
}

063 - Move on Squares 2

$ 2 $ 以上の非負整数 $n$ を用いて表される $ n \times n $ のマスについて、$ n $ が奇数の場合は一筆書きができない

証明
奇数回の移動によって到達可能なマスを $ A $、偶数回の移動によって到達可能なマスを $ B $ とすると、出発地点は $ B $ であり、ゴール直前のマスは $ A $ でなければならない。

ここで、一筆書きをする際の直前のマスへの移動には $ n^2 - 1 $ 回の移動が必要であるが、$ n $ が奇数の場合、直前のマスは $ B $ となるため条件に反する。

063 - Move on Squares 2

let n: Int = Int(readLine()!)!

if (n % 2 == 0) {
  print("Yes")
}
else {
  print("No")
}

064 - All Zero

064 - All Zero

var sum: Int = 0
let k: Int = readLine()!.split(separator: " ").map{ Int($0)! }[1]
readLine()!.split(separator: " ").forEach{ sum += Int($0)! }

if (k < sum || k % 2 != sum % 2) {
  print("No")
}
else {
  print("Yes")
}

065 - Bishop

065 - Bishop

let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (h, w): (Int, Int) = (input[0], input[1])

// 1行または1列の場合は移動不可
if (h == 1 || w == 1) { print(1) }
// 2x2以上のマスの場合
else {
  // 奇数x奇数である場合は移動可能マス数は「マス数の半分 + 1」
  if (h % 2 == 1 && w % 2 == 1) { print((h * w / 2) + 1) }
  // 縦横のどちらかが偶数の場合は移動可能マス数は「マス数の半分」
  else { print(h * w / 2) }
}

066 - Three Cards

全探索に時間がかかる場合は、走査範囲を絞れるだけ絞る

066 - Three Cards

let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, k): (Int, Int) = (input[0], input[1])

/// 各カードの差の絶対値がk未満(= k - 1以下)になる余事象の場合の数
var complement: Int = 0
/*
 黒・白・灰のカードの値をそれぞれa, b, cとすると、aの値を固定することで
 b, cの走査範囲を以下のように絞ることができる
 max(1, a - (k - 1)) ≦ b, c ≦ min(a + (k - 1), n)
 */
for a in 1 ... n {
  for b in max(1, a - (k - 1)) ... min(a + (k - 1), n) {
    for c in max(1, a - (k - 1)) ... min(a + (k - 1), n) {
      if (abs(b - c) <= k - 1) { complement += 1 }
    }
  }
}

print(n * n * n - complement)

067 - Cross Sum（★2）

067 - Cross Sum（★2）

let hw: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (h, w): (Int, Int) = (hw[0], hw[1])
var nums: [[Int]] = [[Int]](repeating: [0], count: h + 1)
for i in 1 ... h {
  nums[i] += readLine()!.split(separator: " ").map{ Int($0)! }
}

var (rowSums, colSums): ([Int], [Int]) = ([0], [0])
var (colSum, answer): (Int, Int)
var output: String = ""
// 行単位での合計
for r in 1 ... h {
  // 行合計
  rowSums.append(nums[r].reduce(0, +))
}

// 列単位での合計
for c in 1 ... w {
  colSum = 0
  nums[1 ... h].forEach{ colSum += $0[c] }
  colSums.append(colSum)
}

for r in 1 ... h {
  output = ""
  for c in 1 ... w {
    answer = rowSums[r] + colSums[c] - nums[r][c]
    output += (c != w) ? "\(answer) " : "\(answer)"
  }
  print(output)
}

068 - Number of Multiples 2

集合 $ S_1, S_2, S_3, \cdots , S_n $ の和集合の要素数は、1つ以上の集合を選ぶ全てのパターンに対して以下の操作を行った結果となる

奇数個選ぶ場合 $ \Leftrightarrow $ 集合群の共通部の要素数を加算
偶数個(※0を除く)選ぶ場合 $ \Leftrightarrow $ 集合群の共通部の要素数を減算

最小公約数・最小公倍数の取得

/// ユークリッドの互除法を用いて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 getLcm(_ num1: Int, _ num2: Int) -> Int {
  let gcd: Int = getGcd(num1, num2)
  // 除算を先に行うことでInt型のオーバーフローを避ける
  return num1 / gcd * num2
}

068 - Number of Multiples 2

let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, k): (Int, Int) = (input[0], input[1])
let nums: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }

/// `nums`から選択した値の数
var choices: Int
/// `nums`から選択した値の最小公倍数
var lcm: Int

var answer: Int = 0
// ビット全探索(計算量: O(2^k))
// k桁の2進数を用意し、フラグが立っていれば桁に対応するnumsの値を選択することとする
for bit in 1 ..< (1 << k) {
  (choices, lcm) = (0, 1)
  
  for index in 0 ..< k {
    if (bit & (1 << index) != 0) {
      choices += 1
      lcm = getLcm(lcm, nums[index])
    }
  }
  
  // numsから値を奇数個選択した場合は要素数を加算
  if (choices % 2 == 1) {
    answer += n / lcm
  }
  // numsから値を偶数個選択した場合は要素数を減算
  else {
    answer -= n / lcm
  }
}

print(answer)

069 - Product Max

069 - Product Max

let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (a, b, c, d): (Int, Int, Int, Int) = (input[0], input[1], input[2], input[3])

print(max(a * c, a * d, b * c, b * d))

070 - Axis-Parallel Rectangle

070 - Axis-Parallel Rectangle

let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, k): (Int, Int) = (input[0], input[1])

var nodes: [[Int]] = [[Int]]()
for _ in 0 ..< n {
  nodes.append(readLine()!.split(separator: " ").map{ Int($0)! })
}

var (count, area, answer): (Int, Int, Int) = (0, Int.max, Int.max)
var (left, right, top, bottom): (Int, Int, Int, Int)
for l in 0 ..< n {
  for r in 0 ..< n {
    for t in 0 ..< n {
      for b in 0 ..< n {
        // x, y座標の範囲を決める
        (left, right, top, bottom) = (
          nodes[l][0],
          nodes[r][0],
          nodes[t][1],
          nodes[b][1]
        )
        
        // 範囲内に含まれる点の個数をカウント
        count = 0
        for i in 0 ..< n {
          if (left <= nodes[i][0] && nodes[i][0] <= right &&
              nodes[i][1] <= top && bottom <= nodes[i][1]) {
            count += 1
          }
        }
        
        // 最小面積を求める
        if (count >= k) {
          area = (right - left) * (top - bottom)
          if (area < answer) { answer = area }
        }
      }
    }
  }
}

print(answer)

071 - Linear Programming

線形計画法(Linear Programming; LP) … 他の線形不等式(=1次不等式)の制約条件を全て満たす線形関数 $ f(x, y) $ の取りうる最大または最小の値を求める手法

例として、以下の制約を満たす線形関数 $ f(x, y) = x + y $ の最大値について検討する。

• $ 3x + y \leq 10 $
• $ 2x + y \leq 7 $
• $ 3x + 4y \leq 19 $
• $ x + 2y \leq 9 $

線形関数 $ f(x, y) $ の最大値は2直線の交点となるため、2直線

a_{i}x + b_{i}y = c_{i} \Leftrightarrow y = - \frac{a_i}{b_i}x + \frac{c_i}{b_i} \\
a_{j}x + b_{j}y = c_{j} \Leftrightarrow y = - \frac{a_j}{b_j}x + \frac{c_j}{b_j}

の交点 $ (x, y) $ を求めればよい。

ここで、$ \frac{a_i}{b_i} = \frac{a_j}{b_j} \Leftrightarrow a_{i}b_{j} = a_{j}b_{i} $ のときは2直線が平行となるため、交点を求める必要はない。

$ a_{i}b_{j} \neq a_{j}b_{i} $ のとき、交点 $ (x, y) $ は以下のように表せる。

(x, y) = (\frac{ c_{i}b_{j} - c_{j}b_{i} }{ a_{i}b_{j} - a_{j}b_{i} }, \frac{ c_{i}a_{j} - c_{j}a_{i} }{ b_{i}a_{j} - b_{j}a_{i} } )

071 - Linear Programming

let n: Int = Int(readLine()!)!
var nums: [[Double]] = [[Double]]()
for _ in 0 ..< n {
  nums.append(readLine()!.split(separator: " ").map{ Double($0)! })
}

var intersection: [Double] = [0, 0]
var answer: Double = Double(Int.min)
var isSatisfied: Bool
for i in 0 ..< n - 1 {
  for j in i + 1 ..< n {
    // 2直線の交点の座標を求める
    (intersection[0], intersection[1]) = (
      (nums[i][2] * nums[j][1] - nums[j][2] * nums[i][1]) / (nums[i][0] * nums[j][1] - nums[j][0] * nums[i][1]),
      (nums[i][2] * nums[j][0] - nums[j][2] * nums[i][0]) / (nums[i][1] * nums[j][0] - nums[j][1] * nums[i][0])
    )
    
    // 全ての条件式を満たすかどうかを判定
    isSatisfied = true
    for k in 0 ..< n where (nums[k][0] * intersection[0] + nums[k][1] * intersection[1] > nums[k][2]) {
      isSatisfied = false
      break
    }
    
    if (isSatisfied == true) { answer = max(answer, intersection[0] + intersection[1]) }
  }
}

print(answer)

072 - Max GCD 2

072 - Max GCD 2

let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (a, b): (Int, Int) = (input[0], input[1])

// iの倍数がa以上b未満の間に2つ以上存在する場合は最大公約数をiにセット
var answer: Int = 1
for gcd in 1 ..< b where (b / gcd > (a + gcd - 1) / gcd) {
  answer = max(answer, gcd)
}

print(answer)

073 - Sum of Maximum

073 - Sum of Maximum

let n: Int = Int(readLine()!)!
let nums: [Int] = [0] + readLine()!.split(separator: " ").map{ Int($0)! }
let div: Int = 1000000007

var answer: Int = 0
// index枚選ぶ場合の数(2^index)
var cases: [Int] = [1]
for i in 1 ... n {
  cases.append(2 * cases[i - 1] % div)
}

for i in 1 ... n {
  // nums[i]が最大値となる場合の数 = nums[i]を選ぶ場合の数(=1) × (i - 1)枚の中から選ぶ場合の数
  answer += nums[i] * cases[i - 1]
  answer %= div
}

print(answer)

074 - Sum of difference Easy

074 - Sum of difference Easy

let n: Int = Int(readLine()!)!
let nums: [Int] = [0] + readLine()!.split(separator: " ").map{ Int($0)! }

var (initial, answer): (Int, Int) = (1 - n, 0)
// nums[i]が加算される回数は初項initial, 公差2の等差数列の一般項initial + (i - 1) * 2で表される
for i in 1 ... n {
  answer += nums[i] * (initial + (i - 1) * 2)
}

print(answer)

075 - Pyramid

組合せの総数の剰余を取得

/// 繰り返し二乗法を用いて累乗の剰余を取得する(計算量: O(log *exp*))
/// - parameters:
///  - base: `Int`型の底(base)
///  - exp: `Int`型の冪指数(exponent)
///  - div: `Int`型の除数(division)
/// - returns: 累乗`base`^`exp`を除数`div`で割ったときの剰余
func getModPower(_ base: Int, _ exp: Int, _ div: Int) -> Int {
  var (mod, answer): (Int, Int) = (base, 1)
  
  // 冪指数expについて、2^i(0 ≦ i ≦ 30)のフラグが立っている場合は剰余を更新
  // → 10^9 < 2^30であるため、iの最大値を30とする
  for i in 0 ..< 30 {
    if (exp & (1 << i) != 0) {
      answer *= mod
      answer %= div
    }
    mod *= mod
    mod %= div
  }
  
  return answer
}

/// 繰り返し二乗法を用いて組合せの総数の剰余を取得する(計算量: O(log *div*))
/// - parameters:
///  - n: `Int`型の要素数
///  - r: `Int`型の組合せ数
///  - factMods: `n!`を`div`で割った剰余を格納する`[Int]`型配列
///  - div: `Int`型の除数
/// - returns: nCrを`div`で割ったときの剰余
func getCombinationMod2(_ n: Int, _ r: Int, _ factMods: [Int], _ div: Int) -> Int {
  // nCrの分母(=除数)となるr!,(n-r)!のモジュラ逆数を求める(計算量: O(log div))
  let (rFactMMI, nrFactMMI): (Int, Int) = (
    getModPower(factMods[r], div - 2, div) % div,
    getModPower(factMods[n - r], div - 2, div) % div
  )
  
  return factMods[n] * rFactMMI % div * nrFactMMI % div
}

075 - Pyramid

let n: Int = Int(readLine()!)!
let nums: [Int] = [0] + readLine()!.split(separator: " ").map{ Int($0)! }
let div: Int = 1000000007

// 階乗の剰余を取得(計算量: O(N))
var factMods: [Int] = [Int](repeating: 1, count: n + 1)
for i in 1 ... n {
  factMods[i] = (factMods[i - 1] * i) % div
}

// nums[i]は最上段に到達するまでの移動回数n - 1のうち、右方向に(i - 1)回進む場合の数だけ加算
var answer: Int = 0
for i in 1 ... n {
  answer += nums[i] * getCombinationMod2(n - 1, i - 1, factMods, div)
  answer %= div
}

print(answer)

076 - Sum of difference

076 - Sum of difference

let n: Int = Int(readLine()!)!
let nums: [Int] = [0] + readLine()!.split(separator: " ").map{ Int($0)! }.sorted()

var (initial, answer): (Int, Int) = (1 - n, 0)
// nums[i]が加算される回数は初項initial, 公差2の等差数列の一般項initial + (i - 1) * 2で表される
for i in 1 ... n {
  answer += nums[i] * (initial + (i - 1) * 2)
}

print(answer)

077 - Distance Sum

077 - Distance Sum

let n: Int = Int(readLine()!)!
var (x, y): ([Int], [Int]) = ([Int.min], [Int.min])
var input: [Int]
for _ in 1 ... n {
  input = readLine()!.split(separator: " ").map{ Int($0)! }
  x.append(input[0])
  y.append(input[1])
}
x.sort()
y.sort()

var (initial, answer) = (1 - n, 0)
// nums[i]が加算される回数は初項initial, 公差2の等差数列の一般項initial + (i - 1) * 2で表される
for i in 1 ... n {
  answer += (x[i] + y[i]) * (initial + (i - 1) * 2)
}

print(answer)

078 - Difference Optimization 1

最適化問題(Optimization) … 全ての制約を満たす値の最大・最小値を求める問題

幅優先探索を用いた最短経路長の取得

/// 幅優先探索を用いてノード群の最短経路長を取得(計算量: O(*M + N*); *M*はエッジ数、*N*はノード数)
/// - parameter nodes: `[[Int]]`型の隣接リスト表現(最初のインデックスはダミー)
/// - returns: 最短経路長を格納した`[Int]`型配列(最初のインデックスはダミー)
func getShortestDistances(_ nodes: [[Int]], _ start: Int) -> [Int] {
  var distances: [Int] = [Int](repeating: -1, count: nodes.count)
  
  /// 幅優先探索
  /// - parameter start: 始点のノード番号
  func bfs(_ start: Int) -> Void {
    var queue: [Int] = [Int]()
    // 始点の最短経路長を0にセット、キューに追加
    distances[start] = 0
    queue.append(start)
    
    while (queue.isEmpty == false) {
      // キューから先頭要素(ノード番号)を抽出
      let pop: Int = queue.removeFirst()
      
      // 抽出したノードと隣接するノードを走査
      for i in 0 ..< nodes[pop].count {
        let neighbor: Int = nodes[pop][i]
        
        // 隣接ノードが未到達ノードであれば最短経路長を更新、キューに追加
        if (distances[neighbor] == -1) {
          distances[neighbor] = distances[pop] + 1
          queue.append(neighbor)
        }
      }
    }
  }
  
  // ノード1を始点とした幅優先探索
  bfs(start)
  
  return distances
}

078 - Difference Optimization 1

let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, m): (Int, Int) = (input[0], input[1])

// 関係性をグラフとして処理
var nodes: [[Int]] = [[Int]](repeating: [], count: n + 1)
nodes[0] = [0]
var members: [Int]
for _ in 1 ... m {
  members = readLine()!.split(separator: " ").map{ Int($0)! }
  nodes[members[0]].append(members[1])
  nodes[members[1]].append(members[0])
}

// 幅優先探索を用いた最短経路長の取得
let answers: [Int] = getShortestDistances(nodes, 1)

// 最短経路長が120を超える または 存在しない(=-1)場合は最大値(=120)を出力
for answer in answers[1 ... n] {
  if (answer > 120 || answer == -1) {
    print(120)
  }
  else {
    print(answer)
  }
}

079 - ModSum

079 - ModSum

let n: Int = Int(readLine()!)!

/*
 N = {1, 2, 3, .. , n - 1, n}に対して、
 P = {1 + 1, 2 + 1, 3 + 1, .. , (n - 1) + 1, 1}と設定した場合が
 N_{i} % P_{i} の総和が最大となる
 → 1からn-1までの総和が最大値
 */
print((n - 1) * n / 2)

080 - Difference Optimization 2

Dijkstra法を用いた最短経路長の取得

/// Dijkstra法を用いてノード0を始点とした各ノードへの重み付き有向グラフの最短経路長を取得する(計算量: O((*M + N*) log *N*))
/// - parameter nodes: `[[[Int]]]`型の隣接リスト表現
/// - returns: 各ノードへの最短経路長を格納した`[Int]`型配列
func getShortestPath(_ nodes: [[[Int]]]) -> [Int] {
  /// ノード0からインデックスに対応するノードまでの暫定累計コスト
  var distances: [Int] = [Int](repeating: Int.max, count: nodes.count)
  /// 始点ノードとして設定済かどうか
  var isDetermined: [Bool] = [Bool](repeating: false, count: nodes.count)
  /// 累計コストを優先度とする優先度付きキュー([隣接ノード, 累計コスト])
  var pQueue: PriorityQueue<(Int, Int)> = PriorityQueue<(Int, Int)>{ $0.1 < $1.1 }
  
  // 始点となるノード0を累計コスト0としてキューに追加
  pQueue.append((0, 0))
  
  while (pQueue.isEmpty == false) {
    // ノード0からの累計コストが最小となる始点ノード
    let from: Int = pQueue.popFirst()!.0
    
    // すでに始点ノードとして走査済の場合はスキップ
    if (isDetermined[from] == true) { continue }
    
    // 始点ノードまでの累計コスト(始点ノードが0の場合は0とする)
    let distanceToFrom: Int
    if (from == 0) { distanceToFrom = 0 }
    else { distanceToFrom = distances[from] }
    
    // 最短距離が確定していない隣接ノードを走査
    for node in nodes[from] where (isDetermined[node[0]] == false) {
      let (to, distance): (Int, Int) = (node[0], distanceToFrom + node[1])
      
      // 暫定累計コストの更新
      distances[to] = min(distances[to], distance)
      // 累計コストが小さい順にソートしながらキューに挿入
      pQueue.append((to, distances[to]))
    }
    
    // 始点ノードを探索済にする
    isDetermined[from] = true
  }
  
  return distances
}

080 - Difference Optimization 2

let input: [Int] = readLine()!.split(separator: " ").map{ Int(String($0))! }
let (n, m): (Int, Int) = (input[0], input[1])

// nodes[i]はノードiの[隣接ノード - 1, 移動コスト]を格納する
var nodes: [[[Int]]] = [[[Int]]](repeating: [[Int]](), count: n)
for _ in 0 ..< m {
  let input2: [Int] = readLine()!.split(separator: " ").map{ Int(String($0))! }
  nodes[input2[0] - 1].append([input2[1] - 1, input2[2]])
  nodes[input2[1] - 1].append([input2[0] - 1, input2[2]])
}

// Dijkstra法を用いて各ノードへの最短経路を取得する
let shortestPath: [Int] = getShortestPath(nodes)

// ノードnまでの最短経路長が初期値Int.maxである場合は-1を出力
if (shortestPath[n - 1] == Int.max) {
  print(-1)
}
else {
  print(shortestPath[n - 1])
}

081 - Bill Changing Problem

貪欲法(Greedy Algorithm) … 局所的に最適解を選択することで解を求める手法

参考: 硬貨の問題が貪欲法で解けるための条件

小さい順にソートした数列 $ \lbrace a_1, a_2, \dots , a_n \rbrace $ について、$ a_i
(1 \leq i \leq n-1) $ に着目する。
非負整数 $ k $ を用いて $ ka_i \geq a_{i+1} $ となる最小の整数を $ p $ 、その差を $ \delta (= pa_i - a_{i+1}) $ とすると、貪欲法を用いた場合の解 $ H(n) $ について常に以下の不等式が成り立てば貪欲法が利用できる。
$$ H(\delta) \leq p - 1 $$

081 - Bill Changing Problem

let n: Int = Int(readLine()!)!
print((n / 10000) + (n % 10000 / 5000) + (n % 10000 % 5000 / 1000))

082 - Interval Scheduling Problem

082 - Interval Scheduling Problem

let n: Int = Int(readLine()!)!

var intervals: [[Int]] = [[Int.min, Int.min]]
for _ in 1 ... n {
  intervals.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
// 終了時刻の早い順にソート
intervals.sort{ $0[1] < $1[1] }

var (now, answer): (Int, Int) = (intervals[0][1], 0)
for i in 1 ... n {
  // 現在の時刻が次の映画の開始時刻より早ければ次の映画は見れる
  if (now <= intervals[i][0]) {
    // 現在時刻を次の映画の終了時刻にセット
    now = intervals[i][1]
    answer += 1
  }
}

print(answer)

083 - We Used to Sing a Song Together（★3）

083 - We Used to Sing a Song Together（★3）

let n: Int = Int(readLine()!)!
let kids: [Int] = readLine()!.split(separator: " ").map{ Int(String($0))! }.sorted()
let schools: [Int] = readLine()!.split(separator: " ").map{ Int(String($0))! }.sorted()

var answer: Int = 0
for i in 0 ..< n {
  answer += abs(kids[i] - schools[i])
}
print(answer)

084 - Sqrt Inequality

084 - Sqrt Inequality

/*
 √a + √b < √c の両辺を2乗すると
 2√(ab) < c - a - b
 c - a - b ≦ 0 ⇔ 条件を満たさない
 c - a - b > 0 のとき、両辺を2乗すると
 4 * ab < (c - a - b)^2
 */
let input: [Int] = readLine()!.split(separator: " ").map { Int($0)! }
let (a, b, c): (Int, Int, Int) = (input[0], input[1], input[2])
let d: Int = c - a - b

if (d > 0 && 4 * a * b < d * d) { print("Yes") }
else { print("No") }

085 - Two Conditions

085 - Two Conditions

import Foundation

let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, x, y): (Int, Int, Int) = (input[0], input[1], input[2])
for a in 1 ... n {
  for b in a ... n {
    for c in b ... n {
      for d in c ... n {
        let sum: Int = a + b + c + d
        let product: Int = a * b * c * d
        if (sum == x && product == y) {
          print("Yes")
          exit(0)
        }
      }
    }
  }
}
print("No")

086 - Parentheses Check

086 - Parentheses Check

import Foundation

let n: Int = Int(readLine()!)!
let s: [String] = Array(readLine()!).map{ String($0) }

var lp: Int = 0
for i in 0 ..< n {
  if (lp >= 0) {
    lp += (s[i] == "(") ? 1 : -1
  }
  else {
    print("No")
    exit(0)
  }
}

print(lp == 0 ? "Yes" : "No")

087 - Simple Math Easy

087 - Simple Math Easy

let n: Int = Int(readLine()!)!
let div: Int = 1000000007

let sum1ToN: Int = n * (n + 1) / 2 % div
print(sum1ToN * sum1ToN % div)

088 - Simple Math

088 - Simple Math

/// 1から`n`までの総和を`div`で割った剰余を取得する
/// - parameters:
///  - n: `Int`型の最大値
///  - div: `Int`型の除数
/// - returns: `1 ... n`の総和を`div`で割った剰余
func sumToNum(_ n: Int, _ div:Int = 998244353) -> Int {
  return n * (n + 1) / 2 % div
}

let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (a, b, c): (Int, Int, Int) = (input[0], input[1], input[2])
let div: Int = 998244353

let sumA: Int = sumToNum(a)
let sumB: Int = sumToNum(b)
let sumC: Int = sumToNum(c)

print(sumA * sumB % div * sumC % div)

089 - Log Inequality 2

089 - Log Inequality 2

import Foundation

let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (a, b, c): (Int, Int, Int) = (input[0], input[1], input[2])

// a ≧ 1の制約上、a ≧ 1^bとなる
if (c == 1) {
  print("No")
  exit(0)
}

/*
 log_2{a} < b * log_2{c}
 ⇔ a < c^b
 */
var fact: Int = 1
// ここで、c ≧ 2であることが保証されているが、2^60 > 10^18よりループ回数は最大でも60回程度に収まる
for _ in 1 ... b {
  // オーバーフローを避けるためa < fact * cを変形
  if (a / c < fact) {
    print("Yes")
    exit(0)
  }
  fact *= c
}
print("No")

090 - Digit Product Equation（★7）

090 - Digit Product Equation（★7）

/// 各桁の値の積を求める
/// - parameter n: `Int`型の整数値
/// - returns: `n`の各桁の値の積
func productEachDigit(_ n: Int) -> Int {
  let digits: [Int] = Array(String(n)).map{ String($0) }.map{ Int($0)! }
  return digits.reduce(1, *)
}

/// `f(x)`の候補を取得
/// - parameters:
///  - digit: `num`の桁数
///  - num: `元の数`
func enumerateFx(_ digit: Int, _ num: Int) -> Void {
  // numが11桁に達した場合
  // → numをnumsに追加し、再帰処理を終了する
  if (digit == 11) {
    nums.insert(productEachDigit(num))
    return
  }
  
  // numが11桁に達していない場合
  // → 現在の1の位の値以上の値を1の位に追加
  let min: Int = num % 10
  for i in min ... 9 {
    enumerateFx(digit + 1, num * 10 + i)
  }
}

let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, b): (Int, Int) = (input[0], input[1])

/// `f(x)`として考えられる値
var nums: Set<Int> = Set<Int>()

// f(x)として考えられる値を列挙
enumerateFx(0, 0)

var answer: Int = 0
for num in nums {
  // f(x)として考えられる値をもとにmを算出(m ≧ 1がここで保証される)
  let m: Int = num + b
  // mをもとにf(m)を算出
  let prodM: Int = productEachDigit(m)
  if (m - prodM == b && m <= n) {
    answer += 1
  }
}

print(answer)