■A - Blood Pressure
ans = (a - b) / 3.0 + b;
■B - Cycle Hit
setに突っ込んでsetのsizeが4かどうか
■C - chokudai
典型90にあったらしい。
単純dp
■D - Number of Shortest paths
通常のbfsと比べ、queにpushしないときにも処理が必要
■E - Red Polyomino
サンプルが状態数の最大値を保証してくれている
setに状態をbitにして詰め込む
vector<set<long long>st(k+1)とでもして
set[i]からset[i+1]に遷移するには
全てのset[i]の状態に対して、まだ白いマスを選択しその周囲のマスが一つでも赤ければ遷移させる。
■F - Rectilinear Polygons
セグ木。
基本的な考えは二次元累積和
二次元累積和は普段長方形ばかり考えているが、多角形での場合も同様にできる。
右下からぐるぐる周りながら+1,-1すればいい。
これをセグ木に載せて更新する。
直接区間更新ができるように、遅延セグ木でやってもいいが
累積和の形で持てば通常セグ木でも十分。
入力の多角形が全て開始が右下固定とかでもなんでもないので
地味に面倒。
