# ABC341 振り返り
- [トヨタ自動車プログラミングコンテスト2024#2（AtCoder Beginner Contest 341） - AtCoder](https://atcoder.jp/contests/abc341)
- ABCD 4完 (1111) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc341)
![[スクリーンショット 2024-02-18 10.47.21.png]]
![[スクリーンショット 2024-02-18 10.48.25.png]]
ABC341 でした。
- A (灰) ··· 1 と 0 を交互に出力。`cycle` を使いました
- B (灰) ··· 貪欲に、左から右に値を渡せるだけ渡す
- C (茶) ··· グリッドを全頂点から全探索。定数倍に気をつける
- D (緑) ··· 包除原理 + 二分探索
- E (水, upsolve) ··· セグメント木。この問題の反転操作は境界付近にしか影響を与えないのを利用
という問題セットでした。
今回は序盤の問題に対する配点が普段よりも低めでした。早解き回になるかと思いましたが案外そうでもなく、 C も D も反射では解けない問題でした。知識で解けた ABC340 よりもやや難しかったかなと思います。
C で 1度 TLE しつつもリカバリして D まで調子よく解いていましたが、E は遅延伝搬セグメント木での解法に執着しすぎて、解けず。想定解法通り、セグメント木で解くほうが簡単でした。
----
## [A - Print 341](https://atcoder.jp/contests/abc341/tasks/abc341_a)
1 と 0 を交互に、指定された文字数分だけ出力します。
Haskell にはまさに値を交互に出力する `cycle` 関数があります。遅延評価で $2 \times N + 1$ 個生成すれば OK。
ところで問題文には 「`0` と `1` が交互に並んだ文字列を出力せよ」とありますが、実際は `1` → `0` の順です。それに気づかずサンプルを動かして「あれ?」となりました 🐤
```haskell
main :: IO ()
main = do
n <- getInt
putStrLn $ map intToDigit $ take (2 * n + 1) $ cycle [1, 0]
```
## [B - Foreign Exchange](https://atcoder.jp/contests/abc341/tasks/abc341_b)
この問題も、問題文を読み解くのに時間がかかりました。10分近く、問題文の解釈に悩んだと思います。
要するに、 $A_i$ から $A_{i + 1}$ へ値を渡せるが、そのとき渡せる値の単位が決まっているという問題です。
問題文を理解してしまえば難しいことはなく、$A_N$ にできるだけ多く値を移したいのでいちばん左から貪欲に移せるだけ右に移していけば良いです。DP の計算っぽく、現在地の値を次に配って、を手続き的に繰り返します。
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
xs <- replicateM (n - 1) getTuple
dp <- newListArray @IOUArray (1, n) as
for_ (zip [1 .. n - 1] xs) $ \(i, (s, t)) -> do
x <- readArray dp i
updateArray (+) dp (i + 1) ((x `div` s) * t)
print =<< readArray dp n
```
Haskeller 的には
```haskell
main :: IO ()
main = do
n <- getInt
as <- getInts
xs <- replicateM (n - 1) getTuple
print $ foldl' (\acc (a, (s, t)) -> (acc + a) `div` s * t) 0 (zip as xs) + last as
```
の方が、いいですかね。
どんなときも Haskeller の矜持を貫きたいところですがまだ精進が足りません。
## [C - Takahashi Gets Lost](https://atcoder.jp/contests/abc341/tasks/abc341_c)
定数倍に気をつけつつ、全頂点から全探索する問題。
グリッドは $500 \times 500 = 250000$ 程度の中途半端なサイズ。移動距離も最大で $500$ 程度とこれまた半端です。
全探索すると $500 ^3 = 125000000$ 、つまり $O(10^8)$ 程度の計算量ですが、$O(10^8)$ 程度ならがんばれば間に合う、というのは typical90 の [055 - Select 5（★2）](https://atcoder.jp/contests/typical90/tasks/typical90_bc) を思い出します。制約時間が 3秒というのもヒントですね。
BFS や DFS で効率化する方法はないかと思いましたが、すぐには思いつかない。C 問題だし、そんなに難しくはないだろうとメタ読みして全探索に振り切りました。
最初 `takeWhile` をせずに `mapAccumL` で、海に入ってもそのまま計算を続ける実装にしてましたがそれでは TLE しました。真面目に `takeWhile + scanl` にして AC。コンテスト後に toyboot さんが調べてくださいましたが、どうもサンクが溜まって間に合わない感じでした。
計算量ぎりぎりの問題なのに横着したのはよくなかったです。なんとなくで全探索で実装開始してしまい、TLE もらうまでさぼっちゃ駄目なことを意識出来てませんでした。
```haskell
lrud@[left, right, up, down] = [(0, -1), (0, 1), (-1, 0), (1, 0)]
resolve n grid t v = do
let res = takeWhile (\u -> grid ! u /= '#') $ scanl f v t
length res == n + 1
where
f pos d = case d of
'L' -> pos `add2` left
'R' -> pos `add2` right
'U' -> pos `add2` up
'D' -> pos `add2` down
main :: IO ()
main = do
[h, w, n] <- getInts
t <- getLine
grid <- getCharGrid ((1, 1), (h, w))
let res = [1 :: Int | (v, c) <- assocs grid, c == '.', resolve n grid t v]
print $ sum res
```
ところで、ABC339 で上下左右の方向定義を間違えてしまい沼った反省から
```haskell
lrud@[left, right, up, down] = [(0, -1), (0, 1), (-1, 0), (1, 0)]
```
とラベリングした盆栽を用意するようにしました。上記は $(h, w)$ 形式ですが $(x, y)$ 形式対応のものも別途用意していて、スニペットから補完で出せます。ちょっとしたことですが、本番中に慌てているときには効果てきめんでした。
## [D - Only one of two](https://atcoder.jp/contests/abc341/tasks/abc341_d)
「$N$ か $M$ で割り切れる数の個数を数える」というのは包除原理で考えると楽ですね。
$N$ で割り切れる数の個数、$M$ で割り切れる数の個数の合計から $N$ でも $M$ でも割り切れる数を引く。
$N$ でも $M$ でも割り切れる数、は $N$ と $M$ の最小公倍数 ($LCM$) です。
こういうときは丁寧にベン図を書くと良いです。
ベン図を書かずに頭の中だけでやってると $2$ 回引く必要があるのを忘れがち。(過去にそれで痛い目に遭ってる)
![[IMG_0583.jpeg|600]]
これで上界までの間に目的の数が何個あるか計算できるので、あとは二分探索です。
```haskell
main :: IO ()
main = do
[n, m, k] <- getInts
let l = lcm n m
(_, ok) = bisect (0, maxBound) (\x -> x `div` n + x `div` m - 2 * (x `div` l) >= k)
print ok
```
本番のときは上界の見積もりに不安があり多倍長整数を使いたいがため直接二分探索するのではなく $LCM$ での周回数を求めて云々、とやってました。おかげでちょっと沼って ChatGPT に助けを借りました。
上界は適当に `maxBound` にしても通ります。正確には $2 \times 10^{18}$ だそうです、この辺の見積もり精度を上げたいですね。
## [E - Alternating String](https://atcoder.jp/contests/abc341/tasks/abc341_e) (upsolve)
与えられた操作を素直にシミュレーションすると、区間更新・区間取得になるので、「すわ Lazy Segtree や!」と決めてかかりましたが、これが落とし穴でした。遅延伝搬セグメント木でも解けるのですが、変なモノイドを載せる感じになり難しくなります。案の定沼って、駄目でした。
一方、観察してみるとクエリ $1$ の反転操作は $L$ と $R$ の境界付近にしか影響を与えません。
なぜなら良い文字列は反転しても良い文字列のままだし、逆も然りだからです。
これに気づけば一点更新・区間取得でよくなり、セグ木に載せる値も Bool となって簡単になります。
隣の文字と異なるか、異ならないかを Bool でセグ木に載せて管理します。
反転する操作では区間の端と端が、そのたび、Bool が反転します。
良い文字列になっているかどうかは、`(&&)` を結合演算とするモノイドとみなしてやれば、区間取得で判定できます。わかってしまえば、シンプルです。
ここ2回、遅延伝搬セグメント木が続いてたので、こういうはやとちRemixを狙っての出題だったのかもしれないですね。
強者のみなさんは、それでも遅延伝搬セグメント木で解ききっていましたが...
```haskell
main :: IO ()
main = do
[n, q] <- getInts
as <- getLine
qs <- replicateM q getInts
tree <- newListST @IOUArray (&&) True (0, n) $ True : zipWith (/=) as (tail as) ++ [True]
for_ qs $ \case
[1, l, r] -> do
updateST tree (l - 1) not
updateST tree r not
[2, l, r] -> printYn =<< rangeQueryST tree l r
_ -> error "invalid"
```
----
## 感想など
パフォーマンス 1111 のゾロ目で、レートは少し上がって 995 になりました。
昨年 12初旬が Highest 994 で、ようやく元に戻しました。が、直近目標の 1000 には惜しくも届かず 😂
E 問題に一時間近く時間を確保できたにも関わらず解けなかったのは、悔しいですね。
今週、遅延伝搬セグメント木の実装を改良していたこともあり、遅延伝搬セグメント木🧠 になっちゃってました。
解法決め打ちで考察は割ととアンチパターンなので、気をつけたいところです。
ここ数回は調子は悪くないです。
ただし、この調子でいくとそろそろまた調子にのって爆死しかねないので、しっかり精進して気を引き締めていこうと思います。