[Q&A] paizaAランク演習問題（陣取りゲーム）の解法について

paizaAランク演習問題（陣取りゲーム）の解法について

解決したいこと

paizaAランク演習問題（陣取りゲーム）の解答についてです。（言語はSwiftです）
https://paiza.jp/works/mondai/a_rank_level_up_problems/a_rank_camp_boss/edit?language_uid=swift

以下に載せているコードが、私の提出コードです。
そして判定結果が、テスト1,2,3は通過・テスト4がタイムオーバー、テスト5,6,7はスキップ　です。

質問ですが、テスト1,2,3では通過しているのに、なぜテスト4でタイムオーバーになっているのか、
分かる詳しい方、教えていただけないでしょうか？

テスト4では、入力値として1000×1000の盤面が与えられていることが分かっています。
私の解答コードの出力結果が間違っている可能性が最も高いですが、
エラーの種類が、「ランタイムエラー」ではなく、「タイムオーバー」なので、より高速なコードがかければ正解になる可能性もあるのか、など分からず困っております。

また、他の演習問題（Aランク区間への足し算）でも、
テスト入力値のデータ量が少ないときは通過して、データ量が増えるとエラーになるというケースを経験しており、省メモリかつ高速なコードでなければならないというような暗黙の制約があったりするのでしょうか。
https://qiita.com/_mitty/questions/32c2aec8937d73250dfa

何かお気づきの方、教えていただけますと幸いです。

私の提出コード

<全体方針>
１、field配列に盤面情報をしまう
２、Acheck配列　Bcheck配列に　A、Bそれぞれのスタート座標をしまう
　　ex) 例えば初期値を代入して、 Acheck = [[3,4]]
　　　　その後陣地を拡大すると、一旦全削除して最新の広げた陣地の座標を代入
　　　　Aceck = [[2,4], [4,4], [3,3], [3,5]]
　　　　というように更新してき、常に１つ前の処理で拡大したばかりの陣地の座標だけをしまう
３、while-loopで、
　　1) field配列をfield_copy配列にコピー
　　（field_copy配列は陣地拡大前の盤面を参照用、field配列は陣地拡大後の盤面に随時更新）
　　2) player変数=Aのとき Acheck配列の座標の数だけfor文で上下左右をチェックする
　　　　 "."を見つけたら、その都度tmpfield配列を"A"に変える
　　　（player変数=BのときはBcheck配列で同様の処理）
　　3) field配列を陣地拡大後の情報に更新
　　　（field = tmpfield）
　　4) loopしていて盤面の変化がない状況が2回続くとき、AもBも陣地をこれ以上拡大できない
　　　　よって、loopを抜ける。
　　　　それ以外の場合は、player変数を"A"であれば"B"に、"B"であれば"A"にスイッチして次の処理へ
４、field配列の”A"と”B"の数をそれぞれカウントし、結果を出力

import Foundation

let size = (readLine()!.components(separatedBy: " ")).map{Int($0)!}
let h = size[0]
let w = size[1]
let firstplayer = readLine()!
var field = [[String]]()
var Acheck = [[Int]]()
var Bcheck = [[Int]]()
for i in 0 ..< h {
    let tmp = Array(readLine()!).map{String($0)}
    field.append(tmp)
    if tmp.contains("A") {
        let j = tmp.firstIndex(where: {$0 == "A"})!
        Acheck.append([i, j])
    }
    if tmp.contains("B") {
        let j = tmp.firstIndex(where: {$0 == "B"})!
        Bcheck.append([i, j])
    }
}

