Codeforces#329 A問題 2Char やってみた

問題

codeforces.com

n個与えられる語を任意に組み合わせ連結して、2個以下のアルファベットでできる最長の語（の長さ）を答える
サンプルはリンク先参照

最初に思い浮かんだこと

「使うかに使わないか」2通りなんだから2のn乗通り試せばいいだろ

思い浮かんだこと

• 3文字以上使ってる語は無視
• 2文字からなる語と1文字からなる語は区別したほうがよさそう
• (x, y) で作れる最長の語の長さは (x, y) , xだけ、yだけ の語の長さの和
• その和同士を比べれば

思った通り書いた

#!/usr/bin/python
# -*- coding: utf-8 -*-

N = input()

single = dict()
double = dict()

for loop in xrange(N):
    inp = raw_input()
    if len(set(inp)) == 1:
        l = inp[0]
        single[l] = single.get(l, 0) + len(inp)

    if len(set(inp)) == 2:
        l = tuple(set(inp))
        double[l] = double.get(l, 0) + len(inp)
# まず文字数ごとに分けてディクショナリを作る。keyが文字(のタプル) で value は作れる語の長さ
# 変数が l 1文字は見にくかったかも。letter の l 

for key in double:
    x, y = key[0], key[1]
    double[(x, y)] += single.get(x, 0) + single.get(y, 0)
#これで value は (x,y) から作れる最長の語の長さなはず

maxs = max(single.values()) 
maxd = max(double.values())
winner = max(maxs, maxd)
# 1文字だけのほうが長くできる可能性もたまにあるので

print winner

Runtime error on test 3

Oh..

test 3:

1
a

double が空なのに max(double.values()) って言ったせいで

ValueError: max() arg is an empty sequence

って言われた。

stackoverflow.com

改良版

前略

try:
    maxs = max(single.values())
except:
    maxs = 0
try:
    maxd = max(double.values())
except:
    maxd = 0
winner = max(maxs, maxd)

print winner

Wrong answer on test 12

Oh..

test 12:

5
zzz
zzzz
zz
z
aaaaaaaaaaaaaaaaaaaaaaaaaaa

「1文字だけ」+「1文字だけ」のパターンをカバーできてなかった模様

改改良版

前略

try:
    maxs = max(single.values())
except:
    maxs = 0
try:
    maxd = max(double.values())
except:
    maxd = 0
try:
    maxss = sum(sorted(single.values(), reverse=True)[:2])
except:
    maxss = 0

winner = max(maxs, maxd, maxss)
print winner

これで Accepted

どうなんでしょうか

おわり

• ディクショナリってあんまり使われてない？
• 提出する前にうまくいかなそうなケースに気付きたい

codeforces.com