見出し画像

[ABC284 Python]AtCoder Beginner Contest 284 A～D問題Python解説

Kai

ABC284のPythonを用いた解説記事です。
ミス等ありましたら、コメントにてご連絡ください。

A問題

N = int(input())
S = [input() for _ in range(N)]
for i in range(1, N+1):
    print(S[-i])

入力された文字列SiをリストSに入れ、後ろから取り出していきます。
インデックスで考えると一番後ろはインデックス=-1、先頭はインデックス=-Nとなりますので、インデックスを指定して逆順に取り出すことができます。

B問題

T = int(input())
for i in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    for j in A:
        if j%2 == 1:
            ans += 1
    print(ans)

たまに出題される複数のテストケースが含まれる問題ですが、
特に深く考えることはありません。
最初にTを受け取り、T回分問題を解くようなプログラムを書けば問題ありません。

問題の中身は特に難しいことはなく、N個の整数が与えられるので、
その中の奇数の個数を数えるという問題でした。
奇数は2で割ると1余るという性質があるので、
それぞれの整数に対して、
上記の条件を満たすものの総数をカウントして出力します。

C問題

N, M = map(int, input().split())
visited = [False for _ in range(N)]
from collections import defaultdict
uv = defaultdict(list)
for i in range(M):
    u, v = map(int, input().split())
    uv[u-1].append(v-1)
    uv[v-1].append(u-1)
#print(uv)
def dfs(now, ans=0):
    next = uv[now]
    if next == []:
        ans = 1
    #print(next, visited)
    for i in next:
        if visited[i]:
            continue
        else:
            visited[i] = True
            ans += 1
            dfs(i)
    return ans
ans = 0
for i in range(N):
    ans += dfs(i)

print(ans)

DFSやBFSの典型的な問題です。
今回はDFSで解きましたが、よく出題されるので、復習していきましょう。

基本的な流れは以下です。
全ての点(i=0,1,…N)について、次の順序で連結成分を数えていきます。
①まずは点は2度以上調べる必要がないので、調べたか調べてないかをリストvisitedで管理します。
Trueであれば既出、Falseは未出です。
②その点に繋がっている点を取り出します。(defaultdictでuv[i]=[iに繋がっている点]とすれば辺の情報を保存できます。)
繋がっている点がない(uv[i]=[])だとすると、その点は孤立点であることが分かるので、連結成分として認め、ans += 1とします。
③繋がっている先の点について、まずその点がTrueであれば既に調べた点であるので、スルーします。未出の点であればその点をTrueにし、ans += 1
さらに再帰関数でその点から先の情報についても調べます。

最終的に変数ansに連結成分の個数が代入されるので、出力すれば大丈夫です。

D問題

T = int(input())
for i in range(T):
    N = int(input())
    ans = 0
    for j in range(2, int(N**(1/3))+1):
        if N % j == 0:
            break
    if N%j**2 == 0:
        print(j,N//j**2)
    else:
        print(int((N//j)**(1/2)), j)

問題文の意味は大体大丈夫だと思います。
N=p^2*qと表すことができるので、
pとqを求めればいいということです。

この問題の肝となる点は、
「pとqはどこまで探せばいいのか」
ということです。

pやqは素数であるので、2,3,5,…と増えていく訳ですが、
テストケースの3つ目の1059872604593911のようなNになると、
当然TLEになります。
なので、pとqを探す範囲をできるだけ狭くして計算量を少なくする工夫が必要です。

結論から申し上げますと、pとqを探す範囲は
「2から3√N(うまく書けませんが、Nの三乗根です笑)」
となります。
なぜかというと、
問題文のとおり、N = p^2*qと表せるので、
上記の条件はmin(p, q) <= 3√Nとなりますが、
もし、min(p, q) > 3√Nとすると、
p^2*q = p*p*q > 3√N*3√N*3√N = N
より、p^2*q >Nとなってしまう訳です。

なのでpとqは2~3√Nの範囲を探せばいいということが分かりました。
ここでもう一つ考えなければいけないのは、
素因数分解についてです。

p,qともに素数であるので、N=p^2*qは素因数分解の形であると分かります。
つまり、Nの約数は、
1,p,q,p*q,p^2,p^2*q(順不同)
であると分かります。

この中で先ほど求めた調べる範囲にあてはまるのは、
pもしくはqのみですね。
ですので、探して出てきた素数はpもしくはqであることが分かります。

後は、その素数がpなのかqなのか判定するのみです。
判定方法はNの約数を見れば一目瞭然です。
「Nはp^2では割り切れるけど、q^2では割り切れない」
ですね。
なので、素数を2乗して、Nで割った余りが0であればその素数はp、0以外であればqと判定することができます。


この記事が気に入ったらサポートをしてみませんか？