AtCoder Beginner Contest 152 D～F問題メモ

AtCoder Beginner Contest 152

• AtCoder Beginner Contest 152 - YouTube

D - Handstand 2

• 整数 $N$ が与えられる
• 次の条件を満たす1以上 $N$ 以下の2つの整数の組 $(A,B)$ の個数を求めよ
  • $A$ の最上位桁の数字と、$B$ の最下位桁の数字が一致
  • $B$ の最上位桁の数字と、$A$ の最下位桁の数字が一致
  • ただし数字は先頭に0を付けない10進数表記とする
• $1 \le N \le 2 \times 10^5$

事前計算で1以上 $N$ 以下の数字を走査し、「先頭桁が $i$ で末尾桁が $j$ の数字の個数 $C_{i,j}$」をあらかじめ求めておく。

再度、1以上 $N$ 以下の数字を走査し、その数字が先頭桁が $j$ で末尾桁が $i$ なら答えに $C_{i,j}$ を加算すればよい。

（最初、まとめて計算しなければいけないと思って時間をかけすぎた。桁DPなら制約がもっとえげつないことに気付こう）

E - Flatten

• 長さ $N$ の正整数列 $A_1,...,A_N$ が与えられる
• 次の条件を満たす正整数列 $B_1,...,B_N$ を考える
  • 全ての添字 $(i,j)$ の組で、$A_iB_i=A_jB_j$ が成り立つ
• このような $B_1,...,B_N$ の総和の最小値を、$\mod 10^9+7$ で求めよ
• $1 \le N \le 10^4$
• $1 \le A_i \le 10^6$

要は、$A_1,...,A_N$ の最小公倍数（LCM）を求めて、各 $B_i$ はそれを $A_i$ で割った値にした場合が最小である。

ただし、ある程度巨大なLCMをきちんと求められますか、という問題。

$A_1,A_2$ のLCMは、通常なら2数の最大公約数をもとめて、$A_1A_2$ をそれで割った値となる。 複数の値があっても、$lcm(A_1,A_2,A_3)=lcm(lcm(A_1,A_2),A_3)$ と順番に更新していけばよい。

しかし今回はそれでは、$A_i$ が互いに素だった場合、$10^{60000}$ くらいの値になりかねない。 また、割り算を伴うので、途中でMODをとってしまうと正しく求められない。

素因数分解の形で管理するとよい。

$A_1 = 2^a3^b5^c, A_2 = 2^d3^e5^f$ と素因数分解できるとすると、その最小公倍数は $2^{\max(a,d)}3^{\max(b,e)}5^{\max(c,f)}$ となる。

$A_i$ を全て素因数分解して各素因数の最大値を取っていくと、各要素がそこまで大きくならない範囲でLCMを保持できる。

最後に各素因数を順番にかけてやればいいが、ここではMODをとりながら行うことができる。

そして、各 $A_i$ につきLCMに逆数をかけた値を足し合わせれば答えとなる。

Pythonなら $pow(x,y,m)$ で比較的高速に簡単にmodの累乗を計算できるので、逐一フェルマーの小定理から $A_i^{-1} \equiv A_i^{MOD-2} \mod{MOD}$ を計算しても間に合う。

$10^{60000}$ ならそのまま計算できる。そう、Pythonならね。（AC 1895ms）（やればよかった）

ただし、加減乗除の内、除だけはかなり遅いので注意。

F - Tree and Constraints

• $N$ 頂点の木が与えられ、辺 $i$ は頂点 $a_i$ と $b_i$ を結ぶ
• 各辺を白または黒で塗る塗り方は、$2^{N-1}$ 通りある
• この内、以下の $M$ 個の制約を全て満たすものの個数を求めよ
  • $u_i$ と $v_i$ が与えられる
  • 頂点 $u_i$ と $v_i$ を結ぶ経路に含まれる辺の内、黒く塗られているものが1つ以上存在する
• $2 \le N \le 50$
• $1 \le M \le 20$
• 制限時間:4sec

