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

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

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

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

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

目次

はじめに
 A.Filter
B.ASCII Art
C.Merge Sequences
D.Bank
E.2xN Grid

はじめに

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

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

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

A.Filter

難易度：

考察

前から順番に要素を調べて偶数を配列に格納。その配列を空白区切りで出力

コード

pypy3

N=int(input())
A=[int(a) for a in input().split()]
B=[]
for a in A:
    if a%2==0:
        B.append(a)

print(*B)

補足

空白区切り
競技プログラミングにおける Python での標準入出力のまとめ

B.ASCII Art

難易度：

考察

Aij 番目の ASCII コードを A の ASCII コードを基準に求めて、chr() 関数でそのアルファベットを復元することで S を完成させられる。

コード

pypy3

324 ms /2000 ms

H,W=[int(hw) for hw in input().split()]
for _ in range(H):
    S=[]
    A=[int(a) for a in input().split()]
    for a in A:
        if a==0:
            S.append(".")
        
        else:
            # a + A の ASCII = Aij 番目の大文字アルファベットの ASCII コード
            # chr(ASCII コード) でアルファベット復元
            S.append(chr(a-1 + ord("A")))
    
    print("".join(S))

補足

アルファベット - ASCII コード変換
PythonでUnicodeコードポイントと文字を相互変換（chr, ord, \x, \u, \U）

C.Merge Sequences

難易度：

考察

A と B を結合した C の要素を見て、それが A,B どちらの要素の何番目だったか復元できる状態で管理したい
index 番号の情報および A,B どちら出身かを表す情報を、各要素に与えてから結合すれば良さそう。

なお、A,B の全ての要素で値の重複はないことが制約から確認できる。

コード

pypy3

N,M=[int(nm) for nm in input().split()]
A=[[int(a),i+1] for i,a in enumerate(input().split())]
B=[[int(b),-(i+1)] for i,b in enumerate(input().split())]
C=sorted(A+B)
AA=[0 for _ in range(N)]
BB=[0 for _ in range(M)]
for j,(c,i) in enumerate(C):
    # A の要素
    if i>0:
        AA[i-1]=j+1

    # B　の要素
    else:
        BB[-i-1]=j+1


print(*AA)
print(*BB)

補足

なし

D.Bank

難易度：

考察

削除待ち集合を使った、優先度付きキューによる最小値出力問題と認識した。

( もっと簡単に解けそう。加筆、修正時に期待 )

コード

pypy3

from heapq import heapify,heappop,heappush
N,Q=[int(nq) for nq in input().split()]
nex=1
H=[]
heapify(H)
wait=set()
for _ in range(Q):
    event=[int(e) for e in input().split()]
    if event[0]==1:
        heappush(H,nex)
        nex+=1

    
    elif event[0]==2:
        x=event[1]
        wait.add(x)
        
    
    else:
        while H:
            if H[0] in wait:
                wait.discard(H[0])
                heappop(H)
            
            else:
                print(H[0])
                break

補足

E.2xN Grid

難易度：

考察

重複区間を求める問題。区間の左端と右端を比較して、重複判定ができる。
計算量は O( N1 + N2 ) で十分高速
L の大きさを賄う配列は作成できないので defaultdict で管理すること

( 図解した方が良いので、スライドでの説明を追加する )

コード

pypy3
460 ms/ 2000 ms

from collections import defaultdict
L,N1,N2=[int(lnn) for lnn in input().split()]
# 上のマスにおける区間を、値ごとに管理
U=defaultdict(list)
now=0
for _ in range(N1):
    v,l=[int(vl) for vl in input().split()]
    U[v-1].append([now,now+l-1])
    now+=l

# 下のマスにおける区間を、値ごとに管理
D=defaultdict(list)
now=0
for _ in range(N2):
    v,l=[int(vl) for vl in input().split()]
    D[v-1].append([now,now+l-1])
    now+=l

ans=0
for u in U:
    if not D[u]:
        continue
    
    # D[u] の値を持つ上のマスの各区間の番号を ind _u で管理
    # D[u] の値を持つ下のマスの各区間の番号を ind _u で管理
    ind_u,ind_d=0,0

    # どちらかの最期の区間を見終わるまで
    while ind_u<len(U[u]) and ind_d<len(D[u]):
        # 上の区間が下の区間より小さい
        if U[u][ind_u][1]<D[u][ind_d][0]:
            # 上の区間をスライド
            ind_u+=1
            continue

        # 下の区間が上の区間より大きい
        if D[u][ind_d][1]<U[u][ind_u][0]:
            # 下の区間をスライド
            ind_d+=1
            continue

        l=max(D[u][ind_d][0],U[u][ind_u][0])
        r=min(U[u][ind_u][1],D[u][ind_d][1])
        # この重複区間の大きさを加える
        ans+=r-l+1
        
        # より左側の区間をもつ方の区間をスライド
        if D[u][ind_d][1]<U[u][ind_u][1]:
            ind_d+=1
        
        else:
            ind_u+=1

print(ans)

補足

終わり

とりあえず、投稿。明日以降加筆、修正する