AtCoder
Swift

AtCoder に登録したら解くべき精選過去問 10 問を Swift で解いてみた

実装リンク集 https://qiita.com/drken/items/6edb1c0542d4c3b7179c
問題一覧 https://abs.contest.atcoder.jp/assignments

私の実装 記事
Ruby (私家版) https://qiita.com/cielavenir/items/c0a45b6b87c411b60b93
Swift https://qiita.com/cielavenir/items/b90a94dce60a620fa2dc
C https://qiita.com/cielavenir/items/ee1e47b844d05dcfc66e
VB.Net https://qiita.com/cielavenir/items/7ddf5e9bac02daf72159
Pascal https://qiita.com/cielavenir/items/530270ac4affca435442
Perl https://qiita.com/cielavenir/items/4d16ba1be4ad6847a914
MoonScript/Lua https://qiita.com/cielavenir/items/6553531e230f39cd6a3d

縛り

残念ながらsort/reverseだけはプリプロセッサでSwift3以上かどうかで処理を分けています。しかしソースファイル単位ではSwift2/4の両方でコンパイルできることを縛りとして設けています。このため、文字列・配列以外のデータ構造は使っていません。

この縛りは、 AtCoderに導入されているSwiftがSwift2.2であること に起因しています。

入出力

入力はreadLineのみです。数値しか使わない場合はvscanfを使う方法が存在しますが、Swift2/4互換の縛りがあるので今回は使えません。
出力はterminator引数で改行を制御できます。こちらは2/4互換のようです、よかった…

解答

例題 PracticeA

https://practice.contest.atcoder.jp/tasks/practice_1

readLine()はString?(Optional)を返すので、!によって変換する必要があります。

また、splitするにはreadLine()!.characters.split{$0==" "}を使います。
(Swift4ではStringを直接splitできます。この辺ようやくまともになった感)

ちなみに、//usr/bin/env swift $0 $@;exit#がコメントにならない言語のShebangのようなものです。cf: https://qiita.com/cielavenir/items/b83552a761419be57285

0.swift
//usr/bin/env swift $0 $@;exit
let a=Int(readLine()!)!
let arr=readLine()!.characters.split{$0==" "}.map{Int(String($0))!}
let b=arr[0]
let c=arr[1]
print(a+b+c,terminator:"")
print(" ",terminator:"")
print(readLine()!)

第1問 ABC086A Product

https://abc086.contest.atcoder.jp/tasks/abc086_a

3項演算子の使い方は(非0をboolとして扱えない以外)Cと同じですね。

1.swift
//usr/bin/env swift $0 $@;exit
let arr=readLine()!.characters.split{$0==" "}.map{Int(String($0))!}
let a=arr[0]
let b=arr[1]
print(a*b%2>0 ? "Odd" : "Even")

第2問 ABC081A Placing Marbles

https://abc081.contest.atcoder.jp/tasks/abc081_a

いくつかやり方があると思いますが、[Character]を選択しました。文字コード配列にしても良いと思います。

ここでようやく解説しますが、letは定数、varは変数です。

ループは、...が終端を含む、..<が終端を含まないループになります。

2.swift
//usr/bin/env swift $0 $@;exit
let s=Array(readLine()!.characters)
var c=0
for i in 0..<3 {
    if s[i]==Character("1") {
        c+=1
    }
}
print(c)

第3問 ABC081B Shift only

https://abc081.contest.atcoder.jp/tasks/abc081_b

arrの各要素に対し2で割ることが出来た回数の最小値です。
INF値として1<<29が使われていますが、2倍してオーバーフローしない中で簡潔に書ける数として競技プログラミングではよく使われます。

3.swift
//usr/bin/env swift $0 $@;exit
let n=Int(readLine()!)!
var arr=readLine()!.characters.split{$0==" "}.map{Int(String($0))!}
var r=1<<29
for i in 0..<n {
    var r0=0
    while (arr[i]%2)<1 {
        arr[i]/=2
        r0+=1
    }
    if r>r0 {r=r0}
}
print(r)

第4問 ABC087B Coins

https://abc087.contest.atcoder.jp/tasks/abc087_b

500円玉と100円玉の枚数を全探索します。

4.swift
//usr/bin/env swift $0 $@;exit
let a=Int(readLine()!)!
let b=Int(readLine()!)!
let c=Int(readLine()!)!
let x=Int(readLine()!)!
var r=0
for i in 0...x/500 {
    for j in 0...(x-500*i)/100 {
        let k=x-500*i-100*j
        if k%50==0&&c>=k/50&&a>=i&&b>=j {r+=1}
    }
}
print(r)

第5問 ABC083B Some Sums

https://abc083.contest.atcoder.jp/tasks/abc083_b

変数sは各i(j)を10で割れるだけ割って、その間に出た余りの和です。

