[Swift] Swift5.2を使ってAtCoderで遊んでみた

遊んでみました

注意：　この記事は競プロに勝つための記事ではありません。遊んでみただけです。

AtCoderは当初からSwiftが使用可能でしたが、バージョンが2.2と低すぎて僕には使えませんでした。

ところが今年に入って最新のSwiftに対応したサーバーが構築中でそのテストが公開で行われています。
Language Test 202001

最新のSwiftは僕でも分かるので遊んでみました。
C言語的な記法によらない解答例なのでちょっと異色だと思います。

手元に置いておきたいスニペット （導入編）

よく使う関数は手元に置いておきましょう。

入力処理

// １行文字列
func readStr() -> String {
  readLine()!
}

// １行整数
func readInt() -> Int {
  Int(readLine()!)!
}

// 空白文字で分割された文字列
func readSpStrs() -> [Substring] {
  readLine()!.split(separator: " ")
}

// 空白文字で分割された整数
func readSpInts() -> [Int] {
  readSpStrs().map { Int($0)! }
}

// 空白文字で分割された２つの整数をタプルで
func readInt2() -> (Int, Int) {
  let ints = readSpInts()
  return (ints[0], ints[1])
}

// 空白文字で分割された３つの整数をタプルで
func readInt3() -> (Int, Int, Int) {
  let ints = readSpInts()
  return (ints[0], ints[1], ints[2])
}

// N行分の整数
func readInt(_ n: Int) -> [Int] {
  (1...n).map { _ in readInt() }
}

基本的に競プロでは例外処理は考えてはいけません。
文字列は必ず読み込めますし、整数値は必ずIntに変換可能です。
force unwrapは恐れず使いましょう。

遊んでみよう！

Language Test 202001ではテストのために過去問題が出されているのですが、この過去問題があのAtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～と同じものとなっています。
これをSwift5.2で解いていきます。

なお、ほとんどすべての問題解説は「過去問精選 10 問」を参照してください。

過去問精選 10 問

以下の解答例では上にあげたスニペットが追加されているものとします。

第 1 問: ABC 086 A - Product

2つの整数の積の偶奇を問う問題ですが、掛け算する必要はありません。

a	b	a×b
奇数	奇数	奇数
奇数	偶数	偶数
偶数	奇数	偶数
偶数	偶数	偶数

いずれかが偶数なら積は偶数です。

let ab = readSpInts()
print(
  (ab[0].isMultiple(of: 2) || ab[1].isMultiple(of: 2)) ? "Even" : "Odd"
)

競プロの場合は入力のArrayのOut of Rangeもほとんど気にすることないですね。

第 2 問: ABC 081 A - Placing Marbles

0と1からなる3文字の文字列に1がいくつ含まれているかを問う問題。
Swiftだと部分文字列の比較がちょっと変になっちゃうのでIntにして足しちゃいます。

print(
  readStr().map(String.init).compactMap(Int.init).reduce(0, +)
)

一つ目のmapは一文字づつの配列への変換です。

第 3 問: ABC 081 B - Shift Only

N次元整数ベクトルの成分に奇数が現れるまですべての成分を2で割るという問題。

再帰関数で。

func f(_ a: [Int], _ count: Int) -> Int {
  if !a.allSatisfy( { $0.isMultiple(of: 2) } ) { return count }

  return f(a.map { $0 / 2 }, count + 1)
}

// Nは読み捨て
_ = readStr()

print(f(readSpInts(), 0))

第 4 問: ABC 087 B - Coins

全パターンを網羅する力技で解きます。

let a = readInt()
let b = readInt()
let c = readInt()
let x = readInt()

print(
 (0...a)
  .flatMap { aa in (0...b).flatMap { bb in (0...c).map { cc in (aa, bb, cc) } } }
  .filter { (i: Int, j: Int, k: Int) in (i * 500 + j * 100 + k * 50) == x }
  .count
)

第 5 問: ABC 083 B - Some Sums

