A7

問題：
ある会社では $D$ 日間にわたってイベントが開催され、 $N$ 人が出席します
参加者 $i$ は $L_i$ 日目から $R_i$ 日目まで出席する予定です
各日の出席者数を出力するプログラムを作成してください

制限時間 : 2000ms

制約：

$1\leqD,N\leq10^5$
$1\leqL_i\leqR_i\leqD$
入力はすべて整数

入力：
$D$
$N$
$L_1$ $R_1$
$L_2$ $R_2$
:
$L_N$ $R_N$

出力：
$D$ 行にわたって出力してください。
$d$ 行目には $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

問題：
あるコンビニは時刻 $0$ に開店し時刻 $T$ に閉店します
このコンビニには $N$ 人の従業員が働いており $i$ 番目( $1\leqi\leqN$ )の従業員は時刻 $L_i$ に出勤し時刻 $R_i$ に退勤します
$t=0,1,2,...,T-1$ それぞれについて時刻 $t+0.5$ にコンビニにいる従業員の数を出力するプログラムを作成してください

制限時間 : 6000ms

制約：

$1\leqT\leq500000$
$1\leqN\leq500000$
$1\leqL_i\leqR_i\leqT(1\leqi\leqN)$
入力はすべて整数

入力：
$T$
$N$
$L_1$ $R_1$
$L_2$ $R_2$
:
$L_N$ $R_N$

出力：
全体で $T$ 行出力してください。
$t+1$ 行目 $(0\leqt\leqT-1)には時刻$ t+0.5$にコンビニにいる従業員の数を出力してください

提出コード

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