# ABC412
- [AtCoder Beginner Contest 412 - AtCoder](https://atcoder.jp/contests/abc412)
- ABCD 4完 (1201) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc412)
![[スクリーンショット 2025-06-29 12.12.08.png]]
ABC412 でした
- A (灰, 10) ··· 入力の2値を `<` で比較する
- B (灰, 41) ··· $S$ の大文字の手前の文字を全部集めて、$T$ と突合する
- C (茶, 607) ··· 直前に選んだドミノ $S_i$ に対し $2S_i$ 以下にある残りドミノのうち最大のものを選んでいく。多重集合を使うと実装が楽
- D (緑, 1186) ··· 条件を満たすグラフは連結成分がすべてサイクル (輪っか) になる。$N \leq 8$ しかないので、$_{28}C_{8}$ を全部試すのが簡単。その上で初期状態 $G$ と対称差を求める
今回は C 以降、難易度が高めだったと思います。
自分のレート帯にとっては E のハードルが高いので、D をどれだけ早く解けるか勝負でした。
D を 87:45 に通し、なんとか水色パフォーマンスは保ったものの、難しい解き方をしてしまい時間を浪費しました。
じっくり考察するともっと簡単な解法が幾つかあったのですが、最初に思いついた実装が面倒な方針に固執してしまいました。
とはいえ、ちゃんと解けたのは良かったです。
## [A - Task Failed Successfully](https://atcoder.jp/contests/abc412/tasks/abc412_a)
入力の 2値を `<` で比較し、成立するものの数を答えます。
```haskell
main :: IO ()
main = do
n <- getInt
vs <- replicateM n getTuple
let res = [i < j | (i, j) <- vs]
print $ countBy (== True) res
```
上の実装はタプルを一度分解して `<` で写像しています。
`uncurry` を使うと 2値タプルを 1値に結合して写像することができるので、こちらの方がより宣言的であります。
(いつも思いますが `uncurry` という名前、あまり良くない名前だと思います)
```haskell
main :: IO ()
main = do
n <- getInt
vs <- replicateM n getTuple
let ans = countBy (== True) $ map (uncurry (<)) vs
print ans
```
## [B - Precondition](https://atcoder.jp/contests/abc412/tasks/abc412_b)
$S$ の大文字のある一つ前にある文字が、全部 $T$ にあるか?
$S$ の大文字のある一つ前にある文字、を全部列挙して $T$ と突合すると良いですね。
$S$ から対象の文字を集めるのは `zip s (tail s)` のいつものイディオムとリスト内表表記を使うとスムーズに書けます。
```haskell
main :: IO ()
main = do
s <- getLine
t <- getLine
let xs = nubOrd' [a | (a, b) <- zip s (tail s), isUpper b]
res = [x `elem` t | x <- xs]
printYn $ and res
```
$S$ から集めた文字 $xs$ と $T$ の突合は「$xs$ が $T$ の部分集合かどうか?」を問われているので、以下のように書くとより宣言的。
本番ではさっとこれが思いつきませんでした。
```haskell
main :: IO ()
main = do
s <- getLine
t <- getLine
let xs = [a | (a, b) <- zip s (tail s), isUpper b]
ans = Set.fromList xs `Set.isSubsetOf` Set.fromList t
printYn ans
```
## [C - Giant Domino](https://atcoder.jp/contests/abc412/tasks/abc412_c)
直感的に貪欲だろうな、という問題。
ある $S_i$ をみているときに、残っているドミノの中から $2S_i$ 以下のドミノがあるかを見つける。その中で最も大きいものを選んでいく、とすれば最適な組み合わせになるでしょう。
まだ使ってないドミノを集合管理したい、直前に選んだドミノの $2S_i$ 以下のものを効率的に検索したい。
データ構造としては順序つき集合が良さそう、かつ、$S_i$ は値に被りがあるので IntMultiSet を使います。
`unfoldr` で残りドミノの集合、直前に選んだドミノ $S_i$ を状態に持ちながら再帰し、`lookupLE` で $2S_i$ 以下のもののうち最大のドミノを探します。
候補が見つからなかった、もしくは $S_i$ が $S_N$ を倒せる大きさになったらそこで再帰は終わり。
これで解けます。データ構造の選択が肝になる問題でした。
C で IntMultiSet はちょっとオーバーキルかなとやや躊躇したものの、そのまま進めて良かったです。
```haskell
t <- getInt
replicateM_ t $ do
_ <- getInt
ss <- getInts
let s1 = head ss
sn = last ss
ms0 = fromListMS $ tail (init ss)
res = unfoldr f (ms0, s1)
where
f (ms, si)
| si * 2 >= sn = Nothing
| otherwise = do
x <- lookupLEMS (si * 2) ms
return (x, (deleteMS x ms, x))
print
$ if lastDef s1 res * 2 >= sn
then 2 + length res
else -1
```
### 追記
たしかに! というわけで多重集合である必要はなく IntSet で大丈夫でした😉
```haskell
main :: IO ()
main = do
t <- getInt
replicateM_ t $ do
_ <- getInt
ss <- getInts
let s1 = head ss
sn = last ss
is0 = IS.fromList $ tail (init ss)
res = unfoldr f (is0, s1)
where
f (is, si)
| si * 2 >= sn = Nothing
| otherwise = do
x <- IS.lookupLE (si * 2) is
return (x, (IS.delete x is, x))
print
$ if lastDef s1 res * 2 >= sn
then 2 + length res
else -1
```
## [D - Make 2-Regular Graph](https://atcoder.jp/contests/abc412/tasks/abc412_d)
D 問題にしては結構難しい問題だと思いました。
ただし、$N \leq 8$ の特徴をうまく使うことで、公式回答にもあったとても簡単な解法に落とし込むこともできます。
まずはその簡単な解法から。
この問題は
1. 条件を満たすグラフの辺集合を全列挙する
2. グラフ $G$ の辺集合と、求めた辺集合の距離 (対称差) を求める
という 2 つのパートに分かれます。
まずは 1 から考えます。
操作後の条件はすべての頂点の出次数が $2$ ですが、これは要するに「連結成分がすべてサイクル (輪っか) になっているグラフ」です。
[ABC287 C - Path Graph?](https://atcoder.jp/contests/abc287/tasks/abc287_c) でパスグラフ (一直線になってるグラフ) かどうかの判定問題がありましたが、パスグラフすなわち一直線の場合は端っこの頂点以外の出次数が $2$ 。ここで端と端が結びつくとすべての頂点の出次数が $2$ になり、サイクルになります。
グラフがサイクルの場合、辺の数が必ず $N$ なります。
$N = 8$ のとき、辺のパターンは $_8C_2 = 28$ 通りしかありません。$28$ 通りの辺から、辺の数 $N = 8$ を選ぶ方法は $_{28}C_{8} = 3108105$ 通りで $10^6$ に収まります。
というわけで、$_{28}C_{8}$ 通りのグラフを全部作って、それぞれのグラフが条件を満たしているか ··· 出次数が全部 $2$ か? を調べることで条件を満たす辺集合分かります。
2 の対称差を求めるのは、包除原理的に考えて操作前 $M$ 個、操作後 $N$ 個の辺があり、その両者に被ってる辺の数 $\times 2$ を引く、として求めることができます。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m getTuple
let s = Set.fromList [if u < v then (u, v) else (v, u) | (u, v) <- uvs]
-- 条件を満たすグラフの辺集合を全探索
ts =
[ Set.fromList [if u < v then (u, v) else (v, u) | (u, v) <- uvs']
| uvs' <- combinations n (comb2 [1 .. n]),
let g = amap length $ graph2 (1, n) uvs',
all (== 2) g
]
-- 2つのグラフの距離 (対称差) を求める
res = [n + m - 2 * Set.size (Set.intersection s t) | t <- ts]
print $ minimum res
```
対称差を求めるのは、対称差の数ではなく対称差の集合そのものを求めることもできます。
こちらを使う方が、汎用的でいいかもしれません。`symDiff` という二つの Set の対称差を求める関数を作りました。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m getTuple
let s = Set.fromList [if u < v then (u, v) else (v, u) | (u, v) <- uvs]
-- 条件を満たすグラフの辺集合を全探索
ts =
[ Set.fromList [if u < v then (u, v) else (v, u) | (u, v) <- uvs']
| uvs' <- combinations n (comb2 [1 .. n]),
let g = amap length $ graph2 (1, n) uvs',
all (== 2) g
]
-- -- 2つのグラフの距離 (対称差) を求める
res = [Set.size (symDiff s t) | t <- ts]
print $ minimum res
symDiff :: (Ord a) => Set.Set a -> Set.Set a -> Set.Set a
symDiff s t = (s `Set.difference` t) `Set.union` (t `Set.difference` s)
```
対称差を求めるのは他にも、二つの辺集合をそれぞれビット集合に変換して `popCount (xor s t)` で対称差を求めるテクニック (典型) などもあります。
ここまでが、より簡単な解法です。
頂点が $8$ しかないし辺の数が限定されているなら、$_{28}C_n$ を`combinations` で全パターン列挙すればいいじゃん、というのは [ABC328 E - Modulo MST](https://atcoder.jp/contests/abc328/tasks/abc328_e) と同じでした。
そこに気がつけなかったのは悔しい。
もとい、1. に関して本番で私がやったのは DFS で「頂点が $N$ 個あるとき長さ 3 以上のサイクルを$1$ つ以上複数個作る全パターンを試す」というものでした。
自己ループも多重辺も許されないので、サイクル長は最低でも $3$ になります。それを `combinations` と `permutations` を使って全部試すという力業です。
$N \leq 8$ なので、計算量は真面目に計算しなくてもいけるだろうと踏んで、ゴリ押し。実装に時間がかかって 60 分くらい使ってしまいました。
```haskell
resolve n = dfs [1 .. n]
where
dfs [] = [[]]
dfs vs =
let v = minimum vs
vs' = delete v vs
in concat
[ [zip ws (tail ws `snoc` v) ++ acc | acc <- dfs (vs \\ ws)]
| k <- [3 .. length vs],
us <- combinations (k - 1) vs',
us' <- permutations us,
let ws = v : us',
ws !! 1 < ws !! (k - 1)
]
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m getTuple
let s = Set.fromList [if u < v then (u, v) else (v, u) | (u, v) <- uvs]
-- 条件を満たすグラフの辺集合を全探索
ts =
[ Set.fromList [if u < v then (u, v) else (v, u) | (u, v) <- uvs']
| uvs' <- resolve n
]
-- -- 2つのグラフの距離 (対称差) を求める
res = [Set.size (symDiff s t) | t <- ts]
print $ minimum res
-- | 2集合の対称差 (symmetric difference)
symDiff :: (Ord a) => Set.Set a -> Set.Set a -> Set.Set a
symDiff s t = (s `Set.difference` t) `Set.union` (t `Set.difference` s)
```