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

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

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

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

A Dif:17

(リスト).pop(0)
とすることで先頭の要素を削除できます。
(リスト).append(0)
とすることで末尾に0を追加できます。

これらの操作をfor文を使ってK回行えばOKです。

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

【提出】

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

# K回(i=0~(K-1))
for i in range(K):
    # 先頭の要素を削除
    A.pop(0)
    # 末尾に0を追加
    A.append(0)

# 答えの出力
# (「*」をつけると[]なしで出力ができる)
print(*A)

B Dif:123

まず時間、分からA,B,C,Dを割り出しましょう。
A=(時間)//10 (10で割った商)
B=(時間)%10 (10で割った余り)
C=(分)//10 (10で割った商)
D=(分)%10 (10で割った余り)

例えば時間が17、分が53だったら
A=17//10=1
B=17%10=7
C=53//10=5
D=53%10=3
となります。

「見間違えやすい時刻」というのはAC:BDがきちんと時刻になっているということです。
すなわち(A*10+C)時(B*10+D)分がきちんと時刻になっているか確認します。
0≤(A*10+C)≤23　かつ　0≤(B*10+D)≤59　となっていれば「見間違えやすい時刻」です。

今の時間から1分ずつ増やしながら条件を満たすか確認していきます。

注意が必要なのは今の時間から23:59まで「見間違えやすい時刻」がない場合もあるということです。
この場合は翌日「00:00」すなわち「0 0」が答えになります。

【提出】

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

# 「見間違えやすい時刻」か判定
def Judge(HH,MM):
    # A=(時間)//10 (10で割った商)
    A=HH//10
    # B=(時間)%10 (10で割った余り)
    B=HH%10
    # C=(分)//10 (10で割った商)
    C=MM//10
    # D=(分)%10 (10で割った余り)
    D=MM//10

    # 「見間違えやすい時刻」になっていれば
    if 0<=A*10+C<=23 and 0<=B*10+D<=59:
        # 答えを出力
        print(HH,MM)
        # 終了
        exit()        

# 今の時間で分だけ増えた場合
# MM=m~59
for MM in range(m,60):
    # 判定
    Judge(h,MM)    

# 時間も分も増えた場合
# HH=(h+1)~23
for HH in range(h+1,24):
    # MM=0~59
    for MM in range(60):
        # 判定
        Judge(HH, MM)

# 今の時間から23:59までに「見間違えやすい時刻」がない場合
# 00:00が答え
print(0,0)

C Dif:327

フォロー関係を連想配列で記録します。

まずFollowという連想配列を用意します。
AがBをフォローしていればFollow[(A,B)]=1となるように記録していきます。
フォローしていなければ=0です。

Follow[(A,B)]=1　かつ　Follow[(B,A)]=1　ならば互いにフォローしているのでYesです。

連想配列(defaultdict)を使ったことがない人は以下を参照してください。

defaultdict(連想配列)について
連想配列は別名「辞書」とも言い、「キー」と対応する「値」を登録できるデータ構造です。
pythonでは標準で搭載されており、dict()と書くことで使えます。
しかし標準のものはデフォルトの値(初期値)が設定できず、存在しない「キー」にアクセスする可能性があるときの処理が面倒です。
defaultdictは標準の連想配列と同様に使えて、さらに初期値を設定できます。
値の割当が行われていない「キー」には自動的に初期値が割り振られます。
「使い方」
・インポート：from collections import defaultdict
・作成(デフォルト0の場合)【O(1)】：変数名=defaultdict(int)
・キー、値の登録【O(1)】：変数名[キー]=値
・値の参照【O(1)】：変数名[キー]

使用例

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

# 作成(デフォルト0の場合)【O(1)】：変数名=defaultdict(int)
AsArray=defaultdict(int)

# キー、値の登録【O(1)】：変数名[キー]=値
# キー、値ともに数値、文字列、タプルを入れることが可能
# ただしリストをキーにすることはできない
AsArray[1]=10
AsArray["Men"]="Taro"
AsArray[(1,2)]=[3,4,5]
 
