TopCoder の傾向と対策（Ｐｙｔｈｏｎ編）

０、はじめに

2013年7月から TopCoder で Python が使えるようになりました。
Python を使うと強力な構文を使って短いコードが書けます。
そして TopCoder で使うアルゴリズムを十分に実装可能です。
print を使ったデバッグもやりやすいように思います。
ただし、Python はどうしても実行速度が遅くなります。
実行速度が Python で十分に足りるか？を見積もるのが最大の問題になります。
そして、メモリの使い方にも気をつける必要があります。
また、Python のバージョンにも気をつけましょう。

重要：TopCoder ではすべての問題が Pyhton で解けることを
保障しないので注意しましょう。
これは主に

速度について、
以下のコードでアリーナは 1.5 秒の実行速度を要します。
よって、ループは最大 20000000 程度に抑える必要があります。

i = 0
while i < 20000000:
  i += 1

メモリについて、
以下のコードで実行可能でした。
5000000 だとエラーなので、最大 4000000 程度までしか使えません。

a = [0]*4000000

2013年12月にメモリが 256MB に増えました。

a = [0]*30000000

まで使えるようになりました。

また、ループは次のように書くことができません。
2000000 のループは速度的には余裕ですが、
内部でメモリを使っているのでメモリエラーになります。

for i in range(2000000):
  pass

2013年12月にメモリが 256MB に増えて 7000000 まで可能。

基本的にはこのようなループでメモリを使うべきではありません。
この場合は以下のようにして回避できます。

i = 0
while i < 2000000:
  i+=1

xrange を使う場合もありますがバージョン確認が必要です。
いまのところバージョン３以降では無いようです。

for i in xrange(2000000):
  pass

１、テンプレート

ブロックはインデントで表す。

# コメント
"""
複数行コメント
"""
class ClassName:
  def MethodName(self,arg0,arg1):
    return 0

配列数が固定の場合は、

  def MethodName(self,arg0,(a,b,c)):

などとしてしまっても良い。

なお、出力は print で自動改行を行います。
改行しない場合は print "abc", とします。

２、変数

型の指定は不要。キャスト用に int ,long, float がある。

a = 1
b = 1.0
c = float(2) / 3
d = "abc"
e = "123"
f = "%04d" % a # 書式に対応
g = int(e) # 文字列が１０進数の数字以外ならエラー
h = str(a)
i = True   # True は値で 1
j = False  # False は値で 0
k = 1000000000000000000000000000000000000000000000000000000

# 文字と数字の相互変換
k = ord("c") - ord("a")
l = "ab" + (chr(j + ord("a")))

３、配列

配列はリストと呼ぶ。
０スタートで終端は含まない仕様。

a = [0]*100
# ２次元配列 (注：10 のループは実行速度を有する)
a2 = [[0] * 10000 for i in range(10)]
b = [1,2,3,4,5]
b2 = range(1,11,2)
len(b)     # 長さ
sum(b)     # 総和
min(b)     # 最小値を返す
max(b)     # 最大値を返す
b += [6]   # 値の追加
b.pop(0)   # インデックスを消去 (省略すると最後を消去)
b[1:3] = []# 1 以上 3 より下を削除 (インデックス 1 と 2 が消える)
c = b[:2]
d = c[1:]
d2 = [-1]  # 最後の要素にアクセス
b.sort()
b.count(2)
b.reverse()

c = set(b)   # set は {0,1,2,2,2} などリテラルでも書ける
d = list(c)
e = tuple(d) # tuple は値が不変な配列のこと (0,1,2) などと書く

s = "".join(["a","b","c"])     # ["a","b","c"] を "abc" に結合
s = ",".join(map(str,[1,2,3])) # [1,2,3] を "1,2,3" に結合
a = "1,2,3".split(",")         # "," で分割
b = "1234".replace("1", "5")   # "1" を "5" に

f1 = 1 in [1,2,3]  # [1,2,3] に 1 が含まれれば True を返す
f2 = (1 and 2) in [1,2,3]  # [1,2,3] に 1 と 2 が含まれれば True を返す
f3 = "bc" in "abcd"  # "abcd" に "bc" が含まれれば True を返す

