【AtCoder】ABC292 のA,B,C,D,E における Python解説

ABC 292 のA,B,C,D,E 問題を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。

この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。

また、問題の難易度を表す指標を Atcoder Problems から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。

質問やご指摘はこちらまで
Twitter : Waaa1471

作者プロフィール
Atcoder ：緑 949
230305 現在

目次

はじめに
A.CAPS LOCK
B.Yellow and Red Card
C.Four Variables
D.Unicyclic Components
E.Transitivity

はじめに

特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的考察が必要になり始めます。
しかし、公式解説ではこの部分の解説があっさりしすぎていて競技プログラミング(Atcoder)を始めたばかりの人にはわかりにくい、難しいと感じるのではないでしょうか。

またC++がわからないと、コードの書き方を勉強することが難しいです。一応、参加者全員のコードを見ること自体は可能ですが、提出コードは必ずしも教育的ではありません(ここで紹介する記事も本番で提出したものとは全く異なります)。そんなものから初学者が解説もなしになにか得ることはとても難しいと思います。実際適当に何人かのコードをみたものの、意味がわからずに終わった経験があるのではないでしょうか。

この記事がそんな方々の勉強の助けになればよいなと思っています。

A.CAPS LOCK

問題ページ

難易度：灰色 7

考察

python では文字列の全ての小文字を大文字に変換する関数が存在するのでこれを利用すればよいです。

コード

pypy3

S=input()
S=S.upper()
print(S)

補足

• 大文字、小文字 操作/判定 関数
  Pythonで大文字・小文字を操作する文字列メソッド一覧

B.Yellow and Red Card

問題ページ

難易度： 灰色 39

考察

各選手の処分状態を管理して、イベント3 での質問に高速に答えることを目指します。
選手が退場処分を受けるのは、イベント2 でレッドカードを提示される瞬間、または、イベント 1 で2枚目のイエローカードを提示される瞬間です。これを検知して、選手の処分状態を更新すればよいでしょう。

コード

pypy3
129 ms/2000 ms

N,Q=[int(nq) for nq in input().split()]
# イエローカードの枚数を管理
table_y=[0 for _ in range(N)]
# 退場処分を受けているかの状態を管理
ng=[False for _ in range(N)]
for _ in range(Q):
    i,x=[int(a) for a in input().split()]
    if i==1:
        if table_y[x-1]==1:
            ng[x-1]=True
            continue

        table_y[x-1]+=1
    
    elif i==2:
        ng[x-1]=True

    else:
        if ng[x-1]:
            print("Yes")

        else:
            print("No") 

補足

なし

C.Four Variables

問題ページ

難易度 ： 茶色 444

考察

変数全てを 1 ～ N の範囲で動かして調べられれば簡単ですが、$O(N^4)$ より不可能です。

そこで、AB を 1 ～ N の範囲で動かします。このとき AB = x とすると、 CD は N-x で決定されます。
あとは、AB = x を成す正整数 A,B の組の個数 : $f(x)$ を求めることができれば、AB+CD=N を満たす (A,B,C,D) の組の個数 ans を以下のように計上することができます。

ans\ = \sum_{x=1}^{N-1}\ f(x)\ +\ f(N-x) ・・➀

さて、$f(x)$ は x の 約数の個数 です。
約数の x の個数は、$O(√x)$ で求めることができるので、以下の通り 1 ～ N-1　のすべての約数を十分高速に求めることが可能です。

\sum_{x=1}^{n-1}\ O( x√x ) 

< O(N√N)

< O(10^8)\   より

以上より、1 ～ N-1 までの約数の個数を全て求めて管理しておき、➀ 式の要領で計上していくことにします。

コード

pypy3
1005 ms/ 2000 ms

# N の約数の個数をカウント
def divisors(N):
    num=0
    for i in range(1,N+1):
        if i*i>N:
            break
        if N%i!=0:
            continue

        num+=1
        if N//i!=i:
            num+=1

    return num


if __name__ =="__main__":
    N=int(input())
    # 約数の個数を管理
    table=[0 for _ in range(N)]
    for i in range(1,N):
        table[i]=divisors(i)

    ans=0
    # AB の値を全探索
    for i in range(1,N):
        ab=i
        cd=N-i
        ans+=table[ab]*table[cd]

    print(ans)

補足

• 変数固定
  登場する変数の一部を固定することで見通しが良くなったり、動かす範囲が限定されて、計算量を削減できるようになる場合があります。
  この問題の計算量の部分で躓いた方は以下に類題を載せておくので、練習してみましょう。
  類題 1
  abc 175 ～ 180 の c または d
  類題 2
  abc 225 ～　230 の c または d
  ネタバレ回避で範囲を記します。

• 約数列挙アルゴリズム
  約数列挙のアルゴリズム
  この問題では約数の個数をカウントするだけでしたが、約数そのものを列挙することも可能です。

D.Unicyclic Components

問題ページ

難易度： 茶色 579

考察

グラフの辺と頂点を数える方法としては、BFS で連結成分を探索する過程で計上していくこと が考えられます。

計上時の注意点として、辺がダブルカウントされます。

単純無向グラフであればこれでお終いなのですが、この問題のグラフには多重辺 および自己ループ 構造が含まれているので工夫して計上しなければなりません。

ダブルカウントされる辺と、自己ループを成す辺を分類して計上することにします。

コード

pypy3
575 ms/2000 ms

from collections import deque
N,M=[int(nm) for nm in input().split()]
# 自己ループ辺の数を管理
table=[0 for _ in range(N)]
G=[[] for _ in range(N)]
for _ in range(M):
    u,v=[int(a)-1 for a in input().split()]
    if u==v:
        table[u]+=1
    else:
        G[u].append(v)
        G[v].append(u)

seen=[False for _ in range(N)]
for i in range(N):
    if seen[i]:
        continue

    que=deque()
    que.append(i)
    # この連結成分に含まれる頂点と辺の総数
    e,v=0,0
    # この連結成分に含まれる自己ループ辺の総数
    eself=0
    while que:
        now=que.popleft()
        v+=1
        eself+=table[now]
        seen[now]=True
        for nex in G[now]:
            e+=1
            if not seen[nex]:
                seen[nex]=True
                que.append(nex)
    
    # 辺は2度数えられている
    if v!=e//2+eself:
        print("No")
        exit()

# 全連結成分で条件を満たせば
print("Yes")

補足

なし

E.Transitivity

問題ページ

難易度： 水色 1272

考察

グラフの最初の状態を Gs, 最終状態を Ge とします。
Ge では、Gs において Vi から到達可能な全ての頂点と Vi が辺を構築することになります。

つまり最終的に、初期状態で到達可能な全頂点との辺を構築することになります。
したがって、各頂点から到達可能な頂点の数 : Ee を計上する必要があるので、これを始点を全探索した BFS で求めることにします。
求めるべき操作回数は、この Ee から初期状態での辺の数 : Es = M を引いた値に一致します。

コード

pypy3
213 ms/2000 ms

from collections import deque
N,M=[int(a) for a in input().split()]
G=[[] for _ in range(N)]
for _ in range(M):
    u,v=[int(a)-1 for a in input().split()]
    G[u].append(v)

ans=0
# 始点全探索
for i in range(N):
    que=deque()
    que.append(i)
    seen=[False for _ in range(N)]
    seen[i]=True
    while que:
        now=que.popleft()
        for nex in G[now]:
            if not seen[nex]:
                seen[nex]=True
                ans+=1
                que.append(nex)


# もともとの辺の数だけ引く
ans-=M  
print(ans)

補足

なし

終わり

コードを残す意味を込めて、解けなかった E も掲載しました。