# ABC339 振り返り
- [日本レジストリサービス（JPRS）プログラミングコンテスト2024（AtCoder Beginner Contest 339） - AtCoder](https://atcoder.jp/contests/abc339)
- 成績 ABCD 4完 (1063) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc339)
![[スクリーンショット 2024-02-04 12.40.24.png]]
![[スクリーンショット 2024-02-04 12.49.11.png]]
ABC339 でした。
B で時間がかかりすぎて一時はどうなるかと思いましたが、終盤で水色diff の D を通してパフォーマンス 1063 で終えました。終わってみればまずまずの結果です。
- A (灰) ··· `takeWhileEnd (/= '.')` で後ろからみる
- B (灰) ··· 現在地点、方向を状態に持って問題文のとおりに配列を更新していく。90度回転は `(i, j) -> (j, -i)`
- C (灰) ··· 累積和をとって途中に負の値がでたら、その最小値で最終結果を 0 基準に直す
- D (水) ··· プレイヤー1 の座標とプレイヤー2の座標の4次元を状態空間にして BFS。速度が問われる
- E (緑) ··· (upsolve) セグメント木で LIS を求める要領でやる。区間max
でした。
B でのミスは、なかなか間違いに気づくことができずに30分以上溶かしてしまいました。$(-1, 0)$ と書くべきところを $(0, -1)$ にしていたという、めちゃくちゃしょうもない間違いでした 😅
E はちょうど今週、セグメント木で LIS を求める計算を知ったところで、解きたかったですが残り時間 10分で落ち着いて考察することができず。惜しかったです。
----
## [A - TLD](https://atcoder.jp/contests/abc339/tasks/abc339_a)
`.` の位置まで後ろからみて出力
```haskell
main :: IO ()
main = do
s <- getLine
putStrLn $ takeWhileEnd (/= '.') s
```
## [B - Langton's Takahashi](https://atcoder.jp/contests/abc339/tasks/abc339_b)
グリッドを時計回り、反時計回りに90度向きを変えながら移動し、都度現在のマスを書き換える。
グリッドはトーラス状になっていて、グリッドサイズを超えるマスに移動したら反対側にワープする。
(現在地, 方向) をコンテキストに持って、操作を $N$ 回繰り返しながら配列を更新していけば OK です。
トーラス状のところは `mod` をとることで表現できます。`mod` を取るので 0 based インデックスにしておくと楽です。
··· なんでこれで30分沼ったか。実装してるうちにグリッドの縦横が $H, W$ 形式と $X, Y$ 形式が頭のなかで曖昧になって、方向の初期値を正しくは $(-1, 0)$ のところ $(0, -1)$ にしているのにずっと気がつけませんでした。プログラミングしてるとなんかこう、一時的に盲目的になることがありますよね。できれば ABC 本戦でそうなってほしくないところです... 😓
いつまでもバグが取れないので飛ばして C に行って、戻ってきたらあっさりわかりました。頭を一度リセットする必要があったようです。
```haskell
main :: IO ()
main = do
[h, w, n] <- getInts
as <- newArray @IOUArray ((0, 0), (h - 1, w - 1)) '.'
let f (pos, (i, j)) _ = do
c <- readArray as pos
if c == '.'
then do
writeArray as pos '#'
let d' = (j, - i)
pos' = bimap (`mod` h) (`mod` w) $ pos `add2` d'
return (pos', d')
else do
writeArray as pos '.'
let d' = (- j, i)
pos' = bimap (`mod` h) (`mod` w) $ pos `add2` d'
return (pos', d')
foldM_ f ((0, 0), (-1, 0)) [1 .. n]
printCharGrid =<< (freeze as :: IO (UArray (Int, Int) Char))
```
## [C - Perfect Bus](https://atcoder.jp/contests/abc339/tasks/abc339_c)
問題文だけを見てるとバスに最初何人乗っていたかを当てる難しそうな問題に感じますが、入力例 $1$ をみるとすぐにわかります。
乗り降りを累積和する過程で負の値が出てくる場合、最初から何人か人が乗車していたことになるので、その分が $0$ になるように直してやればよいです。
```haskell
main :: IO ()
main = do
_ <- getInt
as <- getInts
let s = sum as
as' = scanl' (+) 0 as
if all (>= 0) as'
then print s
else print $ s + abs (minimum as')
```
## [D - Synchronized Players](https://atcoder.jp/contests/abc339/tasks/abc339_d)
今回の山場です。$N \times N$ のグリッドですが $N$ が高々 $60$ と小さいので何やら怪しいですね。
はじめは他方のプレイヤーを最適な位置に動かして、もう一方がそこに到達するまでの最短距離を測る··· みたいな貪欲法的な戦略を考えましたが、それだとしたらこんなにグリッドが狭くある理由にならないし、最適にならないケースは少し考えるとすぐに見つかってしまいます。網羅的に探索するアプローチが必要そうです。
雰囲気的にはグリッドBFSなので、それに狙いを定めて考察してみます。
プレイヤー1 とプレイヤー2 の $2$ つの現在地を BFS する... と考えるとだいぶ難しそうですが、プレイヤー1とプレイヤー2 は常に同じ方向にしか動けないという制約をうまく使うことで単純化できることに気がつきます。
通常のグリッドBFS の場合、状態空間は `((1,1), (n, n))` の 2次元ですが、二人分の座標があることを考慮して `(((1, 1), (1, 1)), ((n, n), (n, n)))` という4次元にします。4次元BFS ですが、状態遷移のときは方向は二人とも同じ方向、4方向にしか動きません。よって $f(v, u) → [(v, u)]$ という状態遷移で、$(v, u)$ 一組に対して 4つの $(v, u)$ が返ってくるという遷移になります。これなら計算量的にも嵩まないし、状態遷移の記述も簡単です。
これで BFS して、二人が同じマスにいるケースの最小距離を求めれば OK です。
例によって自分の BFS 盆栽は、[Haskell の Array](https://zenn.dev/naoya_ito/articles/87a8a21d52c302) の特長を活かして盆栽をいじらずに多次元に拡張できるようにしているので、状態遷移関数を書いて BFS 関数に渡すだけです 🐸
```haskell
reachable grid v
| not (inRange (bounds grid) v) = False
| grid ! v == '#' = False
| otherwise = True
f grid (v, u) =
[ (v'', u'')
| d <- [(1, 0), (0, 1), (-1, 0), (0, -1)],
let v' = v `add2` d
u' = u `add2` d
v'' = if reachable grid v' then v' else v
u'' = if reachable grid u' then u' else u
]
main :: IO ()
main = do
n <- getInt
grid <- getCharGrid ((1, 1), (n, n))
let [p1, p2] = [v | (v, c) <- assocs grid, c == 'P']
let dist = bfs' (f grid) maxBound (((1, 1), (1, 1)), ((n, n), (n, n))) [(p1, p2)]
ans = minimum [dist ! (v, v) | v <- range (bounds grid)]
print $ bool (-1) ans (ans /= maxBound)
```
··· と、ここまではよかったんですがキューに `Data.Sequence` を利用している版では TLE してしまいました 😱
$O(N^4)$ ということもあり結構ギリギリな問題だなと思い、より速い cojna さんの高速なキューの実装である `Data.Buffer` を使ったバージョンに切り替えてなんとか AC。危なかったです。
こういう1ペナはもったいないので、常時 `Data.Buffer` 版を使うように変更するのを検討します。
## [E - Smooth Subsequence](https://atcoder.jp/contests/abc339/tasks/abc339_e) (upsolve)
ぱっと見で DP ですね。
部分列に対してある $A_i$ を入れるか入れないか、を考える。ナップザック問題の要領になります。
状態空間としては $A$ に登場する最大の整数のサイズ用意します。$5 \times 10^5$ の最大空間を用意してしまってもよいです。
![[IMG_0537.jpeg|600]]
とある $A_i$ を部分列につかう場合、$A_i - D$ から $A_i + D$ までの区間から、それまでの最大部分列長をもらってくることができます。区間でもらうので、区間取得ができれば計算が効率的にできる。というわけでセグメント木です。
実はこの問題は知っていれば典型な問題でした。
最長増加部分列長 (LIS) は二分探索で計算するのが基本ですが、セグメント木を使って求める方法があります。この問題は、そのセグメント木で LIS を求める計算と良く似た問題になっています。実際、[D - Flat Subsequence](https://atcoder.jp/contests/abl/tasks/abl_d) という類題 (というかほぼ同じ問題) が ACL Beginner Contest の問題にあり、解いたことある人も多いようです。
```haskell
main :: IO ()
main = do
[_, d] <- getInts
as <- getInts
let k = maximum as
dp <- newListST @IOUArray (k + 1) max 0 $ replicate (k + 1) (0 :: Int)
for_ as $ \a -> do
let l = max 1 (a - d)
r = min k (a + d)
x <- rangeQueryST dp l (r + 1)
updateST dp a (const (x + 1))
print =<< rangeQueryST dp 1 (k + 1)
```
## 感想など
今回の B 問題のようなミスをときどきやってしまいます。
解法がわからないわけではなく、実装の方で細かい間違いをしている。その間違いが細かいがゆえになかなか自分で気がつくことができない... というミスです。緊張がまだ解けてないときにこれをやると、同じところをぐるぐるして抜け出せなくなってしまいます 😂
こういうミスをしないようにと、毎日 ADT をやって実装の正確性を上げようと訓練していますがまだ十分ではないようです。
```
-- (h, w) のとき
upward = (-1, 0)
downward = (1, 0)
left = (0, -1)
right = (0, 1)
```
こういう定義を常に用意して脳死で大丈夫にするというのは、ありかもしれないです。考えます。
緊張しているところでミスをしてはまってしまったわけですが、とはいえ、この緊張度合いは以前に比べるとだいぶ抑えられてはいます。
- 金曜の夜以降、土曜の夜に向けて十分な休息 (= 睡眠・運動・日光浴・食事) をとる
- 定期的に有酸素運動する。だいたい2日に1度は必ず 30〜40分
- 当日は本番開始より数時間前に昼寝して、起きたら運動
- 土曜日日中は (あまり) 競プロしない
- 土曜日はコンテストが終わるまで SNS を遠ざける。他人との繋がりに鈍感になる。他人の目を気にしない精神状態を作る
- 本番前にはカフェインを摂取しない。緊張しがちな自分には覚醒作用がマイナスに働くため
などの積み重ねにより、本番向けに精神状態を調整できるようになってきました。
本番でちゃんと 100% の力を発揮できるようにする、というのも精進の一つ... むしろ半分ぐらいそれが占めるのではと思うようになりました。なんとこれのおかげで、健康診断の結果が改善されました😉