LoginSignup
112
156
@do_an(安東 稜人)

競プロでよく使うけど空で書けないフレーズ

Last updated at Posted at 2024-02-26

はじめに

よく使うけどうろ覚えなものをまとめました．

順列・組合せ・重複列挙

リストからいくつか選んだ順列or組合せor重複組合せを列挙

from itertools import product, permutations, combinations
L = [1,2,3,4]; k = 2; N = 3
for p in permutations(L,k):
    print(p,end=' ')
#(1, 2) (1, 3) (1, 4) (2, 1) (2, 3) (2, 4) (3, 1) (3, 2) (3, 4) (4, 1) (4, 2) (4, 3) 
for c in combinations(L,k):
    print(c, end=' ')
#(1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)
for pro in product((0,1), repeat=N):
    print(pro, end=' ')
# (0, 0, 0) (0, 0, 1) (0, 1, 0) (0, 1, 1) (1, 0, 0) (1, 0, 1) (1, 1, 0) (1, 1, 1)

dict

# 初期化
D = dict()

# 存在しないキー参照でエラーになる対策
D[k] # Error
D.get(k) # None
D.get(k,0) # 0

Counter

3個以上あるkeylistが欲しいときは
L = [k for k,v in c.items() if v>2]
とかできてとても便利

L = [1,1,0,0,2,2,2]

import collections
c = collections.Counter(L)

print(c) # Counter({2: 3, 1: 2, 0: 2})
print(c.keys()) # dict_keys([1, 0, 2])
print(c.values()) # dict_values([2, 2, 3])
print(c.items()) # dict_items([(1, 2), (0, 2), (2, 3)])
print(c.most_common()) # [(2, 3), (1, 2), (0, 2)] # valueが大きい順にソート

defaultdict

valuesの型を指定する
存在しないキーを参照してもデフォルトの値を返す．
デフォルト値はint: 0，str: 空文字列，set: ()，list: []

from collections import defaultdict
D = defaultdict(int)
D = defaultdict(str)
D = defaultdict(set)
D = defaultdict(list)
D = defaultdict(lambda: -1) # デフォルトで-1を返す
# 二次元もとれる
D = defaultdict(lambda: defaultdict(int))
d['key']['a'] += 3

クソデカグリッドのseenを取るときに使える

from collections import defaultdict
seen = defaultdict(bool)
x,y = 1,2
seen[str(x)+','+str(y)] = True

文字列の結合

int型ではエラーがでるので注意
文字列の結合にはO(N)かかるので最後にまとめて結合するのがよい

L = [1,2,3]
L = [str(l) for l in L]
s = ''.join(L)
print(s) # 123

2個目の要素だけでsort

L = [[1,2], [2,1]]
L.sort(key=lambda x:x[1])
print(L) # [[2,1], [1,2]]

enumerate

めっちゃ使う

# 0から始まる
L = [4,5,6]
for i, name in enumerate(L):
    print(i, name)
# [0, 4], [1, 5], [2, 6]

# 1から始まる
for i, name in enumerate(L, 1):
    print(i, name)
# [1, 4], [2, 5], [3, 6]

累積和

0から始まるのが欲しかったら
B = [0] + BでOK

from itertools import accumulate
A=[1,4,3,4,6,5]

# 前から
B = list(accumulate(A))
print(B) #[1, 5, 8, 12, 18, 23]

# 後ろから
B = list(accumulate(A[::-1]))[::-1]
print(B) #[23, 22, 18, 15, 11, 5]

deepcopy

D,Eのやり方もあるよ

from copy import deepcopy
A = [1,2,3]
B = A
C = deepcopy(A)
D = [a for a in A]
E = A[:]

A[0] = 100
print(B,C,D,E) # [100, 2, 3] [1, 2, 3] [1, 2, 3] [1, 2, 3]

10進数 ->2,8,16進数

i = 255

int(bin(i)[2:]) # 11111111
int(oct(i)[2:]) # 377
hex(i)[2:] # ff

int(format(i, 'b'))# 11111111
int(format(i, 'o'))# 377
format(i, 'x') # ff

0埋め

8桁右詰めで右埋め

print(format(i, '08b')) # 11111111
print(format(i, '08o')) # 00000377
print(format(i, '08x')) # 000000ff

n進数 -> 10進数

n<=36までしか対応していないらしい
https://note.nkmk.me/python-bin-oct-hex-int-format/

print(int('10'))
print(int('10', 2))
print(int('10', 8))
print(int('10', 16))

n進数<->10進数

これなら任意に変換できる
https://qiita.com/ether2420/items/061c19a000c52adf7f3e

# n進数->10進数
def base_10(num_n,n):
    num_10 = 0
    for s in str(num_n):
        num_10 *= n
        num_10 += int(s)
    return num_10

# 10進数->n進数
def base_n(num_10,n):
    str_n = ''
    while num_10:
        if num_10%n>=10:
            return -1
        str_n += str(num_10%n)
        num_10 //= n
    return int(str_n[::-1])

上限

【AtCoder】Pythonで競プロをするときの注意点まとめ【競技プログラミング】

再帰上限

dfsでは深さの制限を解除しないとエラーがでる
デフォルトは1000

import sys
sys.setrecursionlimit(10 ** 8)

4300桁制限

pythonのintは桁数を気にしなくてもよいと思っていたけど，
実は4300桁の制限があるらしい．
引数に0を指定すると制限を解除できる．

import sys
sys.set_int_max_str_digits(0)

入力のおまじない

import sys
input = sys.stdin.readline

