# ABC347 振り返り
- [AtCoder Beginner Contest 347 - AtCoder](https://atcoder.jp/contests/abc347)
- AB 2完 (809) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc347)
![[スクリーンショット 2024-03-31 14.29.25.png]]
![[スクリーンショット 2024-03-31 14.28.19.png]]
ABC347 でした。
久し振りに、やってしまいました 😅
C 問題が難しく、そこで完全に調子を崩しました。損切り失敗ですね。
- A (灰) ··· 問題文の通りに実装する
- B (灰) ··· 部分文字列を全部生成してユニークをとる
- C (緑, upsolve) ··· 予定の日程を mod により曜日に置き換えて分布を調べる。分布の範囲が区間長 $A$ に収まっていれば `Yes`
- D (緑, upsolve) ··· $C$ のビットが立ってる/立ってないで取れる行動が決まる。全探索で、条件が成立するパターンを探し、そこから貪欲に復元する
- E (緑, upsolve) ··· 累積和を使って、集合から削除されるタイミングで $A_x$ に、集合が追加されてからそこまでの累積分を加える
でした。
C, D, E ともに緑難易度でしたが、いずれの問題も考察を要する問題で時間内に 3問全て解くのは相応の集中力・実装力を要したと思います
自分は C で送信した回答が 1 WA だったこともあって、その解法に執着した結果盛大に沼ってしまいました。
だいぶ時間が経過したところで順位表をみつつ E に行ったのですがこの意志決定が遅く、E も焦って冷静に考察できずに惨敗でした。
## [A - Divisible](https://atcoder.jp/contests/abc347/tasks/abc347_a)
問題文のとおり、$K$ の倍数にフィルタして、その結果を $K$ で割った数に写像します
```haskell
main :: IO ()
main = do
[n, k] <- getInts
as <- getInts
let as' = map (`div` k) $ filter (\a -> a `mod` k == 0) as
printList as'
```
## [B - Substring](https://atcoder.jp/contests/abc347/tasks/abc347_b)
B問題らしく制約が緩いので、部分文字列を全部生成してユニーク数を数えます。
`substrings` という、部分文字列を全部生成する関数を盆栽しているので、それで一撃でした。`substrings` はたまに出番があります
```haskell
main :: IO ()
main = do
s <- getLine
let s' = Set.fromList (substrings s)
print $ Set.size s'
```
## [C - Ideal Holidays](https://atcoder.jp/contests/abc347/tasks/abc347_c) (upsolve)
今回の山場でした。
先にまず実装です。$A + B$ の mod をとって $N$ 個の予定を曜日の分布にします。
$N$ 個の整数が区間長 $A$ の範囲に全て入っていれば、$N$ 個の予定はすべて休日である可能性があります。
```haskell
main :: IO ()
main = do
[n, a, b] <- getInts
ds <- getInts
let m = a + b
ds' = sort' $ map (`mod` m) ds
ds'' = ds' ++ map (+ m) ds'
as = listArray @UArray (1, 2 * n) ds''
res = [boundLE (d + a - 1) as - boundLT d as | d <- ds']
printYn $ elem n res
```
$7$ 日間のカレンダーを思い浮かべてみるとよいですね。
まず $D$ 日後が週のどの位置か (何曜日か的なこと) にしか関心はないので、 $A + B$ の mod をとります。
これを $N$ 個の値の曜日の分布と考えます。
例えば $A = 3$ のときは、休日が $3$ 日間続ということなので $N$ 個の曜日が全て `xxxoooxxx` と区間長 $3$ の範囲に分布しているなら答えは `Yes` になります。
仮に $N = 5$ だとして、分布を数で表したときに `000131000` とかになっていれば良い。
`131` のところが区間長 $A = 3$ 以内に収まっていて、そこに $N = 5$ 個分すべてが入ってます
というわけで mod をとった結果の最大 - 最小の距離をとって $A$ に収まっていれば... と判定するとよさそうに見えます。
しかし `ooxxxxxxo` という分布になっているケースも (周期性をもっているため) `ooo` が 3 つ連続している... つまり休日区間長が $A$ であるとみなせるので、最大最小の距離ではうまくいかない。ここが落とし穴です。
そして、いやらしいことに、このケースが 1 つだけしか WA にしかならない。
「あと 1 WA とるだけなんだ···! 」と思ってこの解法に執着しているとゲームオーバーです。最大 - 最小を頑張っても、なかなか正解に辿り着けません。
![[スクリーンショット 2024-03-30 22.42.19.png|600]]
こういうときは方針を変えて、周期性を考慮して円環を考えます。
先の週またぎのケースは `ooxxxxxxo|ooxxxxxxo` と円環にして考えるとよいです。
例えば入力例の `1 2 9` は mod 7 に写像すると `1 2 2` になりますが、これを円環にするため `1 2 2 8 9 9` と倍化します。
そして`[1, 2, 2]` をそれぞれ固定 (これを $d$ とする) し、$d$ 〜 $d + A - 1$ の間... つまり $d$ を始点としてそこから区間長 $A$ の間に、何個要素が入っているかを数えます。
この $d 〜 d + A - 1$ というのは $d$ を休日の初日として、休日の終わりまでの区間 (区間長 $A$) です。
予めソートしておくことで区間の中に要素が何個分布しているかを、二分探索で、下界と上界の境界を引くことで数えることができます。
結果、$N$ 個が $A$ におさまるケースがみつかるなら答えが `Yes` になります。
まとめると手順としては
- mod A+B をとってソートする
- 円環に、倍化する
- d を固定して区間長 $A$ の範囲に値が何個あるかを二分探索
- 区間長 $A$ の中に $N$ 個値が入ってるケースがあったら答えは `Yes`
となります。
## [D - Popcount and XOR](https://atcoder.jp/contests/abc347/tasks/abc347_d) (upsolve)
ビットごとに独立に考えるという典型問題ですが、実装に気を遣います。
- $C$ のビットパターンを元に、$X$ と $Y$ それぞれに何ビット $1$ を立てるかを全探索するパート
- 全探索の結果得られた値を満たすビットパターン $X$ と $Y$ を復元するパート
の二つに問題を分割して考察しました。
### $C$ のビットパターンを元に $X$ と $Y$ に何ビット $1$ を立てるか全探索
入力例 1 をビットに置き換えて考えます
```
C 7 00111
----------
X 28 11100 (popCount = a: 3)
Y 27 11011 (popCount = b: 4)
```
となるわけですが、ここで $X \oplus Y = C$ となる必要があります。
ここはビットごとに独立で考えます。
$2$ 進の各桁を考えたとき xor 演算の性質から
- $C$ でビットが立ってない桁は、$X$ と $Y$ の桁は同じでなければいけない。両方 $1$ か両方 $0$
- $C$ でビットが立っている桁は、$X$ と $Y$ の桁は排他でなければいけない。一方が $1$ なら他方が $0$
となります。
加えて立ってるビットの数に $a$ と $b$ になるという制限があります。
これらを整理して考えると
- $X, Y$ を構成するビットのうち、$C$ でビットが立ってない箇所のうち、何カ所ビットを立てるか ··· $x$
- $X$ を構成するビットのうち、$C$ でビットが立ってる箇所のうち、何カ所ビットを立てるか ··· $s$
- $Y$ を構成するビットのうち、$C$ でビットが立ってる箇所のうち、何カ所ビットを立てるか ··· $t$
という $3$ 変数を考える必要があるのがわかります。
さらに入力例 $1$ の $C = 7$ は `111` で $3$ 桁ですが、問題設定的にこれを $60$ ビットまで伸ばしてよいわけです。
よってもう一変数、
- 追加でビットを立てる上位桁数 ··· $k$
も考えるとしましょう
問題の設定に戻ると、これらの変数の間に
$k + x + s = a$
$k + x + t = b$
という等式が成立していると考えられます。
それぞれの変数の取り得る範囲を考えてみると、
- $k$ は $60$ 桁から、$C$ を構成する桁数を抜いた範囲
- $x$ は $C$ を構成するビットの $0$ の個数
- $s$ は $C$ を行程するビットの $1$ の個数で、$t = (1の個数) - s$
とそれぞれ探索範囲はとても狭いので、上記の式を満たす $k, x, s, t$ は全探索で見つけることができます。
ここまでの実装が、以下になります。
```haskell
main :: IO ()
main = do
[a, b, c] <- getInts
-- c のビットが 0 の箇所は s / t ともに 0 or 1 で同じになる
-- c のビットが 1 の箇所は s / t で排他でどちらかが1 でどちらかが 0 になる
let n = bitLength c
one = popCount c
zero = n - one
let res =
[ (k, x, s, t)
| k <- [0 .. 59 - (n - 1)], -- 追加の上位ビット数 (全部 1 にする)
x <- [0 .. zero], -- xor 0 の位置をいくつ 1 にするか (共通)
s <- [0 .. one], -- xor 1 の箇所をいくつ 1 にするか (s 側)
let t = one - s, -- 同上 t 側
k + x + s == a,
k + x + t == b
]
-- (snip.) --
```
全探索により $k, x, s, t$ が決まったらあとはそのそれぞれの数からビット列を復元するパートに移ります。
### 得られた数を満たすように貪欲にビットを復元する
これは、$k, x, s, t$ それぞれの意味するビット列 $4$ つを独立に復元して、最後に論理和をとるのが楽です。
復元は上位ビットまたは下位ビットから貪欲にやっていけばよいです。
$C$ の $2$ 進の桁数を $N$ としたとき
- $k$ の数だけ、$N$ 以降のビットを立てたビット列を作る ··· 入力例 $1$ なら$k = 2$ で `11000`
- $x$ の数だけ、$C$ でビットが立ってない箇所に上位ビットからビットを立てたビット列を作る ··· 入力例 $1$ では $x = 0$ なので `000`
- $s$ の数だけ、$C$ でビットが立っている箇所に、上位ビットからビットを立てたビット列を作る ··· $s = 1$ なら `100`
- $t$ の数だけ、$C$ でビットが立っている箇所に、下位ビットからビットを立てたビット列を作る ··· $t = 2$ なら `011`
$X$ が $k, x, s$ から作ったビットの論理和
$Y$ が $k, x, t$ から作ったビットの論理和
となります。
`resolve` 関数が、その復元のための実装です。
```haskell
resolve :: Int -> Int -> Int -> Int -> Int -> (Int, Int)
resolve c k x s t = do
let n = bitLength c
-- 追加の上位ビット n ビット目から n + k - 1 ビット目。全部 1 にする
let bitsK = foldl' setBit (0 :: Int) [n, n + 1 .. n + k - 1]
-- xor 0 の箇所のビット。上位ビットから貪欲に 1 にできるところを 1 にする
let (_, bitsX) = foldl' f (x, 0 :: Int) [n - 1, n - 2 .. 0]
where
f (remain, bits) i
| not (testBit c i) && remain > 0 = (remain - 1, setBit bits i)
| otherwise = (remain, bits)
-- xor 1 の箇所のビット (1)。上位ビットから貪欲
let (_, bitsS) = foldl' f (s, 0 :: Int) [n - 1, n - 2 .. 0]
where
f (remain, bits) i
| testBit c i && remain > 0 = (remain - 1, setBit bits i)
| otherwise = (remain, bits)
-- xor 1 の箇所のビット (2)。下位ビットから貪欲
let (_, bitsT) = foldl' f (t, 0 :: Int) [0 .. n - 1]
where
f (remain, bits) i
| testBit c i && remain > 0 = (remain - 1, setBit bits i)
| otherwise = (remain, bits)
(bitsK .|. bitsX .|. bitsS, bitsK .|. bitsX .|. bitsT)
main :: IO ()
main = do
[a, b, c] <- getInts
-- c のビットが 0 の箇所は s / t ともに 0 or 1 で同じになる
-- c のビットが 1 の箇所は s / t で排他でどちらかが1 でどちらかが 0 になる
let n = bitLength c
one = popCount c
zero = n - one
let res =
[ (k, x, s, t)
| k <- [0 .. 59 - (n - 1)], -- 追加の上位ビット数 (全部 1 にする)
x <- [0 .. zero], -- xor 0 の位置をいくつ 1 にするか (共通)
s <- [0 .. one], -- xor 1 の箇所をいくつ 1 にするか (s 側)
let t = one - s, -- 同上 t 側
k + x + s == a,
k + x + t == b
]
if null res
then print (-1 :: Int)
else do
let (k, x, s, t) = head res
v = resolve c k x s t
printTuple v
```
### BitSet を使う
こんなことを投稿したばかりなので、BitSet を使った実装も載せておきます。
今回の問題の場合、集合を意識するというよりは上位ビットから、あるいは下位ビットから連続的にみていくのであまり集合操作にする旨みがないですね。
```haskell
resolve' :: Int -> Int -> Int -> Int -> Int -> (BitSet, BitSet)
resolve' c k x s t = do
let cs = BitSet c
n = bitLengthBS cs
let bsK = foldl' (flip insertBS) emptyBS [n + 1 .. n + k]
(_, bsX) = foldl' f (x, emptyBS) [n, n - 1 .. 1]
where
f (remain, bs) i
| remain > 0 && notMemberBS i cs = (remain - 1, insertBS i bs)
| otherwise = (remain, bs)
(_, bsS) = foldl' f (s, emptyBS) [n, n - 1 .. 1]
where
f (remain, bs) i
| remain > 0 && memberBS i cs = (remain - 1, insertBS i bs)
| otherwise = (remain, bs)
(_, bsT) = foldl' f (t, emptyBS) [1 .. n]
where
f (remain, bs) i
| remain > 0 && memberBS i cs = (remain - 1, insertBS i bs)
| otherwise = (remain, bs)
(foldl1 unionBS [bsK, bsX, bsS], foldl1 unionBS [bsK, bsX, bsT])
main :: IO ()
main = do
[a, b, c] <- getInts
-- c のビットが 0 の箇所は s / t ともに 0 or 1 で同じになる
-- c のビットが 1 の箇所は s / t で排他でどちらかが1 でどちらかが 0 になる
let n = bitLength c
one = popCount c
zero = n - one
let res =
[ (k, x, s, t)
| k <- [0 .. 59 - (n - 1)], -- 追加の上位ビット数 (全部 1 にする)
x <- [0 .. zero], -- xor 0 の位置をいくつ 1 にするか (共通)
s <- [0 .. one], -- xor 1 の箇所をいくつ 1 にするか (s 側)
let t = one - s, -- 同上 t 側
k + x + s == a,
k + x + t == b
]
if null res
then print (-1 :: Int)
else do
let (k, x, s, t) = head res
(BitSet v, BitSet u) = resolve' c k x s t
printTuple (v, u)
```
## [E - Set Add Query](https://atcoder.jp/contests/abc347/tasks/abc347_e) (upsolve)
動的に更新される累積和をうまく使うことで、解ける問題でした。
C, D, E はいずれも緑問題で、E が一番 difficulty は高いですが3問の中ではこれが一番易しかったと思います。
入力例1 よりも入力例2 の方が考えやすいので入力例 2 を題材にします。
入力例2 において、時間遷移にともない集合の中身とそのサイズがどう変化していくかをまずは書き出してみます。
![[IMG_0726.jpeg|500]]
少し考えると、各 $A_i$ に溜まっていくカウントは累積的になっているということが見えてきます。
例えば入力例 $1$ の $A_1$ は最終的に $15$ になりますが、$15$ というのは再右列の「集合サイズ」をすべて足し上げた数と一致しています。
このあたりから累積演算の匂いがします。
そこで、再右列の集合サイズの累積和をとって併記してみます。
また、入力例2 において、途中で追加されて途中で一度削除もされる、$2$ に着目してみます。
![[IMG_0727.jpeg|600]]
$2$ が最初に追加されて一度削除されるまでの間に $A_2$ には集合サイズ $2, 3$ が足されて $5$ になるわけですが、累積和の方と対比すると $2$ が追加される直前の累積和 $1$ と、$2$ が削除される直前の累積和 $6$、その差 $6 - 1 = 5$ で一致していることがわかります。
どうやら、$x_i$ が追加や削除される直前の累積和の状態と $x_i$ の間に関連がありそう。
それを紐付けてみます。
![[IMG_0729.jpeg|600]]
$x = 2$ 以外の数は入力例2 においては追加されたあと削除はされません。
ということはそれらの $A_i$ には、集合に追加された以降ずっと累積的に数が溜まっていくことになります。
先ほど $x_i = 2$ は削除のタイミングで計算しましたが、一度も削除されることのない値は、最後に計算することになりそうですね。
最終的に累積和は $15$ になりますので、ここから前例に倣って $x$ が集合に追加される・集合から削除される直前の値を使って、入力例2 の答えと一致するように組み立てていくと以下のようになりました。
- $A_1$ ··· $15 - 0 → 15$
- $A_2$ ··· $6 - 5 → 5, 15 - 11 → 4$ (合計 $9$)
- $A_3$ ··· $15 - 3 → 12$
- $A_4$ ··· $15 - 8 → 7$
うまくいきそうです。
というわけで
- クエリを進めながら局面ごとに累積和を更新する
- $x$ が集合に追加された局面 $t$ を記録しておく
- $x$ が集合から削除されたタイミングで、その直前の累積和の値、局面 $t$ 時点での累積和の値を使って $A_i$ に加わる差分を算出して追加する
- クエリがすべて終了したあとに最後にのこっている集合も、そこで全てが削除されると考えて上記同様の計算を行う
とすると良いです。
実装として累積和の更新は配列で愚直にやっていってもよいですが、BIT やセグメント木で表現してやってもよいでしょう。
### 累積和配列での実装
```haskell
main :: IO ()
main = do
[n, q] <- getInts
xs <- getInts
cs <- newArray @IOUArray (1, q + 1) (0 :: Int) -- 累積和
ts <- newArray @IOUArray (1, n) (0 :: Int) -- x が追加された局面
as <- newArray @IOUArray (1, n) (0 :: Int) -- 製数列A
-- クエリに対し集合を更新しながら累積和も更新していく
-- x 追加のタイミングを覚えておき、x が削除されるところで Ax を更新する
s'' <- foldForM Set.empty (indexed 1 xs) $ \s (t, x) -> do
s' <-
if Set.notMember x s
then do
-- 集合に x を追加する
let s' = Set.insert x s
-- x が追加されたタイミングを記録しておく
writeArray ts x t
return s'
else do
-- 集合から x を削除する
let s' = Set.delete x s
-- 累積和を使って x が追加されてからここまでの累積分を Ax に加える
l <- readArray cs =<< readArray ts x
r <- readArray cs t
updateArray (+) as x (r - l)
return s'
-- 累積和更新
acc <- readArray cs t
updateArray (+) cs (t + 1) (acc + Set.size s')
return s'
-- クエリ終了後に集合に残っている整数も考慮
for_ (Set.toList s'') $ \x -> do
l <- readArray cs =<< readArray ts x
r <- readArray cs (q + 1)
updateArray (+) as x (r - l)
printList =<< getElems as
```
### BIT (Fenwick Tree) を使った実装
```haskell
main :: IO ()
main = do
[n, q] <- getInts
xs <- getInts
ts <- newArray @IOUArray (1, n) (0 :: Int) -- x が追加された局面
tree <- newBIT @IOUArray (1, q) -- BIT
-- クエリに対し集合を更新しながら累積和も更新していく
-- x 追加のタイミングを覚えておき、x が削除されるところで Ax を更新する
(s'', updates) <- foldForM (Set.empty, []) (indexed 1 xs) $ \(s, acc) (t, x) -> do
context@(s', _) <-
if Set.notMember x s
then do
let s' = Set.insert x s
writeArray ts x t -- x が追加されたタイミングを記録
return (s', acc)
else do
let s' = Set.delete x s
l <- readArray ts x
count <- rangeSumBIT tree l t
return (s', (x, count) : acc)
-- 累積和更新
incrementBIT tree t (Set.size s')
return context
-- クエリ終了後に集合に残っている整数も考慮
updates' <- for (Set.toList s'') $ \x -> do
l <- readArray ts x
count <- rangeSumBIT tree l (q + 1)
return (x, count)
let as = accumArray @UArray (+) 0 (1, n) $ updates ++ updates'
printList $ elems as
```
## 感想など
ひさびさに2完で撃沈してしまい凹みました 😂
B, C あたりで躓くと、総崩れになってしまって立て直せずにそのままずるずると... というパターンでした。
ところで過去の撃沈回をみてみたところ、やはり B もしくは C 問題で想定以上に難しい問題が出た回で同じように大敗していることがわかりました。
- ABC334 [B - Christmas Trees](https://atcoder.jp/contests/abc334/tasks/abc334_b) (茶 479) [C - Socks 2](https://atcoder.jp/contests/abc334/tasks/abc334_c) (緑 1030) ··· 2完撃沈
- ABC324 [C - Error Correction](https://atcoder.jp/contests/abc324/tasks/abc324_c) (茶 637) ··· 2完撃沈
- ABC320 [C - Slot Strategy 2 (Easy)](https://atcoder.jp/contests/abc320/tasks/abc320_c) (緑 851) ··· 2完撃沈
- ABC319 [C - False Hope](https://atcoder.jp/contests/abc319/tasks/abc319_c) (緑 1111) ··· 3完撃沈
- ABC312 [C - Invisible Hand](https://atcoder.jp/contests/abc312/tasks/abc312_c) (茶 727) ··· 2完撃沈
ここから言えることは、私は損切りがとても下手、ということですね。
D を飛ばして E を解いてうまくいったケースは過去何度かあるのですが、B や C を損切りするというのが下手なようです。
今回も、C は 1WA になったこともあって「もうちょっと今の解法でがんばればいけるのでは」と執着してしまったのが、失敗でした。
残念ながらその方向に答えはなかったのです。
B や C を飛ばすと、それらを飛ばしたことが頭にちらついて後続の D や E もなかなかうまく思考がまとまらない、というメンタルの弱さが露呈してしまいます。
また、C 問題あたりで想定以上に難しい問題が出ると「C なのにこんなに考察が必要なんだろうか? 」と疑心暗記になって、より深い思考に辿り着けないというメンタルブロックも多分にあるように思います。
B でも C でも、一筋縄にはいかないと思ったらスイッチを入れる。スイッチを入れてもだめならさっさと捨てて、気持ちを切り替えて次の問題に取り組む。これができるようにならないといけません··· と言葉にするのは簡単ですが、これはなかなか難しいですね 😅
鋼のメンタルが欲しいと思う今日この頃です。
また次回頑張ります。