Send More Money [AtCoder Beginner Contest 198 D] - はまやんはまやんはまやん
https://atcoder.jp/contests/abc198/tasks/abc198_d 解説 https://atcoder.jp/contests/abc198/submissions/21692252 覆面算のソルバーを普通に作る。 各文字にその数字を割り当てるかを全探索で決めていこう。 各文字にどの数字を割り当てるかということを考えると順列を作っているような感じになる。 順列の全探索に用いるのはdfsなので、dfsで頑張る。 dfsに入る前に使われている文字を集計して、被りなしの個数を見ておこう。 10個までなら数字を割り当て可能だが、それを超えると無理なのでUNSOLVABLEで答える。 dfs関数 dfs(cu) := cu番目の文字まで確定させている状態で入ってくる 全列挙の形は自然な形であるのでdfsの学習をしていれば理解できるだろう。 各文字について0～9の数字
![Send More Money [AtCoder Beginner Contest 198 D] - はまやんはまやんはまやん](https://cdn-ak-scissors.b.st-hatena.com/image/square/53030039f6ffcf58c13f27128c34e7940fd47d57/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F10328537792368951407%2F26006613715034583%2F1618149353)
競技プログラミングにおける包除原理問題まとめ - はまやんはまやんはまやん
包除原理 包除原理についての偉大なスライド 数え上げをする時の定理 ここが詳しい ここの包除原理の欄も詳しい 基本は状態系包除原理 状態系包除原理を個数に注目して個数系包除原理にするテクがある（抽象化による状態圧縮） 例 n(AorBorC) = n(A) + n(B) + n(C) - n(A&B) - n(B&C) - n(C&A) + n(A&B&C) もし、「dp[i] := i個の&で表現できる組み合わせ数」が高速に計算できれば、 n(AorBorC) = dp[1] - dp[2] + dp[3] 事前計算が高速にできれば包除原理計算部分をO(2^N)からO(N)に削減できる 問題によっては「dp[i] := &でつながれている個数の偶奇がiであるときの組み合わせ数」のように更に状態を圧縮出来る場合もある これ 順列の組み合わせ数は、組合せの組み合わせ数と包除原理から求めるテク
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
