問題一覧 > 通常問題

No.1780 [Cherry Anniversary] 真冬に咲く26の櫻の木

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 33
作問者 : 👑 KazunKazun / テスター : eSeFeSeF
5 ProblemId : 7271 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-30 23:05:43

この問題はAdvent Calendar Contest 2021 9日目の問題 (I問題) である

この問題は 2021 年 12 月 9 日現在の情報をもとに作成した. 現在では情報が更新されており, 不適合な場合がある (サンプルケースの入力).

問題文

26本の桜の木があり, それぞれ桜 A, 桜 B, $\cdots$, 桜 Zと名付けられている.

最初, 桜 $\alpha$ は色 $C_\alpha$ の花を咲かせている.

ここで, この26本の桜の木について調査したところ, 以下の $N$ 個の性質を持っていることがわかった.

  • $i$ 番目の能力は $S_i$ と言われている. 桜 $\alpha$ について, $\alpha$ が文字列 $S_i$ に含まれているそのときに限り, 行動を行うことができる.
    • 桜 $\alpha$ がその時点で色 $A_i$ の花を咲かせている場合, エネルギー $E_i$ を得て, 花の色を $B_i$ に変える.
    • 桜 $\alpha$ がその時点で色 $B_i$ の花を咲かせている場合, エネルギー $E_i$ を得て, 花の色を $A_i$ に変える.
得るエネルギーは負になる場合もあることに注意せよ.

桜 $\alpha$ は使える能力を合計 $K_\alpha$ 回まで能力を使うことができる (同じ能力を複数回使ってもよく, 1回も使わない能力があってもよい).

このとき, 26本の桜の木の咲いている花が全て同じ色になることは可能か? 可能な場合, 26本の桜の木の咲いている花が全て同じ色になるような能力の使い方で, 得るエネルギーの総和の最大値を求めよ.

制約

  • $1 \leq C_\alpha \leq 16$
  • $0 \leq K_\alpha \leq 10^7$
  • $0 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i, B_i \leq 16$
  • $A_i \neq B_i$
  • $-10^7 \leq E_i \leq 10^7$
  • $S_i$ は英大文字からなる文字列
  • $|S_i| \leq 30$
  • 入力される数は全て整数

入力

$C_{{\rm {A}}}$ $C_{{\rm {B}}}$ $C_{{\rm {C}}}$ $C_{{\rm {D}}}$ $C_{{\rm {E}}}$ $C_{{\rm {F}}}$ $C_{{\rm {G}}}$ $C_{{\rm {H}}}$ $C_{{\rm {I}}}$ $C_{{\rm {J}}}$ $C_{{\rm {K}}}$ $C_{{\rm {L}}}$ $C_{{\rm {M}}}$ $C_{{\rm {N}}}$ $C_{{\rm {O}}}$ $C_{{\rm {P}}}$ $C_{{\rm {Q}}}$ $C_{{\rm {R}}}$ $C_{{\rm {S}}}$ $C_{{\rm {T}}}$ $C_{{\rm {U}}}$ $C_{{\rm {V}}}$ $C_{{\rm {W}}}$ $C_{{\rm {X}}}$ $C_{{\rm {Y}}}$ $C_{{\rm {Z}}}$
$K_{{\rm {A}}}$ $K_{{\rm {B}}}$ $K_{{\rm {C}}}$ $K_{{\rm {D}}}$ $K_{{\rm {E}}}$ $K_{{\rm {F}}}$ $K_{{\rm {G}}}$ $K_{{\rm {H}}}$ $K_{{\rm {I}}}$ $K_{{\rm {J}}}$ $K_{{\rm {K}}}$ $K_{{\rm {L}}}$ $K_{{\rm {M}}}$ $K_{{\rm {N}}}$ $K_{{\rm {O}}}$ $K_{{\rm {P}}}$ $K_{{\rm {Q}}}$ $K_{{\rm {R}}}$ $K_{{\rm {S}}}$ $K_{{\rm {T}}}$ $K_{{\rm {U}}}$ $K_{{\rm {V}}}$ $K_{{\rm {W}}}$ $K_{{\rm {X}}}$ $K_{{\rm {Y}}}$ $K_{{\rm {Z}}}$
$N$
$S_1$ $A_1$ $B_1$ $E_1$
$\vdots$
$S_N$ $A_N$ $B_N$ $E_N$
(注意): $C_{{\rm {N}}}, K_{{\rm {N}}}$ と, $S_N$ の添字の "エヌ" は違うものを表していることに注意せよ ($C_{{\rm {N}}}, K_{{\rm {N}}}$ は桜の木の名前 N, $S_N$ は3行目で入力される能力の個数 $N$ である).

出力

26本の桜の木の咲いている花が全て同じ色になることが不可能な場合, Impossible, 可能な場合, 得るエネルギーの総和の最大値を求めよ.

サンプル

サンプル1
入力
1 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
1 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4
ABE 1 2 -1
ABC 2 3 -1
ABD 1 3 -10
CD 2 3 100
出力
88

