AtCoder ABC369 振り返り感想戦(ほぼ緑コーダーがSwiftでA〜D問題まで)

## ABC 369 感想まとめ

* [AtCoder Beginner Contest 369 - AtCoder](https://atcoder.jp/contests/abc369)

今回は用事のためリアルタイム参加はできず、翌日に復習のみ行いました。
レーティング参加ではないし、失敗しても良い機会と考えて、初めてSwiftで書いてみました。

A問題-D問題まではノーヒントで解答。E問題はワーシャル–フロイド法のことをよく覚えておらず、あれこれ悩んでも突破口は見つかりませんでした。

### AtCoderにおけるSwiftについて

ABCにおけるSwiftは、アクティブユーザーが4-5人程度のようです。参加者が約1万人いる中でこの数字は、ちょっと寂しいですね...。

とはいえ、過去にSwiftで参加されていた方が残された記事もあり、参入障壁は低いと思います。

[\[AtCoder\]Swiftでも競プロがしたい！ #競技プログラミング - Qiita](https://qiita.com/kntkymt/items/4f02c6b90462f354de6d)

今回は特に、上の記事を参考にさせていただきました。標準入力の読み取り ```readTwoInts()``` などは、そのまま使用しております。

### Swiftを使った感想

実際やってみて、仕事ではSwiftを触っているとはいえ競プロではずっとPythonだったので、正直なところまだ慣れていなくて、うまく書けないことが多かったです...。

しかし、競プロ特有の処理は業務で書く処理とは大きく異なるので、Swiftの知らない機能を知れたりもあり、刺激になります。

レーティングだけを目指すなら、おそらく利用者の多いがPython有利だと思いますが、他の言語を使うのも新鮮で実に良いと感じた回でした。

## [A - 369](https://atcoder.jp/contests/abc369/tasks/abc369_a)

xを -100〜200 までループして[x A B]をソートして、3つの差が同じなら等差数列としてカウント。ちょっと力技な全探索で解きました。

模範解答例ではO(1)ですが、この解法ではソートしたりあれこれしているので計算量的にはだいぶ増えている。
計算量の面で、あまり良くない解法でした...

``` Swift
func readTwoInts() -> (a: Int, b: Int) {
    let ints = readLine()!.split(separator: " ").map { Int(String($0))! }
    return (a: ints[0], b: ints[1])
}

let ab = readTwoInts()

var count = 0
for i in -110...210 {
    let list = [ab.0, ab.1, i].sorted()
    if list[1] - list[0] == list[2] - list[1] {
        count += 1
    }
}
print(count)

```

## [B - Piano 3](https://atcoder.jp/contests/abc369/tasks/abc369_b)

素直にシミュレーションして計算しました。左手と右手の位置を保存する変数 ```left``` と ```right``` を用意し、更新していく感じです。
```left``` と ```right``` の初期値を ```nil``` にしておいて、初回は移動距離をカウントしないように判定しました。

``` Swift
func readInt() -> Int {
    return Int(readLine()!)!
}

func readIntString() -> (a: Int, b: String) {
    let line = readLine()!.split(separator: " ").map { String($0) }
    return (a: Int(line[0])!, b: line[1])
}

let N = readInt()

var diff = 0
var left: Int? = nil
var right: Int? = nil

// Queryの最後まで読み取り
for _ in 0..<N {
    let line = readIntString()

    // Lの場合
    if line.1 == "L" {
        if let currentLeft = left  {
            diff += abs(line.0 - currentLeft)
        }
        left = line.0        
    }

    // Rの場合
    if line.1 == "R" {
        if let currentRight = right  {
            diff += abs(line.0 - currentRight)
        }
        right = line.0
    }
}

print(diff)
```


## [C - Count Arithmetic Subarrays](https://atcoder.jp/contests/abc369/tasks/abc369_c)
等差数列になっている範囲を求めて、範囲内から2個選ぶ組み合わせの個数(${}_n C_2$)を求める...というのを尺取法で繰り返す方法です。

``` Swift
func readInt() -> Int {
    return Int(readLine()!)!
}

let N = readInt()
let A = readLine()!.split(separator: " ").map { Int(String($0))! }

var left: Int = 0
var right: Int = 1

var answer = 0

while left < N - 1 {
    let leftValue = A[left]
    let diff = A[left + 1] - leftValue
    
    // 同じdiffが続くところまで探索
    var right = left + 1
    for r in (left+1)..<N {
        if A[r] - A[r-1] == diff {
            right = r
            continue
        } else {
            break
        }
    }
    
    // left〜right間にある個数から2個選ぶ 場合の数
    let sequenceCount = right - left + 1
    answer += sequenceCount * (sequenceCount - 1) / 2

    // left を等差数列の右端まで進める(しゃくとり法)
    left = right
}

// 1個の数列の個数を足す
answer += N

print(answer)
```

## [D - Bonus EXP](https://atcoder.jp/contests/abc369/tasks/abc369_d)

動的計画法で ``` dp[i番目のモンスター][攻撃回数 偶数:0/奇数:1] = 経験値```  の配列を埋めていく方針にしました。
累計攻撃回数は偶数奇数だけ記録すれば良い、と気づいたのがうまくいった要因かと思います。

``` Swift
func readInt() -> Int {
    return Int(readLine()!)!
}

let N = readInt()
let A = readLine()!.split(separator: " ").map { Int(String($0))! }

var dp: [(Int, Int)] = [(0,0)]

for i in 0..<N {
    let X = A[i]
    let lastEven = dp.last!.0    // 前回までの攻撃回数が偶数の場合の経験値
    let lastOdd = dp.last!.1     // 前回までの攻撃回数が奇数の場合の経験値

    // 次が偶数になるパターン
    let nextEven: Int
    if lastOdd == 0 {
        nextEven = lastEven
    } else {
        nextEven = max(lastEven, lastOdd + X * 2)
    }

    // 次が奇数になるパターン
    let nextOdd = max(lastOdd, lastEven + X)

    dp.append((nextEven, nextOdd))
}

let answer = max(dp.last!.0, dp.last!.1)
print(answer)
``` 

## [E - Sightseeing Tour](https://atcoder.jp/contests/abc369/tasks/abc369_e)

問題文を読んで、ダイクストラ法でいけるかなと思ったらワーシャル-フロイド法を使うらしいです。ワーシャル-フロイド法、どういうものかきちんと覚えてなかったので、要復習ですね...。