Python：プログラミングコンテストでよく使う処理

動作確認はPython3.4で実施。（AtCoderに合わせている）
随時追加していきます。

## 入力

```python
# 文字列
S = input()

# 数値
N = int(input())

# 決まった数の数値
A, B, C = map(int, input().split())
A, B, C = [int(i) for i in input().split()]

# 配列として受け取る
D = list(map(int, input().split()))
D = [int(i) for i in input().split()]
```

## 数値
### 小数点の切り捨て
```python
int(3.999) # 3
```

## 配列・リスト
### 特定の位置に要素を挿入

```python
>>> a = ['a','b','c','d']
>>> a.insert(2, 'x')
>>> a
['a', 'b', 'x', 'c', 'd']
```

### 特定の位置の要素を削除

```python
>>> a = ['a','b','c','d']

# 末尾の要素を削除
>>> a.pop()
'd'
>>> a
['a', 'b', 'c']

# 1番目（０始まり）の要素を削除
>>> a.pop(1)
'b'
>>> a
['a', 'c']
```

### 配列の分割

* 長さ５のリスト(a)があったときに、a[:2]は、`[a[0], a[1]]`。つまり、a[2]は含まれない。
* a[2:]は、`[a[2], a[3], a[4]]`。つまり、a[2]も含む。

```python
N = 5
a = [i for i in range(N)]
for i in range(N+1):
    print(i, a[:i], a[i:])

# 0 [] [0, 1, 2, 3, 4]
# 1 [0] [1, 2, 3, 4]
# 2 [0, 1] [2, 3, 4]
# 3 [0, 1, 2] [3, 4]
# 4 [0, 1, 2, 3] [4]
# 5 [0, 1, 2, 3, 4] []
```

### [Python3]配列の配列をソートする
https://qiita.com/aki-takano/items/73b3f3ef90e05a441da8


### 逆順に並びかえる

```python
>>> [1,2,3][::-1]  # 並び替えられた新しいリストを作成
[3, 2, 1]

>>> [1,2,3].reverse()  # 破壊的処理
```

### 奇数番目の要素、偶数番目の要素

```python
>>> [0,1,2,3][1::2]
[1, 3]

>>> [0,1,2,3][::2]
[0, 2]
```

### deque（両端に挿入可能なリスト）

```python
from collections import deque

deq = deque()

deq.append(0)
deq.append(1)
deq.append(2)
deq.appendleft(-1)
deq.appendleft(-2)

print(deq)

# 実行結果：
# deque([-2, -1, 0, 1, 2])
```

