LoginSignup
1
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@b150005

E869120本をSwiftで解く(問題36-57)

Last updated at Posted at 2022-06-17

📚 書籍情報

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

演習問題集(AtCoder)

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

解説(公式)

E869120/math-algorithm-book/editorial

解答例

036 - : (Colon)

時針の先端の座標を取得
/// 時・分・秒を表す列挙型
enum Hand {
  /// 時
  case hour
  /// 分
  case minute
  /// 秒
  case second
}

/// 時刻をもとに短針・長針・秒針のベクトルの成分を取得する
/// - note: 針の長さを1, 正午を基準に針が進んだ角度をθとすると、
///         針の先端のx座標はcos(90° - θ) = sinθ, y座標はsin(90° - θ) = cosθ で表される
/// - parameters:
///   - hour: 時
///   - min: 分
///   - sec: 秒
///   - len: 針の長さ
///   - type: 短針・長針・秒針を示す`Hand`型の列挙ケース
/// - returns: `[Double]`型で表される短針・長針・秒針のベクトルのx, y成分
func getHandVector(_ hour: Int = 0, _ min: Int = 0, _ sec: Int = 0, _ len: Int = 1, _ type: Hand) -> [Double] {
  var degree: Double = 0
  switch type {
    case .hour:
      degree = Double((hour % 12) * 60 * 60 + min * 60 + sec) / 120
    case .minute:
      degree = Double(min * 60 + sec) / 10
    case .second:
      degree = Double(sec) * 6
  }
  
  // 度数法[°] → 弧度法[rad] への変換
  let radian: Double = degree * Double.pi / 180
  
  return [Double(len) * sin(radian), Double(len) * cos(radian)]
}
036 - : (Colon)
let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (a, b, h, m): (Int, Int, Int, Int) = (input[0], input[1], input[2], input[3])

// 短針・長針のベクトルの成分(=先端の平面座標)を取得
let vecHour: [Double] = getHandVector(h, m, 0, a, .hour)
let vecMin: [Double] = getHandVector(h, m, 0, b, .minute)

// 短針・長針の2つの端点の差分を算出
let dx: Double = vecHour[0] - vecMin[0]
let dy: Double = vecHour[1] - vecMin[1]

print(sqrt(dx * dx + dy * dy))

037 - Intersection

外積を用いた領域判定
/// 直線で2つに分割される領域に対して、与えられた2点がそれぞれ(直線上を含む)異なる領域に存在するかどうか
/// - parameters:
///  - endPoints: 領域を分割する直線を形成する2つの点
///  - comparedPoints: 異なる領域に存在するかどうかを調べる2つの点
/// - returns: 2点がそれぞれ異なる領域に存在する場合は`true`, 同じ領域に存在する場合は`false`
func existsSeparately(_ endPoints: [[Int]], _ comparedPoints: [[Int]]) -> Bool {
  let (start, end): ([Int], [Int]) = (endPoints[0], endPoints[1])
  let (comp1, comp2): ([Int], [Int]) = (comparedPoints[0], comparedPoints[1])
  
  let vecBase: [Int] = [end[0] - start[0], end[1] - start[1]]
  let vecCompared1: [Int] = [comp1[0] - start[0], comp1[1] - start[1]]
  let vecCompared2: [Int] = [comp2[0] - start[0], comp2[1] - start[1]]
  
  // 基準ベクトルと残りのベクトルの外積同士の積が正の場合は同じ領域に存在
  // → オーバーフロー対策のため、外積の符号(正・負・0)だけ区別できるようにする
  let (op1, op2): (Int, Int)
  switch (vecBase[0] * vecCompared1[1] - vecBase[1] * vecCompared1[0]) {
    case let op where (op < 0): op1 = -1
    case let op where (op > 0): op1 = 1
    default: op1 = 0
  }
  switch (vecBase[0] * vecCompared2[1] - vecBase[1] * vecCompared2[0]) {
    case let op where (op < 0): op2 = -1
    case let op where (op > 0): op2 = 1
    default: op2 = 0
  }
  
  /*
   op1 = op2 = 0となる(⇔全ての点が一直線上に存在する)場合は2つの線分が重なっているかどうかで交差を判定
   直線を形成する2点のうちxまたはy座標が小さい順にそれぞれ点A, Bとし、
   残りの2点のうちxまたはy座標が小さい順にそれぞれ点C, Dとすると、
   A < B < C (< D)または C < D < A (< B) となる場合は交差しない
   */
  if (op1 == 0 && op2 == 0) {
    // 全ての点がy軸と平行に並んでいなければx座標を基準にソート
    if (start[0] != end[0]) {
      let xSortedEndPoints: [[Int]] = endPoints.sorted{ $0[0] < $1[0] }
      let (ax, bx): (Int, Int) = (xSortedEndPoints[0][0], xSortedEndPoints[1][0])
      let xSortedCompPoints: [[Int]] = comparedPoints.sorted{ $0[0] < $1[0] }
      let (cx, dx): (Int, Int) = (xSortedCompPoints[0][0], xSortedCompPoints[1][0])
      
      if (ax < cx && bx < cx) || (cx < ax && dx < ax) { return false }
    }
    // 全ての点がy軸と平行に並んでいればy座標を基準にソート
    else {
      let ySortedEndPoints: [[Int]] = endPoints.sorted{ $0[1] < $1[1] }
      let (ay, by): (Int, Int) = (ySortedEndPoints[0][1], ySortedEndPoints[1][1])
      let ySortedCompPoints: [[Int]] = comparedPoints.sorted{ $0[1] < $1[1] }
      let (cy, dy): (Int, Int) = (ySortedCompPoints[0][1], ySortedCompPoints[1][1])
      
      if (ay < cy && by < cy) || (cy < ay && dy < ay) { return false }
    }
  }
  
  if (op1 * op2 <= 0) { return true }
  else { return false }
}
037 - Intersection
let n: Int = 4
var points: [[Int]] = [[Int]](repeating: [], count: n)
for i in 0 ..< n {
  points[i] = readLine()!.split(separator: " ").map{ Int($0)! }
}

