ずっとほったらかしていた問題。 dfs で全探索するのだけど、愚直に計算すると間に合わない。 • 中途半端に解く配点は 1 種類以下であり、それ以外の配点は完全に解くかまったく解かない。 • 中途半端に解く配点があるなら、それは完全に解く配点以外の配点…

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 : ] ) になります。 そして、その…

dp の巻き戻しするやつ。dfs をして頂点を探索する際に、stack (deque) に次の頂点を入れる前に、dp を変更する前の要素を入れておくことで、dfs順に頂点を探索するときに、行き止まりについてから、一つ前の頂点に戻る時にその時点での dp を再現することが…

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

0完。カス。これが最後のレートつくAGCだったと思うとまあ残り５分で迷いながらもBを提出したのは良かったかも知れない。レート変動ないものを頑張る意味はないのでAGCは今後出ないでしょう。 今日学んだこと。 math.ceil は 15 桁以上の数字は勝手に丸める…

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…