ホームに戻る
TopCoder の傾向と対策(Python編)
0、はじめに
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 を使う場合もありますがバージョン確認が必要です。
いまのところバージョン3以降では無いようです。
for i in xrange(2000000):
pass
1、テンプレート
ブロックはインデントで表す。
# コメント
"""
複数行コメント
"""
class ClassName:
def MethodName(self,arg0,arg1):
return 0
配列数が固定の場合は、
def MethodName(self,arg0,(a,b,c)):
などとしてしまっても良い。
なお、出力は print で自動改行を行います。
改行しない場合は print "abc", とします。
2、変数
型の指定は不要。キャスト用に int ,long, float がある。
a = 1
b = 1.0
c = float(2) / 3
d = "abc"
e = "123"
f = "%04d" % a # 書式に対応
g = int(e) # 文字列が10進数の数字以外ならエラー
h = str(a)
i = True # True は値で 1
j = False # False は値で 0
k = 1000000000000000000000000000000000000000000000000000000
# 文字と数字の相互変換
k = ord("c") - ord("a")
l = "ab" + (chr(j + ord("a")))
3、配列
配列はリストと呼ぶ。
0スタートで終端は含まない仕様。
a = [0]*100
# 2次元配列 (注: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)
とする。
4、ディクショナリ
# キーと値のセット
a = {"a": 1, "b", 3}
# キーと値の追加
a["c"] = 7
# キーがあるかどうかのチェック
if "a" in a:
if "b" not in a:
# キー、値、(キー,値)のリストを得る
a.keys()
a.values()
a.items()
5、制御構文
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 はインデックス
6、関数
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])
7、順列、組み合わせ
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)]
8、クラス
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]
9、数学関数
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、よく使いそうな表現の覚え書き
値の扱い
# 10乗の表記
a = 1e10
# 浮動小数
a = float(3) / 2
# 2進数を10進数に変換
a = int("1010",2)
# 10進数を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")
多次元配列
# 2次元配列 a[10][100]
a = [[0] * 100 for i in range(10)]
# 3次元配列 a[2][3][50]
a = [[[0] * 50 for i in range(3)] * 2 for i in range(2)]
# 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):
# すべての要素に変更を加える (すべての要素を2乗する)
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
# 隣り合う2つの要素で探索
for b1,b2 in zip(a,a[1:]):
# 2つの要素で探索 (i < j)
import itertools
for i,j in itertools.combinations(range(10),2):
# 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)