"「ある頂点の子孫でない頂点に xを足す」は、 「根の子孫に xを足す」と「ある頂点の子孫に -xを足す」に分けることができるので、 全てのクエリを「ある頂点の子孫に x を足す」の形に帰着することができます。"かしこい。は？となりながら解説の言うとお…

一つでもpath上に黒がある個数を、総数ーpath上がすべて白く塗る個数と置き換えて包除原理を使う。 m 個の path の中から i 個を選ぶ方法は itertools.combinations を使い、1つの path が通る辺の集合を辺１つずつに番号を座圧の要領でつけていき、2進数表…

c を降順ソートすると、c [ i ] を新しく頂点に書き込むとき、スコアが c [ i ] になる回数は高々 i 回で、それまでに一つの辺でスコアを c [ i ] 以上獲得している回数は高々 i - 1 回あるので、求める最大値は sum( c [ 1 : ] ) になります。 そして、その…

c を降順ソートすると、c [ i ] を新しく頂点に書き込むとき、スコアが c [ i ] になる回数は高々 i 回で、それまでに一つの辺でスコアを c [ i ] 以上獲得している回数は高々 i - 1 回あるので、求める最大値は sum( c [ 1 : ] ) になります。 そして、その…

まず、根になる頂点は、Bには含まれておらず、そのような点 a がただ一つ存在することが分かる。 そして、次に Ai = a となっている辺を全て取り除くと、Bに含まれない点 b が新たに1個以上現れる。その点は、a しか親になりえないので b の親は a とわかる…

頂点１を根として、dfs をしていき、それまでの xor 和を defaultdict (D) で管理して、現在のxor和 = X^a を満たす a が今までの xor和に含まれていればいいので、dfs 順に D [ 現在のxor和^X ] を足していけばいい。根からの xor和がちょうど X になるとき…

1,...,n のうちの頂点 i から bfs をはじめて最短何回で全頂点辿れるかを計測しつつ、i から１回で通れる頂点, 最短２回で通れる頂点,,, をリストに入れておく。 答えが -1 にならない条件は i から同じ回数で辿りつける任意の２頂点が辺を持たないことであ…

拡張ダイクストラの簡単な問題ということで、まず解いてみました。通常のダイクストラと何が違うかというと、例えば、頂点が3つなら最小距離を保存するリスト d も d = [float("inf")] * 3 とかで十分でしたが、今回の問題のように、総距離が４の倍数になる…

ダイクストラ法の問題 この問題は道路を片方向にしか通れないので、１からｋまでの最短路とｋから1までの最短路は別に求める必要がある。 import sys input = sys.stdin.readline n,m,t = map(int,input().split()) a = list(map(int,input().split())) a = …

ワーシャルフロイド法で解く問題 街の通り方は順列で全探索した 計算量は最大(200**3 + 8!) くらいで pypy3 で 330ms def warshall_floyd(d): #d[i][j]: iからjへの最短距離 for k in range(n): for i in range(n): for j in range(n): d[i][j] = min(d[i][j…

素直に問題文を言いかえせずに解いたら解けるという変わったパターンだった。 制約が最大５０＊５０なことを重視するべきだった。 辺を一つ減らして毎回 Union-find をして一つの木でなかったら (大きさが N でなかったら）ans += 1 するという方針 n, m = m…

ほかっておいた蟻本の2-5章を進め始めた 蟻本がC+で書かれていても、先人の方々が python のコードをまとめてくださっているので独学でもなんとか耐えている 神サイト 蟻本 初級編 python カテゴリーの記事一覧 - じゅっぴーダイアリー今回はワーシャルフロ…

Union-find木 の練習 Union-find のライブラリーはじゅっぴーさんのをそのまま使わせていただいております。 蟻本 python Union-Find木 競技プログラミング - じゅっぴーダイアリーUnion-find はつなげることしかできないので、入力を逆向き (append でなく …

E が Union-find 木でとけるのでこれもそれでいけるのではと考えたが、辺の重みを更新する挙動をよく理解できていないため出来なかった。 結局いつも通り辺のリストを作成して dfs して解いた。 いつもと違う点は、辺のリストに [u-1,w] という形でいれてお…

https://qiita.com/saba/items/affc94740aff117d2ca9コードはこれを参考にしましたこれもとりあえず辺のリストを作成 ループがあることをどう表現するかがポイント 一周したというのを、「一回見た頂点に戻ってきた」と置き換えると memo = [True]*n で一回…

辺がn-1本あるので、すべての頂点が一つの木を構成しているとわかる。辺のリストを管理するには、 for i in range(n-1): u, v = map(int, input().split()) u -= 1 v -= 1 g[u].append(v) g[v].append(u) としてやればよく、辺を全て全探索するには、 def df…