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

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

平方分割

AtCoder ABC 193 C - Unexpressed (灰色, 300 点)

むずかしかった!!! でも、約数列挙でありがちな「 まで試せば良い」という考え方がちゃんと理解できているかを問う良問だった!! 問題へのリンク 問題概要 整数 が与えられる。 1 以上 以下の整数のうち、 2 以上の整数 を用いて と表せないものはいくつ…

JOI 春合宿 2007 day1-2 Factorial (難易度 5)

素因数分解ゲー! 今なら ABC D あたりに出てきそう ジャッジページ 問題文 問題概要 正の整数 が与えられる。 が の倍数となるような最小の正の整数 を求めよ。 制約 解法 (1):素因数分解 まず を素因数分解しよう。 とする。さらに、 をそれぞれ素因数分…

Codeforces Round #683 (Div. 1) D2. Frequency Problem (R3000)

平方分割で解法を分岐する系の問題で、そのうちの片方の問題は Easy Version として D1 で出題されてた (Easy Version は R2600) 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のみからなる 要素の数列 が与えられる。 数列の連続する区…

AtCoder AGC 049 D - Convex Sequence (橙色, 1000 点)

最初は二次元 FFT が必要な気分になっていて右往左往していた。個数制限なしナップサック問題になるのは面白かった! 問題へのリンク 問題概要 正の整数 が与えられる。長さ の非負整数列 であって という条件を満たすものの個数を、1000000007 で割ったあま…

AOJ 2863 Separate String (JAG 模擬地区 2017 H) (500 点)

めちゃくちゃ面白かったし勉強になった! 問題へのリンク editorial 問題概要 文字列 が与えられる。それとは別に 個の文字列 が与えられる。 文字列 をいくつかの連続する区間に分割する方法であって、各区間をなす部分文字列が のいずれかに一致するような…

AOJ 3170 Freqs (HUPC 2020 day1-G)

難しかったー!!平方分割かな...とまでは思ったので、もっと粘り強く考えられるようにならないと...! 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の 4 種類のクエリを 回処理してください。 クエリ 1: が与えられるので、 () を に更新する…

Educational Codeforces 80 E. Messenger Simulator (R2100)

面白かった。 数列の区間に含まれる値の種類数を答えるクエリに素早く答える技術が必要になった。 問題へのリンク 問題概要 がこの順に並んでいる。ここから 回の操作を行う。 回目の走査は、 以上 以下の値 で表され 現在の順列のうち、値 を先頭にもってく…

AtCoder ABC 132 F - Small Products (黄色, 600 点)

こういう風にルートが出てくるの、こどふぉだとよく見るね。 ありがちなのが、長さ の線分を整数長ごとに分割するとき、分割の中に登場する長さの種類は 通りしかないとか、そういう形でよく出てくる。 問題へのリンク 問題概要 整数 が与えれる。 長さ の正…

Codeforces Yandex.Algorithm 2011 Round 2 D - Powerful array (R2200)

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

SPOJ FREQUENT - Frequent values

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

SPOJ DQUERY - D-query

種類数クエリをマスターするぞ! 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内に何種類の整数があるかを答えよ 制約 解法 1: BIT (区間加算、1 点取得) まずは BIT を用いる方法から。 考えやすいよ…

AOJ 2370 RabbitWalking (JAG 冬合宿 2010 day3-B) (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 つをとってもその積が立方数とはならない という条件を満たすようにせよ。 制約 解法 …

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 を根とす…