A
素因数系?1018なのでgcd/lcmでなんかやるタイプだろう
条件は?
→とりあえずp, qは既約にする
→gcd/lcm系なので素因数ベクトルで考える
→まずb=10の場合は?
→どうやらqが2x * 5yならば可能
→さすがにqの素因数のなかでbに含まれないものがあったら不可能だろう
→これの逆(bに含まれないものがなかったら可能)は言える,多分必要十分
整理する
→p, qを既約にする
→qの素因数のなかでbに含まれないものがあるか判定
これをgcd / lcmで実現可能か?
→p /= gcd(p, q)をたくさんやれば共通素因数が全部除去できるので,可能
→Pretest Passed?
→TLE
→小手先改善,はたして
B
fの性質は?
→CSAで最近見た,経路数 mod 2に帰着できるのでリュカの定理
これのmax?一体全体
→…
N = 5000とは?O(N polylog)ではなくO(N2)ということ?
→経路数,O(N2)と来たらどう考えてもDP[x][y] = DP[x-1][y] + DP[x][y-1]が怪しい
→あーこの形でDPがうまくいくんですね
→Pretest Passed
C
問題文が長い,パス
D
かなり実家を感じる
えー長方形を塗って上書きしていく
→長方形iは長方形i+1, i+2, ...の影響を受ける
→後ろのやつらの影響を受けるが前のやつらの影響は受けない,じゃあ逆から考えれば良い性質?
整理する
→以下のクエリを処理せよ
→長方形を塗る
→長方形のなかで,まだ塗られていない場所はあるか?
→これRUPCで見た
→…
→これRUPCでは解けなかった
思考を変える,クエリが全部オフラインで二次元平面なので,平面走査もアプローチとして有力だろう
平面走査をするとどういうクエリになる?
→二次元平面に横線を足す
→二次元平面に横線を抜く
→二次元平面を上から見たときに見れる横線の一覧は?
3つめのクエリが絶望的,本当にこれを処理するの?
→よく考えると各横線について一瞬でもわかるかがわかればいい
→じゃあ1個取得にして取得O(polylog)でならしO(N polylog)のタイプに違いない
3つめのクエリは変更可能
→二次元平面を上から見たときに見れる横線のうち,今まで見れていない奴は1個でもあるか?
とりあえずここまでくれば可能か?
→データ構造なので,とりあえず平方分割で可能か考える
→可能そう
→じゃあSegTreeは?
→多分可能
→実装
→バグって大変でした…(ストレステストまで書いた)
→Pretest Passed,はたして?
→Pretest Passed数みたら大間違いでした。かなしいね