AtCoder
この記事の目的
- 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()]
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=' ')
こういう出力が求められるときに使う
大体ループの中に入れてる
ToDo
- もっとバリエーション増やす
- itertools編とか増やしていきたい