# ABC332 振り返り
- [AtCoder Beginner Contest 332 - AtCoder](https://atcoder.jp/contests/abc332)
- 成績 ABC 3完 (521) [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc332)
![[スクリーンショット 2023-12-11 8.56.55.png]]
ABC332 でした。今回は奮わずでした。
失敗を振り返るのはなかなか大変ですが、こういう時こそ学びがあります。
B と C で沼ってしまい、その焦りで慌てて D の問題文を誤読しました。D の交換操作は隣の行/列しかできないという条件を読み間違えていることに気づかず 😅
- A ··· やるだけ。購入数 x 価格を計算して送料無料にならなければ送料足す
- B ··· 問題文通りに条件分岐する。マグからグラスに水を移すところは丁寧に
- C ··· 貪欲法。在庫管理して、足りなくなったら買う。選択したら購入した分も含めて在庫に戻る
- D ··· 交換操作は可換、順序は無視できる。行と列を別に考えてそれぞれのパターンを順列全探索。操作回数は転倒数
でした。
反省は残りましたが、おかげで自分が序盤でつまづくケースの原因がようやくはっきりと認識できました。次回は同じ失敗はしないと思います。
----
## [A - Online Shopping](https://atcoder.jp/contests/abc332/tasks/abc332_a)
これはやるだけ問題でした。購入した数と単価をかけて総計を出し、送料無料かどうかを判断する。
```haskell
main :: IO ()
main = do
[n, s, k] <- getInts
xs <- replicateM n getTuple
let x = sum $ map (\(p, q) -> p * q) xs
print $ if x >= s then x else x + k
```
----
## [B - Glass and Mug](https://atcoder.jp/contests/abc332/tasks/abc332_b)
沼ってしまいました。
条件分岐を問題文の通り素直にやって $K$ 回操作を行えば良いのですが、3つ目の条件
> マグカップが空になるかグラスが水で満たされるまで、マグカップからグラスに水を移す。
を考えていたら緊張も相まり混乱してしまいました。だんだん、どっちがグラスでどっちがマグかわからなくなってきて、焦りました😅
算数の問題で、グラスとマグの間を移動する水の量は差し引きで変わらない。それを丁寧に計算すれば良いです。
![[IMG_0298.jpeg]]
```haskell
f g m (glass, mag)
| glass == g = (0, mag)
| mag == 0 = (glass, m)
| otherwise = do
let d = min (g - glass) mag
(glass + d, mag - d)
main :: IO ()
main = do
[k, g, m] <- getInts
let (x, y) = foldl' (\acc _ -> f g m acc) (0, 0) [1 .. k]
putStrLn . unwords . map show $ [x, y]
```
----
## [C - T-shirts](https://atcoder.jp/contests/abc332/tasks/abc332_c)
同様にこちらも条件分岐の問題でした。
よく問題を読むと、着れるTシャツがなくなったらロゴ入りを買う。ロゴ入りTシャツの方が貴重なので無地Tシャツから先に消費するという貪欲法で良いことがわかります。
4つ状態管理しましたが、一つ要らなかったですね。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
s <- getLine
let xs@(_, _, a, b) = foldl' f (m, 0, m, 0) s
where
f :: (Int, Int, Int, Int) -> Char -> (Int, Int, Int, Int)
f (_, _, x, y) '0' = (x, y, x, y)
f (muji, logo, x, y) '1'
| muji == 0 && logo == 0 = (0, 0, x, y + 1)
| muji == 0 = (0, logo - 1, x, y)
| logo == 0 = (muji - 1, logo, x, y)
| otherwise = (muji - 1, logo, x, y)
f (muji, logo, x, y) '2'
| logo == 0 = (muji, 0, x, y + 1)
| otherwise = (muji, logo - 1, x, y)
f _ _ = error "!?"
print $ b
```
----
## [D - Swapping Puzzle](https://atcoder.jp/contests/abc332/tasks/abc332_d)
同じサイズのグリッド $A$ と $B$ が二つある。$A$ は **ひとつ隣の** 行と行、列と列を入れ替えることができる。
$B$ と同じにできるか? できるなら何回入れ替え操作を行えば良いか? 最小回数を求める。
この問題に限らず、二つの値を互いに入れ替えるスワップ操作は基本的に可換になるはずです。交換と逆の操作を行うことで元に戻すことができるので、交換という演算に対して逆演算が定義されていると思えば良い。
なので
- 盤面の最終状態は途中の交換の順序に依らない。最終的にどこどこが入れ替わったかで冪等に決まる
- 行と列は別々に考えられる
- ある行を、好きな行に移動させることができる。同様にある列を好きな列に移動させることができる
という性質がある (はずです)。
交換回数は、入れ替えた結果最終的に列と行がどうなったかを初期状態と比較、転倒数を求めれば良い。
例えば元々 `[1, 2, 3, 4, 5]` という列が `[5, 1, 2 ,4, 3]` になったならその転倒数が、列の入れ替え回数です。
実装的には x と y を独立に考えて全ての入れ替えパターンを列挙して試せば良いです。
最初は 行/列 それぞれの入れ替えの組を `combinations 2` で全列挙しそれの冪集合を求めて、行と列の冪集合から一つずつ値を取り出して直積を作り、全探索しました。グリッドをミュータブルにして、実際に書き換えて一致するかどうかでフィルタ。
これでも解けますが、グリッドをミュータブルにした結果、重実装になってしまいました。
```haskell
swapRow h1 h2 grid = do
(_, (h, w)) <- getBounds grid
for_ [1 .. w] $ \j -> do
swapArray grid (h1, j) (h2, j)
swapCol w1 w2 grid = do
(_, (h, w)) <- getBounds grid
for_ [1 .. h] $ \i -> do
swapArray grid (i, w1) (i, w2)
swapGrid :: (Int, Int) -> [Int] -> ([(Int, Int)], [(Int, Int)]) -> IO (([(Int, Int)], [(Int, Int)]), UArray (Int, Int) Int)
swapGrid (h, w) rows (rss, css) = do
grid <- newListArray @IOUArray ((1, 1), (h, w)) rows
for_ rss $ \(h1, h2) -> do
swapRow h1 h2 grid
for_ css $ \(w1, w2) -> do
swapCol w1 w2 grid
grid' <- freeze grid
return ((rss, css), grid')
counts :: (Int, Int) -> ([(Int, Int)], [(Int, Int)]) -> IO Int
counts (h, w) (rss, css) = do
rs <- newListArray @IOUArray (1, h) [1 .. h]
cs <- newListArray @IOUArray (1, w) [1 .. w]
for_ rss $ \(h1, h2) -> do
swapArray rs h1 h2
for_ css $ \(w1, w2) -> do
swapArray cs w1 w2
rs' <- getElems rs
cs' <- getElems cs
x <- countInversion h rs'
y <- countInversion w cs'
return (x + y)
main :: IO ()
main = do
[h, w] <- getInts
ga <- getIntsGrid ((1, 1), (h, w))
gb <- getIntsGrid ((1, 1), (h, w))
let s1 = IS.fromList $ elems ga
s2 = IS.fromList $ elems gb
if s1 /= s2
then print (-1 :: Int)
else do
let rows = elems ga
rx = subsequences $ map (\[a, b] -> (a, b)) $ combinations 2 [1 .. h]
cx = subsequences $ map (\[a, b] -> (a, b)) $ combinations 2 [1 .. w]
grids <- mapM (\(rss, css) -> swapGrid (h, w) rows (rss, css)) [(rss, css) | rss <- rx, css <- cx]
let result = map fst $ filter (\(_, ga') -> elems ga' == elems gb) grids
result' <- mapM (counts (h, w)) result
print $ if null result then (-1) else minimum result'
```
一方、冷静に考えると最終結果は冪等なこともあり、グリッドを直接変えなくても写像で変換後の配列を求めることができることに気づきます。
また、行と列の入れ替えも入れ替えを一つ一つやらなくても最終状態だけ分ければいいので順列で行と列の全パターンを試せば良いでしょう。
二次元配列の行と列をそれぞれ入れ替える写像は、`ixmap` を使えば綺麗に実装できます。
```haskell
count (h, w) (rs, cs) = do
x <- countInversion h rs
y <- countInversion w cs
return (x + y)
main :: IO ()
main = do
[h, w] <- getInts
gridA <- getIntsGrid ((1, 1), (h, w))
gridB <- getIntsGrid ((1, 1), (h, w))
let rows = permutations [1 .. h]
cols = permutations [1 .. w]
xs = [(rs, cs) | rs <- rows, cs <- cols]
grids = map f xs
where
f ix@(rs, cs) = do
let (rix, cix) = (listArray @UArray (1, h) rs, listArray @UArray (1, w) cs)
(ixmap (bounds gridA) (\(i, j) -> (rix ! i, cix ! j)) gridA, ix)
result = filterOnFst (== gridB) grids
values <- mapM (count (h, w) . snd) result
print $ minimumWithDefault (-1) values
```
この実装が本番中にシュッと出てこなかったのは、反省が残ります。
B と C で焦った結果、柔軟さを欠いてしまいました。
----
## 感想など
ここ数回は順調だった中、久しぶりに滑ってしまいましたがおかげで自分が序盤で滑る原因がわかりました。
B, C 問題あたりで少しちゃんと考える必要がある問題なのに、解法を吟味し切らず見切り発車で実装に着手してしまっていることが原因です。
D 問題ぐらいになってくると紙とペンでしっかり考察をして、考察し切るまでは実装に着手しないようにしているのですが、B や C ではそこのプロセスを端折ってずっこける、というのがパターンのようです。
バチャのときはもう少し落ち着いているので、B や C で「ん?」という問題が出たら紙の上で考察するようにしていました。が、本番の時は「早解きせねば」という意識が先行して、考察が不十分なまま実装に入ってしまってました。
これに気づけたのはよかったです。もう同じ失敗はしないと思います!
次回 ABC333 は私用のためおそらく参加が難しいと思いますが、無理してでも出るか思案しています。
今年中にレーティング 1000 に行きたかったのですが、今回のビハインドで少しきつくなってきました。次回出られればワンチャンありそうですが.... 🤔