■A - 中央値
やるだけ
■B - 電卓
printf("%.2f\n", ans);でWA
仕方ないので100倍
■C - 隣接カウント
const int dx = { -1,0,1,0,1,-1,1,-1,0 };
const int dy = { 0,-1,0,1,1,-1,-1,1,0 };
としておくと楽
■D - 分身
両端から絶対に必要な分を決めて、
それ以外の幅を塗りつぶせるように調整
■E - アナグラム
next_permutation
■F - 構文解析
mapにいれてpairに持ち替えてsortして前後比較
■G - 村整備
壁の数だけBFS
■H - マス目のカット
二次元DPとか考えてみるけど
O(N*M*min(N, M)^3)が余裕で間に合うので愚直
■I - ピザ
尺取法
X>Yにして問題ないので
食べれるところまで食べる！
■J - ワープ
ワープは一回使ったら使用禁止としてbfsする
■K - 転倒数
それぞれの組に対して転倒数とどの数が何個持っているかを保持しておけばいい
1000000000で割ったあまりであることを忘れずに
■L - マンションの改築
遅延セグ木２本生やしてやるだけ。と思ったらガッツリTLE
共通で変化する差分と、単独で変化する差分を別に扱うといい
■M - 筆塗り
lca+unionfind
後ろのクエリから処理していく。
lacとuがsameになるまで登っていく
uのnextとlcaがsameなら何もせずに次に
そうじゃないならマージして次に
マージするついでにAnsをメモる
■N - マス目の穴埋め
dp
i行目とi+1行目の状態数2^12通りを持っておいて
その下にi+2をi+1行目と矛盾を発生させずに置けるかどうか。
■O - 宝箱
ダイクストラ
鍵屋を追加して辺を作成、遡るコスト０の辺の作成
どこかで類題を見た記憶
