# ABC324 振り返り - [日本レジストリサービス（JPRS）プログラミングコンテスト2023（AtCoder Beginner Contest 324） - AtCoder](https://atcoder.jp/contests/abc324) - 成績 AB2完 (273) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc324) **やらかし回です** パフォーマンス 273 の灰色パフォーマンスと、ワーストパフォーマンスを出してしまいました 😭 ![[スクリーンショット 2023-10-15 11.01.24.png]] コンテスト終了後に C, D, E を upsolve してみましたが、B のつまづきは事故っぽい一方、C, D, E は普通に解けなかったと思います。 「**認めよう! 今はお前が ... 強い!**」 (どんなんときも上から目線 Fate/UBW のギルガメッシュ) 素直に実力不足を認めたいと思います。 今回の C, D, E は、典型にはめて解くというよりは、その場で対応する地力が求められる問題でしたかね。 自分がその辺の地力が弱いのか、そういう問題でも数多くの経験から選択肢を絞り込んでいくパターン認識力が要求されるのか (つまり経験が足りないのか) は定かではありません。とはいえ悩んだところでやることは一緒なので、経験を積んでいけばいつかなんとかなるとでも思っておきましょう。 - A 問題 (灰) ··· ユニークをとって $1$ つになるかどうか判定 - B 問題 (灰) ··· $2$ で割れるところまで割り、$3$ でも割れるだけ割る。再帰 - C 問題 (茶) ··· 編集距離を DP だと間に合わないので、1 文字だけ違う判定すれば良いだけなのを利用して愚直に判定する - D 問題 (緑) ··· permutations を使えそうで使えない。入力からの全列挙ではなく、平方数の方を全列挙して入力と突合するという視点の切り替え - E 問題 (緑) ··· 文字列 $S_i$ を部品と見た時にそれぞれどれぐらいの価値があるかに変換し、二分探索 ざっとこういう問題セットでした。 ここ最近の中では難易度は高めだったんではないでしょうか? フォローしている人たちからの感想戦の様子からそう感じました。 以下、個々の問題の振り返りです。今回は解法の内容に集中します。 ---- ## [A - Same](https://atcoder.jp/contests/abc324/tasks/abc324_a) ユニークとって $1$ 個になれば全部同じ。ユニーク判定は色々方法がありますが、いつも通り集合を使って判定しました。 ```haskell main :: IO () main = do _ <- getInt as <- getInts putStrLn $ if IS.size (IS.fromList as) == 1 then "Yes" else "No" ``` ---- ## [B - 3-smooth Numbers](https://atcoder.jp/contests/abc324/tasks/abc324_b) $N = 2^x3^y$ の形になるかどうか? あまり深く考えず「ははーん、$N$ は $2$ か $3$ の倍数ってことやろ? mod 取ればええやん」とたかを括って提出したところ WA で青ざめました。 なるほど、$N$ を構成する数に $2$ や $3$ 以外が出てはいけないんだな、$2$ で割り切れる間は割り続けて、その後 $3$ に対しても同じことを繰り返す。 結果 $1$ になればいいけどそこで他の数字が出てくるなら $2$ と $3$ 以外にも必要だよ、と判定します。 ```haskell main :: IO () main = do n <- getInt let x = head . dropWhile ((== 0) . (`mod` 2)) $ iterate (`div` 2) n y = head . dropWhile ((== 0) . (`mod` 3)) $ iterate (`div` 3) x putStrLn $ if y == 1 then "Yes" else "No" ``` --- ## [C - Error Correction](https://atcoder.jp/contests/abc324/tasks/abc324_c) (upsolve) $2$ つの文字列が、同じもしくは $1$ 文字だけ違うなら真、という判定が書けるかどうか。 要は二つの文字列の編集距離が $1$ 以下なら真ということなんですが、DP で編集距離を求めると文字列の長さがそれぞれ $N$ と $M$ だったとき $O(NM)$ かかってしまい、この問題では計算量的に間に合わないはず。編集距離で実装したら予想通り TLE しました。ですよね。 同じか $1$ 文字違うだけ、の判定をもっと速く済ませるには? ここで「 $1$ 文字だけ違う」という特殊ケース... つまり $2$ 文字違うか $3$ 文字違かは考えなくて良いことに注目します。 この場合は、二つの文字列を前からと後ろからそれぞれ挟み込んで突合することで「何文字は一致しているか」を調べることができます。 (確か以前に同じような判定問題が一度出ているような...記憶があやふやですが、前からと後ろから調べるのはやったことがあります。) これで二つの文字列が何文字一致しているかはわかるので、これを使ってコメントにある通り、ケースを一致、置換、挿入、削除の4ケースに分けて丁寧に文字列の一致数の条件を実装していけば良いです。条件分岐のところを正確に実装できるかが鬼門ですね。 ```haskell -- 2つの ByteString が同じ、もしくは1文字だけ異なる場合は True isSameOrSimilar :: BS.ByteString -> BS.ByteString -> Bool isSameOrSimilar t s | n == m && a == n = True -- (一致) 長さ同じ、先頭から末尾まで同じ | n == m && a + b == n - 1 = True -- (置換) 長さ同じ、一文字不一致 | n == m + 1 && a + b >= m = True -- (s に1文字挿入) t が一文字余計 | n == m - 1 && a + b >= m - 1 = True -- (s から1文字削除) t が一文字不足 | otherwise = False where (n, m) = (BS.length t, BS.length s) a = length $ takeWhile (== True) $ BS.zipWith (==) t s b = length $ takeWhile (== True) $ BS.zipWith (==) (BS.reverse t) (BS.reverse s) main :: IO () main = do [n, t'] <- words <gt; getLine let n' = read @Int n t = BS.pack t' ss <- replicateM n' BS.getLine let xs = map fst $ filter (\(_, s) -> isSameOrSimilar t s) (zip [1 :: Int ..] ss) print $ length xs putStrLn . unwords . map show $ xs ``` ---- ## [D - Square Permutation](https://atcoder.jp/contests/abc324/tasks/abc324_d) (upsolve) 入力で与えられた数字を並べ替えて、平方数を何個作れるか? 入力で与えられた数字の並び替えなので順列で全組み合わせを生成してしまえば良さそうですが、 $1 \leq N \leq 13$ という制約が微妙なところでして、 $N = 13$ を順列で回すと TLE してしまいます。 そこで視点を変えて、$N$ 桁までの平方数の方を生成してしまいます。 平方数は - $0 \times 0 = 0$ - $1 \times 1 = 1$ - $2\times 2 = 4$ - $3 \times 3 = 9$ と生成していくわけですが、例えば $1000$ ぐらいになると - $1000 \times 1000 = 1000000$ と、元になった整数に対して平方数の桁数がずっと大きくなります。つまり平方数の桁数を制限すれば、全部生成しても大した個数にはならないという直感が働きます。正確にどれぐらいの数になるかの分析は解説に任せるとして、これぐらいの考察でも平方数を生成するのを軸足にすることはできるでしょう。 平方数を生成したら、その生成された平方数を、入力に与えられた整数だけで作れるかどうかをチェックしていきます。 平方数の桁数は $N桁$に満たないものも生成しているので、それらに対しては $0$ 埋めすることで桁数を合わせます (ここが簡単には思いつかない...) その上で入力と、$0$ 埋めされた平方数をソートしてから比較すれば正しく突合したことになります。 ```haskell main :: IO () main = do n <- getInt s <- getLine -- 入力に permutations すると TLE するので視点を変えて、N 桁までの平方数を生成しそれを入力と突合する -- 入力と生成した平方数の比較にあたっては桁数を揃えたい。平方数が N 桁に満たないものは 0 埋めして桁数を合わせる -- 比較はお互いをソートして比較すると簡単 let ns = sort (map digitToInt s) -- N桁以下の平方数を生成して (4, [3, 2, 0, 4]) の形式で持っておく xs = takeWhile ((<= n) . fst) $ map (\i -> let t = toDigits 10 (i * i) in (length t, t)) [0 ..] -- 0埋め及びソート xs' = map (\(k, t) -> replicate (n - k) 0 ++ sort t) xs print $ length $ filter (== ns) xs' ``` --- ## [E - Joint Two Strings](https://atcoder.jp/contests/abc324/tasks/abc324_e) (upsolve) これは難しかったです。こちらの解説がわかりやすかったので参考にしました。 - [ABC324をPythonで解いてみたよ。(A～E問題) - Qiita](https://qiita.com/hyouchun/items/98b53e9dc8cc0b99e1fe#e---joint-two-strings) $N$ 個の文字列 $S$ から任意の二つをチョイスして、それらを結合したとき、その結合された文字列中に $T$ を (連続とは限らない) 部分列として含むチョイスはいくつあるか? - $S$ が $10^5$ 個あるので、$S_i$ と $S_j$ の組み合わせを全探索していては、$O(N^2)$ で全然間に合わないのはすぐわかります - 二分探索か何かを使って、一方を固定してもう一方を探索するとかで計算量を抑える必要があるというのは、ほんのり思い浮かぶところです そんな朧げながらの方針を頭の片隅に置きつつ、 $S_i$ と $T$ の構造を整理してみます。 - $S_i$ は $T$ を構成する部品である。 - $S_i$ と $S_j$ という二つの部品を、左右からくっつけて $T$ を作る。つまり $S_i$ は $T$ の左部品、もしくは右部品になる - 「$S_i$ を $T$ の左部品として使ったときの価値 (整数)」「$S_i$ を $T$ の右部品として使ったときの価値 (整数)」みたいな特徴量に $S_i$ を変換することができたら、左部品 $S_i$ を固定して条件を満たす別の右部品 $S_j$ を二分探索するみたいな手法が使えるかもしれない。 というように道筋を立てていきます。 まあ、これは結論を知った上で書いてるのですが、多くの経験がある人はこういう思考をするのかなーと想像してます。 この方針でいくとき、$S_i$ をどういう特徴量にすればいいか? 「**$S_i$ を $T$ のそれぞれ左部品、右部品として使ったときにそれぞれどれぐらいの役割を果たせるか**」 を定量化できれば良さそうです···$S_i$ が $T$ の何文字を含んでいるか、がキーになりそうですね。ただしここでは部分文字列、つまり文字の出現順も考慮する必要があるのでさらに踏み込んで考える必要があります。 - ある $S_i$ を左部品として使う ··· $S_i$ が $T$ の先頭何文字を賄えるか? → $T$ の先頭何文字を、$S_i$ は (連続とは限らない) 部分文字列として含んでいるか ─ (a) - ある $S_i$ を右部品として使う ··· $S_i$ が $T$ の後ろ何文字を賄えるか? → $T$ の末尾何文字を、$S_i$ は (連続とは限らない) 部分文字列として含んでいるか ─ (b) と考えます。ややこしいので例を見る。 - 例えば $T = bac$ で $S_i = abba$ の場合、(a) の値は $2$ になる。$T$ の先頭 $2$ 文字の $ba$ を、 $S_i =abba$ は、連続とは限らない部分文字列として含んでいる ($S_i$ 中に $b, a$ の順に出てくる) - 例えば $T = bac$ で $S_i = abba$ の場合、(b) の値は $0$ になる - 直感的に考えても、この $S_i$ を $T$ の右部品としては使えないのはなんとなくわかる。$T$ は $c$ で終わっているが、$S_i$ には $c$ がないので。 - 後ろから考えるので $T' = cab$、 $S_i' = abba$ と反転させて考えると、(a) と同じように考えられる。$T'$ は $c$ から始まるが、$S_i'$ には $c$ は含まないので $0$ 後方の方がわかりづらいのでもう一例 - $T = bac$ で $S_i = aaca$ の場合 - $S_i$ は $T$ の左部品にはなれないのはわかる。$S_i$ には $b$ が含まれないので $T$ の左部品 $\{bac, ba, b\}$ いずれのケースも賄うことができない。 - $S_i$ は $T$ の右部品にはなれそう。$T = bac$ の $ac$ を、$S_i$ は連続とは限らない部分文字列として含んでいる - $T' = cab$ 及び $S_i' = acaa$ と反転させて従前通りに比較すると、$ca$ が $S_i$ に含まれる。つまり $S_i$ は右部品として使ったとき $2$ 文字分の価値があると言える 難しいですね。解説なしでは全然思いつきませんでした。 入力例 $1$ の $S_i$ をそれぞれ変換してみましょう。 ``` T = "bac" (a) (b) S1 abba 2 0 S2 bcb 1 1 S3 aaca 0 2 ``` となりました。 この (a) と (b) の値を足して $T$ の文字数 3 文字以上になれば、その二つの部品を左右からくっつけて $T$ を作ることができます。 - 例えば $S_1$ は左部品としては $2$ 文字を賄うことができて、$S_2$ は $1$ 文字賄うことができます。この二つを使うと $T$ に相当する $3$ 文字を作ることができます - $S_1$ と $S_3$ は $2 + 2 = 4$ で $T$ の $3$ 文字を超えてしまいますが、$S_1$ から $ba$ を $S_2$ からは $c$ を使ったとみなせば良いので、部品の価値の合計が $T$ の文字数を上回る分には問題ないです この表からそれぞれの $(a)$ に対して組み合わせられる $(b)$ を探すのは、これはまあ $(a)$ を固定して $(b)$ を二分探索するという典型で見つけられます。 ```haskell -- s が t の何部分文字列持っているか? -- s = "abba", t = "bac" なら s に b -> a があるので 2 f :: BS.ByteString -> BS.ByteString -> Int f t s = do let !_ = dbg ("(t, s)", t, s) BS.foldl' step 0 s where step i c | i == BS.length t = i -- TODO: i が t の長さと同じになったら打ち切りたい | c == BS.index t i = i + 1 | otherwise = i main :: IO () main = do (n, t) <- do [n_, t_] <- words <gt; getLine return (read @Int n_, BS.pack t_) ss <- replicateM n BS.getLine -- 各 Si が t の先頭何文字と、t の末尾何文字を賄えるかを計算する -- Si に対する結果をそれぞれ left, right に収める -- 例えば T = 3 文字の場合、left に 2 があったら、right の 1 let xs = map (\s -> (f t s, f (BS.reverse t) (BS.reverse s))) ss left = map fst xs right = listArray @UArray (1, n) $ sort $ map snd xs let !_ = dbg ("left", left) let !_ = dbg ("right", right) res = [n - ng | l <- left, let (ng, _) = bisect (0, n + 1) (\x -> l + right ! x >= BS.length t)] print $ sum res ``` ---- ## 感想など 過去一ぐらいの失敗ですが、失敗回からは学ぶものも多いです。 失敗に真摯に向き合うのはなかなか大変ではありますが。 この失敗、朝からの雨、あとこれは自分の問題ですが来週の予定が詰まっているというトリプルパンチでなんだか鬱々としています。 ストレスを上手に跳ね除けたいですね。 言い訳っぽくなるのであとは心の中にしまい込んで、次回への糧としましょう。 ひとまず、やはり難しい問題にじっくり取り組むよりは毎日コンスタントに、適正 diff の問題を解き続ける筋トレをする方が今の自分には向いていそうです。 確率DP や期待値DP の練習を続けていましたが、元の方針に戻したいと思います。