競プロ鉄則 Haskell AtCoder 振り返り7
A7
問題：
ある会社では
参加者
各日の出席者数を出力するプログラムを作成してください
制限時間 : 2000ms
制約：
1≤D,N≤10^5 1≤L_i≤R_i≤D - 入力はすべて整数
入力：
:
出力：
提出コード
import Control.Monad (replicateM, unless)
import Data.Array.MArray (newArray, readArray, writeArray, getElems)
import Data.Array.ST (STUArray)
import Control.Monad.ST (ST, runST)
inputIntList :: Int -> IO [[Int]]
inputIntList n = replicateM n getLine >>= return.(map ((map read).words))
main :: IO ()
main = do
[ds,ns] <- inputIntList 2
let d = head ds
let n = head ns
lrs <- inputIntList n
let arr = aList d lrs
mapM_ print (scanl1 (+) arr)
aList :: Int -> [[Int]] -> [Int]
aList d lrs = runST $ do
arr <- newArray (1,d) 0 :: ST s (STUArray s Int Int)
mapM_ (\[l,r]-> do
readArray arr l >>= \i -> writeArray arr l (i+1)
unless (r==d) $ readArray arr (r+1) >>= \i -> writeArray arr (r+1) (i-1)) lrs
getElems arr
結果
AC 時間：293ms
徒然
最近AtCoderの abc(AtCoder Bigginer Contest) や adt(AtCoder Daily Training) をやるやうになつた
まだ10級だが 色々と勉強になってゐると思ふ
考察
なんと 去年の7月に書いたコードだった(今11月なので 一年半くらゐ前だ)
Mutable Array を使って 見やう見まねで 頑張って書いてゐるのが分かる
inputIntList のところからして なんか ゴチャゴチャしてゐる
それでも 何だか愛ほしい
とにかく 下手でも 不器用でも 自分で何とか考へて 進まうとしてゐるからだ
今は 若干 まう少しシンプルに書ける氣がするし それも結局 少しづつでも續けてきたからだらう
入力の部分は 今ならかう書く
import Control.Monad (replicateM)
ints :: IO [Int]
ints = map read . words <$> getLine
main :: IO ()
main = do
d <- readLn :: IO Int
n <- readLn :: IO Int
lrs <- replicateM n ints
ints の部分は
import qualified Data.ByteString.Char8 as B
import Data.List (unfoldr)
ints :: IO [Int]
ints = unfoldr (B.readInt . B.dropSpace) <$> B.getLine
のやうに ByteString を使って書くことができ この方が速いとよく言はれるが
TLEになるのは Inputの遅さよりも もっと別の原因の方がずっと多いやうな氣がする
別の原因といふのは 主にアルゴリズムだ
この問題のやうに 日づけに對して 参加者を數へ上げていくといふとき
普通は 日程が1日目から10日目まであるとして
A君が 2日目から5日目まで参加する
B君が 3日目から8日目まで参加する
となった場合 日づけに對する参加者のデータを
0 0 0 0 0 0 0 0 0 0
とリセットしてから
A君のとき
0 1 1 1 1 0 0 0 0 0
と更新し
B君のとき
0 1 2 2 2 1 1 1 0 0
と更新する
といふやうに考へるだらう(自分はさうだった)
しかし これだと 日づけの量が 大量になったり 参加者が大量になったとき
参加者ごとに 結構な量のデータを更新しなければならず 時間がかかる
けれども これを
0 0 0 0 0 0 0 0 0 0
とリセットした状態から
A君が
0 1 0 0 0 -1 0 0 0 0
B君によって
0 1 1 0 0 -1 0 0 -1 0
と更新すれば 各々の参加者がデータを更新する回數は 2回だけで済む
そして 最後のデータの累積和をとれば
0 1 2 2 2 1 1 1 0 0
となり 最初の手法と結果が同じになる
かういふことを 自分であみだせ っていふのは 結構きつい
だから 「鉄則」とかで紹介されてゐるアルゴリズム手法といふものは まさに珠玉といふか
「人類の宝」みたいなものだらう
AtCoderに觝れれば觝れるほど コードの奥深さ 世界の廣さ 自分の未熟さを 思ひ知らされる
再提出
import Control.Monad (replicateM)
import qualified Data.IntMap as M
import Data.IntMap ((!))
ints :: IO [Int]
ints = map read . words <$> getLine
main :: IO ()
main = do
d <- readLn :: IO Int
n <- readLn :: IO Int
lrs <- replicateM n ints
let mp = M.fromList (map (,0) [1..(d+1)])
let nmp = foldl updateMap mp lrs
mapM_ print $ init $ scanl1 (+) (M.elems nmp)
updateMap :: M.IntMap Int -> [Int] -> M.IntMap Int
updateMap mp [l,r] = upd (+(-1)) (r+1) $ upd (+1) l mp
where upd f = M.update (Just . f)
結果
AC 時間：534ms
考察
immutable でもクリアできた
コードがよりシンプルでいいと思ふ
B7
問題：
あるコンビニは時刻
このコンビニには
制限時間 : 6000ms
制約：
1≤T≤500000 1≤N≤500000 1≤L_i≤R_i≤T(1≤i≤N) - 入力はすべて整数
入力：
:
出力：
全体で
提出コード
import Control.Monad (replicateM)
import qualified Data.IntMap as M
import Data.IntMap ((!))
ints :: IO [Int]
ints = map read . words <$> getLine
main :: IO ()
main = do
t <- readLn :: IO Int
n <- readLn :: IO Int
lrs <- replicateM n ints
let mp = M.fromList (map (,0) [0..t])
let nmp = foldl updateMap mp lrs
mapM_ print $ init $ scanl1 (+) (M.elems nmp)
updateMap :: M.IntMap Int -> [Int] -> M.IntMap Int
updateMap mp [l,r] = upd (+(-1)) r $ upd (+1) l mp
where upd f = M.update (Just . f)
結果
AC 3971ms 568220KiB
考察
A7と實装はほとんど變はらない
IntMapの範囲が0からtになってゐるのと
更新する場所が l と r になった(A7では l と (r+1)) くらゐだ
これを MArrayで實装すると次のやうになる
再提出
import Control.Monad (replicateM)
import qualified Data.Array.MArray as A
import Data.Array.ST (STUArray)
import Control.Monad.ST (ST, runST)
ints :: IO [Int]
ints = map read . words <$> getLine
main :: IO ()
main = do
t <- readLn :: IO Int
n <- readLn :: IO Int
lrs <- replicateM n ints
let arr = aList t lrs
mapM_ print $ init $ scanl1 (+) arr
aList :: Int -> [[Int]] -> [Int]
aList t lrs = runST $ do
arr <- A.newArray (0,t) 0 :: ST s (STUArray s Int Int)
mapM_ (\[l,r] -> do
A.readArray arr l >>= A.writeArray arr l . (+1)
A.readArray arr r >>= A.writeArray arr r . (+(-1))) lrs
A.getElems arr
結果
AC 1922ms 409608KiB
考察
かかった時間が半分くらゐになった
さらに 入力の部分をBytestringでやったら 366ms になった
Discussion