if (existsSeparately([points[0], points[1]], [points[2], points[3]]) == true &&
    existsSeparately([points[2], points[3]], [points[0], points[1]]) == true) {
  print("Yes")
}
else {
  print("No")
}

038 - How Many Guests?

038 - How Many Guests?
let q: Int = readLine()!.split(separator: " ").map{ Int($0)! }[1]
// 0〜N日目の累積和を算出
var cumSums: [Int] = [0]
readLine()!.split(separator: " ").map{ Int($0)! }.forEach{
  cumSums.append(cumSums.last! + $0)
}

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

for question in questions {
  let (l, r): (Int, Int) = (question[0], question[1])
  print(cumSums[r] - cumSums[l - 1])
}

039 - Snowy Days

039 - Snowy Days
let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, q): (Int, Int) = (input[0], input[1])
/// 1〜N日目の積雪量の階差
var differences: [Int] = [Int](repeating: 0, count: n)
for _ in 0 ..< q {
  let news: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
  let (l, r, snow): (Int, Int, Int) = (news[0], news[1], news[2])
  differences[l - 1] += snow
  if (r != n) {
    differences[r] -= snow
  }
}

var output: String = ""
for i in 1 ..< n {
  // i(=次の日)の積雪量の階差の符号で(i - 1)日目とi日目の積雪量を比較
  switch (differences[i]) {
    case let d where (d < 0): output += ">"
    case let d where (d > 0): output += "<"
    default: output += "="
  }
}

print(output)

040 - Travel

040 - Travel
_ = readLine()!
var sums: [Int] = [0, 0]
readLine()!.split(separator: " ").map{ Int($0)! }.forEach{ sums.append(sums.last! + $0) }

let m: Int = Int(readLine()!)!
var stations: [Int] = [Int]()
for _ in 0 ..< m {
  stations.append(Int(readLine()!)!)
}

var answer: Int = 0
for i in 1 ..< stations.count {
  answer += abs(sums[stations[i]] - sums[stations[i - 1]])
}

print(answer)

041 - Convenience Store 2

いもす法 … 階差(difference)と累積和(cumulative sum)が逆の性質をもつことを利用し、N個の配列とQ回の変動に対して変動区間の開始と終了のみを記録することで累積和の計算量を従来のO(NQ)からO(N + Q)に抑えた手法

041 - Convenience Store 2
let (t, n): (Int, Int) = (Int(readLine()!)!, Int(readLine()!)!)
var changes: [Int] = [Int](repeating: 0, count: t + 1)
for _ in 0 ..< n {
  let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
  let (start, end): (Int, Int) = (input[0], input[1])
  
  changes[start] += 1
  changes[end] -= 1
}

var sum: Int = 0
for i in 0 ..< t {
  sum += changes[i]
  print(sum)
}

数値計算

問題 概要
ニュートン法 $ f(x) = 0 $ となるような根 $ x $
数値微分・数値積分 微積分の演算結果の近似値
多倍長整数計算 巨大な整数同士の演算結果
Karatsuba法, 高速フーリエ変換

042 - Sum of Divisors

参考: 計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜

042 - Sum of Divisors
let n: Int = Int(readLine()!)!

// iの倍数全てに1を加算
var divisorCounts: [Int] = [Int](repeating: 0, count: n + 1)
for i in 1 ... n {
  for j in stride(from: i, through: n, by: i) {
    divisorCounts[j] += 1
  }
}

var answer: Int = 0
for i in 1 ... n {
  answer += i * divisorCounts[i]
}
print(answer)

043 - Is It Connected?

