AtCoder Beginner Contest 334 振り返り

flower

2023年12月24日 07:04

クリスマスイブですが、早速振り返っていきます！

結果

CがむずくてWAでした。Xで他の人の投稿見る感じ、今回はB, Cがかなり難しかったみたいです。そのためか、2完にもかかわらずレーティングが向上しました。

各問題の振り返り

A - Christmas Present

比較してputStrLnするだけです。

main :: IO ()
main = do
  (b, g) <- readPairInt

  putStrLn $ if b > g then "Bat" else "Glove"

B - Christmas Trees

結構難しかった…
要約するとL, Rの2点間の距離をmで分割するだけの問題ではあるのですが、割り切れない場合のスタート地点とゴール地点をどうするかがミソでした。
以下のようにLとA, RとAをmで割った余り分スタート、ゴール地点から左にずらすことで、mで割り切れるように調整します。

スタート地点
- ツリーの基準点Aとスタート地点Lの差分をツリーを置く感覚mで割って
  - 割り切れる場合: スタート地点はL
  - 割り切れない場合: スタート地点は L + m - 余り
ゴール地点
- 地点Rから、Rとツリーの基準Aを引いてmで割った余りを引く

あとはスタート地点、ゴール地点をmで割って1を加えるだけです。

main :: IO ()
main = do
  [a, m, l, r] <- readInputIntList

  print $ solve a m l r

solve :: Int -> Int -> Int -> Int -> Int
solve a m l r =
  let start = if (l - a) `mod` m == 0 then l else l + m - ((l - a) `mod` m)
      end = r - (r - a) `mod` m
   in if start > r
        then 0
        else (end - start) `div` m + 1

C - Socks 2

問題: https://atcoder.jp/contests/abc334/tasks/abc334_c
回答(WA): https://atcoder.jp/contests/abc334/submissions/48796577
- (upsolved): https://atcoder.jp/contests/abc334/submissions/48809052

ソックスに数が割り当てられていて、ソックスが1つ欠けているもの同士を組み合わせて数の差の総和が最小になるようにする問題です。結局解けずにWAとなってしまいました。(Xを見たところ結構難しいとの声がよく見られました。)

問題を解いている時、おそらく以下の2つがポイントかなと判断しました。

ソックスの個数が偶数か奇数かで計算が変わること
奇数の場合、余りのソックスをどれにするかで計算結果が変わること

で、

ソックスが偶数の場合
- 奇数番目、偶数番目でソックスのペアを作って差を計算すればいい
ソックスが奇数の場合
- ソックスの隣同士の差分を取って、さらにその差分の奇数・偶数番目の差異をとり、小さい方を取ればいけるんじゃないか？（よくわかってない）

という方法を取りました。（今見るとソックスが奇数の場合の解き方意味不明すぎる）
で、これをソースに落とし込むとこんな感じです。

main :: IO ()
main = do
  [_, k] <- readInputIntList
  as <- readInputIntList

  print $ if even k then solveEvens as else solveOdds as

solveEvens :: Num a => [a] -> a
solveEvens as = sum $ zipWith (-) evens odds
  where
    odds = map fst $ filter (odd . snd) $ zip as [1 ..]
    evens = map fst $ filter (even . snd) $ zip as [1 ..]

solveOdds :: (Ord a, Num a) => [a] -> a
solveOdds as = sum $ zipWith min odds evens
  where
    diff = zipWith (-) (tail as) as
    odds = map fst $ filter (odd . snd) $ zip diff [1 ..]
    evens = map fst $ filter (even . snd) $ zip diff [1 ..]

まあ当然、ダメでした。

で、解説を見たところ

先頭から順に組にして行ったときの奇妙さの総和を累積和として求め、末尾からの累積和も同様に求めておくことで、全体でO(N) で本問題を解くことができます。

https://atcoder.jp/contests/abc334/editorial/8983

