# ABC327 振り返り
- [HHKBプログラミングコンテスト2023(AtCoder Beginner Contest 327) - AtCoder](https://atcoder.jp/contests/abc327)
- 成績 ABCDE 5完 (1301) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc327)
ABC327 でした。
水色 diff の E 問題も解けて5完で、通算2回目の水色パフォーマンスを出すことができました。よかったです
![[スクリーンショット 2023-11-05 9.07.45.png]]
- A問題 (灰) ··· やるだけ。文字列判定
- B問題 (灰) ··· $A^A = B$ となるような $A$ は存在するか? $B \leq 10^{18}$ に対する上界を見極めて全探索
- C問題 (灰) ··· $9 \times 9$ のグリッドの条件判定問題。$3 \times 3$ マスを 9個抜き取るのが鬼門
- D問題 (茶) ··· グラフの問題だと気づけるかどうか。二部グラフ判定
- E問題 (水) ··· DP。ただし数式の構造から DP で計算すればいいのはどこかを見極める必要あり
という問題セットでした。
周囲を見ていると C → D の間隔がみなさん私よりも早いです。
D はグラフ問題の顔をしていないグラフの問題ですが、グラフだと気づくことができればあとは典型で、そこに気づくのに少し時間がかかりました。
E 問題はぱっと見 DP なわけですが、与えられた数式をそのまま DP に持ち込もうとするとうまく計算できず、どこを計算すれば良いのかを解きほぐす必要がありました。ここに手間取りました。これも私よりも順位が良い人たちは 60分くらいまでに解いて、F を解く余地を残しています。
本戦で水色の DP を解くことができたのはちょっとした達成感がありますが、これでようやくパフォーマンス 1301 ということは、今回ぐらいの成果を安定的に出すことができて初めて水色に到達できるということのようです。水色への道のりはまだまだあります。
----
## [A - ab](https://atcoder.jp/contests/abc327/tasks/abc327_a)
`a` と `b` が隣り合っているところを探す。
実装方法は色々ありそうですが、一番最初に思いついた実装でえいやと実装しました。前回の A とは異なり素直な問題でよかったです。
```haskell
main :: IO ()
main = do
_ <- getInt
s <- getLine
let xs = zipWith f s (tail s)
where
f 'a' 'b' = True
f 'b' 'a' = True
f _ _ = False
putStrLn $ if any (== True) xs then "Yes" else "No"
```
---
## [B - A^A](https://atcoder.jp/contests/abc327/tasks/abc327_b)
$A^A = B$ となる $A$ は、$B \leq 10^{18}$ までに存在するか?
一瞬、$B$ を素因数分解して素数でゴニョゴニョするのかなと思いましたが $B \leq 10^{18}$ なので間に合わない。
上界を見極める問題ですね。ghci で軽く計算してみたところ $20^{20}$ ぐらいで $10^{18}$ を大幅に超えるので、その辺まで適当に全探索すれば良いだろう、ということで実装しました。
オーバーフローが怖いので Integer 使ったつもりでしたが、型推論で Int になってますねw
```haskell
main :: IO ()
main = do
b <- getInt
print $ headWithDefault (-1) $ filter (\i -> i ^ i == b) [1 .. 20]
```
----
## [C - Number Place](https://atcoder.jp/contests/abc327/tasks/abc327_c)
$9 \times 9$ のグリッドをゴニョゴニョして条件に合ってるかどうか判定する問題。
行、列、$3\times 3$ のそれぞれ $9$ マスに $1 \ldots 9$ までの数字が全て含まれていれば真。これを調べます。
行と列の条件判定は簡単ですが、 $3 \times 3$ のタイルを $9$ 個グリッドから抜き取るところがやや面倒ですね。
少し考えましたが、各 $3 \times 3$ タイルの開始点と終点を列挙して `range` で抜き取ることにしました。開始点と終点の列挙は気合と根性のハードコードですw まあ、$9$ 通りなので... この時点ではまだ緊張が抜けていないので、脳死でハードコードする方が気楽であります。
```haskell
checkRows = all (\row -> IS.size (IS.fromList row) == 9)
checkCols = all (\col -> IS.size (IS.fromList col) == 9)
checkCells xs grid = do
let cells = [[grid ! v | v <- range x] | x <- xs]
all (\cell -> IS.size (IS.fromList cell) == 9) cells
main :: IO ()
main = do
rows <- replicateM 9 getInts
let grid = listArray @UArray ((1, 1), (9 :: Int, 9 :: Int)) $ concat rows
xs =
[ ((1, 1), (3, 3)),
((1, 4), (3, 6)),
((1, 7), (3, 9)),
((4, 1), (6, 3)),
((4, 4), (6, 6)),
((4, 7), (6, 9)),
((7, 1), (9, 3)),
((7, 4), (9, 6)),
((7, 7), (9, 9))
]
putStrLn $ if checkRows rows && checkCols (transpose rows) && checkCells xs grid then "Yes" else "No"
```
----
## [D - Good Tuple Problem](https://atcoder.jp/contests/abc327/tasks/abc327_d)
問題文がちょっとややこしいですが、
- $(A_i, B_i)$ というペアが $M$ 個ある
- $A_i$ と $B_i$ が指し示す値は $0$ or $1$ の二値しか取りえない
- 全てのペアにおいて、この $A_i$ と $B_i$ の指し示す値が異なっていれば嬉しい
これを判定する問題。
$A_i$ と $B_i$ をグラフの頂点、ペアを無向辺と考えるとそれが二部グラフになっていれば真、と判定できます。
二部グラフ判定は過去問でもよく出ています。盆栽化してあるのでそれを使って AC しました。
グラフだと気づけるかどうか、という問題ですね。
最初はグラフで考えておらず、適当なペアから始めて芋づる式的に $0$ か $1$ かを埋めていくようなやり方でいけるかな ... と思案し紙の上でシミュレーションしていたのですが「このまま突き進むと沼りそう」という直感が働きました。この辺りは経験の賜物かもしれません。もっと簡単な解法があるのでは、と仮定して自分の脳内の引き出しを幅優先探索して見たところ「グラフで考えたらどうなる?」と気づきました。
気づくことができたのはよかったですが、愚直解をシミュレーションするより前にグラフで考えることができればより良かったと思います。柔軟性が必要です。
```haskell
main :: IO ()
main = do
[n, _] <- getInts
as <- getInts
bs <- getInts
let uvs = zip as bs
g = graph2 (1, n) uvs
cs <- componentsM (g !) (bounds g) [1 .. n]
putStrLn $ if all (isBipartite n (g !)) cs then "Yes" else "No"
-- 二部グラフ彩色 DFS
dfsM :: (MArray a Bool m, Ix v) => (v -> [v]) -> a v Bool -> [(v, Bool)] -> (v, Bool) -> m [(v, Bool)]
dfsM nextStates visited path (v, color) = do
writeArray visited v True
foldM f ((v, color) : path) (nextStates v)
where
f context u = do
seen <- readArray visited u
if seen
then return context
else dfsM nextStates visited context (u, not color)
-- 連結成分ごとに分割した頂点リストを返す。また彩色されている
componentsM :: (MArray IOUArray Bool m, Foldable t, Ix v) => (v -> [v]) -> (v, v) -> t v -> m [[(v, Bool)]]
componentsM nextStates b vs = do
visited <- newArray @IOUArray b False
foldM (f visited) [] vs
where
f visited cs v = do
seen <- readArray visited v
if seen
then return cs
else do
path <- dfsM nextStates visited [] (v, True)
return (path : cs)
-- 二部グラフ判定
-- グラフの隣接頂点の色が全て親頂点とは色が違えば二部グラフになっている
isBipartite :: Int -> (Int -> [Int]) -> [(Int, Bool)] -> Bool
isBipartite n nextStates colored = do
let cs = array @UArray (1, n) colored
all
( \(v, color) ->
all (\u -> cs ! u /= color) (nextStates v)
)
colored
```
----
## [E - Maximize Rating](https://atcoder.jp/contests/abc327/tasks/abc327_e)
今回の山場。DP です。
制約は $N \leq 5000$ 程度で小さいですし、$i$ 回目のコンテストに「参加する」「参加しない」、つまり選ぶ・選ばないなのでナップザック問題あるいは部分和問題の亜種なのはすぐにわかります。
選択した問題の数 $k$ が重要な指標になるので、それを状態空間にとって DP します。最適化する値はレートの数字になります。
ここでレートの計算式を見てみると
$
R = \frac{\sum_{i=1}^{k}{(0.9)^{k - i} \space Q_i}}{\sum_{i=1}^{k}(0.9)^{k - i}} - \frac{1200}{\sqrt{k}}
$
入力である $P_i$ に依存しているのは分子の $\sum_{i=1}^{k}{(0.9)^{k - i} \space Q_i}$ だけであることに気づきます。その分母や、$- \frac{1200}{\sqrt{k}}$ の値は DP で全ての計算が終わった後に計算できます。この分子だけなら単調増加なので、負の値そのほか余計なことに悩む必要もなさそうです。状態遷移が `(+)` で、緩和が `max` の DP に持ち込めば OK。
というわけでその方針で実装していきました。
DP の過程で計算したい分子の数式は、最終的にいくつのコンテストを選択したかの値 $k$ に依存しています。計算過程でわかるのは、この $k$ ではなく「そこまでに何個問題を選択したか」であるわけですが、問題の構造的に入力を後ろ、つまり $P_N$ から遷移させていけば $k$ がわからなくても計算できることに気づきました。
88 : 58 になんとかこれで AC できました。
ところで前回の ABC326 で期待値DP の問題を解くことができなかったので、今週は改めて期待値DPの問題を解いていました。期待値DP では、DP の漸化式を立てたのちにその数式をさらに操作して DP で計算可能な式に変形するというパターンがよくあります。与えられた数式そのままでは計算できなくても式変形すれば DP に持ち込めることがある...という発想が🧠にインストールされていたのが、役に立ちました。
```haskell
main :: IO ()
main = do
n <- getInt
ps <- getInts
let dp = accumDP @UArray @Double f max (-1) (0, n) [(0, 0)] (reverse ps)
where
f (k, x) p
| x == -1 = []
| otherwise = do
let x' = (0.9 ** fromIntegral k) * fromIntegral p
[(k + 1, x + x')]
results = for (assocs dp) $ \(k, a) -> do
let b = sum [ 0.9 ** fromIntegral (k - i) | i <- [1 .. k]]
c = 1200 / sqrt (fromIntegral k)
a / b - c
print $ maximum $ filter (not . isNaN) results
```
----
## [F - Apples](https://atcoder.jp/contests/abc327/tasks/abc327_f) (🍊 未完)
F は遅延評価セグメント木の問題だそうで、話題になっていました。
遅延評価セグメント木は実装を頑張って作ったのですがまだ本戦で使ったことはないです。錆びつかせないためにも、後ほど upsolve 頑張ってみようと思います。
----
## 感想
今週は水色 diff 以上の精進と、AtCoder Daily Traning MEDIUM のバーチャル参加の二本立てで練習してきました。
水色diff 精進だけだとじっくり取り組みすぎて、本戦のように時間的プレッシャーにさらされながら素早く実装する、という状況への適応力が落ちます。以前に確率DP・期待値DP をじっくり一週間練習して臨んだ次のコンテストで、簡単な問題が解けずに爆死したことがありました。
一方、早解き訓練だけですと、今度は今回の問題セットのように手が届きそうだけど自分のレート帯的にちょっと難しい... みたいな問題に対する適応力が上がっていきません。
···という過去の反省から二本立てにしてみました。
早速結果が出たかどうかは定かではない、というかそんなすぐには成果にはつながらないと思いますが、悪くない方針だなと思っているのでしばらく続けてみようともいます。
AtCoder Daily Training はバーチャル参加なら自分の好きな時間に始められますし、その一方で適度な緊張感もあり終了後に他の人とのパフォーマンスの比較もできて良いですね。