AtCoder Beginner Contest 371 振り返り

ABC371の振り返りです。久しぶりに書きます。

## 結果

A,Bの2完でした。今回むずかった

![スクリーンショット 2024-09-21 16.39.41.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/0cadc715-6f2c-3f98-d955-c6b2ea2ad361.png)

![スクリーンショット 2024-09-21 16.40.55.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/167729/6e5f2d28-492d-713f-76a3-7210afba2b2b.png)

## 解説

### A問題

- 問題
  - https://atcoder.jp/contests/abc371/tasks/abc371_a
- 回答
  - https://atcoder.jp/contests/abc371/submissions/57753432

初っ端から難しかったです。「これ真面目にかんがえちゃだめだ」と思って全パターン洗い出しました。
欲をかいて何度か真面目に解こうとしたので時間がかかってしまいました。

```haskell
main :: IO ()
main = do
  [sab, sac, sbc] <- words <$> getLine

  putStrLn $ case (sab, sac, sbc) of
    ("<", "<", "<") -> "B"
    (">", "<", "<") -> "A"
    (">", ">", "<") -> "C"
    (">", ">", ">") -> "B"
    ("<", ">", ">") -> "A"
    ("<", "<", ">") -> "C"
```

### B問題

- 問題
  - https://atcoder.jp/contests/abc371/tasks/abc371_b
- 回答
  - https://atcoder.jp/contests/abc371/submissions/57763978

こっちは難しくなかったです。最初に`False`のArrayをつくって、都度更新していきました。

```haskell
main :: IO ()
main = do
  [n, m] <- getInts
  abs <- replicateM m do
    [a, b] <- words <$> getLine
    return (read @Int a, b)

  let arr = listArray @UArray (1, n) $ replicate n False

  foldM_
    ( \acc (i, s) -> do
        if s == "M" && not (acc ! i)
          then do
            putStrLn "Yes"
            return $ acc // [(i, True)]
          else do
            putStrLn "No"
            return acc
    )
    arr
    abs
```

### C問題(upsolved)

- 問題
  - https://atcoder.jp/contests/abc371/tasks/abc371_c
- 回答
  - https://atcoder.jp/contests/abc371/submissions/57814605

これは難しかった…
問題を見て解けないやつだなと思って速攻で諦めました。

この問題のポイントは
- 頂点を固定した時、`G`と`H`が同型であることをどう判断するか？

で、これを判断するには以下の2つを考える必要があります。

1. GとHの頂点を固定した場合、同型でない辺をどう判断するか？
2. 問題文の定義に従う場合、Hが同じ番号の頂点をつないでいなくても同型になりうるが、これをどう判定するか？

1について何が言いたいかというと、たとえばGの頂点を `G1, G2, .. Gn`, Hの頂点を`H1, H2, .. Hn`とすると例えば

- `G1`と`G2`を繋ぐ辺が存在し、`H1とH2`を繋ぐ辺が存在しない
- `G4`と`G8`を繋ぐ辺が存在し、`H4とH8`を繋ぐ辺が存在する
- `G10`と`G15`を繋ぐ辺が存在せず、`H10とH15`を繋ぐ変が存在する

といったことをどう判断するかということです。
これは問題文から

```
GにはMG​本の辺があり、i本目 (1≤i≤MG​)の辺は頂点ui​と頂点viを結んでいます。
HにはMH​本の辺がありi本目(1≤i≤MH​)の辺は頂点ai​と頂点bi​を結んでいます。
```

とあることから、`accumArray`をつかって以下の様に求めます

```haskell
let g = accumArray @UArray (||) False ((1, 1), (n, n)) $ concat [[((u, v), True), ((v, u), True)] | u : v : _ <- uvs]
    h = accumArray @UArray (||) False ((1, 1), (n, n)) $ concat [[((a, b), True), ((b, a), True)] | a : b : _ <- abs]
```

こうすると、対応する頂点が繋がってる場合は`True`を、繋がっていない場合は`False`を返すarrayができます。ある頂点同士が繋がっているかどうかは

```haskell
g ! (i, j)
h ! (i, j)
```

だけで求められます。すごいぞarray。

次に

問題文の定義に従う場合、同じ番号の頂点をつないでいなくても同型になりうるが、これをどう判定するか？

ですが、これはグラフの頂点が Hi -> Hi' のような対応関係があった場合

- `G1`と`G2`を繋ぐ辺が存在し、`H1'とH2'`を繋ぐ辺が存在する
  - ただし、`H1' = H2, H2' = H3`
- `G4`と`G8`を繋ぐ辺が存在し、`H4'とH8'`を繋ぐ辺が存在する
  - ただし、`H4' = H8, H5' = H10`
- `G10`と`G15`を繋ぐ辺が存在せず、`H10'とH15'`を繋ぐ変が存在する
  - ただし、`H10' = H8, H15' = H5`

の様な時にも同型と言えてしまうわけです。（図示すると一発なのですが、面倒なのでここではやりません）

で、これを考慮すると、当然Hは全ての組み合わせで同型を考える必要があることになります。

じゃあこれをどう解くかと言うと、`permutations`を使います。

permutationsを使うと、以下のように配列の全ての組み合わせを求めることができます。