次のように能力を使うと全ての桜の木に咲く花の色を色 $3$ にすることができる. だだし, $S$ と言われている能力を使い, 花の色を $A$ から $B$ に変えることを $A \xrightarrow{[S]} B$ と表すことにする.

  • 桜 A: $1 \xrightarrow{[{\rm ABD}]} 3$
  • 桜 B: $1 \xrightarrow{[{\rm ABE}]} 2 \xrightarrow{[{\rm ABC}]} 3$
  • 桜 C: $2 \xrightarrow{[{\rm CD}]} 3$
  • 桜 D, $\dots$, 桜 Z: 何もしない
このとき, 得るエネルギーは $\underbrace{(-10)}_{{\rm A}}+\underbrace{(-1-1)}_{{\rm B}}+\underbrace{(100)}_{{\rm C}}+\underbrace{(0)}_{{\rm D}}+\dots+\underbrace{(0)}_{{\rm Z}}=88$ である. また, 全ての桜の木に咲く花の色を同じにする方法で, 得るエネルギーを $88$ より大きくすることはできない. よって, $88$ が答えである.

ここで, 以下のようなエネルギーの使い方はできないことに注意せよ.

  • $\times$ 桜 A が最初に $[{\rm ABC}]$ を使う $\cdots$ 最初, 桜 A は色 $2$ でも色 $3$ でもないので使えない.
  • $\times$ 桜 D が $[{\rm ABE}]$ を使う $\cdots$ ABE の中に D は含んでいないので, 使えない.
  • $\times$ 桜 A が $1 \xrightarrow{[{\rm ABE}]} 2 \xrightarrow{[{\rm ABC}]} 3$ と能力を使う $\cdots$ $K_{{\rm A}}=1$ なので, $2$ 回能力は使えない.

サンプル2
入力
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
0
出力
Impossible

26本の桜の木が咲いている花の色は一致していないのに, 能力を使うことができないので, 咲いている花の色を同じにすることはできない.

サンプル3
入力
2 1 1 4 4 4 2 1 5 6 1 15 7 9 4 2 1 13 13 1 9 3 11 16 2 1
24 24 23 22 23 26 24 21 24 26 23 20 22 21 22 18 23 19 23 20 19 22 23 20 21 16
37
FAULT 1 2 -10
FALLINLOVE 2 3 -3
DOUBT 3 4 -8
PLASTIC 4 5 100
SUBWAY 5 6 -85
BUDDY 6 7 12
BLUEMOON 7 8 0
BAN 8 9 -1
ANSWER 9 10 77
LOVE 10 11 4
LAUNDRY 11 12 5
MICROSCOPE 12 13 74
NOTLONELY 13 14 -4
ANTHEM 14 15 6
STRAYBULLET 1 15 9
DEADEND 4 6 46
SONIA 3 7 35
JAMAICA 8 10 -3
ONWAY 4 13 -4
SILENT 5 10 -4
NERVOUS 9 11 1
ABCDEFGHIJKLMNOPQRSTUVWXYZ 1 2 4
ABCDEFGHIJKLMNOPQRSTUVWXYZ 2 3 7
ABCDEFGHIJKLMNOPQRSTUVWXYZ 3 4 -4
ABCDEFGHIJKLMNOPQRSTUVWXYZ 4 5 5
ABCDEFGHIJKLMNOPQRSTUVWXYZ 5 6 10
ABCDEFGHIJKLMNOPQRSTUVWXYZ 6 7 53
ABCDEFGHIJKLMNOPQRSTUVWXYZ 7 8 31
ABCDEFGHIJKLMNOPQRSTUVWXYZ 8 9 10
ABCDEFGHIJKLMNOPQRSTUVWXYZ 9 10 -46
ABCDEFGHIJKLMNOPQRSTUVWXYZ 10 11 46
ABCDEFGHIJKLMNOPQRSTUVWXYZ 11 12 5
ABCDEFGHIJKLMNOPQRSTUVWXYZ 12 13 13
ABCDEFGHIJKLMNOPQRSTUVWXYZ 13 14 64
ABCDEFGHIJKLMNOPQRSTUVWXYZ 14 15 19
ABCDEFGHIJKLMNOPQRSTUVWXYZ 15 16 0
ABCDEFGHIJKLMNOPQRSTUVWXYZ 16 1 31
出力
35282
サンプル4
入力
2 4 2 15 4 11 6 1 5 6 15 15 7 11 6 12 14 15 13 11 9 4 13 16 4 3
104 1007 1114 1023 215 1129 707 507 1112 516 727 129 417 418 1012 1219 629 323 1021 829 112 1013 505 710 102 928
26
A 2 10 1
B 4 10 1
C 2 10 1
D 15 10 1
E 4 10 1
F 11 10 1
G 6 10 1
H 1 10 1
I 5 10 1
J 6 10 1
K 15 10 1
L 15 10 1
M 7 10 1
N 11 10 1
O 6 10 1
P 12 10 1
Q 14 10 1
R 15 10 1
S 13 10 1
T 11 10 1
U 9 10 1
V 4 10 1
W 13 10 1
X 16 10 1
Y 4 10 1
Z 3 10 1
出力
17518

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。