読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

RUPC2016 Day1 C : AddMul

競プロ 考察

本番ではkenkooooさんにお任せしていた問題。

問題

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=C

解法

次の例を考える。

a+b+b+b+c+c+c+d+d+d = 1*a+3*b+3*c+3*d (15文字)

左辺が入力、右辺が掛け算のみを用いた短縮形である。右辺の短縮形をデフォルトとして考える。文字の種類1つごとに「n*x+」(n:個数, x:数字)が増えると考えると、この短縮形の長さは4 * 4 - 1文字である。(最後の「+」は不要なので引く)。

次に、「1*」は明らかに無駄である。そこで、個数が1となる文字の分だけ、短縮形の長さから2を引く。

1*a+3*b+3*c+3*d = a+3*b+3*c+3*d (13文字)

最後に、同じ係数の項が2個以上あれば「3*(a+b+c)」とまとめられる。この操作により「3*」が3個減り「3*()」が1つ増えるので、結局2文字減らせる。

a+3*b+3*c+3*d = a+3*(b+c+d) (11文字)

以上をまとめて次のように解けばOK。

  1. ans = 4 * (文字の種類数) - 1で初期化
  2. ans -= 2 * (「個数が1の文字」の種類数)
  3. 「個数が2以上の文字」について、その種類数mが2以上であるとき、ans -= 2 * (m - 2)
from collections import Counter

N = input()
S = input().split('+')

dic_chr_num = Counter(S)
dic_num_kind = Counter(dic_chr_num.values())

ans = 4 * len(dic_chr_num) - 1
for num, kind in dic_num_kind.items():
    if num == 1:
        ans -= 2 * kind
    elif kind >= 2:
        ans -= 2 * (kind - 2)

print(ans)