ABC216 D問題
実装にうまくデータ構造を組み合わせて、計算を効率化
上から順に取っていく筒 -> スタックを使って実装
取り出す色の順番 -> キューに追加
キューやスタックは、O(1)で要素の取得ができる！
code:swift
func main(){
let input = readLine()!.split(separator: " ").map{Int($0)!}
var top_color = Int.init(repeating: [], count: N) //
var pipe = Stack.init(repeating: Stack<Int>(), count: M) for i in 0..<M{ //筒の初期化
let k = Int(readLine()!)! //玉の数
let A = readLine()!.split(separator: " ").map{Int($0)!} //玉の色 -1する ＊色 0〜N-1まで
for j in (0..<k).reversed(){
}
}
for i in 0..<M{ //一番上の色を保存している配列の初期化
if pipei.isEmpty { continue } top_color[pipei.top!].append(i) //1の色の球が2の筒の一番上にあった場合、top_color1.append2 }
var next_color = Queue<Int>() //次に出す色を保存
for i in 0..<N{ //初期状態で、取れる色があればキューに入れておく
if top_colori.count == 2{ next_color.enqueue(i)
}
}
while(!next_color.isEmpty){ //O(N)
let color = next_color.dequeue()! //次の色はこれ O(1)
//筒から出そう
//筒の番号を知りたい
for i in 0..<2{ //2つの筒から出すから
let pipe_num = top_colorcolori //筒の番号 if !pipepipe_num.isEmpty{ //筒が空ではないなら、最上段の色配列に筒番号追加 let new_top = pipepipe_num.top! //新しい一番上の色 //一色取り出したら、それ以降その色は使わないので以下の処理でいける。
top_colornew_top.append(pipe_num) //色に筒番号をつける if top_colornew_top.count == 2{ //上の玉の色が変わり、その色が２つの筒で一番上になった時 next_color.enqueue(new_top) //取り出す球をキューに追加 ＊一番後ろ
}
}
}
}
for p in pipe{ //筒に球が残っているかどうか調べる。
if !p.isEmpty{
print("No")
return
}
}
print("Yes")
//ここから下は、キューとかの定義
}
public struct Stack<T> {
fileprivate var array = T() public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public mutating func push(_ element: T) {
array.append(element)
}
public mutating func pop() -> T? {
return array.popLast()
}
public var top: T? {
return array.last
}
}
public struct Queue<T> {
fileprivate var array = T() public var isEmpty: Bool {
return array.isEmpty
}
public var count: Int {
return array.count
}
public mutating func enqueue(_ element: T) {
array.append(element)
}
public mutating func dequeue() -> T? {
if isEmpty {
return nil
} else {
return array.removeFirst()
}
}
public var front: T? {
return array.first
}
}
main()