push後rebaseを試した

git

バイトしてて、git push後にtypoに気づいて、前のcommitに含めたいと思ったので、試してみた。 Hello.txtに文字列を挿入した状態で、1つのcommitにしたいという状況を想定した。 % touch Hello.txt % git add Hello.txt && git commit -m 'Hello.txtの作成' …

vim-plugについてメモ

vim

vimのプラグインを書いてみたくなった。そのためのメモ。 vim-plug は、現代の Vim plugin manager の 1 つ。 vim-plug のインストール vim-plug は、1 つの vimscript で配布されているらしい。やることは、/.vim/autoload/にスクリプトファイルを入れるだ…

拡張ダイクストラのメモ

拡張ダイクストラ前回の問題で、拡張ダイクストラを使った。キューにぶち込む値の組を変えていくってことかな?普通のダイクストラの場合は、プライオリティキューに現時点での距離を先頭に、頂点をその次にしたリスト(or タプル)を入れる。これを拡張させた…

ARC 005 C 器物損壊!高橋君

qiita.com 続き。 atcoder.jp dijkstraでどうやってやんだよ...って思って、dijkstraの解答を探した。 ferin-tech.hatenablog.com 拡張ダイクストラとは????????????????????? 明日一通り調べよう... H, W = map(int, input().split())…

ABC 035 D トレジャーハント(2)

昨日の続きです。昨日は、考えでは、ダメなことがわかったので、解答を見た。考えは、だいぶ似ていた。ただし、最短経路上の単位獲得金額がでかい都市を探す必要がなかった。すべての都市を往復することで、経路上の単位獲得金額がでかい都市を特定すること…

ABC 035 D トレジャーハント

qiita.com 続き。 atcoder.jp 考えたこと 1 に戻ってくる最短経路をTから引いて、経路内で最も単位あたりの獲得金額が高い頂点を探して、そこで最大限いたことにするというものを実装してみた。結果的にダメだった。8割くらいACしたけど、残り2割がダメだっ…

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 = …

SoundHound 2018 予選 D - Saving Snuuk

qiita.com 続きです。 atcoder.jp ダイクストラな問題みたい。普通にわからんかったが。 editorial.pdfを見て実装してみる。 最後の出力が になってここがボトルネックになってTLEになっている。editorialにもここの処理書いてないやん。適当に検索したら、…

単一始点最短路探索アルゴリズム(1)

こんにちは、えぬわいです(普通) ダイクストラ法の復習です。 import queue push = queue.heappush pop = queue.heappop INF = 10000 from collections import defaultdict G = defaultdict(list) N, M, S, GOAL = map(int, input().split()) V = N d = [] f…

ARC 041 D 辺彩色(2)

自分の中で、けものみちが熱いです。 qiita.com 続き。 atcoder.jp 難しいなぁと思いながら、解説は理解できたが、実装がわかんなかったので、実装例を見てみた。 kmjp.hatenablog.jp お世話になってる kmjp さん!!!かっけー pythonで書き直し。 from sys…

閉路探索

前回の記事で、解説みると、奇数長の閉路を探索する必要があることがわかった。 閉路の検出ってどうやるんだっけなぁって思って調べた。 inzkyk.github.io わかりやすい。擬似コードも載ってる。確認する。 from collections import defaultdict G = default…

ARC 041 D 辺彩色(1)

qiita.com 続きをやっている。 atcoder.jp 普通にわかんなかったが?(半ギレ) 解答見る。 考察で、逆順に辿ると、上書きする機能がなくなる←天才か? 始点と最初の色で全探索。それプラス、奇数サイクルのことを考えるものらしい。 辺彩色のコードわからんと…

Nuxtでデータフェッチする

vue

Nuxtで自前でapiサーバー建てつつ、コンポーネントのasyncDataでデータをフェッチするっていうのがやりたかった。 はじめに、プロジェクトディレクトリ直下に、apiというディレクトリを用意して、json用のルーティングを用意する。 // project/api/index.js …

Maximum-Cup 2018 C 嘘つきな天使たち

最近努力が足りていないえぬわいです。 qiita.com 続きです。 atcoder.jp 2 部グラフで解けた。塗った時の数を記録していけば、おk。連結であることが保証されていないので、その点は気をつけた。自分で考えてACできるとちょーきもちー。 from collections i…

CODE FESTIVAL 2017 qualB C 3 Steps

俺ガイルとゲーマーズの最終巻が読めていないえぬわいです。今週は、全然解けてないですね〜。もっと解かないとな〜。 qiita.com 続きです。 atcoder.jp ワカンねぇな〜って思って、解説見たら問題の解釈が間違っていたみたい。 思い出した2部グラフの特徴と…

AtCoder ABC 126 D - Even Relation

ぼくがかんがえたさいきょうの生活習慣を送っているえぬわいです。3 日だけですけど。これから続けていくんだという気持ち。 qiita.com 続きです。 atcoder.jp ARC 036 D 偶数メートルのとっかかりの部分みたいな感じでした。たまたま偶数メートルの解説を読…

