質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Swift

Swiftは、アップルのiOSおよびOS Xのためのプログラミング言語で、Objective-CやObjective-C++と共存することが意図されています

Q&A

解決済

1回答

1085閲覧

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

cardamon_sa

総合スコア1

Swift

Swiftは、アップルのiOSおよびOS Xのためのプログラミング言語で、Objective-CやObjective-C++と共存することが意図されています

0グッド

0クリップ

投稿2020/07/15 10:03

編集2020/07/15 12:27

前提・実現したいこと

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

発生している問題

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

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

該当のソースコード

swift

1import Foundation 2 3func readInts() -> [Int] { 4 readLine()!.split(separator: " ").map { Int($0)! } 5} 6 7func main() { 8 let nk = readInts() 9 let (n,k) = (nk[0],nk[1]) 10 var sequence = [Int]() 11 for _ in 1...n { 12 sequence.append(Int(readLine()!)!) 13 }//______________________ここまで入力 14 15 // 0が入力されている場合、答えはnになるためnを出力して処理を終了する 16 if sequence.firstIndex(of: 0) != nil { 17 print(n) 18 return 19 } 20 var ans = 0 21 var index = 0 22 var resMultiplied = 1 23 24 for startIndex in 0..<n { 25 index = startIndex 26 while index < n && resMultiplied * sequence[index] <= k { 27 resMultiplied *= sequence[index] 28 index += 1 29 } 30 ans = max(ans, index - startIndex) 31 32 // 開始するインデックスがインデックスを超えないようにする 33 if startIndex == index { 34 index += 1 35 } 36 resMultiplied = 1 37 38 } 39 print(ans) 40 41} 42main() 43

試したこと

Swift

1// 略 2if sequence.firstIndex(of: 0) != nil { 3 print(n) 4 return 5 } 6// 略

Swift

1// 略 2if ss.contains(0) { 3 print(n) 4 return 5 } 6// 略

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

追記

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fuzzball

2020/07/15 11:57

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

2020/07/15 12:33 編集

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

2020/07/15 13:03

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

2020/07/15 13:51

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

2020/07/15 13:58

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

回答1

0

ベストアンサー

Swift

1 if startIndex == index { 2 index += 1 3 }

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

投稿2020/07/15 10:31

yudedako67

総合スコア2047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

cardamon_sa

2020/07/15 14:49 編集

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問