AtCoder Beginner Contest 358 振り返り

ABC358の振り返りです。

## 結果

A,B,Cの3完でした。Dもいけそうだったからちょっと悔しい

![スクリーンショット 2024-06-22 18.08.43.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/eef0890f-211d-e39b-e20e-dab899c65666.png)

## 解説

### A問題

- [問題](https://atcoder.jp/contests/abc358/tasks/abc358_a)
- [回答](https://atcoder.jp/contests/abc358/submissions/54566149)

`getLine`を`words`して比較します。

```haskell
main :: IO ()
main =
  do
    [s, t] <- words <$> getLine
    putStrLn $ if s == "AtCoder" && t == "Land" then "Yes" else "No"
```

### B問題

- [問題文](https://atcoder.jp/contests/abc358/tasks/abc358_b)
- [自分の回答](https://atcoder.jp/contests/abc358/submissions/54581656)

`scanl'`をつかって、現在の時間と`Ti`を比較して畳み込みをしていきます。

```haskell
main :: IO ()
main = do
  [_, a] <- readInputInts
  tn <- readInputInts

  let ans = L.scanl' (\acc t -> if acc > t then acc + a else t + a) 0 tn

  putStrLn $ L.intercalate "\n" $ map show $ tail ans
```

### C問題

- [問題文](https://atcoder.jp/contests/abc358/tasks/abc358_c)
- [回答1](https://atcoder.jp/contests/abc358/submissions/54595053)

zip全探索を使います。全てのbitが1になっている状態を用意しておき、`S1, S2, ..,Sn`の各組み合わせのbitの論理和と同値のもので`filter`します。その中で、最も要素数が少ない値が答えになります。

まずはすべてのbitが1になっている値を用意しておきます。
これが全て選択された状態になります。

```haskell
let m' = 1 `shiftL` m - 1
```

次に、`S1,S2,..,Sn`をbitに変換します。`o`である場合は`1`,`x`の場合は`2`にします。これは以下の様に表現できます。これを`map`して、すべてのSをbitにしておきます。

```haskell
(L.foldl' (\(acc :: Int) s -> if s == 'o' then acc `shiftL` 1 .|. 1 else acc `shiftL` 1) 0)
```

`subsequences`を使って、すべて組み合わせをリストにしておきます。先頭が`[]`なので、`tail`で除去しておきます。

```haskell
tail $ subsequences ssn'
```

その後に`foldl1`をつかって、各組み合わせの論理和をとります。これとすべて選択された値`m'`を比較し、一致する値で`filter`します。これが求める結果(全種類のポップコーンを食べた組み合わせの配列)になります。

```haskell
L.filter (\ss' -> L.foldl1 (.|.) ss' == m') $ tail $ subsequences ssn'
```

filterした結果には、全ポップコーンを選択した組み合わせのリストが入ったリストになっています。ですので、各組み合わせの長さを`map`で取得し、その中から最も小さい値を取得すればそれが答えになります。

```haskell
print $ L.minimum $ map L.length $ L.filter (\ss' -> L.foldl1 (.|.) ss' == m') $ tail $ subsequences ssn'
```

全体のコードは以下の通りです。

```haskell
main :: IO ()
main = do
  [n, m] <- readInputInts
  ssn <- replicateM n getLine

  let m' = 1 `shiftL` m - 1

  let ssn' = L.map (L.foldl' (\(acc :: Int) s -> if s == 'o' then acc `shiftL` 1 .|. 1 else acc `shiftL` 1) 0) ssn
  print $ L.minimum $ map L.length $ L.filter (\ss' -> L.foldl1 (.|.) ss' == m') $ tail $ subsequences ssn'
```

### D問題(upsolved)

- [問題](https://atcoder.jp/contests/abc358/tasks/abc358_d)
- [回答](https://atcoder.jp/contests/abc358/submissions/54615897)

二分探索しようとしたり、`IntSet`を使ってWAになったりしてタイムオーバーでした。
`IntSet`は重複した値を一つにしてしまうので、今回の様な問題では使えません。(そういう時には、自作の`IntMultiSet`のようなものを使う様です。)

今回は`sort`して尺取り方で解けば解けます。haskellだと以下のようになります。

```haskell
main :: IO ()
main =
  do
    [n, m] <- readInputInts
    an <- L.sort <$> readInputInts
    bn <- L.sort <$> readInputInts

    print $ solve an bn

solve :: (Num a, Ord a) => [a] -> [a] -> a
solve an bn = go an bn 0
  where
    go _ [] res = res
    go [] _ _ = -1
    go (a : an') bn@(b : bn') res =
      if a >= b
        then go an' bn' $ res + a
        else go an' bn res
```

パターンマッチのあるhaskellだとあんまり苦労なく解ける問題だったと思います。多分Cの方が難しかった…

## 全体を振り返って

今回は調子よかったので、次もこの調子で頑張ります！できれば4完したい…！

## おまけ Rustの回答

- [問題A](https://atcoder.jp/contests/abc358/submissions/54655808)
- [問題B](https://atcoder.jp/contests/abc358/submissions/54676046)
- [問題C](https://atcoder.jp/contests/abc358/submissions/54701155)
- [問題D](https://atcoder.jp/contests/abc358/submissions/54725060)

ちなみに、D問題は以下の様に解くことができます。
rustのiteratorの現在位置は状態として保持されるのでこのような解き方ができる様です。

```rust
fn main() {
    input! {
        (n, m): (usize, usize),
        mut an: [usize; n],
        mut bm: [usize; m],
    }

    an.sort();
    bm.sort();

    let mut ans = 0;
    let mut a_iter = an.iter();

    for b in bm {
        if let Some(a) = a_iter.find(|&&a| a >= b) {
            ans += a;
        } else {
            println!("-1");
            return;
        }
    }

    println!("{ans}");
}

```