class ListNode(object): def __init__(self, key, val): self.key = key self.val = val self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.head = ListNode(-1, -1) # 新しいほう self.tail = ListNode(-2,-2) …

最近キョウプロを初めて一か月ぐらいで購入してすぐに投げた蟻本をやり直していて、２部グラフをやったので問題を探して挑戦した。 問題読んだけれども２部グラフどこで使うんだろうってなった。 解説読むとすごい分かりやすかったが、偶数個離れたところに…

Dまでの4完だったが、Dを解くのに時間をかけすぎた。 反省するべき点はあるけれど、実装力と論理的思考力はそこそこの水準になってきていると思っているので、うっかりミスとかを減らしていくことでどこかで飛躍的にパフォをあげられる気もする。また、Dは時…

gRPCとは そもそもRPCとは Remote Procedure Callの略。ここでいうProcedure＝手続きは関数ぐらいの意味合い。 雑にいうと、ローカル環境で実行を命令した関数が、実際は別の環境で行われて処理の結果だけ享受できる感じ。 ローカルで関数を動かしてDB側でク…

以前解いたときは、i番目までのカードの中からｊ枚カードを選択するとして、i番目をj枚目として選ぶときに合計がj*AになるものをDPで数え上げた。が、このやり方だと３次元配列になってややこしいので２次元で何とかしたかった。 prd_xxxさんの解答が行数少…

問題は人のグラフを言語のグラフ（辺？）を使って全員をつなげるか、みたいな感じでUnionFindですべて同じUnionにできるかどうかなどで判断できると考えた。 今回は愚直に人を言語の辺でつないでいった。最初はdequeを使っていたが、dequeを使っても何度も何…

その時最大の値を //2 すればいいよね→とすると計算量がO(NM)で解けなくね？ っとなって死んだ。 毎回最大や最小の値が必要な場合、優先度付きキュー（pythonだとheapq）があるのでこれを使えばいいことが分かっていれば瞬殺できる問題だった。 heapqは子が…

本番では解けなかったので解説見て解いた。優先度付きキューはほとんど触ったことないので発想になかった。別解の方はなるほどわからんなのでそのうち理解したい。 覚えて置きたい所 ・制限の厳しいものから選んでいくと見通しが立ちやすい（今回は残り支払…

勉強してもすぐ忘れるのでグラフ系の実装や流れについて未来の自分向けに。 処理の流れ スタート地点を決める。スタート地点までの移動コストを０とする。 現在のノードi（スタート直後はスタート地点＝ i ）につながっているノードのうち、未探索かつ、最も…

蟻本読んでたら出てきたのでC++からpythonにした。 同じ集合に所属するかどうか（Union-Find！）や、集合を合体するときに使う構造らしい。 練習問題も後日解いてみよう。 class UnionFindTree: def __init__(self, n): #親のノード番号を入れる。初期値はす…