競プロ鉄則 Haskell AtCoder 振り返り6

A6

問題：
遊園地「ALGO-RESORT」では$N$日間にわたるイベントが開催され、$i$日目 ($1≤i≤N$) には $A_i$人が来場しました。
以下の合計$Q$個の質問に答えるプログラムを作成してください。

• $1$ 個目の質問：$L_1$日目から$R_1$日目までの合計来場者数は？
• $2$ 個目の質問：$L_2$日目から$R_2$日目までの合計来場者数は？
• :
• $Q$ 個目の質問：$L_Q$日目から $R_Q$日目までの合計来場者数は？

制限時間 : 2000ms

制約：

• $1≤N,Q≤10^5$
• $1≤A_i≤10000$
• $1≤L_i≤R_i≤N$
• 入力はすべて整数

入力：
$N$ $Q$
$A_1$ $​A_2$ ⋯ $A_N$
$L_1$ $R_1$
$L_2$ $R_2$​
:
$L_Q$ $R_Q$
​
出力：
全体で$Q$行出力してください。
$i$ 行目 ($1≤i≤Q$) には、$i$ 個目の質問への答えを整数で出力してください。

提出コード

import Control.Monad (replicateM)
  
inputIntList :: Int -> IO [[Int]]
inputIntList n = replicateM n getLine >>= return.(map ((map read).words))
          
partSum :: Int -> Int -> [Int] -> Int  
partSum l r as = as!!r - as!!(l-1)  
  
main :: IO ()
main = do
  nq <- getLine >>= return.map read.words
  let q = last nq 
  (as:lrs) <- inputIntList (q+1)
  let aAccums = scanl (+) 0 as 
  let sums = map (\[l,r] -> partSum l r aAccums) lrs
  mapM_ print sums

結果

TLE(Time Limit Exceeded,時間切れ) 時間：2214ms

徒然

ずいぶんとやってゐなかったので ほぼ 何をやったか忘れてしまった
B8の問題で つまづいてしまひ その後 操画作りに熱中してゐたこともあり ご無沙汰だ
「變」を9月末に一應完成させ それから ごたごたあって わかひめの制作にも 本格的に取り組めてゐない中 コードの技術を磨きたい思ひも高まってきた
B8も無事クリアできた
色々と勉強になったと思ふので 振り返るのも意義深いのではないだらうか

考察

main函數の上から3行まで(doを除く)は 入力されたものを得るだけのものだ
この際 まう少し効率的 といふか 分かりやすい書きかたを考へたい
入力された一行分を単語に分けて(スペースで区切って) それを整数型にする といふのは同じ作業だ
これは map read . words と合成できる(readで 何の型にするかは 後のコードから コンパイラに判断してもらふ)
getLineで得た一行に 上の變換を施す といふことを 指定回數くり返し 變數に束縛する といふことを明確にしたい

それから 時間切れの主な原因と考へられるのは リスト内の要素をインデックスで指定して取り出す といふ as!!r みたいな作業だ
リストは 私の理解では 要素が加はる時 本を上に積み上げるやうにしていくため たとへば 上から10番目の要素を取り出したいとき 一番上に積んであるものから順々に數へていって 10番目のものを取り出す といふやうなことをしてゐるから 要素が1000個もあったりして 685番目を探せ なんていふ時は かなり遅くなる
こんなとき 配列(Array)を使ってやれば インデックスを指定すると瞬時に その値が取り出せる
そこも含めて改變したコードを載せる

再提出

import Control.Monad (replicateM)
import Data.Array (listArray,Array,(!))
  
getInts :: Int -> IO [[Int]]
getInts n = replicateM n $ getLine >>= return . map read . words
          
partSum :: Int -> Int -> Array Int Int -> Int  
partSum l r as = as!r - as!(l-1)  

makePair :: [Int] -> (Int,Int)
makePair [a,b] = (a,b)
makePair _ = (0,0)
  
main :: IO ()
main = do
  [[n,q],as] <- getInts 2
  lrs <- getInts q >>= return . map makePair
  let aAccums = scanl (+) 0 as 
  let ar = listArray (0,n) aAccums
  let sums = map (\(l,r) -> partSum l r ar) lrs
  mapM_ print sums

結果

AC 時間：525ms 警告なし

考察

