AtCoder Beginner Contest 176 振り返り
結果
ABCEの4完でパフォ1391。
Eを23分で通したあたりはキタ━(゚∀゚)━!!と思いましたがDが通らず爆発しました。
A | B | C | D | E | F |
---|---|---|---|---|---|
0:38 | 1:31 | 2:31 | (7) | 23:14 | - |
問題
A - Takoyaki
切り上げよ。
N, X, T = map(int, input().split()) print((N+X-1)//X*T)
切り上げ除算のイディオム。
B - Multiple of 9
バカでかい数が9の倍数かどうか判定せよ。
N = input() ad = 0 for n in N: ad += int(n) print('Yes' if ad % 9 == 0 else 'No')
桁ごとに足して9の倍数かどうか判定した。
Pythonは多倍長整数演算が得意な子なので、普通にN%9を計算できることに後で気づいた。
print('No' if int(input()) % 9 else 'Yes')
C - Step
数列を講義単調増加にするためにどれだけ下駄を履かせる必要があるか。
N = int(input()) *A, = map(int, input().split()) prev = 0 ans = 0 for a in A: if prev > a: ans += prev-a else: prev = a print(ans)
B問題で出てもおかしくない問題だったと思う。
D - Wizard in Maze
2点間の最短コストを求めよ。
- 東西南北にコスト0の辺を張る。
- それ以外のワープできる地点にコスト1の辺を張る。
計算回数%%2.5 \times 10 ^7%%くらい必要で、ダイクストラで大丈夫か?と疑心暗鬼になる。
テストケースの1つだけTLEになるのが解消できず撤退。
結論としてはダイクストラがちゃんと書けていなかった。キューに突っ込む前の枝刈りができていないのがTLEの原因。
ちなみに想定解は0-1 BFSというもの。知らなかったので勉強になった。
コスト0の辺はキューの先頭に、コスト1の辺はキューの末尾に追加してやると、優先度付きキューより計算量がlogぶん落ちる。
E - Bomber
制約的に各マスに注目する解法はダメなので、爆破対象の座標をうまく集計して解く方法を考える。
行ごと・列ごとに爆破対象の個数をカウントして、ともに最大になるような地点に爆弾を設置するのが最善。
ただし、設置した場所に爆破対象がある場合を考慮する必要がある。
- %%i%% 行目にある爆破対象の数を %%R_i%%、%%i%% 列目にある爆破対象の数を %%C_i%% と表す。
- 答えは%%\underset{i}{\max}R_i + \underset{j}{\max}C_j%% 。ただし、%%R_i+C_j%%を最大にする全ての地点%%(i, j)%%に爆破対象がある場合は %%1%% を引く。
最後の %%1%% を引くか判定するところは、爆破対象が %%M%% 個しかないので、高々 %%M+1%% 個調べれば十分。
import sys read = sys.stdin.buffer.read readlines = sys.stdin.buffer.readlines input = sys.stdin.buffer.readline H, W, M = map(int, input().split()) HH = [0]*H WW = [0]*W d = set() for line in readlines(): h, w = map(int, line.split()) h -= 1 w -= 1 d.add((h, w)) HH[h] += 1 WW[w] += 1 m = -1 argm = [] for i, c in enumerate(HH): if c > m: m = c argm = [i] elif c == m: argm.append(i) mH = m aH = argm m = -1 argm = [] for i, c in enumerate(WW): if c > m: m = c argm = [i] elif c == m: argm.append(i) mW = m aW = argm ans = mH + mW for h in aH: for w in aW: if (h, w) not in d: break else: continue break else: ans -= 1 print(ans)
総評
見事に水中位パフォで安定してしまっています。まあ精進量を考えると妥当です。
Windows+Pip環境でPyTorchのインストールがうまく行かない
解決
ここにwhlファイルが転がっているので、対応するcpのものを選ぶ。
例
pip install https://download.pytorch.org/whl/cpu/torch-1.6.0%2Bcpu-cp38-cp38-win_amd64.whl
cpを確認するときはこう。
>>> from pip._internal.utils.compatibility_tags import get_supported >>> get_supported()
Pythonで非再帰AVL木
追記 upper_boundを開区間に変更しました。
Motivation
操作 | 計算量 |
---|---|
要素xの挿入 | %%O(\log N)%% |
要素xの削除 | %%O(\log N)%% |
要素xの検索 | %%O(\log N)%% |
x以上かつ最小の要素を検索 | %%O(\log N)%% |
x未満かつ最大の要素を検索 | %%O(\log N)%% |
k番目の要素を取得 | %%O(\log N)%% |
こんなことができるデータ構造がほしい。C++はstd::setやstd::mapが使えてずるい(?)ので、Pythonでも使えるようにする。
平衡二分木の一種であるAVL木をPythonで実装してみた。PyPyは再帰が遅いことが知られているので非再帰で実装。以下のページにお世話になった。
参考にしたページ
verify
- ABC128 E - Roadwork - 1772 ms
- ARC033 C - データ構造 - 735 ms
- ABC140 E - Second Sum - 579 ms #set仕様(keyのみ)
コード
class Node: """ノード Attributes: key (any): ノードのキー。比較可能なものであれば良い。(1, 4)などタプルも可。 val (any): ノードの値。 lch (Node): 左の子ノード。 rch (Node): 右の子ノード。 bias (int): 平衡度。(左部分木の高さ)-(右部分木の高さ)。 size (int): 自分を根とする部分木の大きさ """ def __init__(self, key, val): self.key = key self.val = val self.lch = None self.rch = None self.bias = 0 self.size = 1 class AVLTree: """非再帰AVL木 Attributes: root (Node): 根ノード。初期値はNone。 """ def __init__(self): self.root = None def rotate_left(self, v): u = v.rch u.size = v.size v.size -= u.rch.size + 1 if u.rch is not None else 1 v.rch = u.lch u.lch = v if u.bias == -1: u.bias = v.bias = 0 else: u.bias = 1 v.bias = -1 return u def rotate_right(self, v): u = v.lch u.size = v.size v.size -= u.lch.size + 1 if u.lch is not None else 1 v.lch = u.rch u.rch = v if u.bias == 1: u.bias = v.bias = 0 else: u.bias = -1 v.bias = 1 return u def rotateLR(self, v): u = v.lch t = u.rch t.size = v.size v.size -= u.size - (t.rch.size if t.rch is not None else 0) u.size -= t.rch.size + 1 if t.rch is not None else 1 u.rch = t.lch t.lch = u v.lch = t.rch t.rch = v self.update_bias_double(t) return t def rotateRL(self, v): u = v.rch t = u.lch t.size = v.size v.size -= u.size - (t.lch.size if t.lch is not None else 0) u.size -= t.lch.size + 1 if t.lch is not None else 1 u.lch = t.rch t.rch = u v.rch = t.lch t.lch = v self.update_bias_double(t) return t def update_bias_double(self, v): if v.bias == 1: v.rch.bias = -1 v.lch.bias = 0 elif v.bias == -1: v.rch.bias = 0 v.lch.bias = 1 else: v.rch.bias = 0 v.lch.bias = 0 v.bias = 0 def insert(self, key, val): """挿入 指定したkeyに値valを挿入する。 その後、平衡を保つように回転を行う。 Args: key (any): キー。 val (any): 値。 Note: 同じキーがあった場合に上書きする。 """ if self.root is None: self.root = Node(key, val) return v = self.root history = [] while v is not None: if key < v.key: history.append((v, 1)) v = v.lch elif v.key < key: history.append((v, -1)) v = v.rch elif v.key == key: v.val = val return p, pdir = history[-1] if pdir == 1: p.lch = Node(key, val) else: p.rch = Node(key, val) while history: v, direction = history.pop() v.bias += direction v.size += 1 new_v = None b = v.bias if b == 0: break if b == 2: u = v.lch if u.bias == -1: new_v = self.rotateLR(v) else: new_v = self.rotate_right(v) break if b == -2: u = v.rch if u.bias == 1: new_v = self.rotateRL(v) else: new_v = self.rotate_left(v) break if new_v is not None: if len(history) == 0: self.root = new_v return p, pdir = history.pop() p.size += 1 if pdir == 1: p.lch = new_v else: p.rch = new_v while history: p, pdir = history.pop() p.size += 1 def delete(self, key): """削除 指定したkeyの要素を削除する。 その後、平衡を保つように回転を行う。 Args: key (any): キー。 Return: bool: 指定したキーが存在するならTrue、しないならFalse。 """ v = self.root history = [] while v is not None: if key < v.key: history.append((v, 1)) v = v.lch elif v.key < key: history.append((v, -1)) v = v.rch else: break else: return False if v.lch is not None: history.append((v, 1)) lmax = v.lch while lmax.rch is not None: history.append((lmax, -1)) lmax = lmax.rch v.key = lmax.key v.val = lmax.val v = lmax c = v.rch if v.lch is None else v.lch if history: p, pdir = history[-1] if pdir == 1: p.lch = c else: p.rch = c else: self.root = c return True while history: new_p = None p, pdir = history.pop() p.bias -= pdir p.size -= 1 b = p.bias if b == 2: if p.lch.bias == -1: new_p = self.rotateLR(p) else: new_p = self.rotate_right(p) elif b == -2: if p.rch.bias == 1: new_p = self.rotateRL(p) else: new_p = self.rotate_left(p) elif b != 0: break if new_p is not None: if len(history) == 0: self.root = new_p return True gp, gpdir = history[-1] if gpdir == 1: gp.lch = new_p else: gp.rch = new_p if new_p.bias != 0: break while history: p, pdir = history.pop() p.size -= 1 return True def member(self, key): """キーの存在チェック 指定したkeyがあるかどうか判定する。 Args: key (any): キー。 Return: bool: 指定したキーが存在するならTrue、しないならFalse。 """ v = self.root while v is not None: if key < v.key: v = v.lch elif v.key < key: v = v.rch else: return True return False def get(self, key): """値の取り出し 指定したkeyの値を返す。 keyが存在しない場合はNoneを返す。 Args: key (any): キー。 Return: any: 指定したキーが存在するならその値、存在しないならNone。 """ v = self.root while v is not None: if key < v.key: v = v.lch elif v.key < key: v = v.rch else: return v.val return None def lower_bound(self, key): """下限つき探索 指定したkey以上で最小のキーを見つける。 Args: key (any): キーの下限。 Return: any: 条件を満たすようなキー。そのようなキーが一つも存在しないならNone。 """ #ret = float('inf') ret = None v = self.root while v is not None: if v.key >= key: if ret is None or ret > v.key: ret = v.key v = v.lch else: v = v.rch return ret def upper_bound(self, key): """上限つき探索 指定したkey未満で最大のキーを見つける。 Args: key (any): キーの上限。 Return: any: 条件を満たすようなキー。そのようなキーが一つも存在しないならNone。 """ #ret = -float('inf') ret = None v = self.root while v is not None: if v.key < key: if ret is None or ret < v.key: ret = v.key v = v.rch else: v = v.lch return ret def find_kth_element(self, k): """小さい方からk番目の要素を見つける Args: k (int): 何番目の要素か(0オリジン)。 """ v = self.root s = 0 while v is not None: t = s+v.lch.size if v.lch is not None else s if t == k: return v.key elif t < k: s = t+1 v = v.rch else: v = v.lch return None def __contains__(self, key): return self.member(key) def __getitem__(self, key): return self.get(key) def __setitem__(self, key, val): return self.insert(key, val) def __delitem__(self, key): return self.delete(key) def __bool__(self): return self.root is not None def __len__(self): return self.root.size if self.root is not None else 0
使い方
avl = AVLTree() avl[10] = 'a' # avl.insert(10, 'a')と等価 print(avl[10]) # --> a avl[20] = 'b' avl[30] = 'c' avl[40] = 'd' print(avl.lower_bound(15)) # --> 20 print(avl.find_kth_element(2)) # --> 30 print(40 in avl) # --> True del avl[40] # avl.delete(40)と等価 print(40 in avl) # --> False
AtCoder Beginner Contest 175 振り返り
結果
TLEに怯える日々を過ごしています。3完でパフォ1308。
お気持ち的には大爆死ながらレートは-1でほぼ変動なし。
とはいえ青を目指すには低いパフォを続けるわけには行かないので上げていきたい。
A | B | C | D | E | F |
---|---|---|---|---|---|
1:32 | 4:54 | 10:03 | (4) | (1) | - |
問題
A - Rainy Season(1:32)
3文字与えられる。Rがいくつ連続しているか数えよ。
from itertools import groupby S = input() if 'RRR' in S: print(3) elif 'RR' in S: print(2) elif 'R' in S: print(1) else: print(0)
最初RLEを使おうとしてgroupby
を読み込んだが面倒くさくなった。
A問題は方針を2秒で立てられるかの勝負だと思っているので今回は敗北(?)
B - Making Triangle(4:54)
棒が最大100本与えられる。長さが異なるものを3本選んで三角形を作れる組み合わせは何通りあるか?
一瞬 D - Triangles が頭をよぎったが今回はNが小さいので全探索で大丈夫。
ソートしてから条件を書き並べた。
N = int(input()) *L, = map(int, input().split()) L.sort() cnt = 0 for i in range(N): for j in range(i+1, N): for k in range(j+1, N): if L[k] < L[i] + L[j] and L[i] != L[j] and L[j] != L[k] and L[k] != L[i]: cnt += 1 print(cnt)
C - Walking Takahashi(10:03)
座標Xからなるべく原点に近づきたい。1ステップで±Dだけ動ける。Kステップ後の時点で原点との最短距離を求めよ。
ちょうどKステップであるというのを読み飛ばしていてclarに助けられた。
X, K, D = map(int, input().split()) if abs(X) >= D*K: print(abs(X)-D*K) else: q, r = divmod(X, D) if q & 1 == K & 1: print(r) else: print(D-r)
Kステップかけて原点付近まで到達できない場合はなるべく原点に向かって進む。
そうでない場合は原点を超える直前までに何回移動するかを求め、その回数とKの偶奇が一致しているかどうかで場合分け。
pythonだと負数の剰余もいい感じに計算してくれるので簡潔に書ける。
D - Moving Piece
順列に従って移動+スコア獲得をする。K回以下( %%K \leq 10 ^9%% )の移動で達成できるスコアの最大値を求めよ。
最初にダブリングを書いて、そこでK回以下に気づく(実装する前によく見よう)。
方針転換:移動先を与えるリストは順列なので複数のサイクルができる。各サイクルについて獲得スコアの総和が正なら、最大回数ループを続ける(嘘解法)。そうでないなら区間和が最大となるように選ぶ。
これは嘘で、例えば獲得スコアが10 → 10 → -15 のようなループで7回移動するとき、
- 10 → 10 → -15 → 10 → 10 → -15 → 10
- 10 → 10 → -15 → 10 → 10
この2つを比較すると、前者の2回ループ+1回移動よりも後者の1回ループ+2回移動のほうがスコアが高い。結局最後までこれに気づかず。
それ以前の問題として、区間和の最大を求める段階で%%O(N ^2) \simeq 10 ^7%%オーダーの計算が必要なのだが、Pythonがこなせる計算量に対して悲観的すぎるため、何か計算量を改善する方法があるかとググったりしていた。
強いPythonistaならPyPyの力を信じたりNumPy+NumbaやCythonを使って何とでもなるのかしら。
E - Picking Goods
かなり典型的なDPに見えた。
%%dp[i][j][k] = (i, j)%%の地点で、その行で拾ったアイテムの個数が%%k%%個であるときの価値の総和の最大値
とすれば、遷移をうまく書くことができる。
しかし、制約から最大で%%3000 \times 3000 \times 4 \simeq 10 ^7%%オーダーの計算。PyPyで提出したもののTLE。
NumPyを使って書き直したものの手元で全く速くなっていない…(Numbaを試してみるべきだったか)
コンテスト後に配列使い回しで通ることが判明。あと、dpテーブルをdp[k][i][j]の順に持つだけでも通るらしい。ぐぬぬ。
import sys input = sys.stdin.buffer.readline H, W, K = map(int, input().split()) B = {} for _ in range(K): r, c, v = map(int, input().split()) B[(r, c)] = v dp = [[0]*(W+1) for _ in range(4)] for i in range(1, H+1): for j in range(1, W+1): if (i, j) in B: v = B[(i, j)] dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j]) dp[1][j] = max(dp[1][j-1], dp[0][j]+v) dp[2][j] = max(dp[2][j-1], dp[1][j-1]+v) dp[3][j] = max(dp[3][j-1], dp[2][j-1]+v) else: dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j]) dp[1][j] = dp[1][j-1] dp[2][j] = dp[2][j-1] dp[3][j] = dp[3][j-1] print(max(dp[i][-1] for i in range(4)))
総評
パフォーマンスだけ見れば現状の実力どおりの結果なので仕方なし。
Eはもう少し高速化を粘れば通せていたかもしれない。とはいえDも通せていない状況で定数倍高速化を頑張る気にはなれなかった。
次に向けて実力を付けていきたい。