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

#AtCoder
https://atcoder.jp/

# この記事の目的
* Atcoderでのコンテスト本番中にあたふた慌てないように整理すること
* 問題を解いてる途中に参照しやすい状態にすること
* アウトプット作業に慣れること
* Markdown記法に慣れること
* 目次でページ内リンクがやりたかった(githubの.mdではうまくいかなかった)<br>→(2019/10/02時点)あれ、うまくリンクとんでない、、、どうして、、、(勉強中)<br>→(2019/10/03時点)見出しに番号をつけないことで解決したがやっぱり番号付けたい(勉強中)


【**随時更新予定**】

[入力編]:(#入力編)
[リスト編]:(#リスト編)
[数値編]:(#数値編)
[書き方編]:(#書き方編)
[出力編]:(#出力編)

|目次|
|-----------------|
|1. [入力編](#入力編)|
|[appendix[解答用紙]](#appendix)|
|2.[リスト編](#リスト編)|
|3.[数値編](#数値編)|
|4.[書き方編](#書き方編)|
|5.[出力編](#出力編)|

#入力編
####1.0 入力用
```python
import sys
input = sys.stdin.readline
```
これで`input()`だけより早くなるらしい
####1.1 単入力
```python
n=int(input())
```
![mono.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/499408/ea050628-7a17-e90b-06e5-2fc45178da6b.png)
こういうときの入力
####1.2 複数入力
```python
n,m=(int(x) for x in input().split())
```
![multi.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/499408/7bc618e4-c0b3-cd9c-a7f8-54d80b7ba16c.png)
N Kのようなときの入力
####1.3 リスト入力
```python
l = [int(i) for i in input().split()]
```
![multi.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/499408/7bc618e4-c0b3-cd9c-a7f8-54d80b7ba16c.png)
h<sub>1</sub> h<sub>2</sub> ... h<sub>N</sub>　のようなときに使う

j<sub>1</sub>
j<sub>2</sub>
.
.
.
j<sub>N</sub>
のようにタテに並んでいるときは

```python
j=[]
for _ in range(n):
    j.append(input())
```

##appendix
解答用紙

```python: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だけのリスト
```python
l=[]
l=[0]*n
```
####2.2 リストに要素追加
```python
l.append(n)
```
####2.3 重複なしのリスト
```python
l=set(l)
```
####2.4 リストを大きい順(降順)にソート
```python
l.sort(reverse=True)
```
####2.5 優先度付きキュー
例として、【「リストaの最大値を1/2してリストaに戻す」をm回繰り返す】

```python
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))
```

--------------------------------------------------------------

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

```python
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 素因数分解リスト列挙
```python
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
```python
n%2==0
```
####3.3 最大公約数,最小公倍数
nとmの最大公約数ansを求める

```python
import math
ans=math.gcd(n,m)
```

最小公倍数はgcdを用いて

```python
def lcm(n,m):
    return (n*m)//math.gcd(n,m)
```
####3.4 約数列挙,公約数列挙
```python
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`を用いて、

```python
ansdiv=set(make_divisors(n))&set(make_divisors(m))
```
#書き方編
#### 4.1 2重ループを1行に
```python
import itertools
for i,j in itertools.product(range(n), range(n)):
    pass
```
計算量は変わらないから競プロ的にはいらない？
#### 4.2 リスト内組み合わせ
```python
import itertools
itertools.combinations(list,n)
```
計算量多めだから注意
#出力編
#### 5.1 スペース区切り出力
```python
print(s,end=' ')
```
![out.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/499408/b1458093-434e-a9fb-4891-65dba8e064f4.png)
こういう出力が求められるときに使う
大体ループの中に入れてる

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

####github
[https://github.com/kobayu0902art/AtCoder](https://github.com/kobayu0902art/AtCoder)