ABC 348
ABC 348 に参加しました。
A 問題
cojna さんの提出 が痺れます。 Shortest もシンプルで凄い。
B 問題
最小・最大を読み間違えており、なかなか大変な問題だと思っていました。
実装のコツは、
- 小数の精度不足を恐れ、距離の 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 (リスト) | getLine |
String (n 回出力) |
TLE (5,000 ms 超え) |
| 提出 2 | BS.getLine |
String (n 回出力) |
593 ms |
| 提出 3 | BS.getLine |
Builder (1 回出力) |
326 ms |
提出 4 (StateT) |
BS.getContents |
Builder (1 回出力) |
301 ms |
提出 5 (PrimParser) |
PrimParser |
Builder (1 回出力) |
137 ms |
主な学びは次のとおりです:
- 入力処理には
ByteStringを使った方が圧倒的に速い (TLE 解消) - 出力に
Builderを使うと速い (-270 ms) - 入力に
BS.getContentsを使うと僅かに速い (-25 ms) 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)