CとDの解答。Dは本番中に正解できなかった。

C: A and B and Team Training

プログラミングコンテストに出るチームを編成したい。1チームは経験者1人と未経験者2人、もしくは経験者2人と未経験者1人の3人で構成されるとする。経験者と未経験者の人数n,mが与えられるので、作ることのできるチーム数の最大値を答えよ。

解法

nとmの多い方から2を引き、少ない方から1を引くことを繰り返していけばいい。n,mが両方とも1のときは、それ以上チームを作れないので注意。

n,m = map(int,raw_input().split())
ans = 0
while n and m:
    if max(n,m) == 1: break
    if n > m:
        n -= 2
        m -= 1
    else:
        n -= 1
        m -= 2
    ans += 1
print ans

C問題にしてはずいぶんと簡単だった。

D: A and B and Interesting Substrings

英小文字からなる文字列sと各文字へのポイント表xが与えられる。sの部分文字列で、初めと終わりが同一文字で、初めと終わりを除いた文字のポイントの合計が0であるようなものはいくつあるか答えよ。|s| ≦ 10⁵, 10^-5 ≦ xi ≦ 10⁵。

解法

はじめからどんどんと文字のポイントを足し合わせることを考える。文字列長が最大10⁵なので、ポイントの総和も最大10⁵通りしかない。合計のポイントが0で始点と終点が同一文字の区間を探すために、ポイントの総和に対してその文字列の末尾を記録していく。

ある場所 i で総和がsumとなった場合、場所j (j < i) で総和がsum-x[s[i]]かつ、s[i] = s[j]となるような場所があれば、その2つの区間の差での合計のポイントは0であり、始点と終点も同じ文字なので条件を満たす。

したがってsumに対応した文字の数リストを抱えて、前から順番に文字のポイントを足していき、sum-x[s[i]]かつ、s[i] = s[j]となる場所の数を足していけばいい。

from collections import defaultdict

def hist():
    return [0]*26
    
alpha = "abcdefghijklmnopqrstuvwxyz"
atoi = {alpha[i]:i for i in xrange(26)}

x = map(int,raw_input().split())
s = [atoi[si] for si in raw_input()]
n = len(s)

sums = defaultdict(hist)
sum = 0
ans = 0
for i in xrange(n):
    sum += x[s[i]]
    ans += sums[sum-x[s[i]]][s[i]]
    sums[sum][s[i]] += 1
print ans