前回のABC振り返りです。
※前回の記事はこちら
https://qiita.com/flowerhill/items/70846a01bcbbebd03852
今回の結果
A,B 2完でした。ずっと横ばい
各問題の振り返り
A - Capitalized?
先頭が大文字 かつ 先頭以外が全て小文字で判定します。
module Main where
import Data.Char
main :: IO ()
main = do
s <- getLine
putStrLn $ if (isUpper . head) s && (all isLower . tail) s then "Yes" else "No"
C - Leftover Recipes
2種類の料理A, Bがあって、Aの料理を作るには材料iがAiグラム、Bの料理を作るには材料iがBiグラム必要になります。但し、Ai+Bi≤Qi でなければなりません。
この条件で、料理を作れる最大の数はいくつになるでしょう？という問題です。
正直解いてる時は全くわかりませんでした。実装してみたのですが重すぎるので提出もできず。
実際は全探索で解けるみたいです。(1≤N≤10なのでTLEにもならない)
この回答を参考に解いてみました。
https://atcoder.jp/contests/abc338/submissions/49706483
解き方としては、Aの料理を作る数を固定して、その値一つ一つに対してBの料理を作る数を計算していきます。
つまり、以下のような解き方になります。
- Aの料理を作る数のリストを作っておいて、そのリストの一つ一つに対してBの料理を作れる数を計算する
- その後、Aの料理を作れる数 + Bの料理を作れる数を計算する。
- するとAの料理を作る数とBの料理を作る数の合計のリストができるので、その最大値が答えになる。
料理を作る数は、それぞれ以下のようになります。
- Aの料理を作る数の最大値は
Qi / Ai - Bの料理を作る数の最大値は
Qi - (Ai * (Aの料理を作る数)) / Bi
但し、制約条件から0≤Ai≤10^6,0≤Bi≤10^6なので、割る数が0の時を考慮する必要があります。
0で割る時は大きい値を返すようにしておけば良いので、今回はmaxBoundを返すようにしました。(Maybeを使ってもできそうです。)
実装はこちらになります。
safeDiv :: Int -> Int -> Int
safeDiv _ 0 = maxBound
safeDiv q d = q `div` d
ここから、Aの料理を作る数を計算します。
Aの料理を作れる数のリストは以下のように求められます。
let !numAMax = VU.minimum $ VU.zipWith safeDiv qs as
minimumとしているのは、これがAの料理を作る最大値になるためです。(そうしないと、Qi≤Ai*(料理を作る数)となるAiが出てきてしまいます。)
ここで、あるAの料理を作る数に対するBの料理を作る数は、Aの料理を作る数をnとすると、
safeDiv (q - n * a) b
のように求められます。
これをAの料理を作る数に対して適用したいので、generateを使って以下のように書きます。
let !ans = VU.maximum $ VU.generate (numAMax + 1) $ \n -> (+ n) . VU.minimum $ VU.zipWith3 (f n) qs as bs
where
f n q a = safeDiv (q - a * n)
コードの全体像はこのような感じです。(!はBangPatternsによる正格評価です。1)
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TypeApplications #-}
module Main where
import qualified Data.ByteString.Char8 as BC
import Data.Char as C
import Data.Vector.Unboxed as VU
main :: IO ()
main = do
_ <- readLn @Int
!qs <- VU.unfoldr (BC.readInt . BC.dropWhile C.isSpace) <$> BC.getLine
!as <- VU.unfoldr (BC.readInt . BC.dropWhile C.isSpace) <$> BC.getLine
!bs <- VU.unfoldr (BC.readInt . BC.dropWhile C.isSpace) <$> BC.getLine
let !numAMax = VU.minimum $ VU.zipWith safeDiv qs as
let !ans = VU.maximum $ VU.generate (numAMax + 1) $ \n -> (+ n) . VU.minimum $ VU.zipWith3 (f n) qs as bs
where
f n q a = safeDiv (q - a * n)
print ans
safeDiv :: Int -> Int -> Int
safeDiv _ 0 = maxBound
safeDiv q d = q `div` d
全体を振り返って
今回C問題が全然解けず苦戦しました。片方を固定してもう片方を探索するという処理のイメージが掴めなかったのが原因です。
今回その実装方法がわかったので、次回以降でしっかり実装できるようにしていきたいです。
追記
C問題でMaybeを使うとこうなりました。
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TypeApplications #-}
module Main where
import qualified Data.ByteString.Char8 as BC
import Data.Char as C
import Data.Maybe (catMaybes)
import Data.Vector as V
main :: IO ()
main = do
_ <- readLn @Int
!qs <- V.unfoldr (BC.readInt . BC.dropWhile C.isSpace) <$> BC.getLine
!as <- V.unfoldr (BC.readInt . BC.dropWhile C.isSpace) <$> BC.getLine
!bs <- V.unfoldr (BC.readInt . BC.dropWhile C.isSpace) <$> BC.getLine
let !numAMax = V.minimum $ V.catMaybes $ V.zipWith safeDiv qs as
let !ans = V.maximum $ V.generate (numAMax + 1) $ \n -> (+ n) . V.minimum $ V.catMaybes $ V.zipWith3 (f n) qs as bs
where
f n q a = safeDiv (q - a * n)
print ans
safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv q d = Just $ q `div` d
実行時間は20ms -> 50msと結構増えてるのですが、これはVectorのcatMaybesの計算量がO(n)であることが原因だと思われます。