なお、リストのコピーには注意する。
以下のコードは 0 を出力する。
これは python がすべてを参照渡しで行うからである。

a = [1,2,3]
b = a

b[1] = 0

print a[1]

リスト a を b にコピーするには。

b = list(a)

とする。

４、ディクショナリ

# キーと値のセット
a = {"a": 1, "b", 3}

# キーと値の追加
a["c"] = 7

# キーがあるかどうかのチェック
if "a" in a:
if "b" not in a:

# キー、値、(キー,値)のリストを得る
a.keys()    
a.values()
a.items()

５、制御構文

if a == 0:
  pass                 # 何もしないときは pass と書く
elif a == 1 or a == 2:
  pass
elif not(3 <= a <= 5):
  pass
else:
  print a
  
b = True if a == 0 else False

while a < 7:
for i in a:             # リスト a 内すべて
for i in range(8):      # 0 から 7
for i in range(1,8):    # 1 から 7
for i in range(7,0,-1): # 7 から 1
for i in range(1,8,2):  # 1 3 5 7
  break
else:                   # break で終了しない場合呼ばれる
  pass

次のようにも書ける。

a = [i for i in range(1, 10)]
b = [i**3 for i in range(1, 10000) if i**3 < 10000]
c = [0 if i == 1 else i for i in a] # a の要素に 1 があれば 0 に
d = sum(i * i for i in range(1, 10))
e = sum(i >= 5 for i in [2,3,4,5,6,7])
f = [v for i, v in enumerate([1,2,3,4,5]) if i % 2 == 0] # 偶数番目を取り出し

for i in sorted([4,1,3,2]):
for a, b, c in ((1,2,3),(4,5,6)):
for a, b in zip([1,2,3],[4,5,6]):
for i, v in enumerate(["a", "b", "c"]): # i はインデックス

６、関数

python はすべての値が参照渡しされる。
しかし、動作はあたかも値渡しのように動作することがある。
関数の動作は頭の中でしっかり整理しておく必要がある。

def f(b):
  b = 3

a = 1
f(a)

これは a = 1 で a が 1 を参照していると考える。
f(a) を行うことで b は a が参照するのと同じ 1 を参照する。
b = 3 で新たに 3 が作成され b は 3 を参照する。
関数が破棄されると b の参照は破棄される。
a は依然として 1 を参照している。
これは値渡しのように動作しているが、実際は参照渡しである。

# ラムダ関数を用いてすべての要素に 1 を加算
a = map(lambda x: x+1, [1,2,3])

７、順列、組み合わせ

permutations は C++ の next_permutation と異なる。
C++ の next_permutation の場合、
0,1,1 の次は 1,0,1 で、次は 1,1,0 である。
python の permutations の場合、
0,1,1 の次は 0,1,1 で、次は 1,0,1 である。
これは 1 と 1 を入れ替えていることも考えるため。

import itertools

a = list(itertools.product('AB', 'ab', '12'))

[('A', 'a', '1'), ('A', 'a', '2'), ('A', 'b', '1'),
 ('A', 'b', '2'), ('B', 'a', '1'), ('B', 'a', '2'),
 ('B', 'b', '1'), ('B', 'b', '2')]

a = list(itertools.product('AB', repeat=2))

[('A', 'A'), ('A', 'B'), ('B', 'A'), ('B', 'B')]

a = list(itertools.permutations(range(3)))

[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]

a = list(itertools.permutations(range(3), 2))