なるほどー！となりました。しかし、末尾からの累積和をどのように解くかがいまいちわかりません。
それで、他の方の回答を見てみるとこれ(https://atcoder.jp/contests/abc334/submissions/48803187)がわかりやすくて、「chunksOf関数を使って2つづつ取り出しながらscanrで右scanを行う」という方法で計算していました。
ここで、chunksOfとscanrについて簡単に解説すると、

chunksOfは、引数に指定した数の分をchunkにして取り出す関数で、配列に適用する場合のシグネチャは以下の通りとなります。

chunksOf :: Int -> [e] -> [[e]]

一つ目の引数にchunkのサイズを、二つ目に対象の配列を取ります。ドキュメント(https://hackage.haskell.org/package/split-0.2.4/docs/Data-List-Split.html#v:chunksOf) から例を引用すると、以下の様に利用できることがわかります。ちなみに使う場合は事前にsplitパッケージの追加が必要です。

>>> chunksOf 3 [1..12]
[[1,2,3],[4,5,6],[7,8,9],[10,11,12]]

で、scanrはどのようなものかというと、これは右からscan指定く関数で、シグネチャは以下の通りとなります。(scanrは基本的な関数かもですが、自分がわかってないので解説)

scanr :: (a -> b -> b) -> b -> [a] -> [b]

こちらもドキュメント(https://hackage.haskell.org/package/base-4.19.0.0/docs/Prelude.html#v:scanr) から実用例を持ってくると以下の様に使えます。(こっちはパッケージの追加は不要です。)
対象リストの末尾から計算されていて、結果も末尾が初期値になって手前に向かって計算結果が格納されていることがわかると思います。

>>> scanr (+) 0 [1..4]
[10,9,7,4,0]

この2つを使うと、末尾からchunkを2つづつ取って差分の累積和を取っていく計算を以下の様に書くことができます。

let suff = L.scanr (+) 0 $ map (\[a, b] -> b - a) $ chunksOf 2 (tail as)

これを利用して、ソックスの個数が奇数の場合は以下の様に計算できます。

let pre = L.scanl' (+) 0 $ map (\[a, b] -> b - a) $ chunksOf 2 (init as)
    suff = L.scanr (+) 0 $ map (\[a, b] -> b - a) $ chunksOf 2 (tail as)
 in minimum $ zipWith (+) pre suff

ソックスの個数が偶数の場合も、chunksOfを使うと以下の様にスッキリ書くことができるので

sum $ map (\[a, b] -> b - a) $ chunksOf 2 as

これを合わせると、正解を求める関数は以下の様に書くことができます。

solve :: (Integral a1, Ord a2, Num a2) => a1 -> [a2] -> a2
solve k as
  | even k = sum $ map (\[a, b] -> b - a) $ chunksOf 2 as
  | otherwise =
      let pre = L.scanl' (+) 0 $ map (\[a, b] -> b - a) $ chunksOf 2 (init as)
          suff = L.scanr (+) 0 $ map (\[a, b] -> b - a) $ chunksOf 2 (tail as)
       in minimum $ zipWith (+) pre suff

改めて、全体像は以下の様になります。

main :: IO ()
main = do
  [_, k] <- readInputIntList
  as <- readInputIntList

  print $ solve k as

solve :: (Integral a1, Ord a2, Num a2) => a1 -> [a2] -> a2
solve k as
  | even k = sum $ map (\[a, b] -> b - a) $ chunksOf 2 as
  | otherwise =
      let pre = L.scanl' (+) 0 $ map (\[a, b] -> b - a) $ chunksOf 2 (init as)
          suff = L.scanr (+) 0 $ map (\[a, b] -> b - a) $ chunksOf 2 (tail as)
       in minimum $ zipWith (+) pre suff

全体を振り返って

今年最後のAtCoderでしたが、今回は結構難し目だった様です。
結果からすると2完でしたが、おかげでレーティング下がらず安心しました(笑)
来年までにとりあえず、以下のことをやっておきたいと思ってます。

実践プロパティベーステストを読破して要領を掴んでおく
https://zenn.dev/toyboot4e/books/seriously-haskell を読んでAtCoderへの準備をしっかりやっておく

今年はAtCoder初めたばっかりなのとHaskellが不慣れなこともあって苦戦しましたが、来年は飛躍の年にしたいと思います！
そして今年は本当にいろんな方にお世話になりました。この場を借りてお礼申し上げます。これだけでもHaskellでAtCoder初めて本当に良かったと思います。どうぞ来年もよろしくお願いいたします。
それでは、良いお年を！！

この記事が気に入ったらサポートをしてみませんか？