# 値の参照【O(1)】：変数名[キー]
print(AsArray[1])
print(AsArray["Men"])
print(AsArray[(1,2)])

# 値が割当されていないキーも参照可能(値はデフォルト値)
print(AsArray[99])

【提出】

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

# defaultdictのインポート
from collections import defaultdict
# 連想配列を作る(初期値は0)
Follow=defaultdict(int)

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

    # Ti=1
    if T==1:
        # AがBをフォロー
        Follow[(A,B)]=1
    # Ti=2
    elif T==2:
        # AがBへのフォローを外す
        Follow[(A,B)]=0
    # Ti=3
    elif T==3:
        # AがBをフォロー かつ BがAをフォロー ならば
        if Follow[(A,B)]==1 and Follow[(B,A)]==1:
            # 「Yes」を出力
            print("Yes")
        # そうでなければ
        else:
            # 「No」を出力
            print("No")

D Dif:559

クエリ1のたびにAのすべての要素にxを代入しているとTLEします。
そこで「xが代入された」という情報だけ保持しておき、クエリ3についてはそこからどれだけ増えたかで計算します。

Cxをクエリ1で代入された値とします。最初は0にしておきます。
更にクエリ2で差分が変更された部分を記録するChangedというリストを用意します。最初はChanged=[1,2,3,...,N]としておきます。
AはCxからどれくらい増えたかという差分を表すものとします。

・クエリ1
Cx=xとします。CxがAの全ての要素に代入されているということです。
更にChangedから差分が変わっている(=0でないもの)Aの要素を確認して0にします。

・クエリ2
A[i]にxを足します。つまりCxからx分だけ増えているということを記録します。
同時にChangedにiを記録します。

・クエリ3
(Cx+A[i])を出力します。

例で動作を見ましょう。(1インデックスで解説しています。すなわちA1=A[1],A2=A[2],...となります)
5
3 1 4 1 5
6
3 2
1 1
2 3 4
3 3
1 5
3 2

A=[3,1,4,1,5]
Changed=[1,2,3,4,5]
Cx=0

「query1：3 2」
(Cx+A[i])=(Cx+A[2])=0+1=1
1を出力する。

「query2：1 1」
Cx=1とする。
Changed=[1,2,3,4,5]番目のAを全て0にする。※操作の後Changedは空にする
A=[0,0,0,0,0]

「query3：2 3 4」
A[3]に4を足す。
A=[0,0,4,0,0]
Changedに3を追加する。
Changed=[3]

「query4：3 3」
(Cx+A[i])=(Cx+A[3])=1+4=5
5を出力する。

「query5：1 5」
Cx=5とする。
Changed=[3]番目のAを0にする。
A=[0,0,0,0,0]

「query6：3 2」
(Cx+A[i])=(Cx+A[2])=5+0=5
5を出力する。

【提出】

# 入力の受け取り
N=int(input())
# A[0]=0など適当な値を埋めることでずらす
A=[0]+list(map(int,input().split()))
Q=int(input())

# クエリ1で代入される値
Cx=0
# クエリ2で差分が変更された箇所(初期値は1~N)
Changed=list(range(1,N+1))

# Q回
for q in range(Q):
    # 入力の受け取り
    query=list(map(int,input().split()))

    # クエリ1
    if query[0]==1:
        # xを割り振り
        x=query[1]
        # Cxに代入
        Cx=x
        # Changedが空でない限り(Changedの長さが0より大きい)
        while 0<len(Changed):
            # インデックス番号を取り出し
            i=Changed.pop()
            # 差分(A[i]を0にする)
            A[i]=0

    # クエリ2
    elif query[0]==2:
        # i,xを割り振り
        i,x=query[1],query[2]
        # A[i]に追加
        A[i]+=x
        # 変更したインデックス番号を記録
        Changed.append(i)

    # クエリ3
    elif query[0]==3:
        # iを割り振り
        i=query[1]
        # 答えの出力
        print(Cx+A[i])

