# ABC311 振り返り
- [トヨタ自動車プログラミングコンテスト2023#4(AtCoder Beginner Contest 311) - AtCoder](https://atcoder.jp/contests/abc311)
- 成績 ABCD 4完 ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc311)
- 前回 [[ABC310 振り返り]]
前回は D 問題の難易度が高く四苦八苦しましたが、今回は Difficulty はなだらかに上がっていってる感じでバランスの良い問題セットだったのかなーと思います。
私は見ての通り ABCD 4完でした。やはり E 問題の壁は高く今回も5完はなりませんでした。そして E は解法の考察含めかすりもしなかったので、青色ぐらいあるかなーと思ったら水色下位ということで。まだまだ壁は高いです。
とはいえ現時点の自分の実力を考えると妥当な出来かなとは思いました。コンテスト本番に緑の問題を解くことができたのは初めてでした。
以下、一部リンクがローカルの内部リンクなので動作しません。コードは主要な箇所のみの抜粋です。
----
## [A - First ABC](https://atcoder.jp/contests/abc311/tasks/abc311_a)
A、B、C の三文字を全部見つけるにはどこまで探索したらいい? という問題。
手続き型なら辞書か何かでフラグを持って for ループを回して3つとも見つかったら打ち切り、みたいにするところでしょうか
関数型だと、こういう状態を持ったループは一瞬考えますね。ここは Haskell の中でも好きな関数 `mapAccumL` を使うのです...ドヤァ! そして RE 出しましたw サーセンww
前回に引き続き A でミスしました。精神的ダメージが大きいです 🤮
```haskell
main :: IO ()
main = do
_ <- readLn @Int
s <- getLine
let abc = Set.fromList "ABC"
(_, xs) =
mapAccumL
( \acc c ->
let acc' = Set.insert c acc
in (acc', abc `Set.isSubsetOf` acc')
)
Set.empty
s
print $ succ . fromJust $ elemIndex True xs
```
----
## [B - Vacation Together](https://atcoder.jp/contests/abc311/tasks/abc311_b)
みんなの予定が共通して空いてるところはどこで、その連続区間長はいかほど?
「調整さん」みたいな問題です
みんなの予定が共通して空いているところは、`o` であるところが `True` として縦に畳み込んでいけばすぐにわかります。
結果 `xxxoooooxoox` みたいな一つの文字列になるので、連長圧縮。綺麗に解けました。
```haskell
main :: IO ()
main = do
[n, _] <- getInts
ss <- replicateM n getLine
let s' = foldl1 (zipWith f) ss
where
f 'o' 'o' = 'o'
f _ _ = 'x'
result = map snd . filter ((== 'o') . fst) $ rle s'
print $ case result of
[] -> 0
xs -> maximum xs
{-- Library --}
rle :: Eq a => [a] -> [(a, Int)]
rle = map (\x -> (head x, length x)) . group
```
----
## [C - Find it!](https://atcoder.jp/contests/abc311/tasks/abc311_c)
この問題は結構面白い問題でした。結果的には以下のように、素朴な方法で解けました。
- 適当な頂点からグラフを辿る。出次数はどの頂点も1で、次に訪問する頂点は一意に決まっている。よって BFS や DFS は必要ない
- 過去に訪問した頂点がまだ出てきたら、そこが閉路の開始地点
- ので、その開始地点から再度、グラフを辿って自身に戻ってくるまでの経路をリストアップする
これだけでした。
```haskell
main :: IO ()
main = do
n <- readLn @Int
as <- getInts
let g = listArray @UArray (1, n) as
-- 遷移関数
f = (\(v, seen) -> (g ! v, IS.insert v seen))
-- 一度見た頂点に再度辿り着いたらそこが閉路
let v = fst . head $ dropWhile (uncurry IS.notMember) $ iterate f (1, IS.empty)
-- 見つけた頂点を開始点にして、再度同じことを繰り返すと訪問履歴が閉路の経路になる
let us = map fst . takeWhile (uncurry IS.notMember) $ iterate f (v, IS.empty)
print $ length us
putStrLn . unwords . map show $ us
```
最初は DFS や BFS でのグラフの閉路抽出の問題かと思いそれでやろうと思いましたが、閉路判定 (閉路があるかどうか) の実装は持っているが、抽出の実装はやったことがなく持っていないことに気づき「う、やば」となりました。コンテスト中に閉路抽出の実装に改良できる? どうしようか? と思いましたが、それで時間を食い潰すとまずいと思い、一旦飛ばして D に行きました。
D を解いたことで気持ちが落ち着いて改めて考えてみると「そうか、出次数は 1 だからそんなことしなくても良いのか」ということに気がつきました。そもそも C 問題で、グラフの閉路抽出は出ないとも思い。
### Functional Graph
こういう、グラフがただの数列で表現されていて各頂点からの出次数が 1 しかないというのはときどき見かけます。こういうグラフを Functional Graph というらしいです。
> Functional Graph とは各頂点の出次数がちょうど 1 の単純な有向グラフのことである. グラフが $\{1,…,n\}→\{1,…,n\}$ の関数として表現できることがその名の由来であると思われる.
> [My Algorithm : kopricky アルゴリズムライブラリ](https://kopricky.github.io/code/GraphDecomposition/functional_graph.html)
> **Functional Graph の性質**
> $G$ の連結成分が $K$ 個あって $C_1,C_2 \ldots C_k$ とする。このとき、各連結成分には閉路が 1 つだけ存在する。
> [解説 - 東京海上日動プログラミングコンテスト2022（AtCoder Beginner Contest 256）](https://atcoder.jp/contests/abc256/editorial/4135)
> 大切な性質として、連結成分ごとに閉路が存在する。つまり、連結成分の個数＝閉路の個数となる
> [競技プログラミングにおける細かな話題まとめ - はまやんはまやんはまやん](https://blog.hamayanhamayan.com/entry/2017/06/07/234608)
**Functional Graph は連結なら必ず閉路がある** というのが面白い性質ですね。
どの連結成分にも必ず閉路があるので、もし閉路抽出アルゴリズムを仮に持っていたら適当な頂点選んでそれを一回走らせるだけでも良かったんだなあと。「仮に閉路抽出できたとしても、どの連結成分に閉路があるかわからなかったら全頂点から探索しないといけなくて難しい?」と思ってましたが、そんなことはなかった。
### トポロジカルソート?
ところで、この問題は有向グラフです。有向グラフで閉路がない、つまり DAG の場合はトポロジカルソートが可能です。
ではこの問題のように閉路のある有向グラフにトポロジカルソートをすると?
···という方法で閉路を見つけて解くこともできたようです。
ただ、これまた私の手元のトポロジカルソートは DFS ベースの、DAG であることを仮定したものになっていて閉路があってもそれっぽく動いてしまい、閉路を捉えることができないようです。BFS ベースの出次数を使ったトポロジカルソートであれば、それが可能であるという記事を見かけたので、宿題とします。
----
## [D - Grid Ice Floor](https://atcoder.jp/contests/abc311/tasks/abc311_d)
ドラゴンクエストの氷の床のように、足を踏み入れるとツルツル滑って前方に進み続けてしまい障害物にあたるまで方向転換することができない。なお、ドラクエを思い浮かべたのはアラフィフ / アラフォー世代のようで、他の皆さんはポケモンを話題にしていました。「え? サンタさんに頼んだのこれじゃない? おじさん、ポケモンはよくわからないんだ··· ドラクエきちゃってごめんな。」
もとい、色々な解法がありそうな、面白い問題です。
停止したマスがどこか、を管理して解く方法を採用した方が多かったのでしょうか? kyopro_friends さんの回答はそうなってました。(公式の解法はまだ理解できておらず)
自分は [043 - Maze Challenge with Lack of Sleep（★4）](https://atcoder.jp/contests/typical90/tasks/typical90_aq) でもやった、(グリッドではなく) BFS の探索空間を3次元に拡張して3次元目に現在の進行方向を持たせる方法を採用しました。やっててよかった競プロ典型。
グリッドの頂点を `(2,2)` ではなく `[(2,2,L), (2,2,R), (2,2,U), (2,2,D)]` と4方向分あると考えて
- 氷を滑ってる間は `(2, 2, R)` からは `(2, 3, R)` にしか遷移できない
- 壁にぶつかったら (次の遷移先が壁だったら)、そこから四方どこにでも移動できる
として遷移を記述します。あとはこれを普段通り BFS にかける。
```haskell
data LRUD = L | R | U | D deriving (Show, Eq, Ord, Ix)
-- 遷移関数 f v
f :: UArray (Int, Int) Char -> (Int, Int, LRUD) -> [(Int, Int, LRUD)]
f grid v@(_, _, d) = do
let du = case d of
L -> (0, -1, L)
R -> (0, 1, R)
U -> (-1, 0, U)
D -> (1, 0, D)
u@(i, j, _) = v `to` du
-- 次の進行方向が '#' だったら、四方いずれかに方向転換可能
if inRange (bounds grid) (i, j) && grid ! (i, j) == '#'
then map (v `to`) [(0, -1, L), (0, 1, R), (-1, 0, U), (1, 0, D)]
else [u]
where
to (x, y, _) (dx, dy, dd) = (x + dx, y + dy, dd)
!_ = dbg ("v", v)
reachable :: UArray (Int, Int) Char -> (Int, Int, LRUD) -> Bool
reachable grid (x, y, _)
| (not . inRange (bounds grid)) (x, y) = False
| grid ! (x, y) == '#' = False
| otherwise = True
main :: IO ()
main = do
[h, w] <- getInts
ss <- replicateM h getLine
let grid = listArray @UArray ((1, 1), (h, w)) (concat ss)
dist = bfs (filter (reachable grid) . f grid) (-1) ((1, 1, L), (h, w, D)) v0s
where
v0s = [(2, 2, d) | d <- [L, R, U, D]]
-- mapM_ print $ chunksOf 4 $ assocs dist
-- いずれかの方向で良いので訪問できた頂点が、今回数えたい対象
print $ Set.size . Set.fromList $ map (\((i, j, _), _) -> (i, j)) $ filter ((/= -1) . snd) $ assocs dist
```
すると以下のような出力が得られます。`-1` ではないところが、通過もしくはたどり着くことができた頂点です。
```
[((2,2,L),0),((2,2,R),0),((2,2,U),0),((2,2,D),0)]
[((2,3,L),5),((2,3,R),1),((2,3,U),-1),((2,3,D),-1)]
[((2,4,L),4),((2,4,R),2),((2,4,U),-1),((2,4,D),-1)]
[((2,5,L),-1),((2,5,R),3),((2,5,U),9),((2,5,D),-1)]
[((2,6,L),-1),((2,6,R),-1),((2,6,U),-1),((2,6,D),-1)]
[((3,1,L),-1),((3,1,R),-1),((3,1,U),-1),((3,1,D),-1)]
[((3,2,L),-1),((3,2,R),-1),((3,2,U),5),((3,2,D),1)]
[((3,3,L),-1),((3,3,R),-1),((3,3,U),-1),((3,3,D),-1)]
[((3,4,L),-1),((3,4,R),-1),((3,4,U),-1),((3,4,D),-1)]
...
```
グリッドで考えた場合に、`LRUD` いずれかの方向で訪問済みにできていれば OK ということになります。ので、最後にこれを二次元にまとめ上げて、頂点数を数えたら一丁上がりです。
### BFS を状態遷移 $f(v)$ にのみ着目して考える
この問題、我ながらいい感じに解けたなあと思います。
というのは、実装上、BFS 関数そのものは盆栽でライブラリ化したそれに一切手を入れずに解けているんですね。
「ある頂点から次の頂点に遷移する」というグラフの状態遷移の部分のみに絞って考えて、問題を解くことができました。その遷移関数は $f(v) = us$ という形で BFS の実装とは外に切り出されていて、この関数を実装して高階関数として BFS に渡せばその状態遷移による探索が行われます。
グラフ探索や DP のように、状態遷移が問題の核心になる問題は、状態遷移以外の部分まで含めて考え始めると急激に認知負荷が上がってしまって私の脳ではその負荷に耐えられません。そこで、状態遷移を $f(v) = us$ というシンプルな形で考えてそれをアルゴリズムに渡すだけで計算が行われるよう盆栽しておき、本番ではこの $f(v)$ をどう記述するかに集中します。
今回、BFS の探索空間を2次元から3次元に拡張しているわけですが、Haskell の配列なら配列の次元数を抽象化することができるのでたとえこれが1次元でも2次元でも4次元でも考え方は同じですし、BFS 関数自体に変更は入りません。
なお以下がその `bfs` 関数の方の実装です。
```haskell
{-- Library --}
bfs :: Ix v => (v -> [v]) -> Int -> (v, v) -> [v] -> UArray v Int
bfs nextStates initial (l, u_) v0s = runSTUArray $ do
dist <- newArray (l, u_) initial
forM_ v0s $ \v0 -> do
writeArray dist v0 0
aux (Seq.fromList v0s) dist
return dist
where
aux Empty _ = return ()
aux (v :<| queue) dist = do
d <- readArray dist v
us <- filterM (fmap (== initial) . readArray dist) (nextStates v)
queue' <-
foldM
( \q u -> do
writeArray dist u (d + 1)
return $ q |> u
)
queue
us
aux queue' dist
```
----
## [E - Defect-free Squares](https://atcoder.jp/contests/abc311/tasks/abc311_e) (🍊未完)
- [最大正方形の面積の求め方を知ってますか？ 2次元の動的計画法（貰う/配る）をビジュアライズしてみました！ - Qiita](https://qiita.com/H20/items/884551b4965739176afc)
(upsolve に時間がかかりそうなので、一旦このまま公開します)
----
## 感想・反省など
コンテストの日は、夕方から有酸素運動。今回もやりました。一汗かいてからコンテストに出て、終わったらビールを飲んで寝る。至福です。
こうして振り返ってみると、今回は ABCD ともに割と納得のいく解法と実装を作れていて、よかったと思います。
特に D 問題は日頃盆栽していた関数型プログラミング脳でのフレームワークがピタッとはまって、成績に貢献できたと思います。
反省点としてはやはり C 問題でしょうか。冷静に考えれば簡単な問題なのに「すわっ、閉路抽出!」と先入観を持ってしまったがために初めから高度な解法を考えすぎてしまいました。それでさっとオーバーキルできればいいのですが、そうでない時は一度リセットして、改めてフラットに考察する癖を身につけたいです。
本番で緑を解く、というアチーブメントを Rated 参加 9回目にして達成しました。この調子で次回以降も頑張りたいと思います。
### Haskell 的なところ
本戦中に無駄なムーブにつながってるところをちまちまと削ぎ落とすようにしています。
これまで Debug.Trace による print デバッグは、実装ができたらわざわざ print デバッグしてる箇所をコメントアウトして提出とやっていましたが、toyboot4e 先生の方法を参考に、コンパイルオプションを使って制御するようにしました。
CPP 言語拡張を使うと Haskell のコードの中で `#ifdef` が使えるようになるので以下のようにして、プロダクションへの提出時はデバッグ関数を何もしない実装に差し替えます。
```haskell
{-# LANGUAGE CPP #-}
#ifdef DEBUG
dbg :: Show a => a -> ()
dbg !x = let !_ = traceShow x () in ()
#else
dbg :: Show a => a -> ()
dbg _ = ()
#endif
```
ローカルでは online-judge-tools を使ってテストを走らせていますが
```zsh
$ oj t -c '../../run.sh' test/sample-1.in
```
というシェルスクリプトを実行することでテストが走ります。このスクリプトの中身は
```shell
#!/bin/bash
stack ghc -- -DDEBUG ./main.hs > /dev/null
if [ $? -eq 0 ]; then
./main
fi
```
と、ghc でコンパイルして実行、その時にデバッグオプションを有効化しています。
自分は今の所、提出コードにライブラリをバンドルしてコンパイル、みたいなことはやっていなくて、必要な関数をコピペで `main.hs` に貼り付ける方法をとってます。バンドルしてコンパイルの方がライブラリ管理の観点では良いのですが、提出用コードに無関係な実装が大量にバンドルされてしまうのがなあ... と思っています。
こういう日頃の身の回り点検、効率化が、本番時に無駄な認知エネルギーを消費せずに温存できることにつながっていると思っていましたが、どうやら強者の方々の中には、ブラウザ上のフォームの中にコード書いて提出してるだけという方がちらほらいるようで... 小技など力で捩じ伏せてしまえ、力こそ全ての世界でした 😇
## TODO
- [x] リファクタリング
- [x] Functional Graph について調べる
- [ ] E upsolve
- [ ] 閉路抽出の実装作っておく
- [ ] BFS のトポロジカルソートのライブラリ整理