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 を消すと良さそう。
今日のコミット。