var player = firstplayer
var finishcheck = false
var cnt = 0
var tmpAcheck = [[Int]]()
var tmpBcheck = [[Int]]()
var p = 0
while finishcheck == false {
    //陣地拡大前の盤面を保持しておく
    let field_copy = field
    //上下左右チェック
    if player == "A" {
        for x in 0 ..< Acheck.count {
            let i = Acheck[x][0]
            let j = Acheck[x][1]
            //上
            if i - 1 >= 0 { if field_copy[i - 1][j] == "." { field[i - 1][j] = player; tmpAcheck.append([i - 1, j])}}
            //下
            if i + 1 < h { if field_copy[i + 1][j] == "." { field[i + 1][j] = player; tmpAcheck.append([i + 1, j])}}
            //左
            if j - 1 >= 0 { if field_copy[i][j - 1] == "." { field[i][j - 1] = player; tmpAcheck.append([i, j - 1])}}
            //右
            if j + 1 < w { if field_copy[i][j + 1] == "." { field[i][j + 1] = player; tmpAcheck.append([i, j + 1])}}
        }
        Acheck = tmpAcheck
        tmpAcheck.removeAll()
    } else {
        for x in 0 ..< Bcheck.count {
            let i = Bcheck[x][0]
            let j = Bcheck[x][1]
            //上
            if i - 1 >= 0 { if field_copy[i - 1][j] == "." { field[i - 1][j] = player; tmpBcheck.append([i - 1, j])}}
            //下
            if i + 1 < h { if field_copy[i + 1][j] == "." { field[i + 1][j] = player; tmpBcheck.append([i + 1, j])}}
            //左
            if j - 1 >= 0 { if field_copy[i][j - 1] == "." { field[i][j - 1] = player; tmpBcheck.append([i, j - 1])}}
            //右
            if j + 1 < w { if field_copy[i][j + 1] == "." { field[i][j + 1] = player; tmpBcheck.append([i, j + 1])}}
        }
        Bcheck = tmpBcheck
        tmpBcheck.removeAll()            
    }

    //盤面の変化チェック
    if field == field_copy {
        if cnt == 0 {
            //次のプレイヤーがマスを拡大できるかもしれない
            //プレイヤー交替
            if player == "A" { player = "B" } else { player = "A" }
            cnt += 1
        } else if cnt == 1 {
            //cnt=0でもcnt=1でも盤面の変化なし
            //ゲーム終了のため抜ける
            finishcheck = true
        }
    } else {
        //プレイヤー交替
        if player == "A" { player = "B" } else { player = "A" }
        cnt = 0
    }
}

//勝敗
var Anum = 0
var Bnum = 0
for i in 0 ..< h {
    let a = (field[i].filter{$0 == "A"}).count
    let b = (field[i].filter{$0 == "B"}).count
    Anum += a
    Bnum += b
}

//出力
if Anum > Bnum {
    print("\(Anum) \(Bnum)")
    print("A")
} else if Bnum > Anum {
    print("\(Anum) \(Bnum)")
    print("B")
}

私の提出コード　（時間計測チェック用）

@ktz_aliasさんのご指摘を踏まえて、コードのどこで時間がかかっているのか確認しました。

確認用に50*10の盤面を仮で作成し、コードの各部分で実行に要する時間を計測しています。
(質問の1000*1000の巨大盤面には遠く及びませんが、paiza上で実行できることは確認しています)
見やすさのため、いずれの所要時間も ×100000 にして出力しています。

結果は、
pointA・・・ほぼかからない
pointB・・・序盤はほぼかからないが、処理が進むにつれて急激に重くなっている
でした。

処理が進むにつれてfield配列のデータ量が急激に増えている　ということではなく、
ずっと同じ要素数の配列を更新し続けているだけなのですが、なぜ、処理時間が増えていくのでしょうか？
こちらも、何かご存知でしたら教えていただけないでしょうか。

import Foundation

/*-----------------------非表示-----------------------
let size = (readLine()!.components(separatedBy: " ")).map{Int($0)!}
let h = size[0]
let w = size[1]
let firstplayer = readLine()!
var field = [[String]]()
var Acheck = [[Int]]()
var Bcheck = [[Int]]()
for i in 0 ..< h {
    let tmp = Array(readLine()!).map{String($0)}
    field.append(tmp)
    if tmp.contains("A") {
        let j = tmp.firstIndex(where: {$0 == "A"})!
        Acheck.append([i, j])
    }
    if tmp.contains("B") {
        let j = tmp.firstIndex(where: {$0 == "B"})!
        Bcheck.append([i, j])
    }
}
*/-----------------------非表示-----------------------

