今回もAtCoder Beginner Contestに参加． ギリギリC問題まで解けた．
単純なアリゴリズムで実装しても実行時間エラーが問題になってくる．今回のC
問題は少し頭をひねらないと解けない問題だった．
A – Cabbages
条件文を書くときに少し立ち止まって見てみる．
すると `if N <= A`の条件文はｍ三項演算子で書くことができる．
let input = readInts()
let N = input[0]
let A = input[1]
let X = input[2]
let Y = input[3]
if N <= A {
print(X*N)
} else {
print(X*A+Y*(N-A))
}
print( N <= A ? X * N : X * A + Y * ( A - N ))今回のような見やすさを重視するなら上でもいいが，アプリ開発だと三項演算子を使ったほうがコードの見通しが良くなる．
B – Bouzu Mekuri
- 文字列から任意のindexを取得する方法
- enumeratedを使用すると取得可能
- 文字列のイテレータを回して，judgeをtrueからfalseに変化させている．
func readInt() -> Int {
return Int(readLine()!)!
}
func main1() {
let N = readInt()
var S = readLine()!
var judge = false
for c in S {
if c == "1" {
print(judge ? "Aoki" : "Takahashi")
break
}
judge = judge ? false : true
}
}
main1()
イテレータ使用する際に配列の順番も取得するには，enumerated関数をシーケンス変数にわたすとindexが取得可能
また，文字列を配列として認識させて，indexを取得すれば，isMultibple関数が使えるため非常に簡潔に表現することができる．
let S = Array(readLine()!)
print(S.firstIndex(of: "1")!.isMultiple(of: 2) ? "Takahashi" : "Aoki")C – Colorful Candies
スライドでカウントしていく問題
初めてこの形式の問題を解いた．鍵は連想配列を使って，O（N）のループ内で，どのkeyが出現して，どのkeyが削除されるかの2つの計算を行うことで計算量を削減することができる．
今回は出現するkeyをベースにN回ループを行い，
削除するkeyは i >= K という条件を使うことでアルゴリズムを実現した．
let (N, K) = readTwoInts()
let Cs = readLine()!.split(separator: " ").map { Int($0)! }
var (now,ans) = (0,0)
var dic: [Int:Int] = [:]
//問題は1からN-K+1 O（N）までの数繰り返す
for i in 0..<N {
let key = Cs[i]
dic[key,default: 0] += 0
if dic[key,default: 0] == 0 {
now += 1
}
dic[key]! += 1
if i >= K {
let delKey = Cs[i-K]
dic[delKey]! -= 1
if dic[delKey]! == 0 {
now -= 1
}
}
ans = max(ans, now)
}
print(ans)
連想配列はnilを返す可能性がある．あらかじめ初めて見るkeyに対して0を足している代入している．
まとめ
今回は，グラフのアルゴリズムを使用することはなかったので新しい発見があった．
連想配列を用いてスライドしていく発想は別の問題にも応用ができそうだと感じたため類題を解いて自分のものにしたいと思う．
コンテスト後
コンテストが終わってから，毎週D問題以上の問題を解いて解説する勉強会を始めた．
Atcorderが続いているのも研究室のメンバーのおかげであるので張り切って資料を作ったので，ここにその資料を共有しておきます．
おわり