アルゴリズム 概要
深さ優先探索(Depth First Search) 進めるだけ進んだ先のノード周辺を探索(LIFO, スタック)
幅優先探索(Bredth First Search) 出発地点のノード周辺を探索(FIFO, キュー)
問題 計算量 概要
単一始点最短経路問題(重みなしグラフ) O(M + N) 任意のノードから各ノードまでの最短経路長
幅優先探索
^ (重み付きグラフ) O($ N^2 $) Dijkstra法
^ (重み付きグラフ) O(M log N) 優先度付きキュー
全点対間最短経路問題 O($ N^3 $) 全ての2ノード間の最短経路長
Warshall-Floyd法
最小全域木問題 O(M log M) 複数都市間を往来可能にする最小金額
Kruskal法
最大フロー問題 O(MN) 始点から終点に流せる水の最大流量
Jim Orlin法
二部マッチング問題 O($ M \sqrt{N} $) 二部グラフにおけるノードを重複させない最大エッジ数
Hopcroft-Karp法

※ 上記の計算量において $ M $ はエッジ数、$ N $ はノード数を表す

深さ優先探索を用いた連結性判定
/// 深さ優先探索を用いてグラフが連結であるかどうかを判定(計算量: O(*M + N*); *M*はエッジ数、*N*はノード数)
/// - parameter nodes: `[[Int]]`型の隣接リスト表現(最初のインデックスは判定に使用しない)
/// - returns: 連結である場合は`true`、そうでない場合は`false`
func isConnected(_ nodes: [[Int]]) -> Bool {
  var isVisited: [Bool] = [Bool](repeating: false, count: nodes.count)
  
  /// 深さ優先探索
  /// - parameter node: 現在のノード番号
  func dfs(_ node: Int) -> Void {
    // 現在のノードを到達済ノードとしてセット
    isVisited[node] = true
    
    // 隣接ノードのうち、未到達ノードに対して再帰処理を実行
    for next in nodes[node] {
      if (isVisited[next] == false) { dfs(next) }
    }
  }
  
  // ノード1から深さ優先探索
  dfs(1)
  
  // 全ての頂点が到達済であれば連結であり、そうでなければ連結でない
  for i in 1 ..< isVisited.count {
    if (isVisited[i] == false) { return false }
  }
  
  return true
}
043 - Is It Connected?
let nm: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, m): (Int, Int) = (nm[0], nm[1])

var nodes: [[Int]] = [[Int]](repeating: [], count: n + 1)
for _ in 0 ..< m {
  let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
  nodes[input[0]].append(input[1])
  nodes[input[1]].append(input[0])
}

if (isConnected(nodes) == true) {
  print("The graph is connected.")
}
else {
  print("The graph is not connected.")
}

044 - Shortest Path Problem

幅優先探索を用いた最短経路長の取得
/// 幅優先探索を用いてノード群の最短経路長を取得(計算量: 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
}
044 - Shortest Path Problem
let nm: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, m): (Int, Int) = (nm[0], nm[1])

var nodes: [[Int]] = [[Int]](repeating: [], count: n + 1)
for _ in 0 ..< m {
  let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
  nodes[input[0]].append(input[1])
  nodes[input[1]].append(input[0])
}

let distances: [Int] = getShortestDistances(nodes, 1)
for i in 1 ... n {
  print(distances[i])
}

045 - Easy Graph Problem

045 - Easy Graph Problem
let nm: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, m): (Int, Int) = (nm[0], nm[1])

var nodes: [[Int]] = [[Int]](repeating: [], count: n + 1)
for _ in 0 ..< m {
  let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
  nodes[input[0]].append(input[1])
  nodes[input[1]].append(input[0])
}

var answer: Int = 0
for i in 1 ..< nodes.count {
  if (nodes[i].filter{ $0 < i }.count == 1) {
    answer += 1
  }
}

print(answer)

046 - 幅優先探索

046 - 幅優先探索
let rc: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (row, col): (Int, Int) = (rc[0], rc[1])

let start: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let goal: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }

var squares: [[Character]] = [[Character]](repeating: [Character](repeating: Character("-"), count: col + 1), count: row + 1)
var distances: [[Int]] = [[Int]](repeating: [Int](repeating: -1, count: col + 1), count: row + 1)

for r in 1 ... row {
  let input: String = readLine()!
  
  for c in 1 ... col {
    squares[r][c] = input[input.index(input.startIndex, offsetBy: c - 1)]
  }
}

// 幅優先探索
var queue: [[Int]] = [[Int]]()
// 始点の最短経路長を0にセット、キューに追加
distances[start[0]][start[1]] = 0
queue.append([start[0], start[1]])

while (queue.isEmpty == false) {
  // キューから先頭要素(行・列番号)を抽出
  let pop: [Int] = queue.removeFirst()
  let (pR, pC): (Int, Int) = (pop[0], pop[1])
  
  // 隣接しうるマス
  let neighbors: [[Int]] = [
    // 上
    [pR - 1, pC],
    // 下
    [pR + 1, pC],
    // 左
    [pR, pC - 1],
    // 右
    [pR, pC + 1]
  ]
  
  // 隣接マスが移動可能マスかつ未到達マスである場合は最短経路長を更新、マスを追加
  for neighbor in neighbors {
    let (nR, nC): (Int, Int) = (neighbor[0], neighbor[1])
    if (squares[nR][nC] == "." && distances[nR][nC] == -1) {
      distances[nR][nC] = distances[pR][pC] + 1
      queue.append([nR, nC])
    }
  }
}

