pythonで競技プログラミング 覚え書き

pythonで競技プログラミングはじめました。atcoderでレーティング灰色です。まずは目指せ茶色です。PASTは初級でした。単純にコーディングして問題を解くことが達成感があって楽しいのでやっています。

このページは私の個人的な備忘録です。素人なので色々間違ってるかも。間違いに気づいた親切な方は教えていただけると助かります。

競技プログラミングとは

与えられた問題を制限時間内になるべく早く多く解くことを競う競技です。私はAtCoder社の運営する、AtCoderで競プロをやっています。問題に対する回答はオンラインで提出し、リアルタイムで正解、不正解が判定されます。

競技プログラミングと、業務としてのプログラミングの違いは、「F1ドライバー」と「トラック、タクシー、路線バスの運転手、または営業職の人が車を運転する場合」の2者の対比のようなものかな、と思っています。(私は業務としてのプログラミングの経験はありませんが。)

あるいはウェイトリフティングと総合格闘技と捉えている人もいる。これは秀逸な例えかも。

ガイダンス

ガイダンスはこの2記事が秀逸と思う。

AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~

https://qiita.com/drken/items/fd4e5e3630d0f5859067

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編:競プロを始めよう】

https://qiita.com/e869120/items/f1c6f98364d1443148b3

精進

過去問を解くなりして競技プログラミングのスキルアップを図ることをこの界隈では「精進する」と表現するようだ。精進するには「atcoder problems」のtraining機能が役にたつ。

https://kenkoooo.com/atcoder/#/training

使うにはGitHubのアカウントが必要。ない人は一緒に作ってしまおう。

標準入力

まずはこれを適切に使えるようにならないと話にならない。

文字1行

一番基本的なやつ。入力を文字列として受け取る。

S=input()

pythonの文字列はリストとして各要素にアクセスできるので便利。整数データでもあえて文字列として受け取って処理するのも時に有効。10進数の格桁に簡単にアクセスしたい時など。

整数1行

整数として受け取る場合は下記。

N=int(input())

上で出てきた「input()」で受け取ったものをint(整数型)に変換して変数にぶちこんでいるだけ。

1行に複数の整数

よくあるパターン。あまりにも頻出するので覚える気がなくてもすぐに覚えてしまう。

N,M=map(int,input().split())

1行に複数の文字列

あまり登場しない?

S,T=map(str,input().split())

出力

出力も入力の次に大事。print()で出力すればよい。

A=10
print(A)
#出力は 「10」

複数個ならべるならカンマで区切って書く。

A=10
B=5
C=1
print(A,B,C)
#出力は 「10 5 1」

文字でも一緒。

リストを出力する時、[’a’,’b’,’c’]じゃなくて「abc」のようにまとめて(結合して)出力したい時はjoin。たまにしか使わないので忘れがち。

A=['a','b','c']
print(A)
#出力は ['a','b','c']
print(''.join(A))
#出力は abc

10進数の格桁の求め方

10で割った余りが一番したの桁。10で割った商をさらに割って余りをどんどん求めていく。

あえてstr型として、インデックスを使って各桁を取得するのも便利。

Dict型の操作

それぞれの要素が何個ずつあるのか数え上げる時は、dict型を使うと良い。

ABC091 B Two Colors Card Game で使ったときの例。

https://atcoder.jp/contests/abc091/tasks/abc091_b

T=dict()
for i in range(M):
	tmp = input()
	if tmp in T:
		T[tmp]+=1
	else:
		T[tmp]=1

要素を一つ一つ読み込むときに、その要素が辞書の中にあれば、そのキーの値を+1、もしまだなければ、要素を作って値に1を入れる。ここらへんの基礎的な操作ができないと、何もできないケース多し。

辞書には順番の概念は無い。しかし「sorted」を使ってkeyもしくはvalueでソートできる。返ってくるのはdict型ではなくlist型が返ってくるので注意。

ABC081 Not so diverseなど。

https://atcoder.jp/contests/abc081/tasks/arc086_a

keyでソートする例(昇順)。

t=sorted(t.items())

keyでソート(降順)

t=sorted(t.items(),reverse=True)

valueでソート

t=sorted(t.items(),key=lambda x:x[1])

valueでソート(降順)

t=sorted(t.items(),key=lambda x:x[1],reverse=True)

値のスワップ

そのうち書く。

min,max

そのうち書く。

リストのcopy

ちゃんとcopyメソッドでコピーしないと、中身が連動してしまう。

https://techblog.recochoku.jp/5158

import copyしてから、copy.copy、copy.deepcopyなど。

アルゴリズム

最大公約数の求め方(ユークリッドの互除法)

最大公約数:ユークリッドの互除法 整数A,B間の最大公約数(Greatest Common Divisor : GCD)は「ユークリ...

素数の求め方(エラトステネスの篩(ふるい))

エラトステネスの篩 ある正の整数N以下の素数を高速で求めるアルゴリズムです。計算量はO(NloglogN)となります。 pyt...

全探索 計算量を減らす工夫系

愚直にループを回すと計算が間に合わないパターン。

B – Sum of Three Integers

C – 4/N

bit全探索

C – To 3

N=input()

ans=100000

for bit in range(1<<len(N)):
    
    tmp=''
    if bit==0:
        tmp=N
        if int(tmp)%3==0:
            print(0)
            exit()
    for i in range(len(N)):
        if bit&(1<<i):
            tmp+=N[i]
    if int(tmp)%3==0 and len(N)-len(tmp)<ans:
        ans=len(N)-len(tmp)
