okinawa

IT勉強メモ

Python学習メモ

競技プログラミング Python

AtCoderで試しにPythonを使ってみることにしたのでメモを。

主に競技プログラミングで必要になることを箇条書き。

標準出力

print("あああ")

# end 末尾の改行なしで出力
print(100, end="-")
print(200) # 100-200

#sep 区切り文字を指定
print(100, 'apple') # 100 apple
print(100, 'apple', sep = ",") #100,apple

i = ['a', 'b', 'c']
print(*i) # a b c
print(*i, sep = "") # abc

標準入力の受け取り

num = int(input())

#int
N=int(input())
A,B=map(int, input().split())

#文字列
S=input()
S,T=map(str, input().split())

#list
A=list(map(int, input().split()))
S=[input() for i in range(n)]

#list2(１つずつ切り離してListにしたいとき）
A=list(map(int, input()) #splitいらず
S=list(map(str, input()) #splitいらず

# N行の空の2次元配列
A1＝[[] for _ in range(N)]

# 2次元配列（N行の標準入力をまとめて受け取り）
A2 = [list(map(int, input().split())) for _ in range(N)]

内包表記

[式 for 任意の変数名 in イテラブルオブジェクト]

# list(map(int, input().split()))が式。N回式を繰り返してリストに格納しますよ、ということ
A2 = [list(map(int, input().split())) for _ in range(n)]

# []が式？N行１列で空の２次元配列を作る
A1＝[[] for _ in range(N)]

[式 for 任意の変数名 in イテラブルオブジェクト if 条件式]

# 偶数のみリストに格納
A = [i for i in range(10) if i % 2 == 0]

・参考
Pythonリスト内包表記の使い方 | note.nkmk.me

演算子

足し算：+

引き算：-

掛け算：*

割り算の商(整数値int)：//

割り算の商(小数値float)：/

割り算の余り：%

累乗：**

データ型

動的型付け言語なので、変数宣言時に型指定はしない。

int型：整数

float型：浮動小数点

str型：文字列

bool型：真偽値

list型：リスト・配列（変更可能）
x = ['Hello', 'World', 9]

tuple型：タプル（変更不可）
x = ('Hello', 'World', 9)

dict型：辞書（連想配列）
x = {'cat':'tama', 'dog':'pochi', 'year':1776}

set型：集合(順序なし）
x = {'cat', 'dog', 'bird'}

char型：存在しない

listの操作一覧

要素数を指定して初期化  
list = [0]*100 #100個の要素を値０で初期化

# 2次元配列の初期化（5要素）
list2 = [[] for _ in range(5)] # [[], [], [], [], []]

要素取得  
list[0]

要素長さ取得  
len(list)

末尾に追加  
list.append(1)

要素変更
list[2] = 5

要素指定して追加  
list.insert(値,要素番号）

末尾に別のlist追加  
list.extend([3, 5])
または
n=[1,2]
n2=[3]
n3=[4]
n = n + n2 + n3 #[1,2.3.4]

全削除  
list.clear()

１要素削除
del list[要素番号]

1要素削除（値で検索して削除）  
list.remove(値)  

要素番号を取得(値で検索して取得）
list2 = [0, 2, 5]
list2.index(5) #2

要素を取得して削除（スタックっぽい動作）    
list.pop(要素番号)  
list.pop() 指定なしだと末尾を削除。

ソート  
list.sort()  
listそのものをソートする

逆順ソート
list.sort(reverse=True)

ソート２  
list2 = sorted(list)  
ソートしたlistを返す。listそのものはソートされない。

反転  
list.reverse()

コピー  
import copy  
list2 = copy.copy(list1)  

list1 = list2 これだと参照渡しになってしまう

全要素の合計値
num = sum(list)

文字列をList化
s = "PHP"
list1 = list(s) #['P','H','P']

# ２次元配列宣言（空）
list1=[[] for _ in range(n)]

# ２次元配列宣言（任意の値）
list1 = [[i, 0] for i in range(3)] #[0,0][1,0][2,0]

dict型（連想配列）の操作

# 初期化 
d = {'cat':'tama', 'dog':'pochi', 'year':1776}

# 値の取得
value = d['cat'] # tama

# 値の変更
d['cat'] = 'nyansuke'

# 追加
d['name'] = 'suzuki'

# d から d[key] を削除します。
del d[key]

# d がキー key を持っていれば True を、そうでなければ、 False を返します。
key in d

#全ての値を取得
for i in d.values()

#全てのキーを取得
for i in d.keys()

# 全てのキーリストを返す
list(d)

defaultdict

競プロだとdefaultdictがいいらしい。

・dictとの違い

dictは存在しないキーを指定して値を取得しようとすると、エラー。

defaultdictは存在しないキーを指定して値を取得しようとすると、設定した関数の初期値が返ってくる

さらに存在しないキーに値を追加すると、キーを作ってくれる。

・参考サイト
https://memoribuka-lab.com/?p=1680

from collections import defaultdict

# defaultdict(関数)
default_dict = defaultdict(int)
print(default_dict[3]) # 存在しないキー。０が返る。int関数の初期値が０なので。

#辞書の中に集合 {key ： value集合{1,2,3}}
default_dict2 = defaultdict(set)
default_dict2[1].add(3) #存在しないキー：１を作ってくれる {1 : {3}}
default_dict2[1].add(5) # {1 : {3, 5}}

set(集合）の操作

重複なし・順序なしの集合。SQLっぽい。

・参考サイト
Python | 集合と他の集合との関係を調べる(等しいかどうか、部分集合かどうかなど)

set1 = {1, 1, 2, 2.0, 3, 3.00, 4, 4.000} # 1,2,3,4
set2 = {4, 5, 6, 7}

set3 = set() # 空のset

set1.add(5)

set1.remove(5)

# リストの中身を全追加
list1 = [1,2,3]
set3.update(list1)

# 集合同士の比較が簡単！普通の比較演算子が使える
if set1 == set2
if set1 != set2
if set1 <= set2
if set1 < set2
if set1.isdisjoint(set2) # 一致するものが一つも無い時にTRUE

# 和集合
union = set1 | set2 #1 2 3 4 5 6 7

# 差集合
except = set1 - set2 #1 2 3

# 積集合(重複部分だけ）
intersect = set1 & set2 #4

優先度付きキュー

優先度付きキュー (Priority queue) はデータ型の一つ。

  • 最小値 or最大値をO(logN)で取り出す
  • 要素をO(logN)で挿入する

通常のリストO（N）より高速。

・使い所
「リストの要素の挿入」と「最小値（最大値）を取り出す」ことを繰り返すような時に使う。

・参考
【Python】優先度付きキューの使い方【heapq】【ABC141 D】 - Qiita

import heapq
list1 = [3, 5, 2]
heapq.heapify(list1)
print(list1) # [2, 5, 3]

# 追加
heapq.heappush(list1, 1)#[1, 2, 3, 5]
heapq.heappush(list1, 4)#[1, 2, 3, 5, 4]

# 最小値を取得＆削除
heapq.heappop(list1)#[2,4,3,5]

# 最大値を取得したいときは追加時に-1を掛けておく
list1 = []
heapq.heappush(list1, 5*-1)
heapq.heappush(list1, 3*-1)
heapq.heappush(list1, 2*-1) #[-5, -3, -2]
x = heapq.heappop(list1) # -5を取得できる
print(-x)# 5

関数定義

def hello(name):
    print(name)
    print(f"Hello, {name}")
return name

if

if 1+1 == 2:
  print("ok")
elif 1+2 != 3:
  print("ok2")
else: 
  print("ng")


if 1 > 2 and 1 > 3 or 5 < 7
   print("ok")

for

continue,breakもあるよ。

numbers = [3, 14, 15, 92, 65, 77]

total = 0
for number in numbers:
    total += number

print(total)

range

range 型の値 (オブジェクト) は、等間隔で並ぶ整数型。

# 5 以上 10 未満の整数の集合
print(list(range(5,10))) # [5, 6, 7, 8, 9]

# 範囲が無効な場合、空になる
print(list(range(10,5))) # []

# 引数が 1 つの場合、from の値が 0 となる
print(list(range(4))) # [0, 1, 2, 3]

# 10 から 15 未満の範囲で 2 ずつ変化する整数の集合
print(list(range(10, 15, 2))) # [10, 12, 14]

# 16 から 10 より大きい範囲で -2 ずつ変化する整数の集合
print(list(range(16, 10, -2))) # [16, 14, 12]

# 1~5未満
for i in range(1,5)
   print(i)

while

number = 998244352

while number % 2 == 0:
    number //= 2
    print(number)

map関数

map関数はリストやタプルなどの各要素にまとめて指定した関数を使える。

Javaで言うところのSteam APIみたいなのだろうか。

競技プラグラミングだと標準入力をまとめて受け取るときに使う。

書き方→map(関数, リストやタプル)

N, A, B = map(int, input().split())
C = list(map(int, input().split()))

上記のintはint関数で、文字列を整数に変換する。

スライス

スライスは、リストや文字列、タプル等のシーケンス型の一部をインデックスを指定して取り出す操作のこと。

s[開始位置 : 終了位置 : ステップ数]　※終了位置はN未満までが出力されることに注意

s = "ABCDEFG"

# 全出力
print(s[0:7])

#0~2未満。 ABが出力
print(s[0:2])

# ４番目だけ出力 D
print(s[3])

# 4番目以降を出力 DEFG
print(s[3:])

# 末尾からN番目の要素を出力 F
print(s[-2])

# 末尾からN個の要素を出力 FG
print(s[-2:])

# 最初からN-1番目まで ABC
print(s[:3])

# 最初から末尾N番目まで ABCDE
print(s[:-2])

#逆順で全取得 GFEDCBA
print(s[::-1])

Fraction Decimal(小数の計算）

・使い所
誤差を許容できる場合： →そのまま計算する

少数ありの数値計算(割り算がない場合)： →Decimalを使う

割り算がある数値計算： →Fractionを使う

・計算速度
float > Decimal > Fraction

・注意
DecimalもFractionも引数はstring

from fractions import Fraction
from decimal import Decimal

print(0.1+0.2)#0.30000000000000004
print(Decimal("0.1")+ Decimal("0.2"))#0.3
print(Fraction("0.1")+ Fraction("0.2"))#3/10
print(float(Fraction("0.1")+ Fraction("0.2")))#0.3
print(Decimal('1') / (Decimal('1')/Decimal('60'))) # 59.99999999999999999999999999
print(float(Fraction('1')/(Fraction('1')/Fraction('60'))))#60

参考サイト

プログラミングにおける数値計算はワナがいっぱい - Qiita

ソートの色々

# 普通のソート
list1.sort()
list1.sort(reverse=True)
list2 = sorted(list1)
list2 = sorted(list1, reverse=True)

# 引数には要素が1個ずつ渡されてくる
def sample(a):
    return a[1]#リスト内タプルの2番めの要素でソート

# list型
list = [(0, 1), (2, 3), (1, 2), (3, 0)]#2次元配列でも結果は同じ？
list = sorted(list)
print(list) #[(0, 1), (1, 2), (2, 3), (3, 0)]
list = sorted(list, key=sample)
print(list)#[(3, 0), (0, 1), (1, 2), (2, 3)]
list = sorted(list, key=lambda a: a[1])#ラムダ式。リスト内タプルの2番めの要素でソート。
print(list)#[(3, 0), (0, 1), (1, 2), (2, 3)]
list = sorted(list, key=lambda a: -a[0])#ラムダ式。逆順ソート。
print(list)#[(3, 0), (2, 3), (1, 2), (0, 1)]

#list ２次元配列を行ごとにソート
# １行毎にソートかけていくしかなさそう。
list1=[[50000, 1, 2, 3], [1, 1000, 2999], [777, 1, 2]]
list2=[0]*3
for i in range(3):
  list2[i]=sorted(list1[i])
print(list2)#[[1, 2, 3, 50000], [1, 1000, 2999], [1, 2, 777]]


# Map型
my_dict = {'banana': 3, 'apple': 1, 'cherry': 2}
sorted_dict = sorted(my_dict.items(), key=lambda x: x[0])#keyでソート
print(sorted_dict)# [('apple', 1), ('banana', 3), ('cherry', 2)]
sorted_dict = sorted(my_dict.items(), key=lambda x: x[0], reverse=True)#逆順ソート
print(sorted_dict)# [('cherry', 2), ('banana', 3), ('apple', 1)]
sorted_dict = sorted(my_dict.items(), key=lambda x: x[1])#valueでソート
print(sorted_dict)# [('apple', 1), ('banana', 3), ('cherry', 2)]


# 複数要素でソート
def sample2(a):
    return a[1], a[0]#valueが同じならkeyでソート
    
my_dict = {'banana': 3, 'apple': 1, 'cherry': 1}
sorted_dict = sorted(my_dict.items(), key=sample2)#valueが同じならkeyでソート
print(sorted_dict)# [('apple', 1), ('cherry', 1), ('banana', 3)]
sorted_dict = sorted(my_dict.items(), key=lambda x: (x[1], x[0]))#ラムダ式。valueが同じならkeyでソート
print(sorted_dict)# [('apple', 1), ('cherry', 1), ('banana', 3)]


#複雑なソートはcmp_to_key
from functools import cmp_to_key
# 基本形
# 大小の比較結果は -1, 0, 1 のいずれかを返す。小さければ -1 を返し、等しければ 0 を返し、大きければ 1 を返す。
# 引数a=0番目の要素 引数b=1番目の要素　→　引数a=1番目の要素 引数b=2番目の要素...と順繰りに渡されてくる
def sample3(a, b):
    if a > b: return 1
    if a == b: return 0
    if a < b: return -1

# タプルの1つ目の要素が同じなら、2つ目の要素の逆順でソート    
def compare(a, b):
    if a[0] > b[0]: return 1
    if a[0] < b[0]: return -1
    if a[0] == b[0]:
        if a[1] < b[1]: return 1
        if a[1] == b[1]: return 0
        if a[1] > b[1]: return -1
        
list = [('apple', 1), ('apple', 3), ('cherry', 1)]
list = sorted(list, key=cmp_to_key(compare))
print(list)# [('apple', 3), ('apple', 1), ('cherry', 1)]

・参考リンク
【Python】cmp_to_keyでソートの実装 - okinawa

要素の数え上げ(Counter）

イテラブルなオブジェクトの要素を数え上げる。

リスト、タプル、辞書、文字列など。

from collections import Counter
c = Counter() # 空のカウンター

c = Counter(['a', 'a', 'b', 'c'])
print(c['a']) # 2

# Counterは連想配列型で{key: 出現回数}を持つ
s = "abbcccdddd"
print(Counter(s))#Counter({'d': 4, 'c': 3, 'b': 2, 'a': 1}) 

c = Counter(s)
print(c['d'])# 4

# most_common
#出現回数順に出力
print(c.most_common())#[('d', 4), ('c', 3), ('b', 2), ('a', 1)]
# 出現回数上位2個を出力
print(c.most_common(2))#[('d', 4), ('c', 3)]

他にも差集合や積集合も求められるらしい。

参考サイト

Python: カウンタ。Counter()関数で要素数を計算する - コムテブログ

コレクションのアンパック（複数の変数に分解）

コレクションの中身を分解して取り出すイメージ。

# アンパック基本
a = [1,2,3]
b,c,d = a
print(b,c,d)# 1 2 3

a = (1,2,3)
b,c,d = a
print(b,c,d)# 1 2 3

a = {1,2,3}
b,c,d = a
print(b,c,d)# 1 2 3

# *でアンパック
a = [1,2,3]
b,*c = a
print(b,c)# 1 [2, 3]
*b,c = a
print(b,c)#[1, 2] 3

# アンパック使い所(出力)
a = [1,2,3]
print(a) #[1, 2, 3]
print(*a)#1 2 3

# アンパック使い所。別のコレクションに一部を移し替え
a = [1,2,3]
b, *c = a
c = set(c) # listからSetへ変換
print(b,c) #1 {2, 3}

・参考サイト
Pythonでタプルやリストをアンパック（複数の変数に展開して代入） | note.nkmk.me

・アンパック活用例
Submission #43662262 - freee Programming Contest 2023（AtCoder Beginner Contest 310）

文字をASCIIコードに変換

# 文字→ASCII
asci = ord("A") # 65

# ASCII→文字
s = chr(asci) # A

ちなみに、Pythonにchar型はないようで。

全体の参考サイト

https://algo-method.com/topics