ABC249C - 解説つき！競ってわかる　はじめてpythonプログラミング

ABC249C の解説

解答コード

https://atcoder.jp/contests/abc249/submissions/31307760 （シンプル）
https://atcoder.jp/contests/abc249/submissions/31220829 （numpy）
https://atcoder.jp/contests/abc249/submissions/31221873 （DFS，解説しない）

問題

任意の文字列を選び，アルファベットの個数を数える問題です．

解説

考え方について，概要図を投下します．

文字列の選択の仕方についてbit全探索を行います．そのときに，アルファベットの出現回数がKになる個数をカウントし，最後のそのカウントの最大値を求めれば良いです．

bit全探索を行うための処理ですが，こちらの関数で実行しました．
bit全探索の記述方法はたくさんあります．
itertoolsのproductや，itertoolsのcombinationsを使うことも可能です．
長くなるので，ここでの言及は避けます．
docstring内にあるExample をみてもらえれば，処理の概要は理解してもらえると思います．
全て0で始まる初めのイテレーションを避けたいときに変更が容易なので，最近はこのような自作関数（またはクラス）で使用してます．
解説のために少し手直しました \(^o^)/．

def bitrange(n, start=0, stop=None):
    """
    make bit sequences. 

    Parameters
    ----------
    n : int
        bit length

    Yields
    ------
    seq: list

    Example
    -------
    >>> for seq in bitrange(2):
    >>>    print(seq)
    [0, 0]
    [1, 0]
    [0, 1]
    [1, 1]
    """

    def countup():
        for i in range(n):
            seq[i] += 1
            seq[i] %= 2
            if seq[i] == 1:
                break

    seq = [(start>>j)&1 for j in range(n)]
    if stop is None: 
        stop = 1<<n
    for _ in range(start, stop): 
        yield seq
        countup()

標準入力を読み込みます．Sは長さ26の配列で管理しても，文字列を数字に置き換えた状態のどちらで管理しても良いと思います．
ansのとりうる最小値として暫定的に0で定義しておきます．

N, K = map(int, input().split())
S = [[ord(s)-97 for s in input()] for _ in range(N)]
ans = 0

bit探索を実行します．使用する（seqが1のところの）文字列に含まれるアルファベットの出現個数を+1します．
最後に，count関数でK個の配列数を数えて，暫定的な答えと大小比較します．

for seq in bitrange(N):
    bucket = [0]*26
    for bit, Si in zip(seq, S):
        if bit:
            for si in Si:
                bucket[si] += 1
    cnt = bucket.count(K)
    ans = max(ans, cnt)
print(ans)

続いて，numpyの解法について説明します．
numpyでは，Sの文字列を長さ26のベクトルとして扱います．
説明のために3つのベクトルのうち任意の個数選んだベクトルの和を考えたいと思います．
このとき表は次のようにして求められます．

これを今回のN個の長さ26のベクトルついて考えます．
numpyのインポートと長さ26のN個のベクトルを読み込みます．

N, K = map(int, input().split())
S = np.zeros((N, 26), int)
for i in range(N):
    for s in input():
        S[i, ord(s)-97] = 1

初期値は全て0で定義して，表の1行目から順に計算していきます．

X = np.zeros((2**N, 26), int)
r = 1
for i in range(N):
    X[r:r*2] = X[:r] + S[i]
    r *= 2

これで，上図でいう表（ここでは行列）になっているので，
最後にK個となる数を数えて最大値をとります．

ans = (X == K).sum(axis=1).max()
print(ans)

以上，ABC249Cの解説でした．

＜参考解説リンク＞