きろく

特筆すべき記録のまとめ

2019-12-16から1日間の記事一覧

AtCoder Beginner Contest 147:E - Balanced Path

問題 解法 解答 問題 https://atcoder.jp/contests/abc147/tasks/abc147_e 解法 dp(i, j, k) := マス (0, 0) から マス (i, j) までのパスで「偏り」が(以上でも以下でもなく)k となるかどうか という DP を考えると,遷移は (0, 0, |A[0][0] - B[0][0]|) …

AtCoder Beginner Contest 147:D - Xor Sum 4

問題 解法 解答 問題 https://atcoder.jp/contests/abc147/tasks/abc147_d 解法 bit ごとに操作は独立なので,A の中で 2^k 桁目が 1 であるものの数をそれぞれ数えておき,この数を用いて答えを計算する.各 2^k 桁目について(1 の個数)*(0 の個数)* 2^…

AtCoder Beginner Contest 147:C - HonestOrUnkind2

問題 解法 解答 問題 https://atcoder.jp/contests/abc147/tasks/abc147_c 解法 N 人それぞれが「正直者」かそうでないかを 2^N 通りすべて試し,与えられた情報に合致する組み合わせの中で最も「正直者」の数が多いものを答えにすればよい.O(2^N * N). 解…