AtCoder Beginner Contest 206 振り返り

第4回目のコンテストの参加。今回はC問題まで解けた。ABCを始めてから1ヶ月経った今、

少しずつ解ける問題が増えてきた。アルゴリズムの実装方法もある程度考えられるようになった。

でもまだまだだ。D問題にチャレンジすらできていない状況。Cは確実に実装していきたい。

そんなこんなで今回のABC206を振り返る。

A – Maxi-Buying

https://atcoder.jp/contests/abc206/tasks/abc206_a

思考

• 整数に戻す必要があるため、浮動小数点型を整数型(Int)に戻してあげる

もしくは

• floor()を使う
  • 切り捨て演算を行うことができる
  • (Double) -> Double

B – Savings

https://atcoder.jp/contests/abc206/tasks/abc206_b

思考

• 何回ループを回すか
  • 今回は何も考えずに、計算時間内に終わる回数ループさせて計算
  • Nをループの数iを用いて減算

func main1() {
    var N = readInt()


    for i in 1..<10_000_000 {
        N -= i
        if N <= 0 {
            print(i)
            return
        }
    }
}

main1()

1からNまでの和は,以下の数式で表せる。

知らないアルゴリズムはコンテスト中には実装はできない。練習が大事になってくる。

C – Swappable

https://atcoder.jp/contests/abc206/tasks/abc206_c

思考

• 連想配列(辞書型)のデータ構造を用いる
• keyにAiの数の大きさ
• valueにAiの出現回数
• 1 1 1 2 2 3の時 1:3 2:2 3:1になるようなものを準備
• 動的計画法を用いて数え上げる

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

func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}

let N = readInt()

let As = readInts()

var dictionary: [Int:Int] = [:]
//Aに対してiを格納する.
for i in 0..<N {
    dictionary[As[i], default: 0] += 1
}

var count = 0
var sum = 0
for (key,value) in dictionary {
    dictionary[key] = nil
    count += value * sum
    sum += value
}
print(count)

まとめ

C問題からは少しアルゴリズムを知らないと解けない問題が出てくる。

過去問題を継続的に解いていくことが、レベルアップの近道なので、愚直に問題を解いていこうと思った。