E Dif:996

種類数は各数の出現回数を数えて確認します。
例えば入力例1の場合
3 4 5 2 2
2 2 1 1
3 2 5 3
3 4 4 3

最初の状態では
1が2個
2が3個
3が4個
4が2個
5が1個
で5種類となります。1個以上あるものは1種類と数え、0個のものは数えません。
塗りつぶされた部分の数について出現回数をマイナスし、1,2,3,...の値が0か、1以上かを順に確認して種類数を数えます。

塗りつぶす範囲が変わったときの差分を考えます。

lが増えたとき、変化する部分は図のように
青い数が増える
赤い数が減る
というところだけであることがわかります。よってこの部分の増減だけ確認することで計算量を減らすことができます。

まず初期状態(塗りつぶされていない状態)での各数の出現回数を数えます
(k,l)=(0,0)で塗りつぶされるマスについて出現回数をマイナスし、種類数を確認します。(愚直に計算)
(k,l)=(0,1)は(k,l)=(0,0)で塗った部分から1列ずれて増えた部分、消えた部分のみ出現回数をプラスマイナスし、種類数を確認します。
(k,l)=(0,2)は(k,l)=(0,1)で塗った部分から1列ずれて増えた部分、消えた部分のみ出現回数をプラスマイナスし、種類数を確認します。
...
(k,l)=(1,0)で塗りつぶされるマスについて出現回数をマイナスし、種類数を確認します。(愚直に計算)
(k,l)=(1,1)は(k,l)=(1,0)で塗った部分から1列ずれて増えた部分、消えた部分のみ出現回数をプラスマイナスし、種類数を確認します。
(k,l)=(1,2)は(k,l)=(1,1)で塗った部分から1列ずれて増えた部分、消えた部分のみ出現回数をプラスマイナスし、種類数を確認します。
...

このように計算を行うことで計算量を減らすことができます。

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

【提出】

# pypyで提出

# 入力の受け取り
H,W,N,h,w=map(int,input().split())
# グリッド
G=[]

# g=0~(H-1)
for g in range(H):
    # 入力の受け取り
    Ai=list(map(int,input().split()))
    # グリッドへ追加
    G.append(Ai)

# 初期状態(塗っていない)での各数の出現回数のカウント
Initial=[0]*(N+1)

# g(行)=0~(H-1)
for g in range(H):
    # r(列)=0~(W-1)
    for r in range(W):
        # マス(g,r)の数をカウント
        Initial[G[g][r]]+=1

# 出現回数から種類数を確認
def AnsCount():
    # 種類数
    result=0
    # i=1~N
    for i in range(1,N+1):
        # 出現回数が1以上なら
        if 1<=count[i]:
            # 種類数にカウント
            result+=1
    # 種類数を返す
    return result

# 答え
ans=[[0]*(W-w+1) for i in range(H-h+1)]

# k=0~(H-h)
for k in range(H-h+1):
    # 種類数
    count=[0]*(N+1)
    # i=1~N
    for i in range(1,N+1):
        # 初期値をコピー
        count[i]=Initial[i]

    # (k,0)で塗る場合
    # g(行)=k~(k+h-1)
    for g in range(k,k+h):
        # r(列)=0~(w-1)
        for r in range(w):
            # 塗った部分の数について出現回数をマイナス
            count[G[g][r]]-=1

    # (k,0)の答えを記録
    ans[k][0]=AnsCount()

    # l=1~(W-w)
    for l in range(1,W-w+1):
        # g(行)=k~(k+h-1)
        for g in range(k,k+h):
            # 増えた部分(塗りつぶされなくなった部分)
            count[G[g][l-1]]+=1
            # 減った部分(塗りつぶされた部分)
            count[G[g][l+w-1]]-=1
        # (k,l)の答えを記録
        ans[k][l]=AnsCount()

# i=0~(H-h)
for i in range(H-h+1):
    # 答えの出力(「*」をつけると[]なしで出力)
    print(*ans[i])

【広告】

『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 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』

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

『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