Go to Qiita Advent Calendar 2024 Top
LoginSignup
5
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

@sano192

ABC284 A～E問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

Last updated at Posted at 2023-01-10

ABC284(AtCoder Beginner Contest 284)　A～E問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

その他のABC解説、動画などは以下です。

更新時はツイッターにて通知します。
https://twitter.com/AtCoder4

A Dif:10

まず各入力をリストに受け取ります。
次にリストの内容をひっくり返します。
最後にリストの内容を順に出力します。

この問題では
・リストの使い方
・リスト内容をひっくり返す(逆順にする)方法
・リストの内容を順に出力する方法
を知っている必要があります。コンテスト中でもわからなければググりましょう。

・リストの使い方
リストは複数の要素を入れられる箱のようなものです。
まず空のリストを用意しましょう。名前をAとします。

A=[]

次にN回入力を受け取り、順にAへ格納します。
N回処理を行うときはfor i in range(繰り返し回数)と書きましょう。
リストへの追加は.append(追加する要素)と書きます。

for i in range(N):
    S=input()
    A.append(S)

リストの内容をひっくり返す(逆順にする)には
リスト名[::-1]
と書きます。

A=A[::-1]

最後にリストの内容を順に出力します。
for i in range(N)と書くことでi=0,1,2,3,...,(N-1)と順番に代入しながら処理ができます。
Aの最初の要素はA[0]、次がA[1],...となっているので、A[i]を出力すればOKです。

入力の受け取り、出力がわからない方は以下の記事を参考にしてください。

【提出】

# 入力の受け取り
N=int(input())

# 空のリストを用意
A=[]

# i=0~(N-1)
for i in range(N):
    # 入力の受け取り
    S=input()
    # SをAに追加
    A.append(S)

# Aの内容をひっくり返す
A=A[::-1]

# i=0~(N-1)
for i in range(N):
    # A[i]を出力
    print(A[i])

B Dif:14

まず制約を確認しましょう。
Nは最大100なので、Aそれぞれの要素が奇数かどうか確認する方法だとテストケース1個あたり100回の計算が必要になります。
更にテストケースは最大100個なので計算量は最大で100*100=10000回になります。

pythonでは制限時間2秒以内にだいたい10^6=1000000回の計算ができますのでこれなら余裕で間に合います。

Aの各要素が奇数かどうかは2で割った余りが1になっているかで確認します。

【提出】

# 入力の受け取り
T=int(input())

# T回
for i in range(T):
    # 入力の受け取り
    N=int(input())
    A=list(map(int, input().split()))

    # 答え
    ans=0

    # i=0~(N-1)
    for i in range(N):
        # A[i]を2で割った余りが1ならば
        if A[i]%2==1:
            # 答えにカウント
            ans+=1
            
    # 答えの出力
    print(ans)

C Dif:193

BFS(幅優先探索)で解きます。
BFSは幅優先探索(breadth first search)の略称で、グラフを探索するアルゴリズムです。

BFSの解説動画を作りましたので、本問が難しいと感じた方は是非御覧ください。

(1)つながっている頂点を記録する
(2)各頂点が訪問済みかどうかを記録するリストを作る
(3)頂点i=1,2,3,...について訪問済みでなければ答えにプラス1してBFSを開始
(4)キューに頂点iを入れ、訪問済みにする
(5)キューの左端から頂点の番号を取り出す=今いる頂点
(6)今いる頂点から行ける頂点が未訪問ならば、訪問済みにしてキューへ追加
(7)キューが空になるまで(5)~(6)を繰り返し、空になったら(3)へ戻る
※キューについてわからない人は下部の「dequeについて」を御覧ください。

実際にやってみましょう。

以下のようなグラフを考えます。
ABC284C1.png

(1)つながっている頂点を記録する
これはconnectという二次元配列に記録します。
例えば頂点①と頂点②がつながっているので
connect[1]=[2]
となります。
頂点②は頂点①,頂点④とつながっているので
connect[2]=[1,4]
となります。
これらの関係を全て記録します。

(2)各頂点が訪問済みかどうかを記録するリストを作る
訪問済みかどうかなので名前をvisitedとします。
例えばvisited[1]=Falseなら頂点①は未訪問、=Trueなら訪問済みです。

(3)頂点i=1,2,3,...について訪問済みでなければ答えにプラス1してBFSを開始
i=1、すなわち頂点①からスタートです。頂点①はvisited[1]=Falseで未訪問なので答えにプラス1してBFSを開始します。
答え：1

(4)キューに頂点iを入れ、訪問済みにする
キューに頂点①を入れます。
キュー：1
訪問済みにします。
visited[1]=True

(5)キューの左端から頂点の番号を取り出す=今いる頂点
キューには頂点①が入っているので取り出します。
キュー：(空)

