# ABC354 振り返り
- [パナソニックグループ プログラミングコンテスト2024（AtCoder Beginner Contest 354） - AtCoder](https://atcoder.jp/contests/abc354)
- ABC3完 (Unrated 参加)
![[スクリーンショット 2024-05-19 11.52.54.png]]
ABC354 でした。
少し体調が芳しくなかったので、Unrated 参加にしました。
Rated の緊張感がなかったこともあってか案の定、集中できず ABC の3完でした。
E は順位表をみてもしやと思い ChatGPT に投げたら通っただけなのでノーカンです。
- A (灰) ··· $2^0, 2^1 \dots$ の累積和を $\leq N$ の間とる
- B (灰) ··· やるだけ。 $T \mod N$ を計算して、対象のメンバーを特定する
- C (茶) ··· $A_i$ で降順にソートして $C$ の累積 min を取り、それを上回らない $C_i$ のみ残す
- D (水, upsolve) ··· 原点からのケースだけ考えれば良い。$x$ 方向は $\mod 4$ 、$y$ 方向は $\mod 2$ で同じパターンを繰り返すのを利用して計算。その後、矩形の部分領域計算を行う
- E (水, upsolve) ··· 後退解析 + bitDP
でした。
D は初見で難しそうと思って手をつけなかったのですが、やってみたらそうでもなかったです。
図形の問題をみると難しいと思い込んでしまうのは悪い癖です。
E は再帰でやりましたが、途中でメモ化が必要なことに気づきゲームオーバー。
後退解析のゲーム問題は慣れが必要ですが、まだまだです。
## [A - Exponential Plant](https://atcoder.jp/contests/abc354/tasks/abc354_a)
$2$ の累乗の累積和を $\leq H$ の間分取り続けて回数を数える、で OK です。
$2^1$ から始めてしまい 1ペナもらいました 😅
```haskell
main :: IO ()
main = do
h <- getInt
let res = takeWhile (<= h) $ scanl' (+) 0 [2 ^ i | i <- [0, 1 ..] :: [Int]]
print $ length res
```
## [B - AtCoder Janken 2](https://atcoder.jp/contests/abc354/tasks/abc354_b)
割とやるだけです。
$C_i$ の総和 $T$ をもとめて $\mod N$ をとる。それをインデックスにして辞書順に並べたユーザー一覧を参照する。
```haskell
main :: IO ()
main = do
n <- getInt
xs <- replicateM n $ auto @(BS.ByteString, Int)
let (ss, cs) = unzip xs
BS.putStrLn $ sort ss !! (sum cs `mod` n)
```
## [C - AtCoder Magics](https://atcoder.jp/contests/abc354/tasks/abc354_c)
より強く安いカードだけを残したい。強さ、コストで下位互換 (強さが弱くてコストが高い) のカードは全部廃棄する。
とりあえず、入力の並び順には意味がないので、こういうときはおもむろにソートしてみるのが良いです。
二値あるので強さ $A$ でソートします。より強い方に関心があるので降順。
入力例 $1$ だと入力件数が少ないので、$(5, 4)$ と $(4, 5)$ も追加した入力をソートしてみます。
すると以下のようになります。
```
A 5 4 3 2 1
C 4 5 2 4 1
```
$A$ の行に着目すると、当たり前ですが、一番左に最強の $5$ があります。
この並び順を維持さえできていれば、ある $i$ に対し、それよりも強いカードは必ず左に存在していることになります。
この並び順のまま $C$ について考えてパターンを見つけることができるなら、$A$ について考えることが少なくて済みそうです。
というわけで $C$ を睨んでみます。コストの観点でみるとより安いものを残したいわけです。
ある $C_i$ からみたときにそこから左により安いカードがあるなら、そのカード $i$ はコストの観点で捨てる候補になり得ます。
ここで先に $A$ でソートしていることが役に立ちます。 $i$ より左にあるカードは、強さが $i$ より強いことは確定しているので $C_i$ をみて、$C_i$ よりも安いカードが左にあるなら $i$ は捨てていいことが確定します。
つまり、$A$ で降順にソートしてその順を維持している限り、 $C$ だけで判定できることを意味します。
というわけで
```
C 4 5 2 4 1
```
だけに着目して「自分より左に自分より小さな数があるか」をみていくわけですが、これは累積 min で分かります。
だいたい「自分より左に小さい / 大きい」とか「自分より右に小さい / 大きい」みたいな話が出てきたら累積 min / max (あるいは BIT / セグメント木による区間クエリ) で判定できます。
というわけで $A$ でソートし、$C$ の累積 min をとって突合し条件を満たすもの ··· $C_i$ がその時点の累積 min を上回らない $i$ だけ残す、で OK。
```haskell
main :: IO ()
main = do
n <- getInt
xs <- replicateM n getTuple
let cs = [(i, c) | (i, (_, c)) <- sortOn' (Down . fst . snd) (indexed 1 xs)]
s = scanl1 (\(_, acc) (i, c) -> (i, min acc c)) cs
res = [i | ((i, ci), (_, x)) <- zip cs s, ci <= x]
print $ length res
printList $ sort' res
```
## [D - AtCoder Wallpaper](https://atcoder.jp/contests/abc354/tasks/abc354_d) (upsolve)
[ABC331 D - Tile Pattern](https://atcoder.jp/contests/abc331/tasks/abc331_d) と同様の考え方で解くことが出来ます。
この問題の厄介なところは入力で与えられる $A, B, C, D$ による矩形領域が、広い図形の中の中途半端なところで開始終了するところです。
原点からだけ考えるので良いなら、それほど難しくはないのです。
が、矩形の部分領域は二次元累積和の要領で計算することができて、その簡単な「原点からの計算方法だけ考える」ことで解くことができます。
```haskell
-- 矩形部分領域計算の抽象
rectRangeQuery :: (Num a1) => ((a2, b) -> a1) -> (a2, b) -> (a2, b) -> a1
rectRangeQuery f (a, b) (c, d) = f (c, d) - f (a, d) - f (c, b) + f (a, b)
```
こういう矩形の部分領域を計算する抽象があれば、そこに渡す関数 $f(x, y)$ を考えて実装するだけで良いです。
evima さんの公式解説もしくは ABC331 D の解説に詳しく書いています。
というわけで
- 部分的な領域の計算であることは忘れて、原点 $(0, 0)$ から $(x, y)$ までの計算を関数 $f(x, y)$ として定義する
- それを矩形部分領域計算の抽象に渡す
これでいけます。
$f(x, y)$ をどう計算するかですが、図を入力例 $1$ よりもすこし拡大して用意してみると見えてきます。
![[IMG_1030.jpeg]]
- $x$ 方向は周期 $4$ つまり $\mod 4$ で同じパターンを繰り返している
- $y$ 方向は周期 $2$ つまり $\mod 2$ で同じパターンを繰り返している
というわけで、この縦横を考えると周期 $4$ と周期 $2$ の組み合わせの $8$ パターンを考えれば良さそうです。
$x$ 方向の$\mod 4$ と $y$ 方向の $\mod 2$ を取った値を $(a, b)$ と表すと、
- $(0, 0)$
- $(0, 1)$
- $(1, 0)$
- $(1, 1)$
- ...
- $(3, 1)$
という合計 $8$ パターン。
これの $8$ ケースの寄与数を考えてみます。
答えとして求める数字は面積の $2$ 倍なので、ある $1$ マス全体が塗りつぶされているマスの寄与数は $2$ で、斜めに半分だけ塗られているマスは寄与数 $1$ と考えます。各 $8$ パターンの寄与数はそれぞれ
![[IMG_1031.jpeg|600]]
になりますね。
図をみて数えるだけで表を作ることができます。
あとは原点 $(0, 0)$ から任意の $(x, y)$ の間に、この $(0, 0)$ や $(3, 2)$ のようなパターンがそれぞれ何個ずつ出現するかがわかれば、上記の表により寄与数の合計に写像することができます。それは割り算、剰余と掛け算で計算するだけ、簡単です。
これで関数 $f (x, y)$ ができあがるので、前述のとおり `rectRangeQuery` に渡して計算すれば一丁上がりです。
```haskell
table = listArray @UArray ((0, 0), (3, 1)) [2, 1, 1, 2, 0, 1, 1, 0 :: Int]
f (x, y) = do
let (p, q) = x `divMod` 4
(p', q') = y `divMod` 2
let xs = indexed 0 $ zipWith (+) (replicate 4 p) (replicate q 1 ++ replicate (4 - q) 0)
ys = indexed 0 $ zipWith (+) (replicate 2 p') (replicate q' 1 ++ replicate (2 - q') 0)
sum [table ! (x', y') * (i * j) | (x', i) <- xs, (y', j) <- ys]
main :: IO ()
main = do
[a, b, c, d] <- getInts
print $ rectRangeQuery f (a, b) (c, d)
```
問題に特化した部分のみの高階関数を定義して、既存の抽象に渡して綺麗に解けると気持ちがよいです。
## [E - Remove Pairs](https://atcoder.jp/contests/abc354/tasks/abc354_e) (upsolve)
苦手なゲーム + 後退解析の問題です。
bit DP で解くと楽ですね。
後退解析なので、
- 「ある局面から $1$ 手進めると相手の負けが確定するなら、その手番が勝ち。確定しないならその手番は負け」が基本的な考え方
- ゲーム終盤の方から考えていく。もっとも終盤は、カードが1枚も残っていない局面。その状態からは必ずその手番が負けることが確定する
- カードが残っていない局面から、カードが残っている局面に少しずつ後退していく。最終的には全カードが揃っている状態にまで後退
- 後退した局面から $1$ 手先に進められない (引けるカードがないなら) ··· 負け確定
- 後退した局面から $1$ 手先に進められる ··· このとき進めた局面は既に計算済みであるので、その結果を参照する。$1$ 手先が負けなら相手が負けることを意味しているので、その手番は勝ち
という考え方で解きます。
より詳細にブレイクダウンします。
- $N \leq 18$ 枚のカードのうち、ある局面であとどのカードが残っているのかを集合で表現する (BitSet を使いました)
- ある局面の集合からカードを2枚取り除くのが、その局面から次に一手進めることに相当するが、取り除けるのは選んだ $2$ 枚のカード $i$ と $j$ のうち $A_i = A_j$ もしくは $B_i = B_j$ のケースだけである (また当然だが $i$ と $j$ が集合に含まれていない場合は取り除けない)
- **この 2 枚を取り除いた結果 ··· つまり一手先に進めた結果、敗北局面に遷移する場合、この手番の勝利が確定**
- そうでない場合 (1手進められない / 1手進めたけど相手が勝ち) は負け確定、ということになる。(ここの考え方が後退解析のポイントであり慣れないと混乱するところ···。その局面以降の勝敗はわかっている前提で計算を進めていくので、遷移した結果勝てないなら、その手番は負けが確定する)
前述の通りこの問題の実装は bit DP でやると楽です。
DP での遷移にあたり、毎回、場に残ったカードの2枚組み合わせを全探索する必要がありますが、高々 $_{18}C_{2}$ 回程度なのでナイーブにやっても間に合います。
```haskell
main :: IO ()
main = do
n <- getInt
xs <- listArray @Array (1, n) <
gt; replicateM n getTuple
dp <- newArray @IOUArray (emptyBS, fullBS n) False
for_ [emptyBS .. fullBS n] $ \s -> do
-- この局面で選択できる2組
let pairs =
[ (i, j)
| (i, j) <- comb2 (toListBS s),
let (ai, bi) = xs ! i
(aj, bj) = xs ! j,
ai == aj || bi == bj
]
for_ pairs $ \(i, j) -> do
x <- readArray dp (deleteBS j $ deleteBS i s) -- 1手進めたら False (敗北) なら相手が負け、つまり先手の勝ち
unless x
$ writeArray dp s True
result <- readArray dp (fullBS n)
putStrLn $ bool "Aoki" "Takahashi" result
```
## 感想など
ABC を解いたあと D を飛ばして E に行きましたが、結果的には D の方が簡単でした。
図形問題は考察をある程度進めないと難易度を見積もりにくく、飛ばしがちなのが難しいところですね。
とはいえ E は慣れている人にとっては典型だったようで、順位表をみても E を先に解いた人が、その時点では多かったです。
上位プレイヤーと同じ行動を取ることが必ずしも良い結果に繋がるとは限らない、ということを学びました 😅
E は取り組んでみて WA や TLE が出て結構難しいなあと思ったんですが、順位表をみているとジャイアントキリングしている人がいつもより多かったので、もしやと思ったらやはり ChatGPT 案件でした。
E を ChatGPT に聞いてそのまま投げたらあっさり通って拍子抜けしましたが、自分としてはそれよりも、本番で初めて Haskell ではない Python の実装を投げてみたらばそのジャッジが即座に始まって結果が出たところの方が衝撃でした。
Haskell だとそこで数十秒から場合によっては数分待たされることもあります。
マイナー言語だとジャッジ開始タイミングが遅いことは知ってはいたんですが、実際に体感してみるとあまりにも体験が違うので、AtCoder 運営のみなさんにはこれは仕様ですと割り切って欲しくないなあと、改めて思いました。
他のプレイヤーと差がつくということよりも、ジャッジを待っている間は思考をなかなか切り替えられないというところを気にしています。
生成AI と競技プログラミングの関係については、ここから様々な議論を経てルールその他へ反映されていくのかなと思います。
自分としては競技プログラミングの主目的をレートを上げることにはおいていないので、そこまで気にしていない (今回も Unrated だから投げてみたけど Rated だったらやらなかった) のですが、確かに盛り上がりに水を差すことではあると思います。
なかなか難しい問題ですが、運営のみなさんを信じてこれからの推移を見守りたいと思います。踏ん張りどころだと思うので、頑張って欲しいです。
ところでキーボードを分割キーボードに変更してみましたが、特に支障なく実装することができました。
体調にどの程度良い影響があるかはまだわからないですが、しばらく分割キーボードを常用してみようと思います。