vim-plugについてメモ

vimプラグインを書いてみたくなった。そのためのメモ。

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

github.com

追記: Plug の引数は、pathじゃなかったです。

拡張ダイクストラのメモ

拡張ダイクストラ

前回の問題で、拡張ダイクストラを使った。

キューにぶち込む値の組を変えていくってことかな?

普通のダイクストラの場合は、プライオリティキューに現時点での距離を先頭に、頂点をその次にしたリスト(or タプル)を入れる。

これを拡張させたのが拡張ダイクストラでおk?

もっとたくさん解けば身につくかな?

ARC 005 C 器物損壊!高橋君

qiita.com

続き。

atcoder.jp

dijkstraでどうやってやんだよ...って思って、dijkstraの解答を探した。

ferin-tech.hatenablog.com

拡張ダイクストラとは?????????????????????

明日一通り調べよう...

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の'<'は、lexicographical_compare - cpprefjp C++日本語リファレンスのようだ。cpprefに書いてあった。難しいなぁと思った。もうちょい掘り下げて理解したい。

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。スッキリしたぜ。

*1:b-1, c

*2:a-1, c

ABC 035 D トレジャーハント

qiita.com

続き。

atcoder.jp

考えたこと

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 船旅

qiita.com

続きです。

atcoder.jp

これはすげー簡単だった。まぁ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

qiita.com

続きです。

atcoder.jp

ダイクストラな問題みたい。普通にわからんかったが。

editorial.pdfを見て実装してみる。

最後の出力が O(N^{2}) になってここがボトルネックになって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した。 今日は週の始まりですね。今週も頑張りましょう!!!