push後rebaseを試した

バイトしてて、git push後にtypoに気づいて、前のcommitに含めたいと思ったので、試してみた。

Hello.txtに文字列を挿入した状態で、1つのcommitにしたいという状況を想定した。

% touch Hello.txt
% git add Hello.txt && git commit -m 'Hello.txtの作成'
[master 56ae89e] Hello.txtの作成
 1 file changed, 1 insertion(+)
 create mode 100644 Hello.txt
% git push origin master
% echo 'HELLO' >> Hello.txt && git add Hello.txt && git commit -m '文字列の追加'      (git)-[master]
[master 41c7647] 文字列の追加
 1 file changed, 1 insertion(+)
% git rebase -i HEAD~2                                                                (git)-[master]
[detached HEAD 7800150] Hello.txtの作成
 Date: Sun Feb 16 03:17:40 2020 +0900
 1 file changed, 2 insertions(+)
 create mode 100644 Hello.txt
Successfully rebased and updated refs/heads/master.
% git log --graph                                                                     (git)-[master]
* commit 7800150975f4504c1775c1220b2ec58edfb5582b (HEAD -> master)
| Author: b1u3 <bp16071@shibaura-it.ac.jp>
| Date:   Sun Feb 16 03:17:40 2020 +0900
|
|     Hello.txtの作成
|
...
% git push origin master                                                              (git)-[master]
 ! [rejected]        master -> master (non-fast-forward)
error: failed to push some refs to 'https://github.com/b1u3-YumaNoguchi/TestRepository.git'

ここで、リモートのコミットグラフとローカルのコミットグラフに明らかに相違があるため、errorが出ることは予測できる。

ここから、方法として、①git push --forceか②git pullするというパターンが考えられる。

①の場合、push までに別の commit がされていた場合、それらの commit は、なかったことになってしまう。これは、結局、別の commit をした人が pull した際に merge することになる。 ただし、運よく別の commit がなかった場合、いい感じになる。

②の場合、自分が merge することになる。

なるほど。理解。

どっちがいいかわからないが、挙動がどうなるかぐらいは知っていた方がいいと思った。

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]))

単純な最短路問題。前回よりもっとシンプルだった。