vim-plugについてメモ
vim-plug は、現代の Vim plugin manager の 1 つ。
vim-plug のインストール
vim-plug は、1 つの vimscript で配布されているらしい。やることは、/.vim/autoload/
にスクリプトファイルを入れるだけ。
これで入る。
curl -fLo ~/.vim/autoload/plug.vim --create-dirs \ https://raw.githubusercontent.com/junegunn/vim-plug/master/plug.vim
vim-plug のプラグインのインストール
プラグインをインストールするには、.vimrc に Plug の宣言文を入れる。
call plug#begin('path/to/plugindir/') Plug 'repository/vim-plug_plugin.vim' call plug#end()
そして、:PlugInstall
を実行する
vim-plug のプラグインのアンインストール
.vimrc の Plug 宣言を抜いた上で、:PlugClean
する。
vim-plug のプラグインのアップデート
:PlugUpdate
をすると、アップデートされる。詳細は、:PlugDiff
追記: Plug の引数は、pathじゃなかったです。
ARC 005 C 器物損壊!高橋君
続き。
dijkstraでどうやってやんだよ...って思って、dijkstraの解答を探した。
拡張ダイクストラとは?????????????????????
明日一通り調べよう...
H, W = map(int, input().split()) field = [] start = () goal = () for i in range(H): line = list(input()) for j, c in enumerate(line): if c == 's': start = (i, j) line[j] = '.' elif c == 'g': goal = (i, j) line[j] = '.' field.append(line) import queue push = queue.heappush pop = queue.heappop INF = 10**9 DYDX = [(0, 1), (1, 0), (0, -1), (-1, 0)] def dijkstra(s): q = [] # リストをぶち込むキュー d = [[[INF for k in range(3)] for j in range(W)] for i in range(H)] for i in range(H): for j in range(W): for k in range(3): d[i][j][k] = INF d[s[0]][s[1]][2] = 0 q.append((0, s[0], s[1], 2)) while q: tmp = pop(q) y = tmp[1]; x = tmp[2]; num = tmp[3] # ゴールだった if y == goal[0] and x == goal[1]: break for dy, dx in DYDX: ny = y + dy; nx = x + dx if 0 <= ny < H and 0 <= nx < W: if field[ny][nx] == '.' and d[ny][nx][num] > d[y][x][num] + 1: d[ny][nx][num] = d[y][x][num]+1 push(q, (d[ny][nx][num], ny, nx, num)) if field[ny][nx] == '#' and num >= 1 and d[ny][nx][num-1] > d[y][x][num]+1: d[ny][nx][num-1] = d[y][x][num] + 1 push(q, (d[ny][nx][num-1], ny, nx, num-1)) return d d = dijkstra(start) for i in range(3): if d[goal[0]][goal[1]][i] != INF: print('YES') break else: print('NO')
いくつかのテストケースでTLEになった。書き方がちょっと悪いかもな。C++ のvector
ABC 035 D トレジャーハント(2)
昨日の続きです。
昨日は、考えでは、ダメなことがわかったので、解答を見た。考えは、だいぶ似ていた。
ただし、最短経路上の単位獲得金額がでかい都市を探す必要がなかった。すべての都市を往復することで、経路上の単位獲得金額がでかい都市を特定することができるので、大丈夫みたいだ。
都市の往復をするには、辺を逆に貼ることで、帰りの移動時間を計算できる。
以下、解答。
```python
from collections import defaultdict
import queue
push = queue.heappush
pop = queue.heappop
INF = 10**20
G1 = defaultdict(list)
# 逆方向
G2 = defaultdict(list)
N, M, T = map(int, input().split())
A = list(map(int, input().split()))
for i in range(M):
a, b, c = map(int, input().split())
G1[a-1].append*1
G2[b-1].append*2
def dijkstra(s, G):
q = []
d = [INF] * N
p = [-1] * N
d[s] = 0
push(q, (0, s))
while q:
cost, v = pop(q)
# 既に q から取り出したものの方が低い
if d[v] < cost:
continue
for to, tmpcost in G[v]:
if d[to] > d[v] + tmpcost:
d[to] = d[v] + tmpcost
push(q, (d[to], to))
return d
# 行き
d1 = dijkstra(0, G1)
# 帰り
d2 = dijkstra(0, G2)
ans = -1
for i in range(N):
ans = max(ans, (T-(d1[i]+d2[i]))*A[i])
print(ans)
```
AC。スッキリしたぜ。
ABC 035 D トレジャーハント
続き。
考えたこと
1 に戻ってくる最短経路をTから引いて、経路内で最も単位あたりの獲得金額が高い頂点を探して、そこで最大限いたことにするというものを実装してみた。結果的にダメだった。8割くらいACしたけど、残り2割がダメだった。
一応経過ということで、明日解答を追加する。
from collections import defaultdict import queue push = queue.heappush pop = queue.heappop INF = 10**7 G = defaultdict(list) N, M, T = map(int, input().split()) A = list(map(int, input().split())) check = dict() for i in range(M): a, b, c = map(int, input().split()) # 有向グラフ G[a-1].append((b-1, c)) if b == 1: check[a-1] = c def dijkstra(s): q = [] d = [INF] * N p = [-1] * N d[s] = 0 push(q, (0, s)) while q: cost, v = pop(q) # 既に q から取り出したものの方が低い if d[v] < cost: continue for to, tmpcost in G[v]: if d[to] > d[v] + tmpcost: d[to] = d[v] + tmpcost p[to] = v push(q, (d[to], to)) return (d, p) def get_path(t, p): path = [] while t != -1: path.append(t) t = p[t] return path rd, rp = dijkstra(0) ans = -1 for c in check.keys(): rd[c] += check[c] path = get_path(c, rp) maxv = -1 for pp in path: maxv = max(maxv, A[pp]) ans = max(ans, (T-rd[c])*maxv) print(max(ans, T*A[0]))
JOI 2007 予選 F 船旅
続きです。
これはすげー簡単だった。まぁ100点問題だしね。
コピペで瞬殺!!!
import queue push = queue.heappush pop = queue.heappop INF = 10**16 def dijkstra(s, G, d): q = [] d[s] = 0 push(q, (0, s)) while q: cost, v = pop(q) # print(f'd[{v}] = {cost}') # 既に q から取り出したものの方が低い if d[v] < cost: continue for to, tmpcost in G[v]: if d[to] > d[v] + tmpcost: d[to] = d[v] + tmpcost push(q, (d[to], to)) from collections import defaultdict G = defaultdict(list) N, K = map(int, input().split()) d = [INF]*N for i in range(K): line = list(map(int, input().split())) if line[0] == 0: dijkstra(line[1]-1, G, d) if d[line[2]-1] == INF: print(-1) else: print(d[line[2]-1]) d = [INF]*N else: G[line[1]-1].append((line[2]-1, line[3])) G[line[2]-1].append((line[1]-1, line[3]))
単純な最短路問題。前回よりもっとシンプルだった。
SoundHound 2018 予選 D - Saving Snuuk
続きです。
ダイクストラな問題みたい。普通にわからんかったが。
editorial.pdfを見て実装してみる。
最後の出力が になってここがボトルネックになってTLEになっている。editorialにもここの処理書いてないやん。適当に検索したら、逆からやれば良いらしい。つよい。
""" 「sからiに円による支払いで移動する際の最小の金額」円と、「iからtにスヌークによる支払いで移動する際の最小金額」スヌークになる。これを最小化すれば良い。 """ from collections import defaultdict G1 = defaultdict(list); G2 = defaultdict(list) N, M, S, T = map(int, input().split()) S-=1; T-=1 for i in range(M): f, t , v1, v2 = map(int, input().split()) G1[f-1].append((t-1, v1)) G1[t-1].append((f-1, v1)) G2[f-1].append((t-1, v2)) G2[t-1].append((f-1, v2)) import queue push = queue.heappush pop = queue.heappop INF = 10**16 d1 = [INF]*N; d2 = [INF]*N def dijkstra(s, G, d): q = [] d[s] = 0 push(q, (0, s)) while q: cost, v = pop(q) # print(f'd[{v}] = {cost}') # 既に q から取り出したものの方が低い if d[v] < cost: continue for to, tmpcost in G[v]: if d[to] > d[v] + tmpcost: d[to] = d[v] + tmpcost push(q, (d[to], to)) dijkstra(S, G1, d1) dijkstra(T, G2, d2) """ for i in range(N): ans = 0 for j in range(i, N): ans = max(ans, 10**15-d1[j]-d2[j]) print(ans) """ anses = [0]*N ans = 10**15 for i in range(N): ans = min(ans, d1[N-1-i]+d2[N-1-i]) anses[N-1-i]=10**15-ans for i in range(N): print(anses[i])
すげ〜。今日もACした。 今日は週の始まりですね。今週も頑張りましょう!!!