# ABC356 振り返り
- [AtCoder Beginner Contest 356 - AtCoder](https://atcoder.jp/contests/abc356)
- ABCD 4完 (981) ··· [コンテスト成績証 - AtCoder](https://atcoder.jp/users/oceajigger/history/share/abc356)
![[スクリーンショット 2024-06-02 8.44.41.png]]
ABC356 でした。
E が難しめの水色 diff でやや壁。私のレート帯的には前回同様 D までスムーズに 4完できるか? というところでした。
結果、4完はできたものの D で苦労してスコアは伸びず、でした。
- A (灰) ··· $(1, L - 1)$ $(L, R)$ $(R + 1, N)$ と区間を生成して $(L,R)$ を reverse する
- B (灰) ··· 縦方向に `(+)` で畳み込んで結果を系列 $A$ と比較
- C (茶) ··· $\{1, 2 \ldots N\}$ の冪集合をすべて生成して、その冪集合ごとにテスト $100$ 件を全部回す
- D (緑) ··· ビットごとに独立に考える。マスクのビットが立っている桁で、$1$ が何回でてくるか数え上げる
でした。
D も開始 40分強ぐらいで実装できていたのですが、1箇所間違えていて、そのバグをとるのに終盤までかかってしまいました。
でもまあ、AC できてよかったです。そのまま時間オーバーを迎えて終了後にウワーっとなるよりよりは遙かにマシです😂
## [A - Subsegment Reverse](https://atcoder.jp/contests/abc356/tasks/abc356_a)
$1 \ldots N$ の系列の $(L, R)$ 区間だけ並び順を逆転させる。
いろいろやり方はありそうですが、3区間にわけて生成して真ん中だけ reverse してやりました。
```haskell
main :: IO ()
main = do
[n, l, r] <- getInts
let as1 = [1 .. l - 1]
as2 = [l .. r]
as3 = [r + 1 .. n]
printList $ as1 ++ reverse as2 ++ as3
```
## [B - Nutrients](https://atcoder.jp/contests/abc356/tasks/abc356_b)
$N$ 種類の食事が用意される。食事には $M$ 種類の栄養素があり、それらの明細がわかっている。
全部食べたとき、それぞれの栄養素を十分、つまりそれぞれ $A_i$ 以上取得できているか?
栄養素ごとの和をとって、それを $A_i$ と比較すればよいですね。
Haskell をやってると「これは縦に畳込めばいいんだな」という心眼で見れるようになります。
というわけで `foldl1` と `zipWith (+)` でリストの構造を保ったまま、複数のリストを一つのリストに畳み込みます。
その上で、$A$ と比較。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
as <- getInts
xss <- replicateM n getInts
let xs = foldl1 (zipWith (+)) xss
res = zipWith (<=) as xs
printYn $ and res
```
## [C - Keys](https://atcoder.jp/contests/abc356/tasks/abc356_c)
高々 $15$ 本程度の鍵があり、それら鍵を幾つか差し込むと開くドアがある。
鍵の組み合わせは $2^N$ 種類考えられる。
どの鍵を差し込んでドアが開いたかどうかのテスト結果が与えられるので、すべてのテストに通る鍵の組み合わせは何種類あるか数えよ
··· $15$ 本程度の鍵の組み合わせ $2^N$ という時点で、冪集合を全列挙できるとピンと来ます。
$2^{15} = 32768$ 程度です。
テストは $100$ 個しかありません。$100 \times 32768$ で $10^6$ オーダーなので、鍵の突合の計算量を合わせても全探索で大丈夫そう。
というわけで
- 鍵の組み合わせ (冪集合) を全部生成する
- 集合ごとにテストにかけて、全テスト結果をパスするか調べる
- 鍵の突合は積集合をとる
としました。
テスト駆動開発的な発想なので、業プロer としては比較的考えやすかったかもしれないです。
では実装です。
いわゆる「ビット全探索」の問題ですが Haskell ではビット全探索の実装は書かなくても `subsequences` でリストから冪集合を生成できます。またテストで使われた鍵の集合と、それら生成された冪集合の突合は Set の API を使えば簡単です。
割とうまく実装できたと思います。
```haskell
main :: IO ()
main = do
[n, m, k] <- getInts
tests <- replicateM m $ do
(_ : xs) <- words <
gt; getLine
return (Set.fromList $ map (read @Int) (init xs), last xs)
let res =
[ and
[ if result == "o" then size >= k else size < k
| (test, result) <- tests,
let size = Set.size $ Set.intersection keys test
]
| keys <- Set.fromList <gt; subsequences [1 .. n]
]
print $ countBy (== True) res
```
### BitSet で実装 ··· 751ms → 41ms
コンテスト中は安全目に倒して集合操作は `Set` でやりましたが、全部ビット演算でやるほうが速いですね。
というわけでビット演算を集合操作のインタフェースで扱えるようにした `BitSet` というライブラリを作ってあるので、そちらで実装。
41 ms になりました。
```haskell
main :: IO ()
main = do
[n, m, k] <- getInts
tests <- replicateM m $ do
(_ : xs) <- words <gt; getLine
return (fromListBS $ map (read @Int) (init xs), last xs)
let res =
[ and
[ if result == "o" then size >= k else size < k
| (test, result) <- tests,
let size = sizeBS $ intersectionBS keys test
]
| keys <- powersetBS (fullBS n)
]
print $ countBy (== True) res
```
## [D - Masked Popcount](https://atcoder.jp/contests/abc356/tasks/abc356_d)
整数 $N, M$ が与えられるので $\displaystyle \sum_{k=0}^{N} popcount(k \& M)$ を求めよ。
$N$ が $0 \ldots 2^{59}$ もあるので、ナイーブにやっていくのは難しい。
$popcount$ や $AND$ 演算などのビット演算が指定されていて、かつ $N$ や $M$ のビットサイズが $60$ 未満に限定されているあたりから「ビットごとに独立に考える」という典型だと睨みます。このあたりは慣れですね。
$0 \ldots 2^{59}$ もあるのは厄介ですが、一方で数が飛んでおらず連番になっているところは何か使えそうです。
ビットごとに独立で考える問題は、ビット列を実際に書き下してパターンを抽出するのが定石。
入力例 $1$ の $M = 3$ を例に考えつつ $N = 4$ では例が少ないので 2進数で4桁ぐらいの整数... $N = 10$ 程度までみてみます。
```
M 0011
-------
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
10 1010
```
求めるのは $AND$ 演算のあとの popcount です。
「ビットごとに独立に考える」という典型を思い出し、ビットごと... つまり列ごとにみていくと、M で 1 が立っている列において、 1 が何個出現するかを数えればよいことがわかります。
ただし 1の出現回数を愚直に数えると間に合わないので効率的に数え上げる必要があります。
よくみると、
$0$ ビット目は `0101010101...` と交互に $0$ と $1$ が出現 ··· $2^0 = 1個$ ごとにサイクル
$1$ ビット目は `0011001100...` と $00$ と $11$ が交互に出現 ··· $2^1 = 2$ 個ごとにサイクル
$2$ ビット目は `0000111100...` と $0000$ と $1111$ が交互に出現 ··· $2^2 = 4$ 個ごとにサイクル
となっているのがわかります。
これを利用すれば割り算により各ビット、$O(1)$ で $1$ が何サイクル出現したかがわかります。
$0$ 始まりなので $N + 1$ 回 $0$ や $1$ が出てくる中、$2^i$ ごとにサイクルしている。となれば $(N + 1) / 2^i$ でサイクル回数が分かります。
やや面倒なのは、`00001111000011` のように最後の $1$ がサイクルの途中で途切れてしまうところですね。
が、ここも割り算の結果の余りを使うとよいです。
サイクルの途中で切れるのが $0$ の場合と $1$ の場合とあるわけですが、余りがなかったらサイクル回数は基本的に両者一致することから、逆に余りがある場合は $0$ のサイクルの方が多いか否で判断できます。$0$ の方がサイクル回数が多いなら、余りは $1$ に使われるべきです。
というわけで整理すると
- $0 \ldots 59$ ビットまで独立に考えて、$M$ のビットが立ってる桁で $1$ が何回出てくるか数える
- 各ビットで $(N + 1) / 2^i$ してサイクル回数を数える
- 余りも出るが、それを $1$ の出現回数に加えるかどうかは $0$ と $1$ のサイクル回数を比較すればよい
となります。
$\mod 998244353$ を忘れずに。
```haskell
main :: IO ()
main = do
[n, m] <- getInts
let res =
[ IntMod (2 ^ i) * IntMod one + if zero /= one then IntMod q else 0
| i <- [0 .. 59],
testBit m i,
let (p, q) = (n + 1) `divMod` (2 ^ i)
(zero, one) = (p `ceildiv` 2, p `div` 2)
]
let IntMod ans = sum res
print ans
```
なお、コンテスト中では、余りを間違えてサイクル回数に足しこんでしまい、サンプルはそれで通りつつ WA をもらいました。
どこかでオーバーフローしてるのか? とか調べはじめ、なかなかバグがとれずに 6 ペナ 😇
終了 5分くらい前に、余りを足すタイミングを間違えているのに気がつき慌てて修正しました。
## 感想など
今回は ABCD と比較的スムーズに解いていて、D のサンプルが通って送信したときには「今日は調子いいなー」と晴々とした気持ちでいました。
が、 WA が出てからのバグ取りフェーズはかなり大変でした。ここからが地獄だ!
過集中の状態のままそこから 60分くらい格闘したので、コンテストが終わったころには 🧠 の方がオーバーフロー気味でしたｗ
翌日のいまもややダメージが残っています
こういう凡ミスがなかなか取れないときは、視野が狭くなっている証拠です。
休憩をとるのが効果的と思うのですが、またしてもそういう冷静なムーブに至らず、必死になってしまいました。
「よし、ここは 5分休憩するか!」みたいな大人の振るまいができるようになりたいですね。
レートがかかってると 1 分 1 秒無駄にするまいとなってしまってなかなか難しい。
スコアは 1000 に届かず、レートは微減。
一進一退でなかなか水色にリーチがかかりません。
1100 〜 1200 の壁が高いですが、まあコツコツやっていけばいつかは突破できるでしょう。
ところで今回も ChatGPT が C や D を解けると話題になっていましたが、私は Rated 参加のときは ChatGPT は基本使いません。
使うにしても問題そのものを解かせるのではなく、イディオムを聞いたりとか未見のライブラリの使い方を聞いたりぐらいですね。
プログラミングの腕を磨く··· 自分の 🧠 を最適化させるために競プロをやる自分には、これぐらいがちょうどよいと思っています。
精進の方は変わらず PAST の過去問をやっています。
結構面白い問題が多くて、楽しんでやれています。
ちょうどいいレベル帯の未AC問題がたくさんあるのは嬉しいですね。
ABC の過去問だと茶 〜 水色下位は全部解いてしまったので、どうしても記憶勝負になってしまうところ、未AC 問題は貴重です。
競プロは継続が命。引き続きコツコツとやっていこうと思います。