問題ページ D - AtCoder Express 2 解法 区間がたくさん与えられるときはとりあえず終点でソートする。あるクエリ(p[i],q[i])が与えられるとき、数える対象となる路線はr[j]<=q[i]であるような路線のみである。したがって終点ソートしておき尺取法の要領で対…

問題ページ Problem - E - Codeforces 考えたこと k進数の下一桁はkで割った余りに等しい a[i] mod k を取っておいてよさそう dp[i番目][金額]=(bool)とかしたいけど10^10なので無理 a[i]がkと互いに素なら0～k-1まで全て取りうる a[i]がkと互いに素でない場…

問題ページ Problem - D - Codeforces 考えたこと p[i]を把握しないといけない y=INFを出力しようと思ったけどだめなのでy=1を出力して確認する p[i]さえわかれば二分探索すればよい m<=10^9ならクエリ回数30回あれば足りる 二分探索を実装して出すと通る y=…

問題ページ Problem - C - Codeforces 考えたこと 燃料xを積んだときに旅行を達成できるか?を考えると単調性がある 判定O(N)でできそうなのでにぶたんできそう 燃料を10^9までしか使わないことが保証されている -1の判定はこれを使えばできそう 不等号に=を…

問題ページ C - Cheating Nim 考えたこと Nimの勝利条件から問題文を言い換えたい 不正者が勝てるのは a[0] xor a[1] xor … xor a[n-1]=0 のときだけ 山の石の数を-1する操作で上の条件を達成する問題になった xorなのでビットごとにみたくなるので2進数の形…

問題ページ No.235 めぐるはめぐる (5) - yukicoder 解法 HL分解の練習として解いた。クエリ0は街Xから街Yに対してC[i]*Zを加算するクエリ、クエリ1は街Xから街Yの値の和を求めるクエリになる。区間に対しての加算と区間和を求めるものなので遅延セグメント…

問題ページ H - 白黒ツリー 解法 頂点に関する制約条件を扱うのは大変なので辺のコストの条件に置き換える。両端の頂点の色が違う辺のコストは0、両端の頂点の色が同じ辺のコストは1とする。こうするとクエリ2について頂点uとvの2頂点間の距離が0かどうかの…