Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
2

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.

@Waaaa1471

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

Last updated at Posted at 2023-04-01

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

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

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

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

作者プロフィール
Atcoder ：緑 1025
20230401 現在

目次

はじめに
A.Alternately
B.Chessboard
C.Gap Existence
D.M<=ab
E.Transition Game

はじめに

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

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

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

A.Alternately

難易度： 灰色 14

考察

S を前から順番に見ていき、M と F が交互に並んでいるか調べます。「 交互に並ぶ 」とは 今見ている位置とその手前の位置の要素が異なっている ということです。
そこで、1つ手前の要素を prev 変数で管理することにします。先頭から順番に要素を見ていく中で、直前に見た要素によって prev 変数を更新していくことで常に一つ手前の要素を記憶している状態を維持し、交互に並んでいるのかを調べることができます。

S には M と F しか含まれないので、直前の要素と今見ている要素が異なり続けていれば M と F が交互に並んでいるとして良いでしょう。
なお、先頭の一つ手前の要素は存在しないのであらかじめ S の先頭に U ( M,F 以外なら何でも ok) を挿入しておきます。

コード

pypy3
76 ms/ 2000 ms

N=int(input())
S=input()
# prev 変数で 1つ手前の要素を管理
prev="U"
for s in S:
    # 交互でない条件
    if s==prev:
        print("No")
        exit()
    
    # prev 変数を今見ている要素で更新
    prev=s

# 交互
print("Yes")

補足

なし

B.Chessboard

難易度： 灰色 31

考察

コマがおかれている( * )マスの名前を出力する問題。
コマがおかれている位置自体は、グリッドを左上から順番に調べていくことで見つけれられます。
次に問題文で提示されているルールを守って、そのマスの名前(長さ 2)を求めます。

名前の 1文字目のアルファベットはグリッドの列に依存します。そのマスが左から j 列目の位置ならば、1文字目のアルファベットは chr( j + ord("a")) で表現できます。( a の ASCII を基準にした j 番目のアルファベット )

名前の 2文字目の整数はグリッドの行に依存します。そのマスが上から i 行目ならば、2文字目の整数は 8 - i で表現できます。

ただし、i , j は 0-indexed であることに注意

コード

pypy3
83 ms/ 2000 ms

S=[]
for _ in range(8):
    S.append(input())

# コマの置かれたマスの位置を調べる
for i in range(8):
    for j in range(8):
        if S[i][j]=="*":
            # 1 文字目は a のASCII コードを基準にしたアルファベット
            # 2 文字目は 8-i で表現できる整数
            ans=chr(j+ord("a"))+str(8-i)
            print(ans)
            exit()

補足

C.Gap Existence

難易度 ： 灰色 162

考察

組 ( i , j ) を全列挙することは N の制約からできません。( N^2 組あるため)
そこで Ai - Aj = X を満たす組の存在を高速に求める方法を考えます。

ここで、Ai - Aj = X ⇔ Ai = X + Aj より、「 Ai - Aj = X を満たす組の存在の真偽 」を 「 A の要素すべてに X を加算した値のうち 1つでも、もともとの A の要素として含まれているかの真偽 」と解釈することができます。集合でデータを管理している場合には要素検索 を O(1) で行えるので、A の要素をあらかじめ集合で管理しておき、A の要素 + X の値がこの集合に含まれているか調べる処理は全体で O(N) と十分高速です。

以上の工夫で制限時間内で、Ai - Aj = X を満たす組 ( i , j ) が存在するか求めることができました。

コード

pypy3
135 ms/ 2000 ms

N,X=[int(nx) for nx in input().split()]
A=[int(a) for a in input().split()]
AA=set(A)
for a in A:
    if a+X in AA:
        print("Yes")
        exit()

print("No")

補足

D.M<=ab

難易度： 緑色 999

考察

後日

コード

pypy3

補足

E.Transition Game

難易度 ： 水色 1285

考察

筆者は 0 → A[0] → A[A[0]] → A[A[A[0]]] → .... 表現できる有向グラフを構築し、高橋君の勝利回数を このグラフにおける有向サイクルを成す頂点の数 と解釈しました。
有向グラフにおける有向サイクルの検出ためには、union-find でグラフを構築すると簡単です。具体的には、i → A[i] の辺を張るとき既に i と A[i] が同じグループであるならば、A[i] → A[A[i]] →.... → i は有向サイクルを成します。この問題では有向サイクルを成す頂点の数を求める必要があるので、A[i] を始点に A[i] に戻ってくるまで有向グラフを探索する中で登場した頂点の数を計上します。

さて、なぜこのような解釈ができるのか？ ですが、有向サイクルに含まれる頂点 i があるとして、i 回目のゲームで青木君がどんな Ki を提示しても、i が含まれる有向サイクルには頂点 i から距離 Ki の頂点が必ず存在するため、高橋君は必ずゲームに勝利します。
逆に、有向サイクルを成さない頂点 j があるとして、j 回目のゲームで青木君が有向グラフ内において頂点 j から他の頂点までの距離として存在しない Kj を提示することで青木君はゲームに勝利することができます。

以上より、高橋君の勝利数 ⇔ 有向サイクルを構成する頂点の個数 が成立することがわかります。

コード

pypy3
332 ms/ 2000 ms
メイン


ここに union-find クラスを書く

if __name__ =="__main__":
    N=int(input())
    A=[int(a)-1 for a in input().split()]
    uf=UnionFind(N)
    # 有向サイクルを成す頂点数
    count=0
    for i in range(N):
        # 同じグループ出ないなら辺を張る
        if not uf.same(i,A[i]):
            uf.union(i,A[i])
        
        else:
            # この有向サイクルを成す頂点の数を調べる
            start=i
            tmp=A[i]
            count+=1
            # 始点 i に戻るまで有向サイクルを探索
            while start!=tmp:
                count+=1
                tmp=A[tmp]
    
    print(count)

union-find クラス

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * n

    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # x,y が同じグループか判定
    def same(self,x,y):
        return self.find(x) == self.find(y)

補足

  • union-find
    ・PythonでのUnion-Find（素集合データ構造）の実装と使い方
    コードの union-find クラスはこの記事を参考にしているのでわからなければこれで勉強してください。関数の仕様がとても分かりやすいのでオススメです。
    ・B - Union Find
    atcoder における union-find の教材です。スライドがとてつもなく分かりやすく、視覚的に操作を理解できるのでこちらも併せてお勧めします
    ・アルゴシキ練習問題
    理解できたら練習しましょう。union-find は出題傾向が高く、実装も簡単で得点減となりうるアルゴリズムです。今すぐ勉強することをお勧めします。

  • 有向サイクル検出 類題
    問題ページ
    ネタバレ回避で abc 255 ～ 260 , d or e 問題と記します。
    筆者はこの類題を過去に考えたことがあったので、この問題を今回解けたのだと思います。

終わり

abc 294 から恒例となっていますが、しばらく記事の考察項目のクオリティが低い期間が続きますが許してください。
修正後 twitter でアナウンスします。

また、D問題についても後日記載します。

1
2
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
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?