bouzuya.hatenablog.com

ぼうずやのにっき

着替え競争 / 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 は除外)
    • 組み合わせた段数が奇数なら加算・偶数なら減算すれば良い (包除原理)
    • 組み合わせた段すべてに共通して存在するキーの数 KL 文字をつくるので K^L
    • それらの合計が答えになる

https://twitter.com/bouzuya/status/1547460889380589569

子どもが風呂から出た際に「着替え競争」を持ちかけてくる。この頃はズルくてあちらが最後の一枚こちらが全裸のときにくる。

普段は負けるのだけど昨日は子どもが最後の一枚を後ろ前に着た。それを指摘し直しているうちにぼくが勝った。……で泣いてしまった。子どもだな〜

後ろ前を指摘した時点で涙ぐんでた。今日は「もう勝負しない」って言ってた。傷を植え付けてしまった。


bouzuya/rust-sandbox its 0.20.1 をつくった。

昨日 (2022-07-13) の its issue unblock のリンクが消えないバグを修正したもの。表示が更新されない場合は一度 query db を消すと良さそう。


今日のコミット。