print(distances[goal[0]][goal[1]])

047 - Bipartite Graph

深さ優先探索を用いた二部グラフ判定
/// 深さ優先探索を用いて二部グラフであるかどうかを判定(計算量: O(*M + N*); *M*はエッジ数、*N*はノード数)
/// - parameter nodes: `[[Int]]`型の隣接リスト表現(最初のインデックスは判定に使用しない)
/// - returns: 二部グラフである場合は`true`、そうでない場合は`false`
func isBipartiteGraph(_ nodes: [[Int]]) -> Bool {
  var values: [Int] = [Int](repeating: -1, count: nodes.count)
  values[0] = -2
  
  /// 深さ優先探索
  /// - parameters:
  ///   - node: 現在のノード番号
  ///   - value: 現在のノードにセットする値
  func dfs(_ node: Int, _ value: Int) -> Void {
    // 現在のノードに値をセット
    values[node] = value
    
    // 隣接ノードのうち、未到達ノードに対して再帰処理を実行
    for next in nodes[node] {
      if (values[next] == -1) {
        if (value == 0) { dfs(next, 1) }
        if (value == 1) { dfs(next, 0) }
      }
    }
  }
  
  // ノード1を始点とした深さ優先探索
  dfs(1, 0)
  
  // 全てのノードが走査済になるまで深さ優先探索を実行
  while let start = values.firstIndex(of: -1) {
    dfs(start, 0)
  }
  
  // 全ての隣接ノードの値を走査し、0と1で交互になっていなければ二部グラフでない
  for node in 1 ..< nodes.count {
    for next in nodes[node] {
      if (values[node] == 0 && values[next] != 1) { return false }
      else if (values[node] == 1 && values[next] != 0) { return false }
    }
  }
  
  return true
}
047 - Bipartite Graph
let nm: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (n, m): (Int, Int) = (nm[0], nm[1])

var nodes: [[Int]] = [[Int]](repeating: [], count: n + 1)
for _ in 0 ..< m {
  let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
  nodes[input[0]].append(input[1])
  nodes[input[1]].append(input[0])
}

if (isBipartiteGraph(nodes) == true) { print("Yes") }
else { print("No") }

048 - Small Multiple

導出過程

全ての整数 $ n $ は任意の非負整数 $ k $ で割った際の剰余が $ 0 $ 以上 $ n - 1 $ 以下の整数になることから、剰余 $ n \bmod k $ をノードの番号としてグループ分けを行うことができる。

そこで、移動コスト $ d\ ( \ 0 \leq d \leq 9\ ) $ を各桁の値として連結した数の剰余をノード番号に対応させることで、$ k $ の倍数のうち各桁の総和が最小となる数はノード $ 0 $ から他のノードを伝ってノード $ 0 $ に戻る場合の最小移動コストを連結した数となり、各桁の総和は最小移動コストの総和として導ける。

このとき、ノード $ p\ (\ 0 \leq p \leq k - 1 \ ) $ に属する整数は任意の整数 $ a $ を用いて $ ak + p $ で表され、ノード $ p $ から移動可能なノード $ q\ (\ 0 \leq q \leq k - 1 \ ) $ について、$$ (\ ak + p\ ) \times 10 + d \equiv q\ ( \bmod k\ ) $$ $$ \Leftrightarrow 10p + d \equiv q\ ( \bmod k\ )\ ( \because 10ak \bmod k = 0\ ) $$という性質が成り立つ。

Dijkstra法を用いてノード $ 0 $ から各ノードへの最短経路を導出するが、通常のキューを利用すると計算量がO($ M^2 $)となってしまうため、優先度付きキュー(Priority Queue) を用いて計算量をO((M + N)log N)にまで軽減させる必要がある。

優先度付きキュー(@koherさん作)
/// 優先度付きキュー
/// - authors: [koher](https://github.com/koher)
/// - seealso: [swift-atcoder-support/Sources/AtCoderSupport/PriorityQueue.swift](https://github.com/koher/swift-atcoder-support/blob/main/Sources/AtCoderSupport/PriorityQueue.swift)
struct PriorityQueue<Element> {
  /// 優先度付きキューの要素
  private var elements: [Element] = []
  /// 順序付け方式
  private let areInIncreasingOrder: (Element, Element) -> Bool
  
  init<S>(_ elements: S, by areInIncreasingOrder: @escaping (Element, Element) -> Bool) where S: Sequence, S.Element == Element {
    self.areInIncreasingOrder = areInIncreasingOrder
    for element in elements {
      append(element)
    }
  }
  
