2022-07-14 着替え競争 / ABC246 の F を解いた
ABC246 : AtCoder Beginner Contest 246 の F を解いた。
- F - typewriter
https://atcoder.jp/contests/abc246/tasks/abc246_f
- 提出: https://atcoder.jp/contests/abc246/submissions/33219556
- 解説 AC
k段目のキーだけでL文字の文字列をつくる場合の数をつくるのは|S_k|^Lだ- うまく重複を排除しないといけない
- 包除原理かなと思ったけど時間がなかったので諦めて解説へ
- 考察はおおむね正解
N <= 18なのでビット全探索で1..=2^Nのすべての組み合わせを調べる (0は除外)- 組み合わせた段数が奇数なら加算・偶数なら減算すれば良い (包除原理)
- 組み合わせた段すべてに共通して存在するキーの数
KでL文字をつくるのでK^L - それらの合計が答えになる
https://twitter.com/bouzuya/status/1547460889380589569
子どもが風呂から出た際に「着替え競争」を持ちかけてくる。この頃はズルくてあちらが最後の一枚こちらが全裸のときにくる。
普段は負けるのだけど昨日は子どもが最後の一枚を後ろ前に着た。それを指摘し直しているうちにぼくが勝った。……で泣いてしまった。子どもだな〜
後ろ前を指摘した時点で涙ぐんでた。今日は「もう勝負しない」って言ってた。傷を植え付けてしまった。
bouzuya/rust-sandbox its 0.20.1 をつくった。
昨日 (2022-07-13) の its issue unblock のリンクが消えないバグを修正したもの。表示が更新されない場合は一度 query db を消すと良さそう。
今日のコミット。