(6)今いる頂点から行ける頂点が未訪問ならば、訪問済みにしてキューへ追加
頂点①から行けるのは頂点②です。
頂点②は未訪問なので訪問済みにしてキューへ追加します。
キュー：2
visited[2]=True

(7)キューが空になるまで(5)~(6)を繰り返し、空になったら(3)へ戻る
キューはまだ空でないので(5)へ戻ります。

(5)キューの左端から頂点の番号を取り出す=今いる頂点
キューには頂点②が入っているので取り出します。
キュー：(空)

(6)今いる頂点から行ける頂点が未訪問ならば、訪問済みにしてキューへ追加
頂点②から行けるのは頂点①,頂点④です。
頂点①は訪問済みなので無視です。
頂点④は未訪問なので訪問済みにしてキューへ追加します。
キュー：4
visited[4]=True

これを繰り返すと頂点①,②,④,⑤が訪問済みになり、キューが空になります。
空になったら(3)へ戻ります。

(3)頂点i=1,2,3,...について訪問済みでなければ答えにプラス1してBFSを開始
i=2はすでに訪問済みです。(つまり頂点①とつながっている=連結成分の内にあるということです)
i=3は未訪問です。(つまり頂点①,頂点②とつながっていない=連結成分でないということです)
頂点③を含む連結成分を追加するので、答えにプラス1します。

これを繰り返すことで連結成分の数を数えることができます。

dequeについて
dequeはリストのようなものですが、先頭から要素を取り出す操作をO(1)で行うことができます。
(リストだとO(N)かかります)
インポート：from collections import deque
作成：変数名=deque()
先頭(左端)に要素追加【O(1)】：変数名.appendleft(要素)
末尾(右端)に要素追加【O(1)】：変数名.append(要素)
先頭(左端)から要素を取り出して削除【O(1)】：変数名.popleft()
末尾(右端)から要素を取り出して削除【O(1)】：変数名.pop()

【使用例】

# インポート：from collections import deque
from collections import deque

# 作成：変数名=deque()
que=deque()

# 先頭(左端)に要素追加【O(1)】：変数名.appendleft(要素)
que.appendleft(1)

# 末尾(右端)に要素追加【O(1)】：変数名.append(要素)
que.append(3)

# 先頭(左端)から要素を取り出して削除【O(1)】：変数名.popleft()
x=que.popleft()

# 末尾(右端)から要素を取り出して削除【O(1)】：変数名.pop()
y=que.pop

詳しく知りたい人は以下のページを見てください。

【提出】

# 入力の受け取り
N,M=map(int, input().split())

# つながっている頂点の記録
connect=[[] for i in range(N+1)]

# M回
for i in range(M):
    # 入力の受け取り
    A,B=map(int, input().split())
    # A→Bがつながっている
    connect[A].append(B)
    # B→Aがつながっている
    connect[B].append(A)

# dequeのインポート
from collections import deque

# 答え
ans=0

# 訪問済みかどうかの記録
visited=[False]*(N+1)

# i=1~N
for i in range(1,N+1):

    # もし頂点iが訪問済みでなければ
    if visited[i]==0:
        # 答えにプラス1(新しい連結成分)
        ans+=1
        # 頂点iを訪問済みにする
        visited[i]=True
        # キューを作る
        que=deque()
        # キューにiを追加
        que.append(i)

        # キューが空になるまで
        while 0<len(que):
            # キューの左端から取り出し(今いる頂点)
            now=que.popleft()

            # to：今いる頂点から行ける頂点
            for to in connect[now]:
                # 頂点toが訪問済みでなければ
                if visited[to]==False:
                    # 訪問済みにする
                    visited[to]=True
                    # キューに追加
                    que.append(to)

# 答えの出力
print(ans)

D Dif:658