参考：[collections.deque](https://docs.python.org/ja/3/library/collections.html#collections.deque)

## 文字列
### 分割

配列の分割と同じように扱える。

```python
S = 'abcde'
for i in range(len(S)+1):
    print('{} "{}" "{}"'.format(i, S[:i], S[i:]))

# 0 "" "abcde"
# 1 "a" "bcde"
# 2 "ab" "cde"
# 3 "abc" "de"
# 4 "abcd" "e"
# 5 "abcde" ""
```

## 文字
### 大文字
```
>>> [chr(i) for i in range(ord('A'), ord('Z')+1)]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
```

### 小文字

```
>>> [chr(i) for i in range(ord('a'), ord('z')+1)]
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
```

## 数学
### 平方根

```python
from math import sqrt
print(sqrt(2))
print(sqrt(4))

# 実行結果：
# 1.4142135623730951
# 2.0
```

### 階乗

```python
from math import factorial
factorial(5)

# 実行結果：
# 120
```

### 整数A、Bに対して、A/Bの切り捨て

```python
>>> 5 // 2
2
>>> 5 // 3
1
```

### 整数A、Bに対して、A/Bの切り上げ

`(A+B-1)//B の商` で求められる。

```python
>>> A = 3; B = 2
>>> (A + B - 1) // B
2

>>> A = 4; B = 2
>>> (A + B - 1) // B
2

>>> A = 5; B = 2
>>> (A + B - 1) // B
3
```

### 最大公約数、最小公倍数
https://qiita.com/aki-takano/items/a43fac70b702d4f22d7e

### 素因数分解

```python
def f(n):
    r = dict()
    while n != 1:
        for i in range(2, n+1):
            while n % i == 0:
                r[i] = r.get(i, 0) + 1
                n /= i
    return r

# 実行結果
# f(12)  # -> {2: 2, 3: 1}
# f(28)  # -> {2: 2, 7: 1}
# f(29)  # -> {29: 1}
```

## ２進数、ビット演算
### ２進数の文字列を得る

```python
>>> format(2, 'b')
'10'

>>> format(7, 'b')
'111'
```

桁数を固定する。（0でパディング）

```python
>>> format(2, 'b').zfill(4)
'0010'
>>> format(2, 'b').zfill(16)
'0000000000000010'
```

### ある数値を２進数に変換したとき、どのビットが立っているか

```python
KETA = 8  # 桁数
bits = []  # どこのビットが立っていたか

N = 9     # 対象とする値
b = format(9, 'b').zfill(KETA)
print(b)
for i in range(KETA):
    if (N >> i) & 1 == 1:
        bits.append(i)
print(bits)

# 00001001
# [0, 3]
```

### XOR（排他的論理和）
どちらか1の場合のみ1、それ以外は0

|A|B|OUT|
|:-:|:-:|:-:|
|000|000|000|
|001|010|011|
|111|010|101|

```python
>>> 0 ^ 0
0
>>> 1 ^ 2
3
>>> 7 ^ 2
5
```


## Python
### 最大再帰数を上げる
https://qiita.com/aki-takano/items/9bbb88db07db3c8f9fb5


### n桁の2進数の数をまとめて作成
https://qiita.com/aki-takano/items/d74b023a82cbfd780bb1

### 文を実行する

```python
>>> eval('1+2+3')
6
```

## 順列、組み合わせ
### 順列
```python
import itertools

a = ['a','b','c']
p = list(itertools.permutations(a))
print(p)

# 実行結果：
# [('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]
```

### 組み合わせ
ループを使う。

```python
a = [1,2,3]
for i in range(len(a)):
    for j in range(i+1, len(a)):
        print(a[i], a[j])

# 実行結果：
# 1 2
# 1 3
# 2 3
```

別のやり方。

```python
>>> from itertools import combinations
>>> list(combinations([1,2,3], 2))
[(1, 2), (1, 3), (2, 3)]
```

```python
>>> a = [1,2,3]
>>> for i in range(len(a)+1):
...     list(combinations(a,i))
... 
[()]
[(1,), (2,), (3,)]
[(1, 2), (1, 3), (2, 3)]
[(1, 2, 3)]
```

## 集合
### 差集合
setを使う。（listではできない）

```python
>>> {1,2,3,4} - {1,4}
{2, 3}
>>> {1,2,3,4}.difference({1,4})  # 上記と同じ
{2, 3}
```

### 共通部分

```python
>>> s1 = set([1,2,3])
>>> s2 = set([2,3,4])
>>> s1 & s2
{2, 3}
```

## 便利なモジュール、データ型など
### Counter
https://docs.python.org/ja/3/library/collections.html#collections.Counter

```python
from collections import Counter

c = Counter()

c['a'] += 1
c['a'] += 1
c['b'] += 1

print(c)

# 実行結果：
# Counter({'a': 2, 'b': 1})
```

## 幾何
### 円
原点を中心とした半径rの円は、`x ** 2 + y ** 2 = r ** 2`
(x1, y1)を中心とした半径rの円は、`(x - x1) ** 2 + (y - y1) ** 2 = r ** 2`

ある座標(a, b)が円の内部にあるかどうかは、次のように判定可能
`(a - x1) ** 2 + (b - y1) ** 2 <= r ** 2`

### 直角三角形の角度を求める

底辺の長さがa、高さがhのときの斜辺と底辺で作られる角の角度を求める。

```python
import math
radian = math.atan2(h, a)
(radian / (2 * math.pi)) * 360
```

参考：https://atcoder.jp/contests/abc144/tasks/abc144_d


## 変数名
ローカル変数名に迷うことがあるので。

* p, prob: 確率
* prev: 一つ前のデータ（ループ処理で）

## また使うかもしれないアルゴリズム
### 回文の判定

```python
S = input()
l = len(S)
kaibun = True
for i in range(l):
    if S[i] != S[l-1-i]:
        kaibun = False
print(kaibun)
```