  init(by areInIncreasingOrder: @escaping (Element, Element) -> Bool) {
    self.init(EmptyCollection(), by: areInIncreasingOrder)
  }
  
  var isEmpty: Bool { elements.isEmpty }
  var count: Int { elements.count }
  var first: Element? { elements.first }
  
  /// ヒープを用いたキューへの値の追加
  mutating func append(_ element: Element) {
    var i = elements.count
    elements.append(element)
    elements.withUnsafeMutableBufferPointer { elements in
      while i > 0 {
        let parentIndex = (i - 1) >> 1
        let parent = elements[parentIndex]
        guard areInIncreasingOrder(element, parent) else { break }
        elements[parentIndex] = element
        elements[i] = parent
        i = parentIndex
      }
    }
  }
  
  /// ヒープを用いたキューからの値の取り出し
  mutating func popFirst() -> Element? {
    guard let element = elements.popLast() else { return nil }
    guard let first = elements.first else { return element }
    
    elements.withUnsafeMutableBufferPointer { elements in
      elements[0] = element
      
      var i = 0
      while true {
        var childIndex: Int = (i << 1) + 1
        guard childIndex < elements.count else { break }
        var child: Element = elements[childIndex]
        let rightIndex = childIndex + 1
        if rightIndex < elements.count {
          let right = elements[rightIndex]
          if areInIncreasingOrder(right, child) {
            childIndex = rightIndex
            child = right
          }
        }
        if areInIncreasingOrder(element, child) { break }
        elements[childIndex] = element
        elements[i] = child
        i = childIndex
      }
    }
    
    return first
  }
}
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
}
048 - Small Multiple
let n: Int = Int(readLine()!)!
/// `nodes[p] = [next, distance]`はノード`p` → ノード`next` の移動コストが`distance`であることを示す
var nodes: [[[Int]]] = [[[Int]]](repeating: [[Int]](), count: n)

// 各ノードp → 隣接ノードq への最小移動コストを算出
for p in 0 ..< n {
  for d in 0 ... 9 {
    let q: Int = (10 * p + d) % n
    
    // 自己ループは最短経路を導出する上で不要経路のため除外
    if (p == q) { continue }
    
    // 隣接ノード・移動コストがすでにnodesに含まれる場合は現在の移動コストと比較
    if let next: Int = nodes[p].indices.map({ nodes[p][$0][0] }).firstIndex(of: q) {
      if (d < nodes[p][next][1]) { nodes[p][next][1] = d }
    }
    // 含まれない場合はnodesに隣接ノード・移動コストの情報がないため追加
    else {
      nodes[p].append([q, d])
    }
  }
}

print(getShortestPath(nodes)[0])

049 - Fibonacci Easy (mod 1000000007)

049 - Fibonacci Easy (mod 1000000007)
let n: Int = Int(readLine()!)!
let division: Int = 1000000007

// フィボナッチ数列の生成
var a: [Int] = [Int](repeating: 1, count: n + 1)
for i in 3 ... n {
  a[i] = (a[i - 2] + a[i - 1]) % division
}

print(a[n] % division)

050 - Power

繰り返し二乗法(repeated squaring) … $ b^e \bmod d $ について、指数部 $ e $ を2進数に変換し、$ i $ 桁目のビットフラグが立っている場合に $ b^{2^i} \bmod d $ の積の剰余を乗算して上書きすることでオーバーフローを避けつつ計算量をO(log e)に抑える手法

例
$ 5^{10} $ を $ 3 $ で割った余りを求める。

$ 10 = 2^1 + 2^3 $ であることから、以下の方程式が成立する。
$$ 5^{10} \equiv 5^2 \times 5^8 (\bmod 3\ ) $$
ここで、$$ 5^2 \equiv 5^1 \times 5^1 (\bmod 3\ ) = 1 $$ $$ 5^4 \equiv 5^2 \times 5^2 (\bmod 3\ ) = 1 $$ $$ 5^8 \equiv 5^4 \times 5^4 (\bmod 3\ ) = 1 $$ であるため、$$ 5^{10} \equiv 1 \times 1\ (\bmod 3\ ) = 1 $$

繰り返し二乗法を用いた累乗の剰余の取得
/// 繰り返し二乗法を用いて累乗の剰余を取得する(計算量: 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
}
050 - Power
let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (a, b): (Int, Int) = (input[0], input[1])
let division: Int = 1000000007

print(getModPower(a, b, division))

051 - Combination Hard

参考: フェルマーの小定理の証明と例題

