ABC 369

ABC 369 に参加しました。

Table 1: Diff 予想
問題 A 問題 B 問題 C 問題 D 問題 E 問題 F 問題
提出 AC AC AC AC AC -
予想 50 400 500 500 1,500 1,200
実際 28 62 323 621 1,301 1,618

A 問題

思い切って全探索する問題だと思いました。

import Data.List;main=interact$f.map read.words;f[a,b]=show$sum[1|x<-[-300..300],(==1).length.nub.(zipWith(-)<*>tail)$sort[a,b,x]]

B 問題

入力で 1 行内に整数と文字が混じっているのが厄介です。 words <$> getLine または、 StateT ベースのパーサがあれば合成 (?) できます:

!ass <- U.replicateM n $ (,) <$> int' <*> char'

(左手の位置, 右手の位置) を持って畳み込みで解けました。

let !res = U.foldl' step s0 as
      where
        s0 = (-1 :: Int, -1 :: Int, 0 :: Int)
        step (!l, !r, !acc) (!i, 'L')
          | l == -1 = (i, r, acc)
          | otherwise = (i, r, acc + abs (i - l))
        step (!l, !r, !acc) (!i, 'R')
          | r == -1 = (l, i, acc)
          | otherwise = (l, i, acc + abs (i - r))

左手と右手は独立した問題なので、実装の共通化もできるようです。

C 問題

苦戦しました。差を取れば素直に RLE (run-length encoding) にできたようです。

Union-Find でも同じようなことができます。なるほど:

C みたいな問題はこんな感じに UF で繋ぐとクソ楽にできる pic.twitter.com/xmcUTBkSCH

— あちゃぴ🍋 (@achapi_kyopuro) August 31, 2024

D 問題

素直な DP です。畳み込みで解けます。

let (!r1, !r2) = U.foldl' step s0 xs
      where
        s0 = ((-1) :: Int, 0 :: Int)
        step (!accOdd, !accEven) x = dbgId (accOdd', accEven')
          where
            accOdd' = max accOdd (accEven + x)
            accEven'
              | accOdd == -1 = 0
              | otherwise = max accEven (accOdd + 2 * x)
 printBSB $ max r1 r2

E 問題

整理すると 短いコードになりました 。

学びの多い問題でした。

Floyd–Warshall vs 全頂点 Dijkstra

計算量は \(O(V^3)\) vs \(O(V(E+V)\log V)\) で Dijkstra の方が小さい はず です。実際は、同程度の速さになりました。案外 Floyd–Warshall の方が無難で良さそう です。

盆栽要素

ライブラリを整理しました。

F 問題

LIS + 経路復元の問題でした。最大値と共に親頂点の位置を記録します。最大値が更新される度に、経路復元用 Map が持つ親の位置を更新します。

出力は Bulider を使うのが計算量の観点で無難です。

Misc