初心者用 AtCoderでよく使うPython表記

目的

pythonと競技プログラミングを学びたいためatcoderを始めました
他の言語ではあまり見ない構文等が沢山あるので、備忘録的な形で少しずつまとめます
速度改善やテクニック的なのも分かり次第追記予定

値取得

• 入力値を取得する方法

取得

# 入力
# 2
# 1 2 3
N = int(input()) # 2
A = list(map(int, input().split())) # [1, 2, 3] 数値変換してリストで代入

一括

# 入力
# 4
# 5
# 6
X, Y, Z = map(int, [input() for __ in range(3)]) # X=4 Y=5 Z=6

• sys.stdin.readline
• こっちのほうが早いらしい
• 下記でinputに置き換え可能？

import sys
input = sys.stdin.readline

配列

• 初期化

a = [0] * 3 # [0,0,0]
b = [0, 1] * 2 # [0, 1, 0 ,1]

• 最後から取得

a = [1, 2, 3]
a[-1] # 3
a[-2] # 2

• スライス
• リスト、タプル、文字列の一部を切り取れる

s = [1, 2, 3, 4, 5]
s[2] # 3
s[1:] # [2, 3, 4, 5]
s[:2] # [1, 2]
s[1:2] # [2]
s[:] # [1, 2, 3, 4, 5]

• ステップ

a = [1,2,3,4,5]
a[::2]  #  [1,3,5]
a[1::2] #  [2,4]

• 特定値の抽出

l = [1, 2, 3, 4, 5]
data = [i for i in l if i % 2 == 0] # [2, 4]

組み込み関数

• all(), any()
  • list, tuple等のイテラブル要素が全て、又は１つ以上Trueか判定

data = [2, 4, 6 ,8]
while(all(i%2 ==0 for i in data):
    # リスト内が全て偶数であれば処理

• enumerate
• イテラルオブジェクトの要素とインデックスを取得出来る

data = [10, 20, 30, 40]
for i, n in enumerate(data):
    print(i, n)
# 1 10
# 2 20
# 3 30
# 4 40

• sorted
• ソート　降順、昇順

data = [3,1,2]
sorted(data)  #[1, 2, 3]
sorted(data, reverse=True) #[3, 2, 1]

• replace
• 文字列を置換

s = 'abcdefg'
s.replace('cde', '') #abfg

• abs
• 絶対値

a = 1
b = -1
abs(a) # 1
abs(b) # 1

数値

• fractions
• math は使えないので注意

import fractions

• 最大公約数、最小公倍数

x, y = 10, 4
gcd = franctions.gcd(x, y) # 2
lcm =  x * y // gcd # 20

numpy

pythonのみで計算より高速なので状況によっては好まれる
勉強中

考え方やテクニック メモ

• スター (グラフ)

中央の頂点と、それから放射状に辺が繋がる合計N個の頂点を持つグラフ
ここから完全グラフにするには、(n-1)(n-2)/2 の辺が必要
下の問題では、スターグラフから辺を増やして求められる値に近づけるテクニックが必要
https://atcoder.jp/contests/abc131/tasks/abc131_e

• ２部グラフ

https://atcoder.jp/contests/abc131/tasks/abc131_f
xとyの２部グラフで考え、連結性毎にx * y - 辺の数で求められる