2部グラフ判定

アニマエールのOP・EDを聞いたら、見返す機運が高まってるえぬわいです。 今日は、蟻本に載ってる2部グラフ判定を自分で実装して理解しました。 ポイントとしては、 とりあえず、塗っていって判定する 塗ってる最中でダメだと思ったら打ち切る 色は、符号を…

ABC 087 D People on a Line

ストライク・ザ・ブラッドで好きなキャラクターは藍羽浅葱。えぬわいです。 qiita.com 続き。 atcoder.jp 重み付きUnionFind木というのがあるらしい... ノード間の重みを保存しつつ、縮約していくアルゴリズムらしい。 qiita.com けんちょんさんの記事を参考…

ARC 036 D 偶数メートル

qiita.com 続き。 atcoder.jp ARC D だけあって解答の読み応えがちげぇぜ(解答見た) UnionFindを使うと、状態管理をすることができる例。 UnionFindで N 個の頂点間を偶数距離で移動できるかの判定に使っている。解答みておったまげた。 class UnionFind(): …

ARC 097 D Equals

ポスター発表が終わりました。えぬわいです。 qiita.com 続きです。 atcoder.jp 概要 1 から N までの数列をシャッフルする。ある数字の組みが与えられるので、その組みの位置をスワップして、最大何個まで元の位置に戻せるかという問題。 考えたこと 組みと…

ABC 049 D 連結

qiita.com 続きです。 atcoder.jp 考察まとめです。 Union-Find木を使って解いてみる。まずTLEになったやつ。 class UnionFind(): def __init__(self, n=None): if type(n) == int: self.par = [i for i in range(n)] self.rank = [0 for i in range(n)] els…

ATC 001 B Union Find

人間は愚か。えぬわいです。 qiita.com atcoder.jp Union-find木の講座用の問題らしい。 Union-Find木とは グループの併合と判定ができるアルゴリズム 併合するのは、グループ同士、判定できるのは、ノード。つまり、グループは木で表される。 初期化 はじめ…

ABC 085 B Kagami MochiとABC 091 B Two Colors Card Game

setとmapを使う問題。 c++で set と map を使ったことがなかったので、調べてやってみる。 #include <cstdio> #include <set> using namespace std; // auto は型推論 int D[100], N; int main() { scanf("%d", &N); set<int> st; int d; for (int i = 0; i < N; i++) { scanf(</int></set></cstdio>…

DPのメモ

個人的なDPのメモ。 DPでだいたい最後にdp[0][K]みたいな感じで、0 添字で参照してるので、これをdp[N][K]みたいに書けるようする。というのが目的。 単純なナップザックの問題だと、dpテーブルの添字が何を表しているのか、読み取りづらい。結果的に、漸化…

aximum-Cup 2018 D Many Go Round(3)

結局こんな感じのDPを書いた。 INF = 10**9+7 def rec(pos, j): if pos == N: if j == L: return 0 return INF # pos 番目を使わない ans = rec(pos+1, j) ans = min(ans, rec(pos+1, (j+a[pos])%M)+(j+a[pos])//M) return ans ans = rec(0, 0) print(ans) p…

Maximum-Cup 2018 D Many Go Round(2)

前回の続き 解答通りに、dp[i][j] := i番目までの燃料タンクを使って番号jの休憩所に止まるための周回の最小回数で再帰関数を作ってみる。 INF = 10**9+7 def rec(pos, j): if pos == -1: if j == L: return 0 return INF # pos 番目を使わない ans = rec(po…

Maximum-Cup 2018 D Many Go Round(1)

ひとりぼっちの〇〇生活のカコちゃんがぼっちーの友達になりましたね。えぬわいです。 qiita.com 続き。 atcoder.jp 難しくなってきたなぁという気持ち。 1 日でなんとかするのは、きつい時期なのかなと。 DPを書く前に普通に再帰関数だけ書いてみてみる。 N…

ARC 057 B 高橋君ゲーム

おはやー!(天下ハナビ)。えぬわいです。 qiita.com 続きです。 atcoder.jp とりあえず、問題通り、再帰関数を書いてみる。 書いてみる。(ここでバグ見つけて無限に時間かかった) とりあえず、今日は、DPにできそうな再帰関数。 N, K = map(int, input().s…

nuxtプロジェクトをherokuへデプロイする

vue

プロジェクトを作成する。 % npx create-nuxt-app <project-name> herokuにアクセスして、アプリを作成する。 dashboard.heroku.com heroku CLI で、ログインする。 % heroku login ログインしたら、gitにリモートリポジトリを追加する。 % heroku git:remote -a <herokuで作ったアプリの名前> % git re</herokuで作ったアプリの名前></project-name>…

飽きた

これは、報告兼けじめです。 重大な報告だと思った? 残念!!!重大じゃないです。 この前取り組んでた ABC 032 D ナップサック問題 これですけど、飽きたので、飛ばします。 以上、報告です。 バグ取りで、無理やなと感じたので、供養。南無。 #include <cstdio> #</cstdio>…