paizaラーニングの演習問題にて正解コードが分からず困っております。
paiza演習問題のURLと私の回答コードを以下の通りです。
質問ですが、実際にコードを提出すると、
入力ケース１・２は正解、入力ケース3がランタイムエラー、入力ケース４ではスキップされました
とジャッジされます。
入力ケース3と入力ケース4で不正解となっているのを直したいのですが、どこをどう直せば良いでしょうか。
paizaでは、paiza内で使用できるチケットがあり、ブラックボックスである入力値や解法なども覗けるようになります。
解法について確認してみたところ「計算量を抑える為、imos法を使用」とありました。
また、不正解となっている入力ケース３では、1000個の数列と1000個のクエリが与えられていることがわかりました。
私の回答コードは時間がかかる愚直な方法だと思いますが、
では、imos法を使って処理の負荷を軽減すれば良いのか、それともコードの出力結果が間違っているのかも分からず、行き詰まっております。
私の見落としについてや、正解コード(imos法使用？)について、詳しい方ご教授いただけますでしょうか？
■質問となる演習問題の下記URL
https://paiza.jp/works/mondai/a_rank_level_up_problems/a_rank_twopointers_step5/edit?language_uid=swift
※言語はswiftです。
※スキルチェックではなく演習問題ですので、コードや解答の掲載は問題ありません。
■私の回答コード
import Foundation
let conditions = (readLine()!.components(separatedBy: " ")).map{Int($0)!}
let n = conditions[0]//数列の要素数
let m = conditions[1]//クエリの数
//数列を配列にしまう
var suretsu = (readLine()!.components(separatedBy: " ")).map{Int($0)!}
//クエリを読み取り、処理する
for _ in 0 ..< m {
let q = (readLine()!.components(separatedBy: " ")).map{Int($0)!}
for j in q[0] - 1 ... q[1] - 1 {
suretsu[j] += q[2]
}
}
//出力
for i in 0 ..< n {
print(suretsu[i])
}
■私の回答コード（imos法使用）
import Foundation
let conditions = (readLine()!.components(separatedBy: " ")).map{Int($0)!}
let n = conditions[0]//数列の要素数
let m = conditions[1]//クエリの数
//数列を配列にしまう
var suretsu = (readLine()!.components(separatedBy: " ")).map{Int($0)!}
//add配列とruiseki配列に初期値代入
var add = [Int]()
var ruiseki = [Int]()
for _ in 0 ..< n {
add.append(0)
ruiseki.append(0)
}
//クエリを読み取り、加算処理
for _ in 0 ..< m {
let q = (readLine()!.components(separatedBy: " ")).map{Int($0)!}
add[q[0] - 1] += q[2]
if q[1] != n {
add[q[1]] -= q[2]
}
}
//累積和
ruiseki[0] = add[0]
for i in 1 ..< n {
ruiseki[i] = ruiseki[i - 1] + add[i]
}
//出力
for i in 0 ..< n {
let result = suretsu[i] + ruiseki[i]
print(result)
}
いもす法はググれば、簡単に見つけられるはずです。
結果がナイーブな方法と一致するよう、そのアルゴリズムに従って実装してみましょう。
ちなみにC#で挑んでみましたが、いもす法を適用してもなお入力ケース3がランタイムエラーになりました。
2行目の数列を空白でSplitして配列化していたため、容量の制限に引っ掛かったっぽいです。
最終的に、配列化を行わず、ループを回して空白の位置を探りつつ、Substringで切り出してやっと突破できました。
1000要素の文字列配列が増えた程度で、512MBの壁を突破したのが信じられませんが、
正直、これを一発で解けというのは無理ゲーに感じました。
@_mitty
Questionerpaizaでは提出コードの必要メモリが512MBを超えると弾かれるのでしょうか？
練習問題で多くの人がアクセスするため、単にメモリの最大使用量をケチっていたか、もしくはMonoがメモリバカ食いなのか
Swiftなら、ワンチャンあるかもなので、ますは素直に「いもす法」でやってみて、だめならメモリやり繰りすればよいかと。
@_mitty
Questioner