【世界一わかりやすい】Atcoder ABC249 C・D問題 Python3解説

ABC249のC,D問題を、Python3で解説します！

とにかく読みやすさを重視した、初心者向け解説です(´・ω・｀)

ゆっくり見ていってね(｀・ω・´)ｷﾘｯ

C問題 『Just K』

問題ページ：C問題 - Just K

考え方

まず、全探索できないか考えよう(｀・ω・´)
$N≦15$なので、$S_1, S_2, ..., S_N$ の中から、好きな個数だけ選ぶ選び方は、せいぜい2の15乗で、$32768$通り。（コードの中では、0indexで考えていくよ）
選び方を全て列挙して、それぞれの場合に、$K$個出現する文字の種類数を数える。

そして、組み合わせ列挙といえば、itertools(｀・ω・´)

itertoolsについて(他サイトより引用させていただきました)
https://note.nkmk.me/python-math-factorial-permutations-combinations/

また、文字の出現回数を調べるときは、collections.Counter()が便利(｀・ω・´)
collections.Counter()は、リストの要素をkey, 要素の出現回数をvalueにもつディクショナリを作ってくれる。

collections.Counter()について(他サイトより引用させていただきました)
https://note.nkmk.me/python-collections-counter/

今回、$S_i$の中に同じ文字は含まれていないので、選んだ$S$を連結して、collections.Counter()を使って、$K$個出現した文字の種類数を数えればいい。
助かる(´・ω・｀)

コード

C.py

'''
入力例
4 2
abi
aef
bc
acg
'''

import itertools
import collections

n, k = map(int, input().split())
S = [] #ここにS0,S1,...,Snを入れていく 

for i in range(n):
    s = list(input()) #collections.Counterを使いたいので、入力をリストにしておく
    S.append(s)

#いまSの中身はこんな感じ
#S = [['a', 'b', 'i'], ['a', 'e', 'f'], ['b', 'c'], ['a', 'c', 'g']]

comb = [] #ここに0~n-1の中から、1~n個選ぶ時の組み合わせを入れていく

for i in range(1, n+1):
    comb += list(itertools.combinations(range(n), i))

#いまcombの中身はこんな感じ
#comb = [(0,), (1,), (2,), (3,), (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3), (0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3), (0, 1, 2, 3)]

ans = 0

for c in comb:
    cnt = 0
    L = []
    for cc in c:
        L += S[cc]
    #例えば、c = (0, 1) の時、Lの中身はこんな感じ↓。選んだsを全部繋げている。
    #L = ['a', 'b', 'i', 'a', 'e', 'f']
    dic = collections.Counter(L)
    #collection.Counter()は、リストの要素をkey, 要素の出現回数をvalueにもつディクショナリ。中身はこんな感じ↓
    #dic = Counter({'a': 2, 'b': 1, 'i': 1, 'e': 1, 'f': 1})
    for d in dic:
        #出現回数がkのものがあったらcntに1足す
        if dic[d] == k:
            cnt += 1
    #最大値を更新したら置き換える
    if cnt>ans:
        ans = cnt

print(ans)

D問題 『Index Trio』

問題ページ：D問題 - Index Trio

考え方

$N≦2×10^5$なので、$i, j, k$のうち、2つについて考えた時点で、$O(N^2)$となりアウト(´・ω・｀)
てことは、$A_1$~$A_N$までのそれぞれに、何かしていくんだろうな、とざっくり考える。
これなら（処理の中身にもよるけど）$O(N)$で済む(｀・ω・´)

$A_1$~$A_N$それぞれの約数のペアを高速で求めて、それが$A_1$~$A_N$に存在するか求めればいい。

約数の高速列挙について(他サイトより引用させていただきました)
約数を$O(\sqrt{N})$で求められるよ！
https://tamlog.hateblo.jp/entry/2021/07/28/020046
今回は列挙ではなく、ペアを求めたいため、一部コードを改変しています。

$A_1$~$A_N$は重複する可能性もあるので、collections.Counter()を使って、出現回数を求めておき、順列の総数を求める。

このとき、collections.Counter()をdefaultdictにしておくと便利(｀・ω・´)
普通のディクショナリでは、存在しないkeyを指定するとエラーになるが、defaultdictでは存在しないkeyを指定すると0を返してくれる。
そのため、場合分けをする必要がなくなって嬉しい(｀・ω・´)

defaultdictについて(他サイトより引用させていただきました)
https://qiita.com/xza/items/72a1b07fcf64d1f4bdb7

コード

※L = make_divisors(i)をL = make_divisors(A[i])に訂正しました
（2022/04/26追記）

D.py

import collections

n = int(input())
A = list(map(int, input().split()))

dic = collections.defaultdict(int) #defaultdict化しておく
dic = collections.Counter(A)

#約数のペアを求める関数
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append((i, n//i))

    return divisors

#例えば、make_divisors(4)ならこんな感じ↓
#[(1, 4), (2, 2)]

ans = 0

for i in range(n):
    L = make_divisors(A[i])
    for l in L:
        if l[0] == l[1]: #(2, 2)など、同じ数字の時
            ans += dic[l[0]]**2
        else:
            ans += dic[l[0]]*dic[l[1]]*2

print(ans)

まとめ

最後まで見てくれてありがとう(´・ω・｀)
これからも自分の勉強がてらABCのC,D問題とか、過去問の解説上げてくかも。
来週も頑張ろうね(｀・ω・´)ｷﾘｯ