# ABC363 振り返り
- [AtCoder Beginner Contest 363 - AtCoder](https://atcoder.jp/contests/abc363)
- ABCD 4完 (1106) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc363)
![[スクリーンショット 2024-07-21 12.19.31.png]]
ABC363 でした。
- A (灰) ··· 次に $100$ の倍数になるのにあと幾つ必要か? なので $\bmod 100$ を使う
- B (灰) ··· 制約が小さいのでシミュレーションで間に合う
- C (茶) ··· 鬼門。permutations で全列挙すると重複があり TLE する。Haskell で書いて C++ に ChatGPT で変換させて通した
- D (緑) ··· 桁ごとに回文数の数は $O(1)$ で求められる。$N$ が何桁かをつきとめて、回文数を生成。左半分のみに着目すると楽
- E (水, upsolve) ··· 海を超頂点とし、Union-Find で沈んだマスを連結していく。都度超頂点の連結成分の頂点数を数える
Haskell には C 問題が鬼門で、苦戦しました。
Haskell で順列といえば `permutations` ですが、これをいつも通りに使うと TLE します 😱
結論 `next_permutation` がある C++ なら比較的スムーズに実装できる問題のようで、Haskell で実装したものを ChatGPT で C++ に変換して通しました。
日頃、C++ に変換して通すような荒技を使ったことがなかったので、そういう発想に至るまでに時間を要しました。
## [A - Piling Up](https://atcoder.jp/contests/abc363/tasks/abc363_a)
丁寧に場合分けしても良いですが、実装が面倒。
少し逡巡したところ、求めるのは $N$ にあと幾つ足したら $100$ の倍数になるか、ということに気がつきました。
```haskell
main :: IO ()
main = do
r <- getInt
print $ 100 - (r `mod` 100)
```
## [B - Japanese Cursed Doll](https://atcoder.jp/contests/abc363/tasks/abc363_b)
A 問題のようにうまく計算する方法はないかと少し考えましたが思い浮かばず。
よくみると制約が小さいので、ナイーブにシミュレーションすればいいことに気がつきました。
```haskell
main :: IO ()
main = do
[n, t, p] <- getInts
ls <- getInts
let xs = takeWhile ((< p) . countBy (>= t)) $ iterate (map succ) ls
print $ length xs
```
## [C - Avoid K Palindrome 2](https://atcoder.jp/contests/abc363/tasks/abc363_c)
$S$ の文字を並び変えて作ることができる文字列のうち、長さ $K$ の回文を部分文字列として含まないものの個数を求める。
文字列 $S$ の長さ $N$ が高々 $10$ 文字と小さい。一見すると、よくある C 問題レベルの典型問題です。
いつもどおり `permutations` で $S$ から文字列をすべて生成、長さ $K$ の回文があるかどうかすべてチェックすればよいと考えました。
で `nubOrd $ permutations s` で全部生成して··· というコードを書いてみたところ入力例 3 で、ローカル実行でも 3秒強かかる。
むむ··· ちょっとあやしいとおもいつつ送信したら案の定 TLE です。
そこから定数倍を削ろうとあれこれ試行錯誤してみましたが、期待通りの速度は得られず。いったん飛ばして D に行きました。
最終的には Haskell で書いた実装を ChatGPT で C++ に変換し、1961 ms でギリギリ通しました。疲れた。
何がだめだったのか。
Haskell の `permutations` を使うと同じ文字でも区別して順列を生成します。つまり `permutations` では被りが出ます。
その被りを取り除くのに `nubOrd` するわけですが、この重複した順列を生成してユニークをとる、という富豪的な実装では計算量的に間に合わないように問題が作られていたようです。C 問題にしては、シビアですね。
C++ の `next_permutation` なら重複が出ないよう順列を走査できます。それを使うのが想定解だったようです。
ところで Python には more_itertools に `distinct_permutations` 関数が実装されていて、これを使えば Python でも TLE せずに通るらしい。
Haskell でも `distinctPermutations` を実装して、`nubOrd . permutations` と差し換えてみたところ、通りました。
当初は C++ に変換しないと通らない問題だなんて「なんて問題だ! 」(小峠) と思いましたが、結果的にはとても勉強になりました。
```haskell
distinctPermutations :: (Ord a) => [a] -> [[a]]
distinctPermutations vs = permute (length vs) (sort vs)
where
permute 0 _ = [[]]
permute _ [] = []
permute n xs = [x : ys | (x, xs') <- select xs, ys <- permute (n - 1) xs']
select :: (Ord a) => [a] -> [(a, [a])]
select [] = []
select (x : xs) = (x, xs) : [(y, x : ys) | (y, ys) <- select xs, y /= x]
substringsK :: Int -> String -> [String]
substringsK k s = [substring i k s | i <- [0 .. length s - k]]
containsPalindrome :: Int -> String -> Bool
containsPalindrome k s = or [s' == reverse s' | s' <- substringsK k s]
main :: IO ()
main = do
[n, k] <- getInts
s <- getLine
let ans = countBy (not . containsPalindrome k) (distinctPermutations s)
print ans
```
## [D - Palindromic Number](https://atcoder.jp/contests/abc363/tasks/abc363_d)
$N$ 番目の回文数を求めるわけですが $N \leq 10^{18}$ と大きいので、全回文数を生成することはできません。
ある桁の回文数は、よくよく考えると、比較的簡単に数え上げることができます。
これにすぐ気づけたのが良かったです。
たとえば $2$ 桁の場合 $11, 22, 33, 44, 55 \ldots$ と $9$ 種類しか回文数はありません。
回文の構造上、前半半分で取り得る数の個数がそれになります。
ChatGPT に $k$ 桁の回文数を数え上げる関数を聴いたら `countPalindromes` が即座に求められました。
ここまでわかればあとは、$1$ 桁目から徐々に桁数を上げていって $N$ 番目は何桁の回文数になるかをつきとめ、その桁数の回文数を生成することにフォーカスすれば良いです。
ここでもまた、前半半分だけ生成して折り返すようにすると、ただの足し算になって簡単でした。
```haskell
-- >>> generate 46 3 19
-- "363"
-- >>> generate 1 1 0
-- "0"
generate :: Int -> Int -> Int -> String
generate n k acc
| even k = s ++ reverse s
| otherwise = s ++ tail (reverse s)
where
start = if k == 1 then 0 else 10 ^ (k `ceildiv` 2 - 1)
remain = n - acc - 1
s = show (start + remain)
-- | 桁数 k の回文数の数
-- >>> countPalindromes 1
-- >>> countPalindromes 2
-- >>> countPalindromes 3
-- 10
-- 9
-- 90
countPalindromes :: Int -> Int
countPalindromes 1 = 10
countPalindromes k = 9 * 10 ^ (k `ceildiv` 2 - 1)
main :: IO ()
main = do
n <- getInt
let (k, count) = last . takeWhile ((< n) . snd) $ iterate' f (1, 0)
where
f (i, acc) = (succ i, acc + countPalindromes i)
putStrLn $ generate n k count
```
## [E - Sinking Land](https://atcoder.jp/contests/abc363/tasks/abc363_e) (upsolve)
upsolve しました。
いろいろな解法がありそうです。超頂点 + Union-Find を使う方法、ヒープを使う方法の二つを思いつきました。
Union-Find 解法が認知負荷が低く、かつ速度も速かったです。
### 超頂点 + Union-Find
海に接したマスが沈むと、隣接しているマスがどんどん浸食されていくわけですが、あるオブジェクトが他のオブジェクトを巻き込んでどんどん大きくなっていく、というのは Union-Find を彷彿させます。
なお、私はこれをスライムがたくさん結合するのになぞらえて「キングスライムモデル」と呼んでいますが、あまり共感されません。
もとい「海に繋がっているマスは幾つあるか」を Union-Find で表現したいわけです。
海を超頂点とみなして、この超頂点に、海に沈んだマスをどんどん連結していき、適宜超頂点を含む連結成分に含まれる頂点数を求めていく··· というモデルがよさそうです。
$i = 1 \ldots Y$ まで時間を経過させながら、各 $i$ で海に沈むマスを扱っていく。
その処理を効率化するため、$A_{i,j}$ の値ごとにマスの座標をリストにまとめあげる ··· $A_{i,j}$ の値をキーにした転置インデックスを作ります。
$i = 1 \ldots Y$ まで回しながら、転置インデックスから $i$ に対応するマスの座標 $v$ を取り出す。
$v$ が海に接している頂点なら、超頂点に連結する。
また、$v$ の上下左右の頂点 $u$ をみて $A_v \geq A_u$ なら $v$ と $u$ も連結する。
こうすることで、雪だるま式に超頂点と繋がる頂点が増えていき、そのサイズを数えることでその時点で海に沈んだマスの数がわかります。
```haskell
lrud@[left, right, up, down] = [(0, -1), (0, 1), (-1, 0), (1, 0)] :: [(Int, Int)]
main :: IO ()
main = do
[h, w, y] <- getInts
grid <- getIntGrid ((1, 1), (h, w))
let ix = index ((1, 1), (h, w))
n = h * w
g = accumArray @Array (flip (:)) [] (1, 10 ^ 5) [(a, v) | (v, a) <- assocs grid]
s = accumArray @UArray (||) False (0, n - 1) [(ix v, True) | v@(i, j) <- indices grid, i == 1 || i == h || j == 1 || j == w]
uf <- newUF @IOUArray (0, n) (-1)
for_ [1 .. y] $ \i -> do
for_ (g ! i) $ \v -> do
when (s ! ix v) $ unite uf (ix v) n
for_ [u | d <- lrud, let { u = v + d }, inRange (bounds grid) u, grid ! u <= grid ! v] $ \u -> do
unite uf (ix v) (ix u)
size <- getSizeUF uf n
print $ n + 1 - size
```
### ヒープによる回答
こちらの方が想定解法に近いでしょうか。
- 最初に、海に接しているマス $v$ を、優先度 $A_v$ でヒープに入れる
- $y = 1 \ldots Y$ まで時間遷移させながら、ヒープから $y$ 以下の優先度の頂点 $v$ を取り出す。取り出されたものは海に沈んだ頂点。その頂点 $v$ の周辺のマス $u$ を、優先度 $A_u$ でヒープに入れて、$y$ 以下の優先度の頂点がなくなるまで繰り返す。
とする。
BFS やダイクストラ法なんかでやっているようなアプローチですね。
IntPSQ を使うと $y$ 以下の優先度の頂点を全部ヒープからとるのが `atMostView` で簡単に実装できますし、ヒープに値を入れすぎないようある頂点がヒープに既に入っているかどうかをチェックすることもできます。
が、それでもやはり実装がちょっとごちゃつきます。
また速度も遅く、1994ms とぎりぎりで危うい。安心して通すためにはミュータブルなヒープを使うなどが必要そうです。
```haskell
lrud@[left, right, up, down] = [(0, -1), (0, 1), (-1, 0), (1, 0)] :: [(Int, Int)]
main :: IO ()
main = do
[h, w, yx] <- getInts
grid <- getIntGrid ((1, 1), (h, w))
let ix = index (bounds grid)
vs0 = [v | v@(i, j) <- indices grid, i `elem` [1, h] || j `elem` [1, w]]
q0 = IntPSQ.fromList [(ix v, grid ! v, v) | v <- vs0]
sunk <- newArray @IOUArray (0, h * w - 1) False
foldForM_ (h * w, q0) [1 .. yx] $ \(!acc, q) y -> do
context@(!acc', _) <- loop grid y sunk (acc, q)
print acc'
return context
loop grid y sunk (!acc, q)
| null xs = return (acc, q')
| otherwise = do
for_ xs $ \(i, _, _) -> do
writeArray sunk i True
q'' <- foldForM q' xs $ \qy (_, _, v) ->
let us = [u | d <- lrud, let u = v + d, inRange (bounds grid) (v + d)]
in foldForM qy us $ \q u -> do
flag <- readArray sunk (ix u)
if not flag && not (IntPSQ.member (ix u) q)
then return $ IntPSQ.insert (ix u) (grid ! u) u q
else return q
loop grid y sunk (acc - length xs, q'')
where
ix = index (bounds grid)
(xs, q') = IntPSQ.atMostView y q
```
## 感想など
やはり 1100 台から水色の 1200 までは壁が厚いです。
今回の C 問題は、私からみたら雲の上の存在であるような他の Haskeller の諸先輩方も軒並みやられていて、ある意味興味深い問題だったと思います。
そんな中、苦労しつつ C も D も解いたのですがそれでもパフォーマンスは 1106 、レートは ± 0 に終わりました。
E を解きたかったですね 😭
今回、C が TLE でだめだったので飛ばして D に行き、D を解いて一度 E に着手しました。この時点ではまだ 60分以上時間が合ったので、そのまま E を解ききる、という戦術もあったかもしれず。
が、E を考察しながらも「いや、一度 C に戻るか?」みたいな思考が邪魔をし続けて集中できず、C に戻って通しました。
その時点でのこり時間が少なくなっており、Union-Find 解法は思いついたもののまとめ上げきれずゲームーオーバーでした。
こういう局面での集中力のコントロールは難しいですね。
···まあ、焦らずコツコツやっていきます。継続は力なりです。
1100 台前後のパフォーマンスが安定的に出せるようになってきたということは、精進していればいずれこれが 1200 になる日もくるでしょう。
あと ChatGPT との付き合い方を少し考えたほうがよさそう。
今回のように咄嗟の機転で C++ に変換するとか、簡単なサブ問題を解かせるなどのため、常に横において戦うのに慣れていくほうが他のプレイヤーに遅れをとらないために必要そうです。
ただし ChatGPT と解法について対話していると思考が深まらずただ時間を無駄に溶かすことも多いので、依存しすぎない程度に手段として使っていくバランスが求められるとは思います。
なお先週は、未履修だった全方位木DP の実装を盆栽していました。
少し時間がかかりましたが、おかげでいい実装ができたので全方位木DP の過去問を無双しようと思います。
次回出たときには瞬殺できるよう鍛えます。
基礎的な問題への対応力はそこそこ担保できていそうなので、引き続き、高度典型力を上げていこうと思います。