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

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

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

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

A Dif:11

図をよく見ると
1と2,3
3と6,7
5と10,11
というように2倍と2倍+1の頂点がつながっているということがわかります。
a<bという条件があるので、bを2で割った商がaであれば「Yes」、そうでなければ「No」ということがわかります。

「Yes」「No」は文字列なので「""」(ダブルクオーテーション)をつけなければならないことに注意してください。

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

【提出】

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

# bを2で割った商がaならば
if b//2==a:
    # 「Yes」を出力
    print("Yes")
# そうでなければ
else:
    # 「No」を出力
    print("No")

B Dif:108

問題文が何を言っているかよくわかりませんね。
まずは入力例を見てみましょう。

i=1の場合はS1とS2、S2とS3、...を比較しています。
i=2の場合はS1とS3、S2とS4、を比較しています。
つまりある文字からi文字先の文字と一致するか否かが問題のようです。S1とS(1+i)文字目、S2とS(2+i)文字目、...と比較していき、違う文字がどこまで続くか？というのを問われています。

あまり難しく考えずに問題文の条件をそのままコードにしてしまうのが楽です。
k=1,2,3,...について、
・l+i≤Nである。
・全ての1≤k≤lを満たす整数kについて、Sk​=S(k+i)​を満たす。
これらを満たす間はl=kとし、そうでなくなったら最大のlとして出力を行います。

pythonでは最初の文字を0文字目と数えます。そのままだと少しややこしいので入力受け取りの際、最初に「?」などの文字をくっつけて0文字目を埋めてしまうのが良いです。

この方法は計算量がO(N^2)となり、最大で5000^2=25000000≒10^7の計算量となります。
pythonだと間に合わないので、提出するときの言語にpypy3を選択して提出しましょう。

pypy3はpythonと同じ文法で高速に動作するプログラミング言語の一種です。
pythonでTLEするときにはpypy3で提出してみるとうまくいくことがあります。

【提出】

# pypyで提出

# 入力の受け取り
N=int(input())
# 0文字目=S[0]を埋める
S="?"+input()

# i=1~(N-1)
for i in range(1,N):
    # lを作る
    l=0
    # k=1~N
    for k in range(1,N+1):
        # ・l+i≤Nである。
        # ・全ての1≤k≤lを満たす整数kについて、Sk​=S(k+i)​を満たす。
        if k+i<=N and S[k]!=S[k+i]:
            # lを更新
            l=k
        # 条件を満たさない
        else:
            # lを出力
            print(l)
            # 次のiへ
            break

C Dif:157

Zの次はAA
AZの次はBA
ZZZの次はAAAA
というような形です。なんとなく繰り上がりの計算に似ていますね。
例えば10進数だと
9の次は10
109の次は110
999の次は1000
となりますし、2進数の場合だと
1の次は10
101の次は110
111の次は1000
となるイメージです。

2進数を10進数に直すときは各桁に2^iを掛けたものを足していくのでした。
例えば1011だったら
左から0桁目：1*2^0=1
左から1桁目：1*2^1=2
左から2桁目：0*2^2=0
左から3桁目：1*2^3=8
1+2+0+8=11となります。

同じノリでこのアルファベット達を26進数として見てみましょう。A=1,B=2,...,Z=26です。
入力例1のABだと
左から0桁目(=B⇔2)：2*26^0=2
左から1桁目(=A⇔1)：1*26^1=26
足して2+26=28です。うまくいきましたね。

本当はこれで正しいのか、論理的な根拠が必要なところですが、細かいところは一旦置いておきましょう。気になる人は公式解説を読んで下さい。
特にコンテスト中なら「これでいけそうだなー」で入力例3が通ったらとりあえず提出してみればOKです。

アルファベットを数字に変換するのはordを使うと便利です。
これは文字→文字コードへ変換してくれる機能で、Aの文字コードが65、Bの文字コードが66、...となっているため、(文字コード)-64をすればいい感じに変換できます。

【提出】

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

# 各文字を数値へ変換したものを格納するリスト
d=[]

# x：Sの各文字について
for x in S:
    # (文字コード-64)を格納
    d.append(ord(x)-64)

# ひっくり返す
# 左から順に処理したいため
d=d[::-1]

# 答え
ans=0

# i=0~(dの長さ-1)
for i in range(len(d)):
    # 26^i*数値
    ans+=26**i*d[i]

# 答えの出力
print(ans)

D Dif:663