```haskell
ghci> import Data.List
ghci> permutations [1..3]
[[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]
```

これを使って、グラフの写像を書くと

```haskell
ps <- permutations [1 .. n]  -- リスト内包表記の中なので、こういう書き方になってる
let m = listArray @UArray (1, n) ps
```

として書くことができます。このように書くと、keyが写像後、valueが写像前として扱うことができるので

```haskell
[ g ! (i, j) == h ! mij
  | i <- [1 .. (n - 1)],
    let mi = m ! i,
    j <- [(i + 1) .. n],
    let mij = (mi, m ! j)
]
```

で同型の判断ができます。
愚直に全探索している形になりますが、ノード数が`1≤N≤8`なので、計算量的にも問題ありません。

で、問題で聞かれていることは

同型でない辺の金額を求め、その合計値を算出し、その中から最小値を求める

ことですから、このように書きます

```haskell
minimum
  [ sum
      [ if g ! (i, j) == h ! mij then 0 else aij ! mij
        | i <- [1 .. (n - 1)],
          let mi = m ! i,
          j <- [(i + 1) .. n],
          let mij = (mi, m ! j)
      ]
    | ps <- permutations [1 .. n],
      let m = listArray @UArray (1, n) ps
  ]
```

補足ですが、各辺同士の金額を求めるarrayは以下のように書いておきます。

```haskell
let ass1 = zipWith (++) (tail $ inits $ repeat 0) (ass ++ [[]])
    aij = listArray @UArray ((1, 1), (n, n)) $ concat $ zipWith (zipWith max) ass1 $ transpose ass1
```

わざわざこのようにしているのは、`A1,3`の金額と`A3,1`の金額が同じなので、これをarrayで取得できるようにしているためです。

全体のコードはこのようになります

```haskell
main :: IO ()
main = do
  n <- readLn @Int
  mg <- readLn @Int
  uvs <- replicateM mg getInts
  mh <- readLn @Int
  abs <- replicateM mh getInts
  ass <- replicateM (n - 1) getInts

  let ass1 = zipWith (++) (tail $ inits $ repeat 0) (ass ++ [[]])
      aij = listArray @UArray ((1, 1), (n, n)) $ concat $ zipWith (zipWith max) ass1 $ transpose ass1
      g = accumArray @UArray (||) False ((1, 1), (n, n)) $ concat [[((u, v), True), ((v, u), True)] | u : v : _ <- uvs]
      h = accumArray @UArray (||) False ((1, 1), (n, n)) $ concat [[((a, b), True), ((b, a), True)] | a : b : _ <- abs]

  print $
    minimum
      [ sum
          [ if g ! (i, j) == h ! mij then 0 else aij ! mij
            | i <- [1 .. (n - 1)],
              let mi = m ! i,
              j <- [(i + 1) .. n],
              let mij = (mi, m ! j)
          ]
        | ps <- permutations [1 .. n],
          let m = listArray @UArray (1, n) ps
      ]
```      

### D問題(upsolved)

- 問題
  - https://atcoder.jp/contests/abc371/tasks/abc371_d
- 回答
  - https://atcoder.jp/contests/abc371/submissions/57893405
  - https://atcoder.jp/contests/abc371/submissions/57873218

Cより簡単な問題です。
累積和を求めて、rからlを引くのですが、1個ポイントがあります。

```
−10^9≤X≤10^9
```

とXの範囲が大きいため、全ての要素を作って計算するとTLEになります。そのため、rとlに一番近い最右の位置をもとめるために二分探索を使う必要があります。(今回は二分探索使うの気づかず時間内に解けませんでした、、)

`IntMap`にちょうど`lookupLE`や`lookupLE`があったので、これを使うとこうなりました

```haskell
main :: IO ()
main = do
  n <- readLn @Int
  xs <- getInts
  ps <- getInts
  q <- readLn @Int
  lrs <- replicateM q getInts

  let xm = IM.fromAscList $ zip xs [1 .. n]
      pAccum = listArray @UArray (0, n) (scanl' (+) 0 ps)

  forM_ lrs \(l : r : _) -> do
    let r' = IM.lookupLE r xm
        l' = IM.lookupGE l xm

    print $
      if isNothing r' || isNothing l'
        then 0
        else pAccum IA.! (snd . fromJust) r' - pAccum IA.! ((snd . fromJust) l' - 1)
```

## 全体を振り返って

Cを飛ばしたのは正解だったのですが、二分探索に気づけなかったのは痛かったです。とはいえ、二分探索の使い方を学ぶ機会になりました。（境界値とか意外とめんどくさい。。）

## おまけ

#### Rustの回答

Dは`unwrap_or_else()`がべんりでした。

- 問題C
  - https://atcoder.jp/contests/abc371/submissions/57818410
- 問題D
  - https://atcoder.jp/contests/abc371/submissions/57935821
  - https://atcoder.jp/contests/abc371/submissions/57935882
  - https://atcoder.jp/contests/abc371/submissions/57935903

#### lower_bound, upper_boundについて

拾いものですが、参考になりました。ややこしいなと思っていたのですが半開区間だったのですね。
https://rsk0315.hatenablog.com/entry/2022/08/12/130515