けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

平方分割

Codeforces Yandex.Algorithm 2011 Round 2 D - Powerful array

Mo のアルゴリズムの練習第三弾!!!!! 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内について、各数値 について が何個出現しているかを として表して、 を求め、その総和を求めよ 制約 考えたこと…

SPOJ FREQUENT - Frequent values

Mo のアルゴリズムの練習第二弾。 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内に最も多く登場する値が、何回登場しているかを答えよ 制約 考えたこと Mo の練習第二弾。 最頻値の頻度を求めるのは、…

SPOJ DQUERY - D-query

Mo のアルゴリズムの練習に 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内に何種類の整数があるかを答えよ 制約 考えたこと うしさんの記事の写経。Mo 法を手に入れた!!! ライブラリの使い方として…

AOJ 2370 RabbitWalking (AOJ-ICPC 600 点)

これを解いていたおかげで ARC 099 E - Independence がすぐに思いつけた感はあるかも。むしろ制約的に ARC 099 E の完全上位互換だと言える。 問題へのリンク 問題概要 頂点 辺の無向単純グラフが与えられる。 このグラフが「奇数長のサイクルがない」とい…

AOJ 3045 Painting (ACPC 2018 day2 G)

コンテスト本番、つたじぇーが頑張って通してくれた!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。初期状態では の要素は全て 0 である。加えて、 個の整数のペア()が与えられる。各ペアに対し以下の操作を行い、最終的な数列 を出力せよ。 各 …

技術室奥プログラミングコンテスト #2 E - 歩くNPCたち(Walking NPCs)

えーーーこれが平方分割的解法って天才すぎでは 問題へのリンク 問題概要 人が一直線上を、初期位置 、速度 で等速直線運動を行う。以下の 個のクエリに答えよ: 秒後に座標 から座標 までの間にいる人数を数えよ 制約 考えたこと が 以下と小さいことが大き…

AtCoder AGC 003 D - Anticube (1100 点)

とくらちゃん・シンヤカトー・てんぷらたんたちと気合いで解いた。 問題へのリンク 問題概要 個の正の整数 が与えられる。この中から最大個数の要素を取り出して どの 2 つをとってもその積が立方数とはならない という条件を満たすようにせよ。 制約 解法 …

Codeforces 511 DIV1 A - Enlarge GCD

大昔 osa_k 法と呼ばれていたやつ。 問題へのリンク 問題概要 個の整数 が与えられ、 をこれらの最大公約数とする。 今、 個の整数から何個かを取り除いて、その最大公約数が より大きくなるようにしたい。取り除くべき最小個数を求めよ。ただし、どのように…

CODE THANKS FESTIVAL 2017 H - Union Sets (600 点)

たくさんの方法がとれる超教育的な問題なので、たくさんの方法で解いてみたん。 問題へのリンク 問題概要 の 個の集合がある。 と とを併合する という操作が 回行われた。以下の 個のクエリに答えよ: と が何回目の操作後にはじめて一緒のグループになった…

AtCoder AGC 002 D - Stamp Rally (1000 点)

部分永続 Union-Find 木の練習をした。 問題概要 (AGC 002 D) N 頂点 M 辺の無向グラフがあります。 グラフは連結です。以下の Q 個のクエリに答えよ: 頂点 x, y が与えられ、「x と y を含む z 個の頂点からなる集合に含まれる頂点の番号の最大値」の最小値…

AOJ 2667 Tree

オイラーツアー第4弾!!! でもせっかくなので色んな方法で解いてみたのん!!! Euler ツアー クエリの平方分割 HL 分解 重心分解 (未、todo) 問題へのリンク 問題概要 頂点 0 を根とする頂点数 N の根付き木において以下の Q 個のクエリに答えよ。なお初…

AOJ 2871 ブロッコリー?カリフラワー? (RUPC 2018 day3-E)

オイラーツアー第三弾! RUPC 2018 で見たばかりの問題でもある。 問題へのリンク 問題概要 頂点 1 を根とする頂点数 N の根付き木が与えられる。初期状態で各頂点に G または W の属性が割り振られている。以下の Q 個のクエリに答えよ: v: 頂点 v を根とす…