ABC 347 / Fastest

ABC 347

ABC 347 に参加しました。

A 問題

map . filter の形で解きました。

main=interact$unwords.((\k->map(show.(`div`k)).filter((==0).(`mod`k)))<$>head<*>tail).tail.map read.words

B 問題

(l, r) 区間を全探索することで連続部分列 (スライス) を列挙します。 String や ByteString のスライスを得るには take len . drop l を使います。 vector だったらズバり slice 関数があります。

ユニークな連続部分列をカウントするためには、 length . nubSort とか Map.size . Map.fromList を使います。

C 問題

今日が何曜日であるかを適当に決めると、すべての予定日が連続した休日に収まります。そのため (`mod` (a + b)) で作った曜日の列を 2 週間分に倍加して、固定幅で走査しました。

たとえば以下の曜日に予定が入っている場合、

 0  3  9

予定一覧を 2 週間分に倍加して、

 0  3  9 10 13 19

幅 3 のウィンドウで見た時に、ウィンドウの含む日数が A 日以内のものがあるか調べます。ウィンドウの左右端の日数の差に注目すれば良いです:

 0  3  9 10 13 19
 <----->: 10 日
    <----->: 8 日
       <----->: 4 日

ところで長さ a + b の配列を作ると RE になって混乱しました。たぶん Heap exhausted; で死ぬために MLE にはなりません。メモリ使用量が異常に多かったことに注目するべきでした。

D 問題

算数で解けそうな問題ですが、あえて全探索に寄せて解法を考え始めます。うおおお！ (略)

E 問題

シミュレーション過程をメモしてみると、位置と時間の 2 軸が見えてきます。位置方向の和を一括処理するのは困難ですが、時間方向の和は一括処理できることに気付きます。

F 問題

DP だと思ったのですが、敷き詰める順番がトポロジカル順にならないですね……。解けません。問題ジャンルすら見えないようです。

類題は ABC 223 E - Placing Rectangles および ARC 074 A らしいです。

Misc

join

本日も cojna さんの影を追い、 join を学びました。配列の倍加などに利用できます。

ghci> import Control.Monad
ghci> join (++) [1,2,3]
[1,2,3,1,2,3]

join もしっかり ポイントフリー Haskell メモ — Avendia に載っていました。このページは時間が経てば立つほど真価を発揮しています。

Fastest

Dijkstra を貼っただけで Fastest が取れてしまいました。

穴場だと思うので、 fastest が欲しければおすすめです。 提出一覧

最小全域木 (MST)

Kruskal 法の実装が filterM でスッキリしました。 Buffer も unfoldrM も mayMaybeM も必要無いようです。なるほどな〜……

{-# INLINE collectMST #-}
collectMST :: (Ord w, U.Unbox w) => Int -> U.Vector (Vertex, Vertex, w) -> U.Vector (Vertex, Vertex, w)
collectMST nVerts edges = runST $ do
  uf <- newMUF nVerts
  flip U.filterM edges' $ \(!v1, !v2, !_) -> do
    -- 新しく unify した場合は @True@ を返却する
    unifyMUF uf v1 v2
  where
    edges' = U.modify (VAI.sortBy (comparing thd3)) edges

PrimParser が気になる

Haskell すきー星人最大の謎の 1 つ、 PrimParser の解読を始めました。入口はこれですね。

withByteString :: B.ByteString -> (a -> IO r) -> PrimParser a -> IO r
withByteString bs k f = case B.toForeignPtr bs of
  (fp, o, I# len#) -> do
    withForeignPtr (plusForeignPtr fp o) $ \(Ptr p#) -> do
      case runPrimParser# f (plusAddr# p# len#) p# of
        (# _, x #) -> k x

ByteString 中のバイト列に toForeignPtr でアクセスし、手動でパースする方針と見ました。 UnboxedTuples に染まっていて面食らいます。

ByteString の内側が ForeignPtr なのは謎です。 Quit using ForeignPtr in favor of ByteArray# #193 を見ると、 ByteString は FFI にも使用されるらしいので、そういうものかもしれません。