このArray型は Array Int Int といふ形をしてゐる
左側の Int はインデックスの型を表してゐて 右側の Int は 配列の要素の型を表してゐる
インデックスなんぞ 整數しか ありえへんやろ〜 みたいに最初思へてたけど
インデックスを(Int,Int) とかすることで 簡單に二次元配列ができてしまふスグレものだ〜
(ちなみにB8の二次元累積和では これを利用した・・・てか 最近初めて知った
それまでは Array Int (Array Int Int) とするものとばかり 思ってゐた)
listArray函數は インデックスのペア(i1,i2) とリストを渡し
渡したリストに i1からi2までのインデックスをひも付けて配列にしてくれる
listArray 0 n aAccums
といふのは 累積和をとったリスト aAccums の最初の要素を インデックス0 そこから順番にリストの要素を取って インデックスnになるまで配列にする といふものだ(と思ふ)
因みに 配列に變換するリストの要素數が足りないとエラーになるが リストの要素數が多すぎても インデックスに對應した配列をつくってくれる
このとき 問題の日數は N 日だが あえて0日目をつくってやり 累積和から 指定された範囲の和を計算するとき 0日目の人數(0人)が利用できるやうにしてゐる (これをしないと partSum で l-1を計算するとき0になることがあるため インデックス0が定義されてゐないとして 實行時エラーになってしまふ)

それと最初のコードで
inputIntList n = replicateM n getLine >>= return.(map ((map read).words))
となってゐるのと 再提出のコードで
getInts n = replicateM n $ getLine >>= return . map read . words
となってゐるところ
これは名前も實装も違ふが 同じ結果を出してゐて それを説明してみたい
まづ 上の inputIntList は getLineを n回くり返し n行分の入力文字列をn個の要素としてもつリストを出力しやうとしてゐる
ここで吐き出される型は IO [String] だ
>>= があることで この吐き出された型の [String]部分について リストのそれぞれに對し(map) 空白で区切ってリストをつくり(words) そのリストのそれぞれの要素に對して 文字列を 整數に變換し (map read) さうしてできたリストを IO として返す(return)
できたものは IO [[Int]] の型を持ってゐる
(ちなみに なぜ read で 文字列(String)が 整数(Int)に變換されるかといふと 型注釈で
IO [[Int]] と最終的なリストの型を指定してゐるため その型に合ふやうにコンパイラが解釈してくれる・・・と勝手に思ってゐます)
次に getIntsについて見ていくと これは getLineで一行分の文字列を取ったら (出力は IO String) その文字列部分に對し wordsを適用して 空白で区切ったリストをつくり map read で その各々に對して 文字列から整数への變換を行ひ IOといふ文脈(カテゴリ？)でそれを返す
出力は このとき IO [Int] となってゐる筈だ
この一連の作業をn回くり返してリストをつくるのが replicateMの役割で 結果 IO [[Int]]型が返ってくる

B6

問題：
太郎君はくじを$N$回引き,$i$回目の結果はA_i$でした．
$A_i=1$のときアタリ，$A_i=0$のときハズレを意味します．
「$L$回目から$R$回目までの中では，アタリとハズレどちらが多いか？」という形式の質問が$Q$個与えられるので，それぞれの質問に答えるプログラムを作成してください．
制限時間 : 2000ms

制約：

• $1≤N,Q≤10^5$
• $0≤A_i≤1$
• $1≤L_i≤R_i≤N$
• 入力はすべて整数

入力：
$N$
$A_1$ $​A_2$ ⋯ $A_N$
$Q$
$L_1$ $R_1$
$L_2$ $R_2$​
:
$L_Q$ $R_Q$
​
出力：
$i=1,2,3,…,Q$それぞれについて，アタリの方が多い場合winを，ハズレの方が多い場合loseを，アタリとハズレが同じ場合drawを，一行ずつ，総計$Q$ 行に出力してください．

提出コード

import Control.Monad (replicateM)
import Data.Array (listArray,Array,(!))
  
getInts :: Int -> IO [[Int]]
getInts n = replicateM n $ getLine >>= return . map read . words
          
partSum :: Int -> Int -> Array Int Int -> Int  
partSum l r as = as!r - as!(l-1)  

makePair :: [Int] -> (Int,Int)
makePair [a,b] = (a,b)
makePair _ = (0,0)

comp :: Int -> Int -> String
comp a b
  | a > b - a = "win"
  | a < b - a = "lose"
  | otherwise = "draw"
  
main :: IO ()
main = do
  [[n],as,[q]] <- getInts 3
  lrs <- getInts q >>= return . map makePair
  let aAccums = scanl (+) 0 as 
  let ar = listArray (0,n) aAccums
  let sums = map (\(l,r) -> partSum l r ar) lrs 
  let difs = map (\(l,r) -> r-l+1) lrs
  mapM_ putStrLn (zipWith comp sums difs)

結果

AC 時間: 463ms 警告なし

考察

comp函數の aは勝った數 b-a は負けた數(全體の回數から勝った數を引いてゐる)なので

comp (勝った數) (勝負した數)
  | (勝った數) > (負けた數) = "win"
  | (勝った數) < (負けた數) = "lose"
  | それ以外 = "draw"

といふ風に實装してゐる(ことを思ひ出した)
かういふ時 zipWithみたいな函數は めっちゃ便利だと思ふ
zipWithの型
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
を眺める・・・
なんか・・・美しくない？？？