ABC 348 / IO, StateT

ABC 348

ABC 348 に参加しました。

A 問題

cojna さんの提出 が痺れます。 Shortest もシンプルで凄い。

B 問題

最小・最大を読み間違えており、なかなか大変な問題だと思っていました。

実装のコツは、

1. 小数の精度不足を恐れ、距離の 2 乗を整数値として使う
   
2. 最大値の検索 (maximum) と添字の発見 (findIndex (== theMax)) の実行を分ける
   

C 問題

maximum . IM.elems . IM.fromListWith min で解きました。

D 問題

体力が \(E_i\) 回復する、と誤読して Bellman-Ford 法を試そうとしていました。 BFS を撃ちまくる富豪プレイで通ります。

考察成功の後もバグが取れず、あきまへんな……。

E 問題

全包囲木 DP として解きたかったのですが、ライブラリがバグっていました。やはりテストを書いて CI/CD を動かす必要があります。

入出力

cojna/iota の PrimParser を読み、 StateT ベースのパーサを実装しました。

ベンチマーク

ベンチマーク代わりに Library Checker の Many A + B を解きました。大量の \(A_i + B_i\) を求める問題です。提出一覧がこちら:

主な学びは次のとおりです:

1. 入力処理には ByteString を使った方が圧倒的に速い (TLE 解消)
   
2. 出力に Builder を使うと速い (-270 ms)
   
3. 入力に BS.getContents を使うと僅かに速い (-25 ms)
   
4. PrimParser (cojna/iota) の入力処理は速い (-164 ms)
   

PrimParser の内部では、 ByteString をバイト単位で読んでいます。シンプルな内容ながら、 UnboxedTuples に染まっているため難解です。

StateT ベースのパーサ

僕は StateT ベースの単純なパーサを使うことにしました。最小構成は以下の形です:

runIO :: StateT BS.ByteString IO a -> IO a
runIO = (BS.getContents >>=) . evalStateT

int' :: (MonadState BS.ByteString m) => m Int
int' = state $ fromJust . BS.readInt . BS.dropWhile isSpace

main :: IO ()
main = runIO $ do
  {- .. -}

入力の分離

main 関数と solve 関数を分離すると、 solve 関数は標準入力以外にも使うことができます:

solve :: StateT BS.ByteString IO ()
solve = {- .. -}

main :: IO ()
main = runIO solve

ghci> -- 文字列リテラルを入力とする
ghci> evalStateT solve $ BS.pack "test input"
ghci> -- ファイル内容を入力とする
ghci> evalStateT solve =<< BS.readFile "test-case.in"

入力処理の柔軟性

使用例です。憧れの (,) <$> int <*> int が書けます:

main :: IO ()
main = runIO $ do
  (!a, !t) <- (,) <$> int' <*> int'
  liftIO $ print $ 5 * a + t - 1

int1 = pred <$> int とすれば、 1-based index から 0-based index への変換も自然に行えます:

main :: IO ()
main = runIO $ do
  -- t は 0-based index に変換して読む
  (!a, !t) <- (,) <$> int' <*> int1'
  liftIO $ print $ 5 * a + t

StateT を使ったおかげで、入力をちょっとずつ読むのが得意です。行単位の読み出し (getLine) に拘束されません:

-- q 個のクエリをパースする例
qs <- U.replicateM q $ int' >>= \case
  -- クエリ 1 は 3-tuple
  1 -> (1 :: Int,,) <$> int' <*> int'
  -- クエリ 2 は 2-tuple
  2 -> (2,,-1) <$> int'

print

runIO 以下では、 print は liftIO . print の形で呼び出す必要があります。

MonadIO を使った print 関数を自作した場合、 liftIO 無しで呼び出しできます。また出力に bytestring の Builder を使うと、多少高速になります。

putBSB :: (MonadIO m) => BSB.Builder -> m ()
putBSB = liftIO . BSB.hPutBuilder stdout

class ShowBSB a where
  showBSB :: a -> BSB.Builder

printBSB :: (ShowBSB a, MonadIO m) => a -> m ()
printBSB = putBSB . (<> BSB.char7 '\n') . showBSB

main :: IO ()
main = runIO $ do
  (!a, !t) <- (,) <$> int' <*> int'
  printBSB $ 5 * a + t

インタラクティブ問題

BS.getContents を実行すると制御が帰って来ませんから、行単位で読めば良い気がします。ごちゃつきますが……:

main :: IO ()
main = do
  (!a, !t) <- evalState ((,) <$> int' <*> int1') <$> BS.getLine
  {- .. -}

以上、 cojna さんや gksato さんのスタイルに迫って来たかと思います。これで悔いの無い所までやり込んだ手応えがあります。

Builder の中身？

ByteString Builder の中身が気になっています。 Data.ByteString.Builder.Internal を見ると、なんとなく差分リストが思い起こされる見た目です。

newtype Builder = Builder (forall r. BuildStep r -> BuildStep r)