srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

2017-01-02から1日間の記事一覧

ABC 036 C - 座圧

問題 問題概要 座標を圧縮する問題。 解法 与えられた数字を座圧する問題。ソートした後に、重複を消去し、二分探索で元の数字のindexを調べれば、圧縮後の座標がわかる。 ミス なし。 コード #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef</bits/stdc++.h>…

ABC 035 D - トレジャーハント

問題 問題概要 省略 解法 一つの場所でできるだけ長く滞在すれば良い。できるだけ長く滞在するには、ある頂点iまで最短距離で行き、iからスタート時点まで市短距離で戻ってこればよい。そして残りの時間滞在すれば良いことになる。 求めるものは、0->iまでi-…

ABC 035 C - オセロ

問題 問題概要 オセロの向きを求める。 解法 一つずつやっていたらO(NQ)になるので、lとrの位置だけを記録してそれぞれの場所を何回ひっくり返されたかを記録すれば良い。ひっくり返された回数が、奇数であれば1、偶数であれば0である。区間に一様に1を加算…