if ans==100000:
    print(-1)
else:
    print(ans)

C – たくさんの数式

C – Train Ticket

ABCD=input()
for bit in range(1<<3):
    tmp=ABCD[0]
    tmp2=int(ABCD[0])
    for i in range(3):
        if bit&(1<<i):
            tmp+='+'+ABCD[i+1]
            tmp2+=int(ABCD[i+1])
        else:
            tmp+='-'+ABCD[i+1]
            tmp2-=int(ABCD[i+1])
    if tmp2==7:
        print(tmp+'=7')
        exit()

A – AKIBA 

S=input()
akiba=['KIH','B','R']
for bit in range(1<<4):
    tmp=''
    for i in range(4):
        if bit&(1<<i):
            tmp+='A'
        if i<3:
            tmp+=akiba[i]
    if tmp==S:
        print('YES')
        exit()
print('NO')

プライオリティキュー

Atcoderでプライオリティキュー(優先度つきキュー)を使う問題。

C – Factory

import heapq

N,K=map(int,input().split())
ab=[list(map(int,input().split()))for i in range(N)]
heapq.heapify(ab)
ans=0
for i in range(K):
    tmp=heapq.heappop(ab)
    ans+=tmp[0]
    heapq.heappush(ab,[tmp[0]+tmp[1],tmp[1]])

print(ans)

D – Powerful Discount Tickets

import heapq

N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(N):
    A[i]=-A[i]
heapq.heapify(A)
for i in range(1,M+1):
    tmp=heapq.heappop(A)
    heapq.heappush(A,-(-tmp//2))
print(-1*sum(A))

D – Summer Vacation

import heapq

N,M=map(int,input().split())
AB=[list(map(int,input().split()))for i in range(N)]
ABlist=[[]for i in range(10**5+1)]
for i in range(N):
    ABlist[AB[i][0]].append(-AB[i][1])
ans=0
q=[]
heapq.heapify(q)
for i in range(1,M+1):
    for j in ABlist[i]:
        heapq.heappush(q,j)
    if len(q)>0:
        ans+=-heapq.heappop(q)
print(ans)

デック:deque

両端キュー。両端からの要素追加がO(1)でできる。

D – String Formation

from collections import deque
S=list(input())
S=deque(S)
Q=int(input())
rev=0
for i in range(Q):
    tmp=list(input())
    if tmp[0]=='1':
        rev+=1
    if tmp[0]=='2':
        if tmp[2]=='1':
            if rev%2==0:
                S.appendleft(tmp[4])
            else:
                S.append(tmp[4])
        else:
            if rev%2==0:
                S.append(tmp[4])
            else:
                S.appendleft(tmp[4])
if rev%2!=0:
    S.reverse()
print(''.join(S))

C – pushpush

from collections import deque

n=int(input())
a=list(map(int,input().split()))
ans=deque()
for i in range(n):
    if i%2==0:
        ans.append(a[i])
    else:
        ans.appendleft(a[i])
if n%2!=0:
    ans.reverse()
ans=list(ans)
ans=[str(i) for i in ans]
ans=' '.join(ans)
print(ans)

動的計画法:DP

Educational DP Contest / DP まとめコンテスト

これを一通り解けばよいでしょう。

BFS:幅優先探索

A – 幅優先探索

D – .. (Double Dots)

DFS:深さ優先探索

A – 深さ優先探索

R,C=map(int,input().split())

c=[list(input())for i in range(R)]
for i in range(R):
    for j in range(C):
        if c[i][j]=='s':
            sx=j
            sy=i
        if c[i][j]=='g':
            gx=j
            gy=i

seen=[[1000]*C for i in range(R)]
que=[[sy,sx]]
seen[sy][sx]=1
ans=0

now=list()
while len(que)>0:
    now.append(que[-1])
    del que[-1]

    if now[0][0]==gy and now[0][1]==gx:
        ans=1
        break

    dy=[0,0,1,-1]
    dx=[1,-1,0,0]

    for i in range(4):
        tmp_y=now[0][0]+dy[i]
        tmp_x=now[0][1]+dx[i]
        if tmp_x<0 or C-1<tmp_x or tmp_y<0 or R-1<tmp_y:
            continue
        if c[tmp_y][tmp_x]=='#':
            continue
        if seen[tmp_y][tmp_x]!=1000:
            continue
        que.append([tmp_y,tmp_x])
        seen[tmp_y][tmp_x]=1
    del now[0]

if ans==1:
    print('Yes')
else:
    print('No')

Union find

B – Union Find

いもす法

C – オセロ

D – Water Heater

import itertools

N,W=map(int,input().split())
STP=[list(map(int,input().split()))for i in range(N)]
bkt=[0]*3*10**5
ans=[0]
tmp=0
for i in range(N):
    bkt[STP[i][0]]+=STP[i][2]
    bkt[STP[i][1]]-=STP[i][2]
ans=itertools.accumulate(bkt)
if max(ans)>W:
    print('No')
else:
    print('Yes')

剰余演算、逆元

割り算の時の処理に注意。よく理解してません。

参考になる本

下記の本は非常にわかりやすい。職場においてあるのをチラチラ見ているだけであるが。お金ができたら買いたい。

スポンサーリンク
スポンサーリンク




スポンサーリンク




シェアする

  • このエントリーをはてなブックマークに追加

フォローする

スポンサーリンク
スポンサーリンク