CF #483

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数みたら大間違いでした。かなしいね