O(N^2)個のものを考える問題
差分更新系の教育的問題かな 問題へのリンク 問題概要 長さ の数列が与えらえる。各 index k に対して、 数列から k 番目の要素を除いたものについて その中から異なる 2 つの要素を選ぶ方法であって (順番は問わず) その 2 つの要素の選び方が等しい という…
ごちゃごちゃとばぐらせながら何とか通した... 問題へのリンク 問題概要 要素の数列 が与えられる。この数列の 通りの区間それぞれについての 区間内の要素の部分集合であって総和が であるものの個数 の総和を求め、998244353 で割ったあまりを求めよ。 制…
確かに AtCoder で完全既出だった！ drken1215.hatenablog.com 問題へのリンク 問題概要 要素の数列 が与えられる。これらから 2 つ選んで和をとって得られる 個の整数の XOR 和を求めよ。 制約 #include <bits/stdc++.h> using namespace std; const int INF = 1<<30; int </bits/stdc++.h>…
こういう問題を求めてた！！ 問題へのリンク 類題として、こんなのがある。 drken1215.hatenablog.com 問題概要 長さ の、各文字が '0'〜'9' のいずれかとなっている文字列 と、素数 が与えられる。 の空でない連続する区間であって、その整数が で割り切れ…
面白かった 問題へのリンク 問題概要 文字列 が good であるとは、 の連続部分文字列であって回文であるような区間をすべてとってきたときに、それらによって が被覆されることをいう。たとえば "aaba" は、"aa" と "aba" によって被覆されるので good であ…
勉強になった...けど、これ知らずにできるもんなの！？ 問題へのリンク あと、LCM の最小値バージョンもある！ drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。 制約 …
差分更新系の代表的問題。でも頭がごっちゃになって大変だった。 問題へのリンク 問題概要 'D', 'M', 'C' からなる長さ の文字列 と正の整数 が与えられる。 の添字 であって S[ ] = 'D' S[ ] = 'M' S[ ] = 'C' を満たすものの個数を求めよ (というクエリに …
200 点問題で最も難しい問題として名高い問題ですね。 これについては、以下の「累積和」について特集した記事で詳しく解説しました！ qiita.com
楽しかった。こういうのでロリハ使うの楽しい。発想自体は Zero-Sum Ranges (200 点) と似てる。 問題へのリンク 問題概要 高橋君は、いつも頭の中に長さ 2000000001 の数列 と、整数値 を思い浮かべている。初期状態では、数列の各要素値と、 の値はすべて …
超典型的なしゃくとり法そのものだった！！！ 問題へのリンク 問題概要 個の整数 があたえられる。数列の連続した区間であって、その総和が 以上となっているものを数え上げよ。 制約 考えたこと しゃくとり法については以前に記事を書いた。 qiita.com この…
面白かった。 「全体についての総和についての総和」を「個別の要素についての総和を各要素について総和」とするテク 区間の連結成分の個数は、各隙間に左端が入り込むかを数える という典型テクが詰まった問題。 問題へのリンク 問題概要 要素からなる数列 …
教育的な典型問題！ 問題へのリンク 問題概要 要素からなる順列 が与えられる。 の連続する各区間について、区間内の最小値を求め、その総和を求めよ。 制約 考えたこと まず思うのが、区間の個数は 個ある。たとえ各区間に対する最小値を で答えられたとし…
しゃくとり法のいい感じの練習問題 問題へのリンク 問題概要 英小文字のみから成る文字列 が与えられる。 の連続する部分文字列のうち「同じアルファベットが2度以上使われることのない」ものが何個あるかを数えよ (空文字列は 1 個とみなす) 制約 考えたこ…
累積和の練習 問題へのリンク 問題概要 個の整数 が与えられる。 各 に対して、数列の 個の連続する区間の値の和の最大値を求めよ。 制約 考えたこと 愚直にやると計算量は の値が 通り考える必要があって 各 に対して 個の区間があって 各区間に対して 個の…
コンテスト本番、つたじぇーが頑張って通してくれた！！！ 問題へのリンク 問題概要 長さ の数列 が与えられる。初期状態では の要素は全て 0 である。加えて、 個の整数のペア()が与えられる。各ペアに対し以下の操作を行い、最終的な数列 を出力せよ。 各 …
桁ごとに考えるしかなさそうなのはそれはそう... 問題へのリンク 問題概要 (ARC 092 D / ABC 091 D) 要素の数列 と が与えられる。 個の整数 の XOR 和を求めよ。 制約 < 解法 XOR 和と言われた時点で、各桁ごとにカウントしたい気持ちにはなる。 個の整数の…
AGC 023 A - Zero-Sum Ranges とほぼ同じ問題なんな。ただし、バケットを愚直に確保すると 109 サイズになってしまうので map とか連想配列が必要になるのん。 問題へのリンク 問題概要 (ABC 105 D) 個の整数 の連続する部分区間のうち、その総和が の倍数と…
treeone さん... 問題へのリンク 問題概要 0 と 1 からなる長さ N の文字列 S が与えられる。 どの連続する K 個の中にも 1 が 3 個以上含まれている という条件を満たすような最小の K を求めよ 制約 3 <= N <= 105 S の中に 1 は 3 個以上含まれる 解法 右…
こんなしゃくとり法もあるのんな。面白いん。 ABC 098 D Xor Sum 2 問題概要 長さ の正の整数列 が与えられる。整数列の連続する部分列のうち、「xor 和と加算和とが等しい」という条件を満たすものを数え上げよ。 制約 数値例 1) 答え: 5 (2), (2, 5), (5),…
本番出てなかったけどこれは... ARC 097 C K-th Substring 問題概要 文字列 s が与えられる。s の連続する部分文字列のうち、辞書順で K 番目の文字列を求めよ。 制約 1 <= |s| <= 5000 1 <= K <= 5 解法 K が小さいのが怪しい。 冷静に考えると、辞書順 K …
