サントリープログラミングコンテスト2023（AtCoder Beginner Contest 321）

　Fまで六完だが遅かったりペナが多かったりで黄色に戻れず。Fは形式的ベキ級数を考えたのは良いのだけど、「注文の多い高橋商店」と同じ問題かと思ったらもっと簡単なDP（形式的ベキ級数で言うなら、簡単な式の掛け算、割り算）だったんですよね。もっと落ち着いてDPの式を考えないと。

コンテストへのリンク

コンテスト後のツイート

F 形式的ベキ級数だと思って「注文の多い高橋商店」の解説を見に行ったが、冷静になると普通にDPで解けた。焦り過ぎです。
G 3^Nのbit DPだと思ったが詰めきれず。

— titia (@titia_til) September 23, 2023

G - Electric Circuit

　解説放送を見てAC。$3^N$のbit DPだとは思ったが、正しい解法にたどりつけなかった。

　集合iに対して、DP[i]=iが連結成分になる場合の数と定義したとき、DP[i]を求めるところで何を引けばいいか分かっていなかった。

　まず、内部でいくつかの連結成分に分かれているかどうかは考慮せずにDPの値を求めておく。そこから$3^N$のbit DPを使って値を引いていく。

　$i=j\cup k$と表せるとき、DP[j]*DP[k]（ではないが、そのようなもの）を引くわけだが、全ての部分集合に対してこれを引くと二重に引かれる部分が出てしまう。iに属するある頂点xを定め、xを含むようなjに対して、DP[j]*DP[i/j]……ではなく、DP[j]*（i/jが一つの連結成分になっていなくても良いが、その外との辺はないような場合の数）を引いていかなくてはいけない。

　（i/jが一つの連結成分になっていなくても良いが、その外との辺はないような場合の数）は、「引く前のDPの値」なので、既に求まっている。

　解法の大枠は分かっても、詰めるのは大変な問題でした。

　ただ、「同じものをダブルカウントしないため、「ある頂点を含むものだけ考える」などしなくてはいけない。」とは、この記事にも書いている。同じところで分からなくなったのは良くない。