素数 $ p $ で割った剰余同士の除算を行う場合は、フェルマーの小定理(Fermat's little theorem)を用いてモジュラ逆数(Modular multiplicative inverse)を求める

任意の整数 $ A, B $ を非負整数 $ p $ で割った剰余の加算・減算・乗算について、以下の合同式が成り立つ。
$$ A + B \equiv (A \bmod p) + (B \bmod p)\ (\bmod p\ ) $$ $$ A - B \equiv (A \bmod p) - (B \bmod p)\ (\bmod p\ ) $$ $$ A \times B \equiv (A \bmod p) \times (B \bmod p)\ (\bmod p\ ) $$
$ A $ が $ B $ で割り切れる剰余の除算は上記のようにそのまま計算しても解が一致しないが、「$ \div\ m $」に対応して解が一致するような「$
\times\ n $」が除数ごとに存在することが知られており、そのような $ n\ (= m^{-1}) $ をモジュラ逆数と呼ぶ。

演算 式
通常の除算 $ a $ $ \times\ a^{-1} $ $ = 1 $
剰余の除算 $ a $ $ \times\ a^{-1} $ $ \equiv 1\ ($$\bmod p$ $) $ $ (\ a^{-1} $はモジュラ逆数 $)$

例① ( $ 58 \div 29 $ )
$ 3 \div 7 \equiv 2\ (\bmod 11\ ) \Leftrightarrow 3 \times 8 \equiv 2\ (\bmod 11\ ) $
→ mod 11 において、7のモジュラ逆数は8
例② ( $ 100 \div 20 $ )
$ 9 \div 7 \equiv 5\ (\bmod 13\ ) \Leftrightarrow 9 \times 2 \equiv 5\ (\bmod 13\ ) $
→ mod 13 において、7のモジュラ逆数は2

ここで、除数 $ p $ に対する元の数 $ m $ のモジュラ逆数 $ n\ (= m^{-1}) $ について、以下の合同式が成り立つ。
$$ m \times n \equiv 1\ (\bmod p\ ) $$
そこで、数式が似ているフェルマーの小定理を用いてモジュラ逆数を求めることができる。

フェルマーの小定理
素数 $ p $ 、非負整数 $ m\ (\ 1 \leq m \leq p - 1\ ) $ について、
$$ m^{p-1} \equiv 1\ (\bmod p\ ) $$

$ m^{p-1} \equiv 1\ (\bmod p\ ) \Leftrightarrow m \times m^{p-2} \equiv 1\ (\bmod p\ ) $ であるため、モジュラ逆数 $ n $ は元の除数 $ m $ を用いて以下のように表すことができる。
$$ n = m^{p-2} \bmod p $$

さらに、$ m^{p-2} $ は底が $ m $、冪指数が $ p-2 $ の累乗であるため、繰り返し二乗法を用いてO(log P) で計算することができる。

繰り返し二乗法を用いた組合せの剰余の取得
/// 繰り返し二乗法を用いて組合せの総数の剰余を取得する(計算量: O(*N*))
/// - parameters:
///  - n: `Int`型の要素数
///  - r: `Int`型の組合せ数
///  - div: `Int`型の除数
/// - returns: nCrを`div`で割ったときの剰余
func getCombinationMod(_ n: Int, _ r: Int, _ div: Int) -> Int {
  var factMods: [Int] = [Int](repeating: 1, count: n + 1)
  
  // 階乗の剰余を取得(計算量: O(N))
  for i in 1 ... n {
    factMods[i] = (factMods[i - 1] * i) % div
  }
  
  // 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
}
051 - Combination Hard
let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (x, y): (Int, Int) = (input[0], input[1])
let division: Int = 1000000007

print(getCombinationMod(x + y, x, division))

052 - Knight

052 - Knight
let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (x, y): (Int, Int) = (input[0], input[1])
let division: Int = 1000000007

// (+1, +2)の移動回数をa, (+2, +1)の移動回数をbとすると、
// (3a, 3b) = (2x - y, 2y - x)で表され、共に非負整数の3の倍数とならなければならない
var (a, b): (Int, Int) = (2 * x - y, 2 * y - x)
if (a % 3 != 0 || b % 3 != 0 || a < 0 || b < 0) {
  print(0)
  return
}
(a, b) = (a / 3, b / 3)

print(getCombinationMod(a + b, a, division))

053 - Sum of 4^N

繰り返し二乗法におけるループ処理回数は、冪指数の制約 $ 10^N $ とその2進数である $ 2^K $ について $ 10^N \leq 2^M $ を満たすような整数 $ M $ のうち、なるべく小さい値であることが望ましい

底が非負整数である累乗同士の大小関係は、全ての累乗に対して $ \tfrac{1}{p} $ 乗した値の大小比較によって求められる。

例
$ 2^{500}, 3^{300}, 6^{200} $ の大小関係

それぞれ $ \tfrac{1}{100} $ 乗すると $ 2^5, 3^3, 6^2 $ となり、$ 3^3 < 2^5 < 6^2 $ であるため$$ 3^{300} < 2^{500} < 6^{200} $$

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

// 等比数列の総和(4^{n + 1} - 1) / 3の分子をdivで割った剰余を求める
let top: Int = getGreaterModPower(4, n + 1, division) - 1

// 分母(除数)のモジュラ逆数を求める
let bottomMMI: Int = getModPower(3, division - 2, division) % division

print(top * bottomMMI % division)

054 - Fibonacci Hard (mod 1000000000)

フィボナッチ数列(Fibonacci sequence)は、行列を用いて以下のように表される。

\begin{align}
\begin{pmatrix}
a_{n+1} \\
a_{n}
\end{pmatrix}
&=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
a_{n} \\
a_{n-1}
\end{pmatrix}
=
\begin{pmatrix}
a_{n} + a_{n-1} \\
a_{n}
\end{pmatrix} \\
&=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\Biggl(
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{n-2}
\begin{pmatrix}
a_{2} \\
a_{1}
\end{pmatrix}
\Biggr) \\
&=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{n-1}
\begin{pmatrix}
a_{2} \\
a_{1}
\end{pmatrix}
\end{align}

ここで、全ての非負整数 $ n\ (\ n \geq 3\ ) $ を用いて次の等式が成り立つことが知られている。

\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{n-1}
=
\begin{pmatrix}
a_n & a_{n-1} \\
a_{n-1} & a_{n-2}
\end{pmatrix}

よって、フィボナッチ数列の第 $ n $ 項 $ a_n\ ( = a_{n-1} + a_{n-2}\ ) $ は $ A^{n-1} $ の2行目の総和となる。

証明
数学的帰納法を用いて証明する。

$ n = 3 $ のとき、

\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^2
=
\begin{pmatrix}
2 & 1 \\
1 & 1
\end{pmatrix}
=
\begin{pmatrix}
a_3 & a_2 \\
a_2 & a_1
\end{pmatrix}

より、命題は真である。
$ n = k\ (\ k \geq 3\ ) $ のとき、

\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^{k-1}
=
\begin{pmatrix}
a_k & a_{k-1} \\
a_{k-1} & a_{k-2}
\end{pmatrix}

が成り立つと仮定すると、$ n = k + 1 $ のとき、

\begin{align}
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^k
&=
\begin{pmatrix}
a_k & a_{k-1} \\
a_{k-1} & a_{k-2}
\end{pmatrix}
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix} \\
&=
\begin{pmatrix}
a_k + a_{k-1} & a_k \\
a_{k-1} + a_{k-2} & a_{k-1}
\end{pmatrix} \\
&=
\begin{pmatrix}
a_{k+1} & a_k \\
a_k & a_{k-1}
\end{pmatrix}
\end{align}

