Codeforces #295 Div.2 A: Pangram, B: Two Buttons, C: DNA Alignment

夕方スタートのCodeforces。本番はABCを解いて全体60位。1667 → 1733 (+66)。Div1で生きていくためにもDまで解けるようになりたい。

問題はこちら。

A: Pangram

英文が与えられるので、これがpangram（すべてのアルファベットが1回以上出てくる）かどうかを判定せよ。

解法

すべてのアルファベットについて登場回数を数えて、登場回数0回のものがあるかどうかを見ればいい。大文字と小文字を区別しないことに注意。

alpha = "abcdefghijklmnopqrstuvwxyz"
hist = [0]*26
n = int(raw_input())
s = raw_input().lower()
for i in s:
    hist[alpha.index(i)] += 1
print "YES" if min(hist) > 0 else "NO"

B: Two Buttons

はじめにある正の整数nを与えらえる。あなたは持っている数字に対して次の2つの操作が行える。

1. 持っている数字を2倍にする
2. 持っている数字から1をひく。

この2つの操作を繰り返して、与えられた数字をmにしたい。mにするのに必要な操作回数の最小値はいくらか答えよ。

解法

BFSで解いた。持っている数字と操作回数をキューに入れて、目的の数字が出てくるまで操作を繰り返す。usedリストで一度調べた数字を調べないように工夫しないと（少なくともpythonでは）TLEとなってしまうので注意。

n,m = map(int,raw_input().split())
if n >= m:
    print n-m
else:
    used = [False]*50001
    used[n] = True
    que = [[n,0]]
    while 1:
        k,i = que.pop(0)
        if k == m:
            break
        if k < m and not used[2*k]:
            used[2*k] = True
            que.append([2*k,i+1])
        if 1 < k and not used[k-1]:
            used[k-1] = True
            que.append([k-1,i+1])
    print i

C: DNA Alignment

AGCTからなる長さNの文字列sを与えられる。これとは別にAGCTからなる同じ長さの文字列tを用意し、ある式（問題を参照してください）に従ってsとtの間で一致する文字をカウントする。このカウントを最大とするような文字列tは何種類あるかを答えよ。

解法

一見複雑に見えるが、手元でいろいろと実験してみると方針が見えてくる問題。各文字のs中での登場回数をカウントし、もっとも大きいカウントとなる文字がいくつあるかを数える。

1つの場合(例えばA)のとき、AAA....Aとなるtが与えられた式の値を最大にする。

2つの場合(例えばAとC)のとき、AAA..+CCC..を並び替えてできるすべてのtが式の値を最大化する。

3つと4つの場合も同様となる。

与えられた式はsとtを、ありうる比較の始点すべてで比べているので、s中での登場回数が多い文字でtが構成されていた方が式の値は大きくなり、tの文字の並び方には影響を受けない。 s中の登場回数が最大となる文字の数をnumとしたとき、答えは num^N % mod となる。

mod = 10**9+7
n = int(raw_input())
dna = raw_input()

cnt = sorted([dna.count("A"),dna.count("G"),dna.count("C"),dna.count("T")])[::-1]
num = cnt.count(cnt[0])

ans = 1
for i in xrange(n):
    ans = ans * num % mod

print ans