どういう場合が「No」になるか考えましょう。
A B
B C
C D
ならば下から順に処理すればできます。
ところがここに
D A
が追加されるとどうやっても処理ができません。
どうやらA→B,B→C,C→D,D→Aというように矢印を張ったとき、ぐるぐる回るループの部分ができるとダメそうだということがわかります。

グラフにループがあるかを判定する方法はBFSも使えるのですが、せっかくD問題なのでUnionFindを使ってみましょう。

UnionFind
UnionFindはグラフにおける2つの頂点の「連結」(Union)と「連結であるかの判定」(Find)を高速で行うことができるデータ構造です。

動画での解説はこちら

きちんとした説明はAtCoder公式が解説スライドを作っているのでそちらを御覧ください。
https://atcoder.jp/contests/atc001/tasks/unionfind_a
UnionFindの実装はかなり難しいです。ですが問題を解くのにそこまで理解する必要はなく、以下のUnionFindクラスをコピペして使えればOKです。

# UnionFind
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parent_size=[-1]*n
 
    def leader(self,a):
        if self.parent_size[a]<0: return a
        self.parent_size[a]=self.leader(self.parent_size[a])
        return self.parent_size[a]
 
    def merge(self,a,b):
        x,y=self.leader(a),self.leader(b)
        if x == y: return 
        if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y]=x
        return 
 
    def same(self,a,b):
        return self.leader(a) == self.leader(b)

※きちんと中身が理解したい方は【広告】欄の『AtCoder 最速で緑になる 基礎・典型50問詳細解説』などをご購入ください。

上記をコードの最初にコピペしてから以下のように使います。
・初期化【O(N)】：変数名=UnionFind(頂点の数)
・頂点の連結【だいたいO(logN)】：変数名.merge(頂点番号1,頂点番号2)
・連結か確認【だいたいO(1)】：変数名.same(頂点番号1,頂点番号2)
　(連結ならTrue,そうでないならFalseを返す)

使用例

# 初期化【O(N)】：変数名=UnionFind(頂点の数)
UF=UnionFind(10)

# 頂点の連結【だいたいO(logN)】：変数名.merge(頂点番号1,頂点番号2)
UF.merge(0,2)
UF.merge(1,3)
UF.merge(3,0)

# 連結か確認【だいたいO(1)】：変数名.same(頂点番号1,頂点番号2)
if UF.same(1,5)==True:
    print("連結")
else:
    print("連結でない")

既に連結の頂点同士について、更にそこへ辺を張ろうとするとループが出来上がります。

よって処理内容としては
入力を受け取り、2つの頂点が連結か確認
→連結でなければ連結する
→連結ならループができるので「No」を出力
という形になります。

今回は各頂点にあたるS,Tが数字でなく文字列なので、入力と同時に頂点番号となる数字を割り振っていきます。
やり方としては連想配列を用意し、キーが名前、値が番号となるようして変換するのが楽です。
番号は何でもOKです。【提出】ではSiに2i番、Tiに(2i+1)番を振っています。ただし既に番号が振られていたら無視です。

【提出】

class UnionFind:
    def __init__(self,N):
        self.N=N
        self.parent_size=[-1]*N
    def leader(self,a):
        if self.parent_size[a]<0: return a
        self.parent_size[a]=self.leader(self.parent_size[a])
        return self.parent_size[a]
    def merge(self,a,b):
        x,y=self.leader(a),self.leader(b)
        if x == y: return
        if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y]=x
    def same(self,a,b):
        return self.leader(a) == self.leader(b)

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

# UnionFindを用意
UF=UnionFind(2*N+2)

# 連想配列(defaultdict)を用意
from collections import defaultdict

# 名前→頂点番号への変換用連想配列
# 初期値は0
Num=defaultdict(int)

# i~1~N
for i in range(1,N+1):
    # 入力の受け取り
    S,T=map(str, input().split())
    # Sに番号がまだ振られていなければ
    if Num[S]==0:
        # 2i番を振る
        Num[S]=2*i
    # Sに番号がまだ振られていなければ
    if Num[T]==0:
        # (2i+1)番を振る
        Num[T]=2*i+1
    
    # SとTが連結であれば
    if UF.same(Num[S],Num[T]):
        # ループになるので「No」
        print("No")
        # 終了
        exit()
    # そうでなければ
    else:
        # 連結にする⇔辺を張る
        UF.merge(Num[S],Num[T])

# 「Yes」を出力
print("Yes")

【広告】

『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