AtCoder Beginner Contest 338 振り返り

前回のABC振り返りです。

※前回の記事はこちら
https://qiita.com/flowerhill/items/70846a01bcbbebd03852

## 今回の結果

A,B 2完でした。ずっと横ばい

![スクリーンショット 2024-01-29 15.43.46.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/20777782-1c09-505d-37aa-683e47b98275.png)

![スクリーンショット 2024-01-29 15.44.39.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/12fc0fb8-337e-ca37-0ef1-08b2f379c087.png)

## 各問題の振り返り

### A - Capitalized?

- [問題文](https://atcoder.jp/contests/abc338/tasks/abc338_a)
- [自分の回答](https://atcoder.jp/contests/abc338/submissions/49705968)

先頭が大文字 かつ 先頭以外が全て小文字で判定します。

```haskell
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

- [問題文](https://atcoder.jp/contests/abc338/tasks/abc338_c)
- [自分の回答(upsolved)](https://atcoder.jp/contests/abc338/submissions/49774571)

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`を使ってもできそうです。)

実装はこちらになります。

```haskell
 safeDiv :: Int -> Int -> Int
 safeDiv _ 0 = maxBound
 safeDiv q d = q `div` d
```

ここから、Aの料理を作る数を計算します。
Aの料理を作れる数のリストは以下のように求められます。

```haskell
let !numAMax = VU.minimum $ VU.zipWith safeDiv qs as
```

`minimum`としているのは、これがAの料理を作る最大値になるためです。(そうしないと、`Qi≤Ai*(料理を作る数)`となるAiが出てきてしまいます。)

ここで、あるAの料理を作る数に対するBの料理を作る数は、Aの料理を作る数を`n`とすると、

```haskell
 safeDiv (q - n * a) b
```

のように求められます。

これをAの料理を作る数に対して適用したいので、`generate`を使って以下のように書きます。

```haskell
  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])
[^1]: 参考: https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/strict.html

```haskell
{-# 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`を使うとこうなりました。

```haskell
{-# 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](https://hackage.haskell.org/package/vector-0.13.1.0/docs/Data-Vector.html#v:catMaybes)の計算量が`O(n)`であることが原因だと思われます。