AtCoder Beginner Contest 209 の 振り返り

今回もAtCoder Beginner Contestに参加した. C問題まで解けた.D問題は見たことあるなーと感じたが,実装までは行けなかった.

最短経路問題については,もっとしっかりと演習を行う必要があるなと感じた.

A – Counting

  • A以上かつB以下の整数の数を答える問題

AはBより小さい条件下で,B-Aを行った数から+1を行うことで正解を導くことができる.

今回の出力は0以下にはならないため,max関数を使用して解くこともできる.

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

let (A,B) = readTwoInts()
print(max(B-A+1, 0))

B – Can you buy them all?

  • 偶数番目,奇数番目の意味が,文章と実際のコードとは異なるため,注意する.私はこの認識ミスでWAを連発してしまった.

文章で言う偶数番目とはA[0]ではなくA[1]のことで,A[0]→1番目,A[1]→2番目となっている.

配列のイテレータを使う際に,indexがほしいときはenumerated()

let (N,X) = readTwoInts()
let As = readInts()
var amount = 0
for (index, A) in As.enumerated() {
    if !index.isMultiple(of: 2) {
        //偶数のとき
        amount += max(A - 1, 0)
    } else {
        //奇数のとき
        amount += A
    }
}

if X >= amount {
    print("Yes")
} else {
    print("No")
}

参考 https://scrapbox.io/appgrapepublic/%E3%82%A4%E3%83%86%E3%83%AC%E3%83%BC%E3%82%BF%E3%83%BC%E3%81%AEindex%E3%82%92%E5%8F%96%E5%BE%97%E3%81%99%E3%82%8B%E6%96%B9%E6%B3%95

ロジックの短縮版 koherさんのコードを参考にさせてもらいました.

確かにこれは読みやすいし簡潔 A + (1 or 0)と書いているところが味噌

 sum += a + ((i + 1).isMultiple(of: 2) ? -1 : 0)

//sum += (index + 1).isMultiple(of: 2) ? A : A - 1 こういう書き方をしていないのがわかりやすい

C – Not Equal

組み合わせの問題.最初問題の意味がよくわからなかった.

具体例からアルゴリズムを導いた.

数列が同じ数であれば,順列組み合わせを使って簡単に求めることができるが,異なる場合はどうするか今回は1から順に選んで行くことができるため,昇順に並べ替えてから選択しCの組み合わせを考えていく.

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

let N = readInt()
let Cs = readInts()
var sortedCs = Cs.sorted()
let mod = 1_000_000_007
var ans = 1
for (index,C) in sortedCs.enumerated() {
    ans = (ans * (C - index) % mod)
}

print(ans)

1000000007で割って良い理由は以下の記事が参考になった.

https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a

今回はInt型でACを取ることができたが,19桁以上になるような計算になってくると,Double型で宣言するのも検討する必要が出てくる.

まとめ

C問題の壁はまだまだ厚い.D問題に取り組むためには演習をしっかりと行っていく必要があると感じた.

週一で参加することを習慣化することができているので,このまま続けていきたい

ABC 209 振り返りはここまで, 前回のコンテストの振り返りも参考までに載せておきます.

ではまた来週👋

前回のコンテスト

1件のコメント

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です