5.swift
//usr/bin/env swift $0 $@;exit
let arr=readLine()!.characters.split{$0==" "}.map{Int(String($0))!}
let n=arr[0]
let a=arr[1]
let b=arr[2]
var r=0
for i in 1...n {
    var j=i
    var s=0
    while j>0 {
        s+=j%10
        j/=10
    }
    if a<=s&&s<=b {r+=i}
}
print(r)

第6問 ABC088B Card Game for Two

https://abc088.contest.atcoder.jp/tasks/abc088_b

#if swift(>=3.0)でSwift3以上かどうかの分岐をします。3以上だとsorted、2だとsortになります。
降順でソートしたら、符号を切り替えながら足しこんでいきます。

6.swift
//usr/bin/env swift $0 $@;exit
let n=Int(readLine()!)!
var arr=readLine()!.characters.split{$0==" "}.map{Int(String($0))!}
#if swift(>=3.0)
arr=arr.sorted{$0>$1}
#else
arr=arr.sort{$0>$1}
#endif
var r=0
var t=1
for i in 0..<n {
    r+=t*arr[i]
    t=(-t)
}
print(r)

第7問 ABC085B Kagami Mochi

https://abc085.contest.atcoder.jp/tasks/abc085_b

ソートしたら、直前の数値と同じかどうか見ていきます。C++のuniqueと同様のアルゴリズムですね。

7.swift
//usr/bin/env swift $0 $@;exit
let n=Int(readLine()!)!
var arr:[Int]=[]
for _ in 0..<n {
    arr.append(Int(readLine()!)!)
}
#if swift(>=3.0)
arr=arr.sorted()
#else
arr=arr.sort()
#endif
var r=1
var t=arr[0]
for i in 1..<n {
    if t != arr[i] {
        t=arr[i]
        r+=1
    }
}
print(r)

第8問 ABC085C Otoshidama

https://abc085.contest.atcoder.jp/tasks/abc085_c

1000円札と5000円札の枚数を全探索します。

import CoreFoundationは、OSXだとDarwin、LinuxだとGlibcをインポートするのとほぼ同義だと思って構いません。つまるところC言語ライブラリです。

8.swift
//usr/bin/env swift $0 $@;exit
import CoreFoundation
let arr=readLine()!.characters.split{$0==" "}.map{Int(String($0))!}
let n=arr[0]
let y=arr[1]
for i in 0...n {
    for j in 0...n-i {
        let k=n-i-j
        if i*1000+j*5000+k*10000==y {
            print(k,terminator:" ")
            print(j,terminator:" ")
            print(i)
            exit(0)
        }
    }
}
print("-1 -1 -1")

第9問 ABC049C Daydream

https://abc049.contest.atcoder.jp/tasks/arc065_a

文字列を逆にして比較していきます。

Swift2/4縛りのため、substring等使えません。Characterを1個ずつ比較しています。
…一応Swift4専用の記法も併記します。可読性全く違うので…

9.swift
//usr/bin/env swift $0 $@;exit
import CoreFoundation
func reversedArray<T>(_ a:[T]) -> [T] {
#if swift(>=3.0)
    return a.reversed()
#else
    return a.reverse()
#endif
}

let T=["dream","dreamer","erase","eraser"].map{reversedArray(Array($0.characters))}
let s=reversedArray(Array(readLine()!.characters))
var c=0
while c<s.count {
    var k:[Character]?=nil
    for e in T {
        let se=e.count
        let ss=s.count-c
        if se<=ss {
#if swift(>=4.0)
            //swift4は上でも下でもいいんですが上のほうが読みやすいですよね
            if Array(s[c..<c+se])==e {
                k=e
                break
            }
#else
            var ce=0
            while ce<se {
                if s[c+ce] != e[ce] {break}
                ce+=1
            }
            if ce==se {
                k=e
                break
            }
#endif
        }
    }
    if k==nil {
        print("NO")
        exit(0)
    }
    c+=k!.count
}
print("YES")

第10問 ABC086C Traveling

https://abc086.contest.atcoder.jp/tasks/arc089_a

dx+dyがdt以下かつdtとの偶奇が一致。

10.swift
//usr/bin/env swift $0 $@;exit
let n=Int(readLine()!)!
var t=0
var x=0
var y=0
var r="Yes"
for i in 0..<n {
    let arr=readLine()!.characters.split{$0==" "}.map{Int(String($0))!}
    let t0=arr[0]
    let x0=arr[1]
    let y0=arr[2]
    let dt=t0-t
    let dx=x0-x
    let dy=y0-y
    if dx+dy>dt || (dt-dx-dy)%2>0 {r="No"}
    t=t0
    x=x0
    y=y0
}
print(r)

終わりに

Swiftのバージョン、上げてください。