kazuma8128’s blog

競プロの面白い問題を解きます

HackerRank Boxes for Toys

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

2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest F. GCD

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

CodeChef January Lunchtime 2019 Wanderer

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

CodeChef SPC19F1 Lockied Away

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

2018-2019 ICPC, NEERC, Northern Eurasia Finals K King Kog's Reception

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

動的な Segment Tree のテクニック

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

ICPC Seoul Regional 2018 参加記

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

CodeChef Strange Transform

問題文 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 …

CodeChef IMGOD Apun Hi Bhagwan Hai !

問題文 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)…

HackerRank Drawing Rectangles

問題文 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 に参加したときに思いついたのでメモ.※何も見ずに書いてるからもしかしたら間違いだらけかもしれないので注意です. ゼータ変換 競プロで使うゼータ変換(?)は, 各集合について, その上位または下位集合の和を求めるや…

Codeforces Round #221 Div.1 D Tree and Queries

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

CodeChef FIBTREE Fibonacci Numbers on Tree

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

HL分解で部分木クエリ

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

ICPC2018 国内予選参加記

suibaka が書いてたしいいかなとは思ったけど, 一回書いてみたかったので書きます. suibaka の参加記 概要 今年はチーム Zerokan_Sunshine として参加しました. 結果は A-F の6完で全体6位でした. めっちゃ良かった. メンバー紹介 suibaka : 実装力の化身. …

区間内の x 未満の値の個数, 区間内の k 番目に小さい値

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

k 番目に小さい値を取得可能な集合を管理するデータ構造

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

CodeChef ARRQRS Logan and his ARRAY Queries

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

Codeforces Round #404 E Anton and Permutation

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

HackerRank Mr. X and His Shots

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

HackerRank Cube Summation

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

HackerRank Heavy Light 2 White Falcon

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

巨大modでの掛け算の高速化 (Codeforces Round #259 D Little Pony and Elements of Harmony)

問題 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 を離散フーリエ変換し…

HackerRank World CodeSprint 13 参加記

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

非負整数値を扱う Trie について

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

RUPC2018 Day3 E Broccoli or Cauliflower

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

Mo's Algorithm について

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

Educational Codeforces Round 13 F Lena and Queries

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