区間dp の問題。区間dp とは、dp[ i ][ i+j ] = list[ i : i+j ] での最大(最小)値として、最大値の遷移を考えるもの。 今回は、dp[ i ][ j ] = ケーキが i+1 番から i+j+1 番まで残っているときの JOI 君の取り分の最大値 として問題を解く。 ケーキが円状…

bit dp の問題。dp[ i ][ k ] = (a,b) として、今まで通った頂点を表す bit i と今いる頂点 k が入りその時の最小値 a と最小値をとりうる通り方の総数 b が保管されている。 k から次の頂点 j に行けるのは i の j の位が０であるときで、 かつ、dp[ i ][ k…

二分探索の問題。二分探索はここのサイトがとても参考になった。 めぐる式二分探索 コピペで使えるPython実装 - 学習する天然ニューラルネット 答えを arg と仮定した場合にそれが条件をみたすなら、arg+1についてもまた調べる、満たさないなら、arg//2 につ…

B - Buildings are Colorful! 制約が小さいのでビルの選び方を n-1Ck-1 通り全探索して間に合う 選んでないビルもビルの最大値に関わることがあることに注意 n,k = [int(i) for i in input().split()] a = [int(i) for i in input().split()] if k == 1: pri…

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となってほしい） そこで通…

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…