ABC119-C Synthetic Kadomatsu
問題
方針
$N$本の竹は、それぞれ最終的に
- 長さが$A$の竹を作るために使われる(Group Aとします)
- 長さが$B$の竹を作るために使われる(Group Bとします)
- 長さが$C$の竹を作るために使われる(Group Cとします)
- 使われない
のいずれかの状態をとる。
どうやらこの問題は$O(4^N)$で解けそうです。
Pythonの場合だと、itertools.product(range(4),N)を使ってそれぞれの場合について考えればよいです。このとき、Group A,B,Cそれぞれに1本以上の竹を割り振る必要があります。
Group A,B,Cに竹が$N_A,N_B,N_C$本入っているとし、長さの総和が$L_A,L_B,L_C$だったとします。
このとき延長・短縮魔法をかける必要のある回数はそれぞれ
$abs(A-L_A),abs(B-L_B),abs(C-L_C)$となります。
また、合成魔法をかける必要のある回数はそれぞれ
$N_A-1,N_B-1,N_C-1$となるため、
この場合必要なMPは
$abs(A-L_A)+abs(B-L_B)+abs(C-L_C)+10(N_A+N_B+N_C-3)$
となります。これのminが答えです
感想
- 350点位の重さがありますね