let h = 50
let w = 10
let firstplayer = "A"
var Acheck = [[1, 6]]
var Bcheck = [[39, 1]]
var field = [
[".", ".", ".", ".", ".", ".", ".", ".", ".", "."],
["#", ".", "#", ".", ".", ".", "A", ".", ".", "."],
[".", ".", ".", "#", "#", "#", "#", ".", "#", "."],
[".", ".", ".", ".", ".", ".", "#", "#", ".", "."],
["#", ".", "#", "#", "#", "#", "#", "#", "#", "."],
[".", ".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", "#", "#", "#", "."],
[".", "#", "#", "#", "#", ".", "#", ".", "#", "."],
[".", ".", ".", ".", ".", ".", "#", "#", "#", "."],
[".", ".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", ".", "."],
["#", ".", "#", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", "#", "#", "#", ".", "#", "#", "."],
[".", ".", ".", ".", ".", ".", ".", "#", ".", "."],
[".", "#", "#", "#", "#", ".", "#", "#", "#", "."],
[".", ".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", "#", "#", "#", "#"],
[".", "#", "#", ".", "#", "#", ".", ".", "#", "."],
[".", ".", ".", ".", ".", ".", "#", "#", "#", "."],
[".", ".", ".", ".", "#", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", "#", ".", ".", ".", "#"],
["#", "#", "#", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", "#", "#", "#", "#", "#", "#", "."],
[".", ".", ".", ".", ".", ".", "#", ".", ".", "."],
[".", "#", "#", "#", ".", ".", "#", "#", "#", "."],
[".", ".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", "#", ".", "#", ".", "#", "#"],
[".", "#", "#", "#", "#", "#", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", "#", "#", ".", "."],
[".", ".", ".", ".", "#", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", ".", "."],
["#", "#", "#", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", "#", "#", ".", "#", "#", "."],
[".", ".", ".", ".", ".", ".", ".", "#", ".", "."],
[".", "#", "#", "#", "#", "#", ".", "#", "#", "."],
[".", ".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", "#", "#", ".", "#"],
[".", "#", "#", "#", "#", "#", "#", ".", "#", "."],
[".", ".", ".", ".", ".", ".", ".", "#", "#", "."],
["#", "B", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", ".", ".", ".", "."],
["#", "#", "#", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", "#", "#", "#", ".", "#", "#", "."],
[".", ".", ".", ".", ".", ".", ".", "#", ".", "."],
[".", "#", "#", "#", "#", "#", ".", "#", "#", "."],
[".", ".", ".", ".", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", ".", "#", "#", ".", "#"],
[".", "#", "#", ".", ".", "#", "#", ".", "#", "."],
[".", ".", ".", ".", ".", ".", ".", "#", "#", "."],
["#", ".", ".", ".", ".", ".", ".", ".", ".", "."]
]

var player = firstplayer
var finishcheck = false
var cnt = 0
var tmpAcheck = [[Int]]()
var tmpBcheck = [[Int]]()
var p = 0
let pointXstart = Date()//------------------------------------pointX Start
while finishcheck == false {

    //陣地拡大前の盤面を保持しておく
    let pointAstart = Date()//--------------------------------pointA Start
    let field_copy = field
    let pointA = Date().timeIntervalSince(pointAstart)
    print("pointA=\(pointA * Double(100000))")     //---------pointA End

    let pointBstart = Date()//--------------------------------pointB Start
    //上下左右チェック
    if player == "A" {
        for x in 0 ..< Acheck.count {
            let i = Acheck[x][0]
            let j = Acheck[x][1]
            //上
            if i - 1 >= 0 { if field_copy[i - 1][j] == "." { field[i - 1][j] = player; tmpAcheck.append([i - 1, j])}}
            //下
            if i + 1 < h { if field_copy[i + 1][j] == "." { field[i + 1][j] = player; tmpAcheck.append([i + 1, j])}}
            //左
            if j - 1 >= 0 { if field_copy[i][j - 1] == "." { field[i][j - 1] = player; tmpAcheck.append([i, j - 1])}}
            //右
            if j + 1 < w { if field_copy[i][j + 1] == "." { field[i][j + 1] = player; tmpAcheck.append([i, j + 1])}}
        }
        Acheck = tmpAcheck
        tmpAcheck.removeAll()
    } else {
        for x in 0 ..< Bcheck.count {
            let i = Bcheck[x][0]
            let j = Bcheck[x][1]
            //上
            if i - 1 >= 0 { if field_copy[i - 1][j] == "." { field[i - 1][j] = player; tmpBcheck.append([i - 1, j])}}
            //下
            if i + 1 < h { if field_copy[i + 1][j] == "." { field[i + 1][j] = player; tmpBcheck.append([i + 1, j])}}
            //左
            if j - 1 >= 0 { if field_copy[i][j - 1] == "." { field[i][j - 1] = player; tmpBcheck.append([i, j - 1])}}
            //右
            if j + 1 < w { if field_copy[i][j + 1] == "." { field[i][j + 1] = player; tmpBcheck.append([i, j + 1])}}
        }
        Bcheck = tmpBcheck
        tmpBcheck.removeAll()            
    }
    let pointB = Date().timeIntervalSince(pointBstart)
    print("pointB=\(pointB * Double(100000))")     //---------pointB End

    /*-------非表示-------
    print("\(player)拡大前")
    for i in 0 ..< h {
        print(field_copy[i])
    }
    print("\(player)拡大後")
    for i in 0 ..< h {
        print(field[i])
    }
    */-------非表示-------
    //盤面の変化チェック
    if field == field_copy {
        if cnt == 0 {
            //次のプレイヤーがマスを拡大できるかもしれない
            //プレイヤー交替
            if player == "A" { player = "B" } else { player = "A" }
            cnt += 1
        } else if cnt == 1 {
            //cnt=0でもcnt=1でも盤面の変化なし
            //ゲーム終了のため抜ける
            finishcheck = true
        }
    } else {
        //プレイヤー交替
        if player == "A" { player = "B" } else { player = "A" }
        cnt = 0
    }
}
let pointX = Date().timeIntervalSince(pointXstart)
print("pointX=\(pointX * Double(100000))")     //-------------pointX End

//勝敗
var Anum = 0
var Bnum = 0
for i in 0 ..< h {
    let a = (field[i].filter{$0 == "A"}).count
    let b = (field[i].filter{$0 == "B"}).count
    Anum += a
    Bnum += b
}

//出力
if Anum > Bnum {
    print("\(Anum) \(Bnum)")
    print("A")
} else if Bnum > Anum {
    print("\(Anum) \(Bnum)")
    print("B")
}

1Answer

@ktz_alias posted at 2021-04-14

テスト４は1000x1000の巨大盤面なので、各プレイヤーの毎ターン

let field_copy = field

によるコピーが負荷の大半を担ってそうな気がします。
このコピーを防ぐ、または抑えることができるかが最優先の課題かなと。

0Like

Comments

@_mitty
Questioner
別の質問に引き続き、今回の質問でも、
アドバイスいただきありがとうございます。

どこで時間がかかっているのかチェックしてみましたが、field配列のコピーが原因ではないようです。
チェックに用いたコードを上の最初の質問に追記しましたので、ご確認いただけないでしょうか。
処理時間を計測していて、原因と思えるような部分を見つけました。（pointB）
何かお気づきの点がありましたら、返信いただけると幸いです。

（追記）
python3で正解例を見れましたので、
まずそのまま正解コードをコピペして提出・・・無事通過
正解コードをコピペしてdelay関数を挟んで、強制的に時間がかかるコードにして提出・・・タイムオーバー
でした。
当然の結果かもしれませんが、「タイムオーバー」のエラーは正しい結果を出力できても時間がかかっている時にでているようです。

paizaAランク演習問題（陣取りゲーム）の解法について

解決したいこと

私の提出コード

私の提出コード　（時間計測チェック用）

1Answer

Comments

Your answer might help someone💌

Popular Questions

paizaAランク演習問題（陣取りゲーム）の解法について

解決したいこと

私の提出コード

私の提出コード （時間計測チェック用）

1Answer

Comments

Your answer might help someone💌

Popular Questions

私の提出コード　（時間計測チェック用）