より、$ n = k + 1 $ のときも命題は真となる。
以上より、全ての非負整数 $ n\ (\ n \geq 3\ ) $ において命題は真である。

行列を取り扱う自作の構造体
/// 行列とその乗算を定義する構造体
struct Matrix {
  /// 行列の成分群
  var values: [[Int]] = [[1, 1], [1, 0]]
  
  init(_ matrix: [[Int]]) {
    self.values = [[Int]]()
    self.values += matrix
  }
  
  /// 行列 A, Bの積の各成分を任意の除数の剰余で表した行列を求める
  /// - parameters:
  ///  - a: `Matrix`型の行列
  ///  - b: `Matrix`型の行列
  ///  - div: `Int`型の除数
  /// - returns: `Matrix`型の行列`a`と行列`b`の積
  static func getProductMod(_ a: Matrix, _ b: Matrix, _ div: Int) -> Matrix {
    // 行列aの行数と行列bの列数が一致しない場合は実行時エラーを発生させる
    let (row, col, common): (Int, Int, Int) = (
      a.values.count,
      b.values[0].count,
      a.values[0].count == b.values.count ? a.values.count : -1
    )
    var answer: [[Int]] = [[Int]](
      repeating: [Int](repeating: 0, count: row),
      count: col
    )
    
    for r in 0 ..< row {
      for com in 0 ..< common {
        for c in 0 ..< col {
          answer[r][c] += a.values[r][com] * b.values[com][c]
          answer[r][c] %= div
        }
      }
    }
    
    return Matrix(answer)
  }
  
  /// 行列の累乗について各要素を任意の除数の剰余で表した行列を求める(計算量: O(log *exp*))
  /// - parameters:
  ///  - base: 底となる`Matrix`型の行列
  ///  - exp: `Int`型の冪指数
  ///  - div: `Int`型の除数
  /// - returns: `base`^`exp`
  static func getPowerMod(_ base: Matrix, _ exp: Int, _ div: Int) -> Matrix {
    var (baseMatrix, answer): (Matrix, Matrix) = (base, Matrix([[1, 1], [1, 0]]))
    
    // 冪指数expについて、2^i(0 ≦ i ≦ 60)のフラグが立っている場合は剰余を更新
    // → 10^18 < 2^60であるため、iの最大値を60とする
    var isFirst: Bool = true
    for i in 0 ... 60 {
      if (exp & (1 << i) != 0) {
        // 右から数えて初めてフラグが立っている部分では、その直前の走査でbaseMatrixがすでに解を持っているため流用
        if (isFirst == true) {
          answer = baseMatrix
          isFirst = false
        }
        else {
          answer = Matrix.getProductMod(answer, baseMatrix, div)
        }
      }
      baseMatrix = Matrix.getProductMod(baseMatrix, baseMatrix, div)
    }
    
    return answer
  }
}
054 - Fibonacci Hard (mod 1000000000)
let n: Int = Int(readLine()!)!
let division: Int = 1000000000

