#CP pythonでのnumpyに関するメモ
10^7とかになるとpythonではatcoderの2s制限にひっかかってくるので、高速化のためにリストではなく、numpyの配列を使うようにしたいわけです。
ということで必要最低限のnumpyの使い方について自分用にまとめておきます。今後追加するかも。
# NumPyモジュールをインポート import numpy as np # リストの配列化 a1 = np.array([1,1,4,5,1,4]) print(a1) # [1 1 4 5 1 4] # 全ての要素が0の要素数nの配列を生成 n = 5 a2 = np.zeros(n,dtype=np.int) #dtypeを指定しないとfloatになるっぽい print(a2) # 配列の長さを取得 l1 = len(a1) print(l1) # 6 # 配列の要素の取得 for i in range(l1): print(a1[i], "", end="") # 1 1 4 5 1 4 print() #改行 # 配列のスライス print(a1[0:3]) # [1 1 4] # 配列同士の四則演算(for文より早いらしい) # リストでやると"連結"になるので注意 a3 = np.array([1,9,1,9,1,9]) print(a1+a3) # [ 2 10 5 14 2 13] print(a1-a3) # [ 0 -8 3 -4 0 -5] print(a1*a3) # [ 1 9 4 45 1 36] print(a1//a3) # [1 0 4 0 1 0] # ある数値との四則演算も可能 print(3+a1) # [4 4 7 8 4 7] print(3-a1) # [ 2 2 -1 -2 2 -1] print(3*a1) # [ 3 3 12 15 3 12] print(3//a1) # [3 3 0 0 3 0] # 配列の連結(リストにおけるextendと同様の挙動) # 配列なのでコピーが発生→遅いらしい a4 = np.append(a1,a3) print(a4) # [1 1 4 5 1 4 1 9 1 9 1 9] # 多次元配列に変換 a5 = a2.reshape(5,1) print(a5) # [[0] # [0] # [0] # [0] # [0]]
まとめ
リスト型はlist, 配列型はarrと表記
- listの配列化 : np.array(list)
- 要素数nの0(整数)だけの配列の生成 : np.zeros(n, dtype=np.int)
- 長さの取得 : len(arr)
- indexがiの要素の取得 : arr[i]
- 配列のスライス(リストと同じ): arr[x:y]
- 配列同士の演算 : arr1 op arr2
- 数値と配列の演算 : x op arr
- 配列の連結 : np.append(arr1, arr2)
- 多次元配列(x行y列)への変換 : arr.reshape(x,y)
#AtCoder ABC116 -D- Python
マジでAtCoderの解法PDFを読むのが苦手なので(日本語力がないので)、お気持ちを書き残そうと思います。
まず最初に貪欲を考える癖があるので気を付けたいです。
今回の問題は種類ボーナスポイントさえなければもちろんおいしさを降順にソートして、k個足すだけで解くことができます。ですが、今回は基礎ポイントがあるのでこうは解けません。
しかし、美味しい順にk個食べても(わりと)いいポイントは得られそうです。ここから改善することを考えます。まず、おいしさ順に上からk個食べた寿司の集合をSとします。よりポイントを高めるためにはSに含まれる種類が増えなければなりません。(もし増えなければ今のSのスコアが最大のはずです) ということでSの中で同じ種類で2つ以上食った寿司の中から一番まずいもの(bと名付けます)を吐きだします。そして食べたことのない一番おいしい寿司(gと名付けます)を食べます。つまり、Sからbを消してaを追加します。しかしこれでスコアが増えるかどうかはわかりません。よって、この作業を繰り返してSのスコアのmaxを取るのがいいでしょう。
コードに起こすと以下のようになります。
n, k = map(int, input().split()) sushi = [] for i in range(n): tmp = list(map(int, input().split())) sushi.append(tmp) eaten = set() # 食べた種類を記憶(集合型) chohuku = [] # 同じ種類で二回以上食べた寿司のスコアを記録 scores = [] # Sのスコアのリスト sushi.sort(key=lambda x:x[1]) sushi.reverse() tmp = 0 # Sのおいしさの合計を保持 for i in range(k): if sushi[i][0] in eaten: # 同じ種類の寿司を食べていた場合 chohuku.append(sushi[i][1]) else: eaten.add(sushi[i][0]) tmp += sushi[i][1] chohuku.sort() scores.append(tmp+len(eaten)**2) for i in range(k,n): # 残りの寿司から美味しい順に食べるものを選ぶ if not sushi[i][0] in eaten and chohuku != []: # 重複が存在し、また食べていない種類のとき tmp -= chohuku.pop(0) eaten.add(sushi[i][0]) tmp += sushi[i][1] scores.append(tmp+len(eaten)**2) print(max(scores))
#CP pythonでのbit演算に関するメモ
pythonでのbit演算についてまとめておきます。
シフト演算はあえて使い方を載せません。個人的にシフト演算はごちゃる気持ちがあるのでpow(2,n)を使って大抵済ませることにします。 どう考えてもシフト演算の方が早いのでそっちでやらないとダメみたいです。
まずは普通のbitのand,or,xor,反転
10進、2進両方で書いてますが、値は同じです。
# and print(2 & 1) # 0 print(0b10 & 0b01) # or print(2 | 1) # 3 print(0b10 | 0b01) # xor print(2 ^ 1) # 3 print(0b10 ^ 0b01) # 反転 print(~2) # -3 print(~0b10)
pythonではintもlongもなく、整数型が何bitであるかは決まっていないのでもしすべての桁の0と1を反転させるなら別の方法が必要になります。それは次にあります。
次にある正整数xが何bitで表現できる数なのかを知る方法です。
単純に0になるまで2で割るだけです。
bitごとの反転は桁数を得た後に桁数の数だけ111...となっているものからひくだけです。
def get_digit(x): digit = 0 while x != 0: digit += 1 x //= 2 return digit # 15の桁数 print(get_digit(15)) # 4 def bit_not(x): dig = get_digit(x) return 2**dig -1 - x # 15のbitごとの反転 print(bit_not(12)) # 3 print(bin(bit_not(0b1100))) # 0b11
また下n桁を取り出す方法は次のような感じになります。
単純に指定した桁まで...111となっているものとのbitのandをとるだけです。
最後のn桁目が1かどうかの判定はシフト演算を使います。(一番右の位を0桁目にするのが都合がよいみたいです)
# 下n桁を取り出す def getunderN(x,n): return x & 2**n-1 print(getunderN(13,3)) # 5 print(bin(getunderN(0b1101, 3))) #0b101 # n桁目が1か判定する # ただし最右bitは0桁目 def JudgeDigitN(x,n): return x >> n & 1 == 1 print(JudgeDigitN(13,3)) # True print(JudgeDigitN(0b1101, 3))
