問題文 https://www.hackerrank.com/contests/101hack50/challenges/boxes-for-toys 問題概要 N個の箱が一列に並んでいて, それぞれ大きさは a_i * b_i * c_i . これらは自由に回転させられる. これらのうちランダムな区間を選び, 含まれる箱のどれでも包含…

問題文 http://codeforces.com/gym/101741/problem/F 問題概要 長さ n の数列のうち、k個を削除して残ったものの GCD の最大値を求めよ. n k a_i 解法 まず, 残すもののうちの１つを乱択で決め打ちする. k が n / 2 以下であるという制約からこれは確率 1/2 …

問題文 https://www.codechef.com/LTIME68A/problems/WNDR 問題概要 N 頂点 M 辺の無向単純グラフ上を K 回移動する. 始点は頂点1. Q個の条件が次のように与えられる. (a_i, b_i) : b_i 回目の移動後に頂点 a_i にいる. このとき, 全ての条件を満たすような…

問題文 https://www.codechef.com/SPCM2019/problems/SPC19F1 問題概要 N が与えられるので、積がN以上となるような非負整数のマルチセットのうち, 和の最小値を求めよ. Nは桁数が 2*10^6 以下の非負整数. 解法 4 = 2 * 2 , 5 当然１もいらなくて (ただしN=1…

問題 https://codeforces.com/contest/1089/problem/K 問題概要 以下のクエリを Q( join t d : 時刻 t に開始して時間 d かかるタスクが予約される (joinでのt は全て異なる) cancel i : i 番目のクエリで追加されたタスクを削除 query t : 現在予約されてい…

区間に(初期値を)代入 普通は区間代入といえば遅延伝搬を使いますが, 遅延なしでも初期値を代入する場合は実は簡単にできます. 方法は, 代入したい区間の各部分木を null に置き換えるだけです. 一応もう少し工夫すると, 区間代入にも一般化できます. 使える…

