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を使う方法が存在します](https://qiita.com/cielavenir/items/2598d47b97a7c9caf970)が、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

```swift: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()!)
```

## 第１問 ABC086A Product

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

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

```swift: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")
```

## 第２問 ABC081A Placing Marbles

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

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

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

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

```swift: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)
```

## 第３問 ABC081B Shift only

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

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

```swift: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)
```

## 第４問 ABC087B Coins

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

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

```swift: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)
```

## 第５問 ABC083B Some Sums

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

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

```swift: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)
```

## 第６問 ABC088B Card Game for Two

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

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

```swift: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)
```

## 第７問 ABC085B Kagami Mochi

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

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

```swift: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)
```

## 第８問 ABC085C Otoshidama

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

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

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

```swift: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")
```

## 第９問 ABC049C Daydream

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

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

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

```swift: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との偶奇が一致。

```swift: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のバージョン、上げてください。