deque

ランダムアクセスがO(N)
O(1)に改良したお話が(こちら)[https://prd-xxx.hateblo.jp/entry/2020/02/07/114818]

from collections import deque
q = deque()

heapq

log(N)で要素を出し入れできる
push,popのとき値を-1倍すると最大値を扱える

from heapq import heapify,heappush,heappop
a = [1, 6, 8, 0, -1]
heapify(a)  # リストを優先度付きキューへ
print(a)
# 出力: [-1, 0, 8, 1, 6] (優先度付きキューとなった a)

print(heappop(a))  # 最小値の取り出し
# 出力: -1 (a の最小値)
print(a)
# 出力: [0, 1, 8, 6] (最小値を取り出した後の a)

heappush(a, -2)  # 要素の挿入
print(a)
# 出力: [-2, 0, 1, 8, 6]  (-2 を挿入後の a)

Decimal

小数の精度を上げる
精度が高い平方根，分数への変換に使う
Decimal型変換するときはstrを経由する．
※ PyPyよりCPythonの方が速い(参考)

from decimal import Decimal, getcontext
getcontext().prec = 1000

a = 2.5
a = Decimal(str(a))
c = (a).sqrt() # print(c) #1000桁のroot2.5

b = 0.1
b = Decimal(b) # 0.1000000000000000055511151231257827021181583404541015625
print(b) # float型だとうまくできない

c = 3.14
Decimal(str(c)).as_integer_ratio() #(-157, 50)

メモ化再帰

フィボナッチ数列が早くなる

from functools import lru_cache
@lru_cache()
def f(x):
    pass

zip

zip()の使い方
複数の配列を頭から同時に参照できる．
これを使うと行列の転置が楽になる．
引数の長さが異なる場合短い長さに調整される．

L = [[1,2,3],[4,5,6]]
list(zip(*L)) # [(1, 4), (2, 5), (3, 6)]
list(map(list,zip(*L))) # [[1, 4], [2, 5], [3, 6]]

A = [1,2,3]
B = [4,5,6]
for a,b in zip(A,B):
    print(a,b)
    # 1 4
    # 2 5
    # 3 6

print(list(map(str,L))) # ['1','2','3']
[str(l) for l in L] # ['1','2','3']

二重ループからbreak

二重ループ内のifを通ってbreakすると
外側ループのelse:continueを通らずにbreakする

for i in range(10):
    for j in range(10):
        # code
        if i*j>80:
            # ループ終了時の処理
            break
    else:continue
    break
print(i,j) # 9 9

if文中のand, or

andは前の命題が偽ならそれ以降は見ない．
orは前の命題が真ならそれ以降は見ない．
グリッド問題でifの回数を減らせる．

A = list('..#'); W = 3

i = 2
if 0<=i<W and A[i]=='#':
    print(True)
else:print(False)

i = 4
if 0<=i<W and A[i]=='#':
    print(True)
else:print(False)

# True
# False

B = []
if not B or B[1]==0:
    print(True)
# True

print

一つ目はスニペットに登録しています．
二つ目はデバッグに重宝します．

# 条件分岐を含める
miss = True
print('Yes' if not miss else 'No') # No

# f文字列
a = -1
print(f"私は{a}歳")

文字列の判定

Pythonで大文字・小文字を操作する文字列メソッド一覧
朝飯前に学べる！便利なPythonのヒント100選【後編】
すべてＯＯか判定する．

# すべてアルファベットまたは数字ならTrue
s = '1a2b3c'
s.isalnum() # True
s = 'happy&happy'
s.isalnum() # False

# 文字列が数値ならTrue
s = '2024'
s.isdigit() # True
s = '00'
s.isdigit() # True

# すべてアルファベットならTrue
s = 'abc'
s.isalpha() # True

# すべて大文字ならTrue
s = 'ATCODER'
s.isupper() # True

# すべて小文字ならTrue
t = 'atocder'
t.islower() # True

ss = 'ATCODER1234!' # 数字や記号は無視される
ss.isupper() # True

すべての文字を大文字，小文字に変換する

s = 'ATCODER'
s = s.lower() # atcoder
t = 'atocder'
t = t.upper() # ATCODER

# 反転もできる
u = 'Atcoder'
u = u.swapcase() # aTCODER

リストの要素がbool値のとき

［解決！Python］all／any関数を使って、リストなどの要素が全て真か／偽か、真な要素があるか／偽な要素があるかを調べるには


# 要素がすべて真ならTrue
seen = [True]*3
if all(seen):
    print(-1) # -1
    
# 要素に真が存在すればTrue
seen = [True, False]
if any(seen):
    print(-2) # -2

# 要素がすべて偽ならTrue
seen = [False]*3
if not any(seen):
    print(-3) # -3
    
# 要素に偽が存在すればTrue
seen = [True, False]
if not all(seen):
    print(-4) # -4

四捨五入

参考1
参考2

from decimal import Decimal,ROUND_HALF_UP
pi = 3.141592653589793

a = Decimal(str(pi)).quantize(Decimal('1'),rounding = ROUND_HALF_UP) 
b = Decimal(str(pi)).quantize(Decimal('1.0'),rounding = ROUND_HALF_UP)
c = Decimal(str(pi)).quantize(Decimal('1.00'),rounding = ROUND_HALF_UP)
d = Decimal(str(pi)).quantize(Decimal('1.000'),rounding = ROUND_HALF_UP)
print(a,b,c,d) # 3 3.1 3.14 3.142
112
156
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
112
156