Edited at

AtCoderコンテスト用まとめ【Python】


AtCoder

https://atcoder.jp/


この記事の目的


  • Atcoderでのコンテスト本番中にあたふた慌てないように整理すること

  • 問題を解いてる途中に参照しやすい状態にすること

  • アウトプット作業に慣れること

  • Markdown記法に慣れること

  • 目次でページ内リンクがやりたかった(githubの.mdではうまくいかなかった)
    →(2019/10/02時点)あれ、うまくリンクとんでない、、、どうして、、、(勉強中)
    →(2019/10/03時点)見出しに番号をつけないことで解決したがやっぱり番号付けたい(勉強中)

随時更新予定

目次

1. 入力編

appendix[解答用紙]

2.リスト編

3.数値編

4.書き方編

5.出力編


入力編


1.0 入力用

import sys

input = sys.stdin.readline

これでinput()だけより早くなるらしい


1.1 単入力

n=int(input())

mono.PNG

こういうときの入力


1.2 複数入力

n,m=(int(x) for x in input().split())

multi.PNG

N Kのようなときの入力


1.3 リスト入力

l = [int(i) for i in input().split()]

multi.PNG

h1 h2 ... hN のようなときに使う

j1

j2

.

.

.

jN

のようにタテに並んでいるときは

j=[]

for _ in range(n):
j.append(input())


appendix

解答用紙


contest_base.py

import sys

import itertools
input = sys.stdin.readline

n=int(input())
n,m=(int(x) for x in input().split())
l = [int(i) for i in input().split()]

print()


基本的にこれをコピーして使いまわしてます

必要な入力だけ残してあとは消す


リスト編 


2.1 空リスト,要素が0だけのリスト

l=[]

l=[0]*n


2.2 リストに要素追加

l.append(n)


2.3 重複なしのリスト

l=set(l)


2.4 リストを大きい順(降順)にソート

l.sort(reverse=True)


2.5 優先度付きキュー

例として、【「リストaの最大値を1/2してリストaに戻す」をm回繰り返す】

import heapq

a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)
for _ in range(m):
temp = heapq.heappop(a)
heapq.heappush(a, (-1)*(-temp//2))


優先度付きキューを使わない場合:

a = [int(i) for i in input().split()]

a.sort(reverse=True)
for _ in range(m):
a[0]=a[0]//2
a.sort(reverse=True)

この場合いちいち全要素をソートしなおすので計算量が膨大になってTLEとなる


数値編


3.1 素因数分解リスト列挙

def factorize(n):

b = 2
fct = []
while b * b <= n:
while n % b == 0:
n //= b
fct.append(b)
b = b + 1
if n > 1:
fct.append(n)
return fct


3.2 偶奇判断:偶数True奇数False

n%2==0


3.3 最大公約数,最小公倍数

nとmの最大公約数ansを求める

import math

ans=math.gcd(n,m)

最小公倍数はgcdを用いて

def lcm(n,m):

return (n*m)//math.gcd(n,m)


3.4 約数列挙,公約数列挙

def make_divisors(n):

divisors = []
for i in range(1, int(n**0.5)+1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n//i)
divisors.sort()
return divisors

公約数列挙はmake_divisorsを用いて、

ansdiv=set(make_divisors(n))&set(make_divisors(m))


書き方編


4.1 2重ループを1行に

import itertools

for i,j in itertools.product(range(n), range(n)):
pass

計算量は変わらないから競プロ的にはいらない?


4.2 リスト内組み合わせ

import itertools

itertools.combinations(list,n)

計算量多めだから注意


出力編


5.1 スペース区切り出力

print(s,end=' ')

out.PNG

こういう出力が求められるときに使う

大体ループの中に入れてる


ToDo


  • もっとバリエーション増やす

  • itertools編とか増やしていきたい


github

https://github.com/kobayu0902art/AtCoder