let answer: Matrix = Matrix.getPowerMod(Matrix([[1, 1], [1, 0]]), n - 1, division)
print((answer.values[1][0] + answer.values[1][1]) % division)

055 - Recurrence Formula 1

$ a_n = 2a_{n-1} + a_{n-2}\ (\ a_1 = a_2 = 1,\ n \geq 3 \ ) $ について、行列を用いて以下のように表される。

\begin{align}
\begin{pmatrix}
a_{n+1} \\
a_{n}
\end{pmatrix}
&=
\begin{pmatrix}
2 & 1 \\
1 & 0
\end{pmatrix}^{n-1}
\begin{pmatrix}
a_1 \\
a_2
\end{pmatrix} \\
&=
\begin{pmatrix}
2 & 1 \\
1 & 0
\end{pmatrix}^{n-1}
\begin{pmatrix}
1 \\
1
\end{pmatrix}
\end{align}

ここで、左辺の $ a_n $ は右辺の計算結果の2行目に対応するが、

A =
\begin{pmatrix}
2 & 1 \\
1 & 0
\end{pmatrix}

とおくと、行列の積の定義上、右辺の計算結果の2行目 $ ( = a_n\ ) $ は $ A^{n-1} $ の $ (\ 2,\ 1\ ) $ 成分と $ (\ 2,\ 2\ ) $ 成分の和となる。

055 - Recurrence Formula 1
let n: Int = Int(readLine()!)!
let division: Int = 1000000007

let answer: Matrix = Matrix.getPowerMod(Matrix([[2, 1], [1, 0]]), n - 1, division)
print((answer.values[1][0] + answer.values[1][1]) % division)

056 - Recurrence Formula 2

056 - Recurrence Formula 2
let n: Int = Int(readLine()!)!
let division: Int = 1000000007

let answer: Matrix = Matrix.getPowerMod(Matrix([[1, 1, 1], [1, 0, 0], [0, 1, 0]]), n - 1, division)
print(
  (2 * answer.values[2][0] + answer.values[2][1] + answer.values[2][2]) % division
)

057 - Domino Tiling

$ x - 1 $ 列目の状態から $ x $ 列目の状態への遷移について検討する。
$ k = 2 $ の場合、各状態から遷移可能な状態は以下のようになる。

k=2.png

$ k = 3, 4 $ の場合も同様に、遷移可能な状態は以下のようになる。

k=3,4.png

ここで、$ x\ (\ 5 \leq x \leq 10^{18}\ ) $ 列目の状態 $ y\ (\ 0 \leq y \leq 2¥{k-1}\ ) $ になりうる場合の数を $ dp[x][y] $ とすると、$ k = 2 $ の場合において、$ x - 1 $ 列目の状態になりうる場合の数と $ x $ 列目の状態になりうる場合の数は、行列を用いて以下のように表される。
※ただし、便宜上 $ 0 $ 列目は全てタイルで埋まっているものとし、$ dp[0][2^{k} - 1] = 1 $ とする

\begin{align}
\begin{pmatrix}
dp[x][0] \\
dp[x][1] \\
dp[x][2] \\
dp[x][3]
\end{pmatrix}
&=
\begin{pmatrix}
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
dp[x-1][0] \\
dp[x-1][1] \\
dp[x-1][2] \\
dp[x-1][3]
\end{pmatrix} \\
&=
\begin{pmatrix}
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 1
\end{pmatrix}^{x}
\begin{pmatrix}
dp[0][0] \\
dp[0][1] \\
dp[0][2] \\
dp[0][3]
\end{pmatrix} \\
&=
\begin{pmatrix}
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 1
\end{pmatrix}^{x}
\begin{pmatrix}
0 \\
0 \\
0 \\
1
\end{pmatrix}
\end{align}
057 - Domino Tiling
let input: [Int] = readLine()!.split(separator: " ").map{ Int($0)! }
let (k, n): (Int, Int) = (input[0], input[1])
let division: Int = 1000000007

let matrix: Matrix
switch k {
  case 2: matrix = Matrix([
    //  1  2  3
    [0, 0, 0, 1],
    [0, 0, 1, 0],
    [0, 1, 0, 0],
    [1, 0, 0, 1]
  ])
  case 3: matrix = Matrix([
    //  1  2  3  4  5  6  7
    [0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 1],
    [0, 0, 1, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 1, 0]
  ])
  case 4: matrix = Matrix([
    //  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0],
    [1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1]
  ])
  default: return
}

let answer: Matrix = Matrix.getPowerMod(matrix, n, division)
print(answer.values[answer.values.count - 1][answer.values[0].count - 1])
1
5
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
1
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?