[(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]

a = list(itertools.combinations(range(3), 2))

[(0, 1), (0, 2), (1, 2)]

８、クラス

class Data:
  def __init__(self,a,b):
    self.a = a
    self.b = b
  def __str__(self):
    return str(self.a) + " " + str(self.b)
  def get(self):
    return (self.a,	self.b)

import operator
a = []
a += [Data(1,2)]
a += [Data(3,4)]
a.sort(key=operator.attrgetter('b'))
print a[0]

９、数学関数

import math

# 素数判定
def isPrime(n):
  if n < 2:
    return 0
  elif n == 2:
    return 1
  for i in range(2, int(math.sqrt(n))+1):
    if not n % i:
      return 0
  return 1

# 因数分解
def fact(n):
  ret = []
  while n % 2 == 0:
    ret.append(2)
    n /= 2
  for i in range(2, int(math.sqrt(n))+1):
    while n % i == 0:
      ret.append(i)
      n /= i
  if n > 1:
    ret.append(n)
  return ret

# 階乗
def factorial(n):
  if n == 0: return 1
  return n * fact(n - 1)

# 最大公約数
def gcd(a, b):
  if b == 0: return a
  return gcd(b, a % b)

# 最小公倍数
def lcm(a, b):
  return a / gcd(a, b) * b

１０、よく使いそうな表現の覚え書き

   値の扱い

# 10乗の表記
a = 1e10
# 浮動小数
a = float(3) / 2
# ２進数を１０進数に変換
a = int("1010",2)
# １０進数を２進数に変換
a = format(10,'b')
# 値のスワップ
a,b = b,a
# 値を捨てる
a,_ = 1,2

   文字列関係

# 文字から数字へ (a = 0 とするとき)
a = ord("c") - ord("a")
# 数字から文字へ (a = 0 とするとき)
a = "ab" + (chr(j + ord("a")))
# 数字から文字列へ
a = str(1234)
# 文字への代入 a[i] = "X" はできない
a = a[:i] + "X" + a[i+1:]
# 数字から文字列へ 書式つき
a = "%08d" % 1234
# 文字列の結合
a = "".join(["ab","cd","e"])
# 文字列の分離
a = "1 2 3".split(" ")
# 文字列の置換
a = "1234".replace("12", "56")
# 文字列がその文字で始まるかを判定
a = "1234".startswith("12")
# 文字列がその文字で終わるかを判定
a = "1234".endswith("34")

   多次元配列

# ２次元配列 a[10][100]
a = [[0] * 100 for i in range(10)]
# ３次元配列 a[2][3][50]
a = [[[0] * 50 for i in range(3)] * 2 for i in range(2)]
# ２次元配列の探索
for y in range(len(a)):
  for x in range(len(a[0])):
    print a[y][x],
  print

   配列関係

# 配列を set へ
a = set(a)
# 昇順ソート
a.sort()
# 反転
a.reverse()
# 降順ソート
a.sort();a.reverse()
# 要素の数をカウント
a.count(2)

   配列の要素をまとめて処理

# 条件を満たす要素数をカウント (i == 0 をカウント)
b = sum(1 for i in a if i == 0)
# すべての要素が条件を満たすかチェック (すべて i == 0 なら 1)
if not sum(0 if i == 0 else 1 for i in a):
# すべての要素に変更を加える (すべての要素を２乗する)
a = [i**2 for i in a]
# 条件を満たすもののみリストに残す (i == 0 を満たさないものは消える)
a = [i for i in a if i == 0]
# 条件を満たすものと満たさないもので処理を変える (i == 0 なら 1 にする、でなければ残す)
a = [1 if i == 0 else i for i in a]

   探索

# 0 から 9 の探索
for i in xrange(10):
# ジェネレータ // 初期値 0 以降 +1 してジェレネート
def g(n):
  while 1: yield n; n+=1
for i in g(0): print i
# 擬似 goto
try:
  if True:
    raise Exception
except Exception:
  pass
# 隣り合う２つの要素で探索
for b1,b2 in zip(a,a[1:]):
# ２つの要素で探索 (i < j)
import itertools
for i,j in itertools.combinations(range(10),2):
# ２つの要素で探索 (i <= j)
import itertools
for i,j in itertools.combinations_with_replacement(range(10),2):
# 順列
import itertools
for i in itertools.permutations(range(4)):
# ビット順列 (permutations ではなく combinations を使おう)
import itertools
for i in set(itertools.combinations(range(10),2)):
# ディクショナリの探索
for k,n in a.items():

# 深さ優先探索
def f(a):
  if len(a) == 10:
    print a
    return
  f(a+[a[-1]+1])
a = [0]
f(a)

# 幅優先探索
import Queue
q = Queue.Queue()
q.put(0)
while not q.empty():
  a = q.get()
  print a
  if a == 10: break
  q.put(a+1)