# ABC312 振り返り
- [ユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312) - AtCoder](https://atcoder.jp/contests/abc312)
- 成績 AB 2完 ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc312)
- 前回 [[ABC311 振り返り]]
**やっちまった回でした**。
前回はパフォーマンスも 1000 を超え、最近は精進でも水色diff を少しずつ解けるようになり手応えを感じていたので今回も... と思いましたがずっこけまして、AB 2完での敗退です。ABCD 4完ぐらいが目標でしたが、C も D も何かミスをしたというよりそもそも正しい解法に辿り着けていなかったです。
まだまだ、自分で思っているよりも自分の今の実力にボラタリティがありそうです。茶色・緑 diff の問題に対応する安定感を高めていく必要があると痛感しました。
以下、実装はコンテスト終了後にリファクタリングしています。コードは主要部分のみ抜粋です。
----
## [A - Chord](https://atcoder.jp/contests/abc312/tasks/abc312_a)
- [提出 #44034061 - ユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)](https://atcoder.jp/contests/abc312/submissions/44034061)
条件分岐。力技でやってしまいます。集合で管理して、ということも書きながら考えましたが勢いで書き切った方が早いと思いそのまま提出しました。
```haskell
solve s
| s == "ACE" = True
| s == "BDF" = True
| s == "CEG" = True
| s == "DFA" = True
| s == "EGB" = True
| s == "FAC" = True
| s == "GBD" = True
| otherwise = False
main :: IO ()
main = do
s <- getLine
putStrLn $ if solve s then "Yes" else "No"
```
----
## [B - TaK Code](https://atcoder.jp/contests/abc312/tasks/abc312_b)
- [提出 #44098011 - ユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)](https://atcoder.jp/contests/abc312/submissions/44098011)
出ました、二次元グリッド全探索問題。Tak Code って何だろう、意味不明... と思いながら解いていました。のちに QR コードのパロディだということを知る。
過去何回かあった、二次元グリッドの重実装問題に比較すると今回は容易でした。
グリッドから 9 x 9 マスを抽出するのを全領域に対して行い Tak Code なるものと比較して条件を満たしているかを確認する。
Haskell の配列のインデックス範囲は Data.Ix の `range` 関数で指定できますが、この `range` がなかなか優れもので 9 x 9 マスの矩形になるように索引リストを生成するのも簡単です。その矩形の索引リストをグリッドの値に写像してやることでその範囲の文字列が得られるので、Tak Code の文字列と比較してやる。配列のマス同士を比較するのではなく、抽出した値を文字列にして文字列比較でやるとややこしくなくて楽です。
```haskell
extract9x9 grid (i, j) = map (grid !) $ range ((i, j), (i + 9 - 1, j + 9 - 1))
isSatisfied takCode s = all (== True) $ zipWith f takCode s
where
f '?' _ = True
f t c = c == t
main :: IO ()
main = do
[n, m] <- getInts
ss <- replicateM n getLine
let grid = listArray @UArray ((1, 1), (n, m)) $ concat ss
takCode = "###.?????" ++ "###.?????" ++ "###.?????" ++ "....?????" ++ "?????????" ++ "?????...." ++ "?????.###" ++ "?????.###" ++ "?????.###"
points =
[ (i, j)
| (i, j) <- range ((1, 1), (n - 9 + 1, m - 9 + 1)),
isSatisfied takCode (extract9x9 grid (i, j))
]
forM_ points $ \(i, j) -> do
putStrLn . unwords . map show $ [i, j]
```
----
## [C - Invisible Hand](https://atcoder.jp/contests/abc312/tasks/abc312_c) (コンテスト後にAC)
- [提出 #44088817 - ユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)](https://atcoder.jp/contests/abc312/submissions/44088817)
この問題でつまづいてしまいました。
$A$ と $B$ の二つの単調増加列がある。その列に対し、任意の値 $X$ で境界を引いてみる。$A$ の左側になった要素の個数 $A'$ と、$B$ の右側になった個数 $B'$ を比較して $A' \geq B'$ になるなら、その $X$ は条件を満たしている。そのような $X$ の最小値を求める。
ここで、数列が二つあるので一方を固定してもう一方を二分探索という方法を取りました。これでサンプルに対しては AC する回答が作れてしまったんですね。これで提出したところ WA と RE が出てしまい「あれっ?」という... 境界条件をバグらせてしまったかなとあれこれやり始めて蟻地獄、これで負け確定の流れになってしまいました。
実際にはこの方法ではなく、$X$ を適当に決めた時の $A$ の個数、$B$ の個数をそれぞれ $f(X)$ と $g(X)$ として $f(X) - g(X)$ とすると、この関数もまた単調増加するので $\geq 0$ になる境界を探す、つまり $X$ を二分探索する···「答えで二分探索」が正解でした。
「答えで二分探索」は最近 [001 - Yokan Party（★4）](https://atcoder.jp/contests/typical90/tasks/typical90_a) や [087 - Chokudai's Demand（★5）](https://atcoder.jp/contests/typical90/tasks/typical90_ci) でやったばかりだったのに、その発想に至れなかったです。最初の解法に固執してしまったこと「二分探索の結果を二分探索する」という組み合わせがあり得ることに想像が至らなかったこと、など反省が残りました。
```haskell
f as x = do
let (ng, _) = bisect (0, n + 1) (\i -> as ! i > x)
ng
where
(_, n) = bounds as
g bs x = do
let (ng, _) = bisect (0, m + 1) (\i -> bs ! i >= x)
m - ng
where
(_, m) = bounds bs
main :: IO ()
main = do
[n, m] <- getInts
as <- getInts
bs <- getInts
let as' = listArray @UArray (1, n) $ sort as
bs' = listArray @UArray (1, m) $ sort bs
(_, ok) = bisect (0, 10 ^ (9 :: Int) + 1) (\x -> f as' x - g bs' x >= 0)
print ok
```
----
## [D - Count Bracket Sequences](https://atcoder.jp/contests/abc312/tasks/abc312_d) (コンテスト後にAC)
- [提出 #44086634 - ユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)](https://atcoder.jp/contests/abc312/submissions/44086634)
DP です。DP であることはすぐにわかったのですが、うまく遷移を構成することができませんでした。
かっこの対応を、`(` が出てきたら $+1$ 、`)` が出てきたら $-1$ として数を累積し、途中で負にならないこと、最後に $0$ になっていることで調べるというのは [002 - Encyclopedia of Parentheses（★3）](https://atcoder.jp/contests/typical90/tasks/typical90_b) でも出てきた典型ですね。
この、かっこの対応を調べる値を、「括弧数」とでも呼ぶとします。
この括弧数を DP の状態空間とみなして、DP の遷移を文字が進むごとの括弧数の移り変わりの遷移に落とし込む、というのがポイントでした。文字数は高々 $3,000$ 文字なので状態空間サイズも $3,000$ に収まります。状態空間内の各状態が、値として抱えるのは取りうる括弧列の数ですね。
- `(` が出たら括弧数は $+1$ される → 現在から $+1$ した状態に遷移
- `)` が出たら括弧数は $-1$ される → 現在から $-1$ した状態に遷移
- `?` が出たら $+1$ にも $-1$ にもなれる → 両方に遷移
として DP を回す。
最終的に括弧数が $0$ になっているのが正しい遷移なので $dp[0]$ が答えになります。
また、`)` がたくさん出てくると括弧数は負になり得ますが、負になったところでそのケースは条件を満たさないので、負になる遷移は全て捨てて構わない。
この手の状態空間を畳み込む状態遷移のDPを `accumArrayDP` という関数でフレームワーク化したので、それで実装すると以下になりました。
···せっかくフレームワークを用意できていても、肝心の状態遷移を構成できなければその力は発揮できないのです!
```haskell
main :: IO ()
main = do
s <- getLine
let n = length s
dp = accumArrayDP @Array f (+) (0 :: IntMod) (0, n) [(0, 1)] s
where
f (i, x) '(' = [(i + 1, x)]
f (i, x) ')' = [(i - 1, x)]
f (i, x) '?' = [(i - 1, x), (i + 1, x)]
let (IntMod x) = dp ! 0
print x
```
## 追記
どうもこの問題の DP の状態を定義できなかったことが、なんでだろう? と気になってきたので、そもそもこの問題の状態をどう考えるのべきなのか、その思考プロセスをもっと言語化してみようと思います。
### DP の「状態」を何にする、どう考えるか
まずこの問題をを`?` が現れない前提で、正しい括弧対応が成立しているか調べるのに括弧数を計算する問題と考えるとどうなるか
```
1234321010
(((())))()
```
となる。上記の例は、途中で負の値も出てこないし、最終的に $0$ であり、正しい括弧対応になっている。
この計算の実装は Haskel なら `scanl` か `mapAccumL` になるだろう。アキュムレータである「計算過程の状態」に括弧数を持たせることになる。手続き型なら、for ループの外側のスコープの変数に記録するとかになる。
括弧数の計算をこうやるのは当たり前だが、ここで着目すべきは「この計算において**括弧数は状態**」ということである。「$i$ 文字目の括弧数の状態。括弧の対応状況」。
さて、次に`?` が現れるこの問題のケースを考える。
```
(???(?
```
`?` が出てくると、状態の表現がスカラー (単一の値) では扱いきれなくなる。 `?` が出てくると、そこで括弧数が $+1$ されるか $-1$ されるかどちらの場合もあり得るので、一つの値ではその一方しか記憶できない。単一の値ではそれを扱えない··· ということで状態をスカラーから配列に拡張することを考え始める。
後でまた詳細に記すが、こうして状態の次元を増やすることで「 $i$ 文字目で括弧数が $j$ だったときの何か」が扱えるようになる。これがただのスカラーだった「状態」を、構造的な広がりを持った「状態空間」に拡張することに相当する。この問題の場合は $0$ から $3000$ までの括弧数それぞれを扱えるデータ構造として、$3001$ 個の要素を持つ配列にする。
[D - 高橋くんの苦悩](https://atcoder.jp/contests/abc015/tasks/abc015_4) のような 3次元DP の問題で、2次元DPから3次元DPに拡張するときもそうだが、DP というのは **まずは原始的な状態ありき** 。そしてその原始的な状態の表現では空間の次元が足りず問題を扱いきれない、ということをきっかけに状態の拡張を行う。こうして分岐があったケース全てを記憶できるようになり、実質的に全探索が可能になる... というのが計算構造の考え方ではないか。となると、この問題も括弧対応計算の定番である「括弧数」に着目するのは突拍子もないことではなく、当然のことのように思える。
同じ説明を再度繰り返す。
問題における計算が扱う状態 (畳み込み計算のアキュムレータ) こそが、DP の状態空間になる。DP の問題では当て勘 (パターン) で状態空間を定義するのではなく、そもそもその計算を原始的に行おうとしたとき (状態分岐がなくスカラーで扱うなどするとき) 何を状態にするか、から出発すると良さそう。そして当然、分岐を考え始めると状態をスカラーで扱っていては埒があがららない。この問題で言えば、前述の通り `?` のところで状態が二方向 (開き括弧と閉じかっこのケースに分岐する) に拡がるのでその広がりをスカラーでは収めることができない。よって次元を拡張する。
なおこの計算過程で状態が複数方向に拡がる感じは DFS のそれを思い出す。再帰を呼び出すとき2回再帰関数を呼ぶと状態数が2倍2倍で拡がっていくやつ。DP の場合、広がる状態が特定の狭い範囲... 定義した一定の状態空間の中に収まるというところがポイント。というか、空間が限定されていて狭くないと DP が使えない、そして、そこで部分問題重複性が発生する。メモ化再帰と DP はここで繋がる。
こうして分岐が発生したいずれの状態も考慮したデータ構造に、状態を拡張したことになる。「DP は全探索みたいなもの」と言われる所以だと思う。
DP の状態定義を理屈で理解しようとするとこういうことになるのでは。
そうか、そういうことだったのかリリン...
そして、これまで自分は DP の状態遷移をここまで整理できていなかった。結構パターン認識で定義してたんだなあということに気づく。なのであまり経験のない状態の定義のパターンに対応できてなかった... というのがおそらく今回の敗因。理詰めで状態、空間への拡張、遷移を考えられるようになるべき。原始的な状態から、必要に応じて状態を広げて複数の状態分岐を扱えるようにする。
### まとめ
この問題を解くための思考プロセスとしては、
- 冒頭に見たような単純なケースを考える
- 「括弧数」という「状態」があることに気づく
- `?` で状態が分岐するから、括弧数も単一の値ではなく配列に拡張して扱うことを決める
- この状態空間が、一文字進むたびにどう変化するか (どう畳み込まれるか) 遷移を考える
この順序で考えれば、勘でおかしな状態を定義してしまってはまるなどの失敗はしない。(本戦ではそれで失敗した)
----
## 感想・反省など
知らないアルゴリズムが出ているとか、説明されても理解できないとかそういう感じではないので、訓練がまだ足りてないなというのが所感です。問題の構造を解法に落とし込むところの正確性が、今回は不十分でした。
前回 ABC 311 はグラフの問題が中心でしたが、グラフの問題は比較的得意なのでこのあたりの正確性が結構鍛えられていそうですが、一方で二分探索や DP などが、基礎体力が不十分。これ以外にも、ABC310 で出たグラフではない DFS なんかも、訓練不足感があります。この辺を強化していこうと思います。
2完という不甲斐ない結果に終わりましたが、こういう結果に終わったときは精神的ダメージが大きい一方、それがきっかけで成長への執着が生まれるので、大きな成長への機会だと思います。
それから、やはり実践形式からの学びは大きいです。
というわけで早速今朝の「あさかつ」に参加しました。バーチャルコンテストそのほかに積極的に参加して、経験値を積むフェーズに入ろうと思います。