はじめに ICPC ソウル地区大会に Zerokan_Sunshine というチームで参加してきました. 結果は 12 問中 7 完で 17 位でした. 10 完早解きじゃないと WF にいけないらしくてとてもつらい. 本番の流れ うろ覚えで書いてるのでたまに時系列おかしいかも. (0:00-1:…

問題文 https://www.codechef.com/problems/STRTF 問題概要 長さ N の数列 A がある. f(A) は i 番目の要素が A[i] XOR A[i+1] となる数列とする. Q 個のクエリ (k, x) が与えられるので f^k(A) の x 番目の要素を求めよ. N ≦ 2e5, Q ≦ 2e5, k ≦ 1e9, x ≦ N …

問題文 https://www.codechef.com/problems/IMGOD 問題概要 整数N (1 分割する対象が区別できるものでの N の分割数 S(N, i) mod 163577857 (1 解法 これは第二種スターリング数というものらしい.S(n, k) = (1 / k!) * Σ(-1)^(k - m) * kCm * m^n = Σ ( (-1)…

問題文 https://www.hackerrank.com/contests/university-codesprint-4/challenges/drawing-rectangles 問題概要 グリッド内の n 個の長方形を, 列または行を削除する操作によって最小回数で全て消したい. その最小回数と消すべき列, 行を出力せよ. ただし長…

このブログの小ネタ記事をまとめときます 遅延評価 Segment Tree の一般的な実装方法 - kazuma8128’s blog 遅延セグ木の抽象化と非再帰化の話 傾きの単調性が要らない Convex Hull Trick - kazuma8128’s blog 一般のCHTの話 Mo's Algorithm について - kazum…

昨日の CodeChef の July Lunchtime 2018 に参加したときに思いついたのでメモ.※何も見ずに書いてるからもしかしたら間違いだらけかもしれないので注意です. ゼータ変換 競プロで使うゼータ変換(?)は, 各集合について, その上位または下位集合の和を求めるや…

問題文 http://codeforces.com/contest/375/problem/D 問題概要 頂点に色が付いたサイズ N の根付き木がある. 根は 1. 以下の Q 個のクエリに答えよ. v k : 頂点 v の部分木に k 個以上含まれるような色の種類数を出力 解法 前に解いたときは木上 Mo で unor…

問題文 https://www.codechef.com/problems/FIBTREE 問題概要 サイズNの木がある. 各頂点は値を持っている(初期値0). Q個の以下のクエリをオンラインで処理せよ. クエリ１：頂点 x から頂点 y へのパス上の各頂点に順番に fib(0), fib(1), ... , fib(k) のフ…

HL分解*1でパスクエリができることは知ってたけど同時に部分木クエリも行えることを知ったのでメモ. (もしかして割と常識なのかな？)これ https://codeforces.com/blog/entry/53170 弱い方のHL分解 元々持ってたライブラリでは, 一回 dfs で各部分木のサイズ…

クエリの定義 基本的なテクニック 値の変更なし ver オフラインクエリ rank kth_min オンラインクエリ rank kth_min まとめ 値の変更あり ver X[p] の値を v に変更 rank kth_min その他 値の変更/挿入あり ver クエリの定義 長さ N の整数列 X に対して, 以…

前提 配列（または bitset） Fenwick Tree 平方分割 Trie（動的 Segment Tree） 平衡二分木 おまけ 前提 集合に対して N 個の 追加・削除・k番目に小さい値の取得 のクエリがくるとします. 集合の要素は順序が付けられるものだけ考えます. 要素が非負整数の…

問題文 https://www.codechef.com/problems/ARRQRS 問題概要 数列に対して以下のクエリを処理せよ 末尾に値 Z を追加 前から X 番目の値を削除 前から X 番目の値を Z に変更 区間 [L, R] に含まれる値の中で小さい方から K 番目の値を出力 クエリ数 : 1e5 …

問題文 http://codeforces.com/contest/785/problem/E 問題概要 1, 2, ... , n の列が最初にあって l_i, r_i が Q 個与えられるので毎回 l_i 番目の値と r_i 番目の値をスワップしてから全体の反転数を求めよ AC までの思考過程 Editorial 曰く, 想定解は平…

問題文 https://www.hackerrank.com/challenges/x-and-his-shots/problem 問題概要 一次元上にN個の線分の集合 X とM個の線分の集合 Y がある. 点または線で重なる線分のペア (x, y) (x ∈ X, y ∈ Y) の個数を求めよ. 解法 各 x ∈ X について, Y に含まれる線…

問題文 https://www.hackerrank.com/challenges/cube-summation/problem 問題概要 N x N x N の3次元配列がある. （N 一点更新クエリと, 範囲和クエリがくるので処理せよ. 解法 Nが小さいので 3 次元の Fenwick Tree を書けば終わりです.3次元は流石にライブ…

問題文 https://www.hackerrank.com/challenges/heavy-light-2-white-falcon/problem 問題概要 頂点に値が振られた木に対する以下のクエリを処理せよ. クエリ１：u-v パス上の各頂点の値に x, 2x, 3x, ... の等差数列を足す クエリ２：u-v パス上の各頂点の…

問題 http://codeforces.com/contest/453/problem/D 解法 大体の方針はアダマール変換を使った XOR の畳み込みでできます. あとは mod を p * 2^m (ただ, 今回は mod が 10^9 よりだいぶ大きいので long long でオーバーフローしてしまうため普通に掛け算で…

最近覚えたのでメモ. 理論とか仕組みとかの説明はしません. 高速フーリエ変換(FFT) 添え字和での畳み込み Σ(i + j = k) a_i * b_j = c_k この形で長さ n の列 a, b から長さ 2n の列 c を求めます. ただし n は2の冪乗とします.列 a, b を離散フーリエ変換し…

今回の World CodeSprint 13 で初めて HackerRank の T シャツをゲットできてテンションが上がったので調子に乗って参加記的なのを書いてみました. 問題番号順じゃなくて解いた時系列順に書いてるので注意. 7問目：Dynamic Trees 問題概要：木の辺を繋ぎかえ…

はじめに 非負整数を二分木のトライ木で管理するアレに関する日本語記事があんまり無いっぽいので雑にメモ. （というかそもそも専用の呼び名ないのかな？）とりあえずここでは Binary Trie って呼んどきます. Binary Trie とは 整数をビット列とみなしてトラ…

問題文 https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp18Day3/problems/E 問題概要 日本語なので省略 解法 Euler Tour をとってやると, あとは必要な操作は「区間和」と「区間のブール値反転操作」だけになります.想定解は遅延評価セグメントツ…

はじめに この記事は Mo's Algorithm について整理するための自分用メモです. ポエム Mo's Algorithm とは, 二次元グリッドにおける与えられた点の集合を上下左右方向への移動だけで巡回するときのより効率の良い順番を見つけるためのアルゴリズムといえるの…

問題文 http://codeforces.com/problemset/problem/678/F 問題概要 直線の式の集合 S があります（最初は空集合）. 以下の3種類のクエリを N 個処理せよ 追加 ： 直線の式 f_i(x) = a * x + b を S に追加 削除 ： x 回目のクエリで追加した直線の式を削除 …

問題文 http://www.spoj.com/problems/ZQUERY/ 問題概要 N 個の 1 または -1 の列が与えられて, Q 個の区間に対してそれぞれ値の合計が０になる連続する最長の部分列の長さを求めよ制約：1 ≤ N ≤ 5 * 10^4, 1 ≤ Q ≤ 5 * 10^4 解法 とりあえず累積和をとって…