重要なことは以下の2つです。
・p,qのどちらかがわかれば他方も簡単にわかる
pがわかればq=N//p^2
qがわかればp=√(N//q)
と計算できます。

・p,qのどちらかは必ず10^7より小さい
仮に両方が10^7だと
p^2*q=(10^7)^2*(10^7)=10^21
となるのでNの制約を超えてしまいます。

以上よりx=2,3,4,...と試し割りし、p,qのどちらかを見つければよいということがわかります。

pythonでは間に合わないのでpypyで提出します。

【提出】

# pypyで提出

# 平方根計算用にsqrtをインポート
from math import sqrt

# 入力の受け取り
T=int(input())

# T回
for i in range(T):
    # 入力の受け取り
    N=int(input())

    # x=2~10^7
    for x in range(2,10**7+1):
        # Nがx^2で割り切れる場合
        # ⇔p=x
        if N%x**2==0:
            # q=N//x^2
            print(x,N//x**2)
            # 次のNへ
            break
        # Nがxで割り切れる場合
        # ⇔q=x
        elif N%x==0:
            # p=√(N//q)
            print(int(sqrt(N//x)),x)
            # 次のpへ
            break

E Dif:1043

実際に単純パスを作りながら数えていきます。

pathというsetを作り、DFSで頂点を回りながら経路に含まれる頂点を追加していきます。
進める頂点がなくなったらpathから削除して戻ります。(最も深い場所に来た場合やループの場合)

ちなみに【提出】のコードはpythonだとACしますがpypyだとTLEするので、普段pypyで提出している人は注意してください。

再帰関数やDFSを書いた経験のある人は比較的簡単に理解、実装できると思いますが、そうでない場合は難しいです。
本問の前に簡単なDFS問題で練習することをおすすめします。
ABC213Dがおすすめです。
ABC213D：https://atcoder.jp/contests/abc213/tasks/abc213_d
解説：https://qiita.com/sano192/items/f4e7c64184714dce6ebf#d---takahashi-tour
また、DFSの解説動画もあるのでそちらもぜひご覧ください。

【提出】

# 再帰回数上限を10^6へ変更(再帰関数を使うときは必須)
import sys
sys.setrecursionlimit(10**6)

# 入力の受け取り
N,M=map(int, input().split())

# つながっている頂点の記録
connect=[[] for i in range(N+1)]

# M回
for i in range(M):
    # 入力の受け取り
    A,B=map(int, input().split())
    # A→Bへ行ける
    connect[A].append(B)
    # B→Aへ行ける
    connect[B].append(A)

# 答え
ans=0
# 経路に含まれる頂点
path=set()

# DFS(今いる頂点)
def DFS(now):
    # path,ansを更新できるように
    global path,ans

    # pathに今いる頂点を追加
    path.add(now)
    # 答えにプラス1
    ans+=1
    # もし答えが10^6になったら
    if ans==10**6:
        # 出力
        print(ans)
        # 終了
        exit()

    # to：今いる頂点から行ける頂点
    for to in connect[now]:
        # 行ける頂点が経路に含まれていなければ
        if to not in path:
            # 次のDFSへ
            DFS(to)

    # 今いる頂点から進める頂点がなくなったら経路から削除
    path.remove(now)

# 頂点1からDFSスタート
DFS(1)
# 答えの出力
print(ans)

【広告】

『AtCoder 最速で緑になる 基礎・典型50問詳細解説』

ABC201～250から基礎・典型問題50問をとてつもなく丁寧かつ詳細に解説した本(kindle)、pdf(booth)です。
灰色、茶色コーダーにおすすめ！
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BBB7RKTP

【booth(pdf)】
https://booth.pm/ja/items/4102300

冒頭5問をサンプルとして無料公開しています
https://qiita.com/sano192/items/6361ed72106cb6dd5843

『AtCoder　凡人が『緑』になるための精選50問詳細解説』

AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/gp/product/B09C3TPQYV/

【booth(pdf)】
https://sano192.booth.pm/items/3179185

1～24問目まではサンプルとして無料公開しています
https://qiita.com/sano192/items/eb2c9cbee6ec4dc79aaf

『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』

ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。

サンプルを5問分公開しています
https://qiita.com/sano192/items/3258c39988187759f756

Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVK3SLV

【booth(pdf)】
https://booth.pm/ja/items/3698647

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVKGH17/

【booth(pdf)】
https://sano192.booth.pm/items/3698668

『AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説』

ABC226~250、ARC129~139 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。

サンプルを4問分公開しています
https://qiita.com/sano192/items/f8f09ea769f2414a5733

Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC129~139の灰・茶・緑DIfficulty問題も書き下ろし ています。

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G13QMS

【booth(pdf)】
https://sano192.booth.pm/items/4025713

ARC129～139の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G337YF

【booth(pdf)】
https://sano192.booth.pm/items/4025737

『AtCoder ABC251～275 ARC140～151 灰・茶・緑問題 超詳細解説』

ABC251~275、ARC140~151 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。

サンプルを4問分公開しています
https://qiita.com/sano192/items/810a4a7d5cf61321bb05

Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC140~151の灰・茶・緑DIfficulty問題も書き下ろし ています。

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BRNTM9Z4

【booth(pdf)】
https://sano192.booth.pm/items/4455120

ARC140～151の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BRNRXPCV

【booth(pdf)】
https://sano192.booth.pm/items/4455133

『Excelでリバーシを作ろう!!　マクロ、VBAを1から学ぶ』

Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！　丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)

サンプルとして「準備」～「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb

【kindle】
https://www.amazon.co.jp/dp/B09XLM42MW

【booth(pdf】
https://sano192.booth.pm/items/3785312

5
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?