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

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

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

Haskellは高い機能性をもった関数型プログラミング言語で、他の手続き型プログラミング言語では難しいとされている関数でも容易に行うことができます。強い静的型付け、遅延評価などに対応しています。

Q&A

解決済

1回答

360閲覧

Haskellのリストにおいてk番目の要素を削除する方法が知りたいです

kurokko

総合スコア15

Haskell

Haskellは高い機能性をもった関数型プログラミング言語で、他の手続き型プログラミング言語では難しいとされている関数でも容易に行うことができます。強い静的型付け、遅延評価などに対応しています。

0グッド

0クリップ

投稿2023/01/27 10:05

前提

Haskellで競技プログラミングの問題を解いています。

実現したいこと

リストのk番目の要素を削除する素早い方法を教えてもらいたいです。

発生している問題

TLEとなってしまいます。
おそらくリストのk番目の要素を削除する処理(deleteKの部分)で遅くなっていると思うので、このような質問をいたしました。
問題は
https://atcoder.jp/contests/abc125/tasks/abc125_c
です。

該当のソースコード

haskell

1import Control.Monad 2import qualified Data.ByteString.Char8 as BS 3 4main = do 5 n <- getLine 6 --list <- map read . words <$> getLine 7 list <- map (read . BS.unpack).BS.words <$> BS.getLine 8 print $ result list 9 10 11allGCD list = foldr gcd (head list ) list 12 13deleteK k list = (take k list) ++ (drop (k+1) list ) 14 15deleteRe list = map (\pair -> deleteK (fst pair) list) ziped 16 where ziped = zip [0,1 ..] list 17 18 19resultList list = map allGCD tmpList 20 where tmpList = deleteRe list 21 22result list = maximum $ resultList list

よろしくお願いいたします。

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

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

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

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

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

actorbug

2023/01/27 15:17 編集

遅い原因が deleteK だけではないので、別の方法を探したほうが良いです。 例えば、resultList list の計算量を考えると(tmpList の作成の計算量はとりあえず無視)、 tmpListの各要素が長さ n-1 のリストなので、それぞれの allGCD を求めるのに n-1 回の計算が必要、 tmpList の長さが n なので、ここだけで n * (n-1) で O(n^2)の時間がかかります。 どうしても高速化する方法を思いつかないなら、解説に頼りましょう。 Haskellでやるなら、解説に書いてある累積和を使う方法が良いかと思います。(というかHaskellでセグメントツリーを使う方法を私が知らないので他に選択肢が無かった) https://blog.hamayanhamayan.com/entry/2019/04/28/085936
kurokko

2023/01/27 15:43

回答していただきありがとうございます! 無事解決いたしました。
guest

回答1

0

自己解決

以下のようにしたところ無事解決しました。
実行速度が10倍早くなり、なおかつシンプルに書けてとても驚いています。

haskell

1 2import Control.Monad 3import qualified Data.ByteString.Char8 as BS 4 5main = do 6 n <- getLine 7 list <- map (read . BS.unpack).BS.words <$> BS.getLine 8 print $ result list 9 10result xs = maximum $ zipWith gcd (scanl gcd 0 xs) (tail $ scanr gcd 0 xs)

ありがとうございました。

投稿2023/01/27 15:43

kurokko

総合スコア15

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.48%

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

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

質問する

関連した質問