「少なくとも1つは黒である」という条件は扱いづらいので、「全て黒でない」に言い換えて、それを全体から引くのがセオリー。

今回のように条件が複数ある場合、全体から「どれか1つでも満たさない場合の数」を引く必要があるが、それは包除原理を用いれば計算できる。

辺数は最大49と小さいので、辺集合を1辺を1bitとしたビットフラグで表せる。 $u_i$ から $v_i$ まで、使った辺のbitを立てながらDFSなどで探索し、経路に使う辺集合を計算しておく。

入力例3
    1      2      3        辺の横の数字は辺番号
① --- ② --- ③ --- ④
                `--- ⑤
                  4
条件   経路  辺集合  bit表現
   1   1～3   {1,2}     0011
   2   2～4   {2,3}     0110
   3   2～5   {2,4}     1010

または、適当な頂点 $r$ を根として、$r$ から全頂点への使う辺集合 $G_{r,v}$ をビットフラグで求めておけば、 $u,v$ 上の経路は $G_{r,u} \ XOR \ G_{r,v}$ で計算できるので計算量を減らせる。（今回は制約が小さいので恩恵は少ないが）

包除原理を用いるにあたり、全条件の内、一部だけを確実に満たさないパターン数（あとは満たしても満たさなくてもよい）を考える。 どの条件を満たさないかは、$2^M$ 通りある。これを全探索する。

$M$ 個中 $C_1,C_2,...,C_k$ の条件を満たさない場合、このいずれかの条件に対応する経路に含まれる辺は黒に塗られてはいけない。 各条件で使う辺集合のbitORを取って、'1'が立っているのがそれに該当する辺である。

他の辺はどうあってもよいので、$k$ 個の条件を全て満たさないパターン数は、$2^{N-1-bitORで1が立っている辺数}$ となる。

条件集合  条件集合  k  辺集合  not黒な  満たさない
 bit表現                bitOR   辺の数    場合の数
     000        {}  0    0000        0         2^4
     001       {1}  1    0011        2         2^2
     010       {2}  1    0110        2         2^2
     011     {1,2}  2    0111        3         2^1
     100       {3}  1    1010        2         2^2
     101     {1,3}  2    1011        3         2^1
     110     {1,2}  2    1110        3         2^1
     111   {1,2,3}  3    1111        4         2^0

ここから以下のように包除原理を適用すると「満たさない条件が1つでもある場合の数」を計算できる。

$(k=1の時の場合の数の和) - (k=2の時の場合の数の和) + (k=3の時の場合の数の和)$ $= (kが奇数の時の場合の数の和) - (kが偶数の時の場合の数の和)$

これを全事象の数から引けばよいが、全事象はつまり $k=0$ の時の場合の数なので、結局

$(kが偶数の時の場合の数の和) - (kが奇数の時の場合の数の和)$

を計算すれば、答えとなる。

辺集合の計算に $O(NM)$。

条件集合のイテレートに $O(2^M)$、各条件集合でbitORを求めるのに $O(M)$、立っているbitを数えるのに $O(N)$ より、$O((M+N)2^M)$。あわせて $O(NM+(N+M)2^M)$ となる。

最大値を代入して $7 \times 10^7$ くらい。これに定数倍がかかるのでそれなりに重くはあるが、4秒なら通る。

包除原理を用いなくても、DPでも計算できる。

あらかじめ各辺につき、「この辺が黒く塗られたら、条件 $C_1,C_2,...$ を満たすことが出来る」という情報 $F_i$ を、1条件を1bitとしたビットフラグで計算しておく。

• $DP[i][f] = i$ 番目の辺まで見て、満たされた条件集合が $f$ である場合の数
• $DP[0][0]=1$

として、以下のように遷移していく。

• $i$ 番目の辺を黒く塗る場合
  • $DP[i+1][f | F_i] += DP[i][f]$
• $i$ 番目の辺を白く塗る場合
  • $DP[i+1][f] += DP[i][f]$

最終的に $DP[N-1][111...11]$ が答え。$O(NM+N2^M)$