atcoder.jp与えられた’１’のマスを移動できる最大値を求める問題。 普通の bfs だと例えば 1 1 0 1 1 0 1 0 0 が与えられたときに a[1][1]をスタートとしても 3 2 0 2 1 0 3 0 0 のような移動距離を返してくる（本当は a[2][0] = 5となってほしい） そこで通…

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

解説AC。文字列の偶数番目と奇数番目で条件をかえながら dp を作った。 文字列の長さが奇数のときは、2つ飛ばしを2回まで、または3つ飛ばしを一回まで使うことができる。 よって dp[i][[j] を i = i 番目の数字、 i が偶数なら j = 0（もう一つ飛ばししかで…

一組ずつ条件に照らし合わせると当然TLEする Rがa個、Bがb個、Gがｃ個あるとすると、最大a*b*c個ある。 そこから条件２に当てはらないものを引いていくという方針。 条件２ではじかれるものは s[i] != s[i+m+1] and s[i+m] != s[i+2*m+2] and s[i+2*m+2] != …

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

atcoder.jp要約すると Σ|Ai-b| (0≤i≤n) を最小にするbがわかるかどうかという問題。 ネタバレすると Ai (0≤i≤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…