シコウノストレージ

自分自身の考えを整理するために書いています。

精進記録

典型26

木の問題。

隣り合ってない頂点を探索するためにDFSを行い、各階層ごとにbool値を反転させて隣り合わないグループに分ける。

最初そのまま提出したがそれだとn/2よりも数が少ない可能性があるため、WA。

それを直してAC。

 

典型28

問題見ても太刀打ちできないと感じ解説へ。

2次元のimos法を使うらしい。

imos法が分からないので調べたまとめ。

ようは累積和で、2次元の場合inの場所とoutの場所を2つずつとり、縦と横で累積和をとることによって、この問題だと1×1㎡のマスのタイルに対して何枚重なっているかが分かるので掛け算などをせずに重なった各枚数ごとの面積を求めることができる。

 

abc211d

dfsで最短路を求めて、もう一度dfsで求めた最短路で行ける道のうちn頂点に行けるものの個数を計算するという方針を立てて提出したがTLE。

解説を見るとどうやらDPで求めるらしい。