ABCコンテスト2回目の参加。今回はB問題までしか解けなかった。今回のABCのために一週間練習問題をコツコツと解いてきたが、今回のC問題は初めて見る形式で難しかった。
とりあえず解けた問題の振り返りを行う。
A – Rock-paper-scissors
サーバル、フェネック、アライグマの 3 人がじゃんけんをして、あいこになりました。
フェネックが出した手を表す文字 xx とアライグマが出した手を表す文字 yy が与えられます。それぞれ、0 はグー、1 はチョキを、2 はパーを表します。
サーバルが出した手を表す文字を出力してください。なお、答えは一意に定まります。
最初問題を読む時は問題文からではなくて、入出力の例を見てから問題文を読んだ方が情報が整理されることがわかった。
B – Nuts
- 10より大きい要素をフィルターで取得
- reduceでそれぞれの要素を足し合わせる。
- 足し合わせる値は$1ではなく$1-10を足すのが味噌
回答
let _ = readInt()
let As = readInts()
let result = As.filter { $0 > 10 }.reduce(0) { $0 + $1-10}
print(result)ナッツ食べたい(笑)
C – Tour
考察
- Aの配列、Bの配列を準備
- Bの配列は同じ要素が被るのがあるためSetを使用して被りなしの配列を準備 SetB
- Aのi番目の要素からSetBの要素を比べて異なればカウント同じであればカウントしない
func readTwoInts() -> (a: Int, b: Int) {
let ints = readLine()!.split(separator: " ").map { Int($0)! }
return (a: ints[0], b: ints[1])
}
let (N,M) = readTwoInts()
let data = (0..<M).map { _ in readTwoInts()}
var arrA = data.map { $0.a }
var arrB = data.map { $0.b }
var setB: Set<Int> = []
var count = 0
for i in arrB {
setB.insert(i)
}
count = N
for a in arrA {
for j in Array(setB) {
if j == a {
count += 0
} else {
count += 1
}
}
}
print(count)結果
これだけでいけると思ったが、結果は部分的ACでWAであった。
解説にはDFSやBFSを使用して解く問題らしい。この辺りの知識はまだまだなので演習をこなしながらこれから頑張りたい！
06-16_11-24追記
この問題は有向グラフの問題で、グラフの知識があれば比較的簡単に解ける問題だとわかった。
再帰関数を使って現在のVにたいしてどのくらいグラフが深く伸びるかを確認する。(DFS)
グラフGに必要な要素
- 頂点 (vertex) の有限集合 V=(v1,v2,…,vn)V=(v1,v2,…,vn)
- 辺 (edge) の有限集合 E=(e1,e2,…,em)E=(e1,e2,…,em)
の組として定義され、G=(V,E)G=(V,E) と表される。各辺 e∈Ee∈E は 2 つの頂点 vi,vj∈Vvi,vj∈V の 組として定義され、e=(vi,vj)e=(vi,vj) のように表される。
- 有向グラフ
方向を持ったグラフ無向グラフも存在する - パス
同じ頂点を二度通らないものをパスとよぶ
追記の答え
//NとMの読み込み
let (N,M) = readTwoInts()
//N個の空の配列
var G = [[Int]].init(repeating: [], count: N)
//それぞれの頂点に隣接しているV情報を保存
let _ = (0..<M).map { _ in
let (A,B) = readTwoInts()
G[A-1].append(B-1)
}
//####################
//vは頂点
func dfs(v:Int) {
if temp[v] {
return
}
//vには足をふみいれないようにする。
temp[v] = true
//vvは頂点が持つ到達可能頂点
for vv in G[v] {
dfs(v: vv)
}
}
var temp = [Bool]()
var answer = 0
for i in 0..<N {
temp = [Bool](repeating: false, count: N)
dfs(v: i)
answer += temp.filter{ $0 == true }.count
}
print(answer)