整数の各桁の和を取る問題。
Swiftの場合String#reduceで一文字づつとれるのでそれを使います。
あとは全パターンを網羅する力技です。

let nab = readSpInts()
let n = nab[0]
let a = nab[1]
let b = nab[2]

func f(_ i: Int) -> Int {
  String(i)
    .reduce(0) { $0 + Int(String($1))! }
}

print(
  (1...n)
    .filter { (a...b) ~= f($0) }
    .reduce(0, +)
)

第 6 問: ABC 088 B - Card Game for Two

与えられた数列を大きい順に並べ替えて交互に足す引くを繰り返した結果が求める答えです。

_ = readInt()
let a = readSpInts().sorted(by: >)

print(
  a.enumerated()
    .reduce(0) { t, ii in
      ii.offset.isMultiple(of: 2) ? t + ii.element : t - ii.element
  }
)

別解

// 呼び出されるごとに足すと引くを交互に繰り返す２引数関数
let f = { () -> (Int, Int) -> Int in
  var op = 1
  return { t, i in
    defer { op *= -1 }
    return t + i * op
  }
}()

_ = readInt()
let a = readSpInts().sorted(by: >)

print(a.reduce(0, f))

第 7 問: ABC 085 B - Kagami Mochi

与えられた数列からユニークな数（すう）の数（かず）を求めなさい、という問題です。

extension Array where Element: Hashable {
  func uniqued() -> Array {
    var set = Set<Element>(minimumCapacity: count)
    return filter { set.insert($0).inserted }
  }
}

let n = readInt()

print(readInt(n).uniqued().count)

僕の中での最速最短の安定uniquedメソッドです。

第 8 問: ABC 085 C - Otoshidama

「過去問精選 10 問」の解説通りです。
...ややこしいのでノーコメントで。

let ny = readSpInts()
let n = ny[0]
let y = ny[1]

let r = (0...n)
  .lazy
  .flatMap { (m: Int) -> [(Int, Int, Int)] in
    (0...n)
      .map { g in
        (m, g, 10_000 * m + 5_000 * g + (n - m - g) * 1_000)
    }
  }
  .first { m, g, k in k == y && (n - m - g) >= 0 }
  .map { m, g, _  in (m, g, (n - m - g)) }

if let rr = r {
  print(rr.0, rr.1, rr.2)
}
else {
  print("-1 -1 -1")
}

lazyを使うことでflatMap内の関数は必要な部分だけ計算されます。

第 9 問: ABC 049 C - Daydream

「過去問精選 10 問」の解説通りです。

var s: Substring? = .init(readStr())

func removeList(_ s: Substring) -> Substring? {
  ["dream", "dreamer", "erase", "eraser"]
    .compactMap { t in s.hasSuffix(t) ? s.dropLast(t.count) : nil }
    .first
}

while s != "", let ss = s.flatMap({ removeList($0) })  { s = ss }
if s == "" { print("YES") }
else { print("NO") }

第 10 問: ABC 086 C - Traveling

間違えているんだけどAtCoderのテストデータではACです。

let n = readInt()
let isOK = (1...n)
  .map { _ in readSpInts() }
  .allSatisfy { p1 in
    let dt = p1[0]
    let dist = abs(p1[1]) + abs(p1[2])
    return dt >= dist && (dt - dist).isMultiple(of: 2)
}

print(isOK ? "Yes" : "No")

時間tと空間座標(x, y)の組(t, x, y)を時空座標と呼ぶとすると、問題の要旨は「与えられた時空座標の集合と{(0, 0, 0)}の和集合の任意の2つの元が互いに到達可能であるか」を問う問題ですが、僕の解答は「与えられた時空座標の集合の任意の元と(0, 0, 0)は互いに到達可能であるか」を調べています。

僕の解答は本来はWAなんですが、AtCoderのテストではACなので大正解で大正義です。

おわり

最後の３問は難しくて自分でも訳が分からなくなってます。
が、Swiftで遊べるのは楽しいですね！

早く本番サーバーに導入されないかなぁ。