【Swift】atCoder ABC032 C問題について

Question

前提・実現したいこと

下記コードの実行速度を上げたいです。

発生している問題

以下、3つのテストケースでTLEが発生しています。

• subtask2_02.txt
• subtask2_16.txt
• subtask2_17.txt

該当のソースコード

import Foundation

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

func main() {
    let nk = readInts()
    let (n,k) = (nk[0],nk[1])
    var sequence = [Int]()
    for _ in 1...n {
        sequence.append(Int(readLine()!)!)
    }//______________________ここまで入力
    
    // 0が入力されている場合、答えはnになるためnを出力して処理を終了する
    if sequence.firstIndex(of: 0) != nil {
        print(n)
        return
    }
    var ans = 0
    var index = 0
    var resMultiplied = 1
    
    for startIndex in 0..<n {
        index = startIndex
        while index < n && resMultiplied * sequence[index] <= k {
            resMultiplied *= sequence[index]
            index += 1
        }
        ans = max(ans, index - startIndex)
        
        // 開始するインデックスがインデックスを超えないようにする
        if startIndex == index {
            index += 1
        }
        resMultiplied = 1
        
    }
    print(ans)

}
main()

試したこと

// 略
if sequence.firstIndex(of: 0) != nil {
        print(n)
        return
    }
// 略

を

//　略
if ss.contains(0) {
        print(n)
        return
    }
//　略

に変えて提出してみましたが同じ結果でした。
Swiftで解答された方がいらっしゃらなかったので、他言語で解答された方のコードと比較してみましたが、
アルゴリズム的に大差はないように見えました。

追記

TLE判定が出たテストケース意外では全てAC判定が出ています。

Comments

[fuzzball]

速度の前に正しいコードを考えるべきでは？
現在のコードでは「最も長いもの」を求められていないと思います。

[cardamon_sa]

情報が不足していたため、追記しました。
今回はたまたまAC判定が出ているが
別にテストケースを用意し実行した場合、
WA判定が出る可能性のあるコードであるということでしょうか？

[fuzzball]

https://atcoder.jp/contests/abc032/tasks/abc032_c
この問題でいいでしょうか？
入力例2で正解にならないと思います。

[cardamon_sa]

その問題です。URL貼るべきでした、すみません。
入力例2についてですが、
if sequence.firstIndex(of: 0) != nil {
print(n)
return
}
↑の部分で整数列に0がある場合、整数列全てをかけることができるため
「最も長いもの」であるNが出力され処理が終了するようにしています。
試しに入力例2を実行してみたところ、出力例2と同じ結果が得られました。

[fuzzball]

これは失礼しました。
var ans = 0 から上は入力処理か何かかと思って目に入ってなかったです。
申し訳ないです。

[cardamon_sa]

とんでもないです。
私の質問に情報が不足していたため、お手数をかけしてしまいました。
気にかけてくださりありがとうございました。

Answer 1

        if startIndex == index {
            index += 1
        }

今の処理だとこのコードが全く無意味です。
このコードがあるということは、前のループの結果を利用して次のループの計算を途中から始めるという構想はあったはずなので、その方針で書き直してください。

Comments

[cardamon_sa]

ご回答、ありがとうございます。
修正してみます。
___________________________
追記
無事AC判定が出ました。
ありがとうございました。