ミラティブ プログラミングコンテスト2025（AtCoder Beginner Contest 414）に参加したので振り返り。
今回はABCの3完。Dも考察は問題なかったが、リストのソートの遅さに起因するTLEに泣いた。。。
A - Streamer Takahashi
\(X_i \le L\) かつ \(R \le Y_i\) な \((X_i,Y_i)\) の個数を数えればよい。
main :: IO ()
main = do
(n,l,r) <- int3
xys <- int2list n
let result = filter (\(x,y) -> x <= l && r <= y) xys
print $ length resultB - String Too Long
問題文の通り、文字列を復元しつつ、復元した長さが 100文字を超えたら "Too Long" を出力するようにすれば良い。
Either l r モナドを使うと、100文字を超えた場合に計算を打ち切ることができ効率的。
main :: IO ()
main = do
n <- val ucInt
cls <- map (\[c,l] -> (head $ BS.unpack c, fst $ fromJust $ BS.readInt l)) <$> list2 n ucBS
putStrLn $ solve2 cls
solve :: [(Char,Int)] -> String
solve cls = case foldlM f (0,"") cls of
Left x -> x
Right (_,x) -> x
where f :: (Int,String) -> (Char, Int) -> Either String (Int, String)
f (acc,lr) (c,l) = if acc + l > 100
then Left "Too Long"
else Right (acc + l, lr <> replicate l c)コンテスト中は foldlM ではなく foldl' で実装していた。この場合は最後まで計算してしまう。
solve :: [(Char,Int)] -> String
solve cls = fromEither $ snd $ foldl' f (0,Right "") cls
where f :: (Int, Either String String) -> (Char, Int) -> (Int, Either String String)
f (acc,lr) (c,l) = case lr of
Left _ -> (acc,lr)
Right x -> if acc + l > 100
then (acc + l, Left "Too Long")
else (acc + l, Right $ x <> replicate l c)遅延評価に任せるのが一番簡単だと思う。
solve :: [(Char,Int)] -> String
solve cls = let (as,bs) = L.splitAt 100 . concatMap (\(c,l) -> replicate l c) $ cls
in if not (null bs) then "Too Long" else asC - Palindromic in Both Bases
\(10\) 進数と \(A\) 進数が両方とも回文数になる数になにか特徴があるのかと思ったが、そういったものは思いつかなかった。 なので、まず \(10\) 進数の回文数を全部列挙し、それぞれについて \(A\) 進数でも回文数になっているかを確認する方針にした。
\(10\) 進数の回文数を作る処理について。 まず \(1 \le k\) なる \(k\) を各桁の数字からなるリスト \(L_k\) に変換する。 その後、 \(L_k\) と \(L_k\) を反転したリスト、もしくは \(L_k\) を反転し先頭を削ったリストを結合すれば、 \(10\) 進数の回文が得られる。 \(N\) の制約が \(1 \le N \le 10^{12}\) なので、最大でも \(k \le 10^6\) となり、十分間に合う。
\(A\) 進数で回文数かの確認は、 \(10\) 進数のときと同じ要領で数をリストに直し、 reverse して同一かを見れば良い。
main :: IO ()
main = do
a <- val ucInt
n <- val ucInt
print $ solve a n
solve :: Int -> Int -> Int
solve a n = sum $ filter (<= n) $ concat $ do
k <- [1..10^6-1]
let cand = endig 10 k
cand1 = reverse cand
cand2 = tail cand1
return $ filter (\z -> let y = endig a z in y == reverse y) $ map (dedig 10) [cand <> cand1, cand <> cand2]
endig :: Integral a => a -> a -> [a]
endig !p = reverse . L.unfoldr (\ !k -> if k == 0 then Nothing else Just (k`mod`p, k`div`p))
dedig :: Integral a => a -> [a] -> a
dedig !p = foldl' (\acc x -> acc * p + x) 0ちなみにコンテスト中、数をリストに直す・リストを数に直す処理を show / read 使用して実装していたが、これはとても遅い。
今回は制限時間が3秒なので助かった（コンテスト時の実行時間は約2.7秒）。
ローカルで実行していてもとても遅く、提出してもTLEになるだろうと思って色々実装を見直していたが、
あまり意味はなかった（ show / read でも遅いながらに通るからね）。
随分と時間を食ってしまって残念。。。
solve :: Int -> Int -> Int
solve a n = sum $ filter (<= n) $ concat $ do
x <- [1..10^6-1]
let cand = show x
cand1 = reverse cand
cand2 = tail cand1
return $ filter (\z -> let y = endig a z in y == reverse y) $ map (read @Int) [cand <> cand1, cand <> cand2]D - Transmission Mission
状況を掴むためにまず手元で実験してみる。
まず、家の位置は昇順に並んでいると仮定してよく、同じ位置に家があっても電波強度に寄与しない。 また、家同士はできるだけ密集していたほうが、電波強度の合計は小さくできそうである。 更に、1つの基地局がカバーする家々に注目すると、電波強度は家々の中で最も離れている家同士の距離に等しい。
この観察から、家同士の距離を降順に並べ、先頭から \(M-1\) 個取り除いた残りの和が、求める電波強度の最小値になると考えられる。
当初、以下のようなコードを提出しTLEとなってしまった。
main :: IO ()
main = do
(n,m) <- int2
as <- nubOrd . L.sort <$> list1 ucInt
let dist = drop (m-1) $ L.sortOn Down $ zipWith (-) (tail as) as
print $ sum dist結局TLEが解消せず、コンテスト中はD問題を通せなかった。
敗因は2つ。
- 根本原因は、遅いリストのソートを使っていたこと。
nubOrd（もしくはnubInt）を使用していたこと。
今回は \(1 \le N \le 5 \times 10^5\) という制約で、これだとリストのソートでは間に合わないっぽい（ほんとかな・・・？）。
また nubOrd の処理も遅く、これも足を引っ張っていた（ nubInt にしても変わらず）。
家の位置について nubOrd を実行する代わりに、家同士の距離について値が \(0\) の要素を取り除くようにして、なんとか1.9秒台でコンテスト後AC。
リストではなく、 Vector をソートするように変更したものが以下。これで170ms程度に改善した。
main :: IO ()
main = do
(n,m) <- int2
as <- vSort <$> vector n ucInt
let dist = VU.drop (m-1) $ vSortOn Down $ VU.filter (/=0) $ VU.zipWith (-) (VU.tail as) as
print $ VU.sum distちなみに
vSort :: (Ord a, VG.Vector v a) => v a -> v a
vSort = VG.modify $ VAI.sortBy compareであるが、これを
vSort :: (Ord a, VG.Vector v a) => v a -> v a
vSort = VG.modify VAI.sortとすると、とても遅くなる1。
感想
B問題で、コンテスト中は思いつかなかったが、 Either l r モナドを使えばモナドの力で早期リターンが可能になる。
Right に通常の値、 Left に早期リターン時の値を入れておくパターンはそれなりに有用だと思うので、覚えておこう。
Cは回文用のリストを作成する処理が思い浮かばず、無理やり show / read で処理してしまった。。。
あまりに遅いと、サンプル問題でACしてても提出できないので、今度から桁ごとの数字を見るときは、上で実装したような関数を使おう。
Dについては、リストのソートを使っていたのが敗因。今までリストのソートでTLEになったことがなかったので、非常に悔しい。。。
今度から、ソートが必要な場面では Vector でソートするようにしよう。
また nubOrd / nubInt もめちゃめちゃ遅いので、できるだけ使わないようにしよう（今回みたいに filter など他関数で代用できないか考える）。
そろそろ4完をコンスタントに出したい。。。
https://zenn.dev/toyboot4e/books/seriously-haskell/viewer/2-4-1-vector#%E3%82%BD%E3%83%BC%E3%83%88 この記事を最初見たときは、「そこまで遅くなるものか？？？」と思って
VAI.sortを使っていたが、VAI.sort版の提出とVAI.sortBy compare版の提出で実行時間が全く異なる。↩︎