HaskellでABC427を解く

はじめに

Bではまり惨敗でした。

A問題

文字数は奇数とわかっているので真ん中以外の前後を取り出し繋げれば良い

A

main = do
  s <- getLine
  let len_2 = length s `div` 2
  let hs = take len_2 s
  let ts = drop (len_2+1) s
  putStrLn $ hs ++ ts

A問題提出

B問題

最初に思いついたのが A n = A (n-1) + f ( A (n-1) ) という再起方法でしたがこれだと計算が爆発して返ってきません。
メモ化する方法で対応しましたがメモ化にかなり時間溶かされました。

B

main = do
  n <- readLn :: IO Int
  let ans = as n
  print $ ans A.! n

as n = arr
  where
    arr = A.listArray (0,n) [a i | i <-[0..n]]
    a n
      | n == 0 = 1
      | n == 1 = f (a 0)
      | otherwise = a (n-1) + f (arr A.! (n-1))

f x = sum $ map digitToInt s
  where
    s = show x

B問題提出

次の項を次々に生成していくにはunfoldrがいいのは薄々勘付いてましたが時間内に実装できる自信がなくコンテスト中には採用しませんでした。
以下はコンテスト後の実装です。スッキリ書けてます。

B'

main = do
  n <- readLn :: IO Int
  print $ as !! n

as = 1 : unfoldr (\a -> Just (a, a + f a)) 1

f x = sum $ map digitToInt s
  where
    s = show x

C問題

辺を一つづつ減らしていって正しい２分グラフが得られてら終了というまさに解説動画でTLEになるとされている方針で実装しました。
コンテスト後30分後に完成し提出しましたがやはりTLEでした。
辺の数の最大は50ほどなのでO(50)で計算できると勘違いしてこの方針を採用してしまいましたが実際はO(2^50=1125899906842624)と
とても間に合うオーダーではありませんでした。

C問題提出(TLE)

解説動画通りに先に点の色を決めてしまって辺の左右が同じ色のものをカウントするようにすれば良い。確かにこのやり方だったらC問題という感じですね自分がやろうとしたやり方は重すぎました。あとDPTable作るのにreplicateMを使うといい感じになるのでこのやり方覚えておこう。

C'

main = do
  [n,m] <- readInts
  let bitDPTables = replicateM n [False,True] -- これでbit全探索用のテーブルができあがる

C問題提出(AC)

おわりに

今回はBにハマりCの考察が不十分で方針大間違いという結果に終わりました。