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())

こういうときの入力
####1.2 複数入力

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

N Kのようなときの入力
####1.3 リスト入力

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

h₁ h₂ ... h_N　のようなときに使う

j₁
j₂
.
.
.
j_N
のようにタテに並んでいるときは

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=' ')

こういう出力が求められるときに使う
大体ループの中に入れてる

###ToDo

• もっとバリエーション増やす
• itertools編とか増やしていきたい

####github
https://github.com/kobayu0902art/AtCoder