連続部分列を扱う問題
AtCoder
AtCoder800点
ARC-F
数え上げ問題
変数変換して扱いやすい同型な問題を見出す
重複組合せ
二項係数
条件の言い換え
ダブルカウントを防ぐ場合分け
場合分け
操作によって作れるものの集合を考える(判定関数を考える)
赤色diff
ARC-like
連続部分列を扱う問題
グラフ・盤面・数列の個数の数え上げ
0と1と2の問題
禁止文字列
かなり時間かかった 問題へのリンク 問題概要 のみからなる長さ の数列であって、どの連続する部分列に対してもその総和が にならないようなものの個数を 998244353 で割ったあまりを求めよ。 制約 考えたこと 最初は包除原理かな...と思ったけど、どうにも…
AOJ
JAG
AOJ-ICPC450点
文字列
文字列検索問題
ローリングハッシュ
区間
AOJ-ICPC
JAG夏合宿
N個の文字列の問題
連続部分列を扱う問題
連想配列(setやmap)
種類数
ロリハそのものな問題！！！ 問題へのリンク 問題概要 長さ の文字列 が与えられ、 の連続する部分列が 個指定される。こうして作られる 個の文字列のうち、相異なるものは何通りあるか答えよ。 考えたこと ロリハで頑張る #include <iostream> #include <vector> #include <string> #i</string></vector></iostream>…
AtCoder
AtCoder200点
unrated公式コン
累積和
各kに対して
クエリ処理問題
数列
区間
前処理
解空間:O(N^2)通りの選択肢
解空間:O(N^2)個の区間
累積和テク:区間の総和を累積和で高速に求める
そのまま覚えたい典型問題
【問題集】累積和
【問題集】累積和・いもす法
連続部分列を扱う問題
最大スコア
最適化問題
累積和の練習 問題へのリンク 問題概要 個の整数 が与えられる。 各 に対して、数列の 個の連続する区間の値の和の最大値を求めよ。 制約 考えたこと 愚直にやると計算量は の値が 通り考える必要があって 各 に対して 個の区間があって 各区間に対して 個の…
条件の言い換え
いもす法的変換
累積和
数列
AtCoder
ABC-D
AtCoder400点
数え上げ問題
解空間:O(N^2)通りの選択肢
nC2
区間
バケット
水色diff
Zero-Sum Ranges
【問題集】整数変数の式で表された条件を扱う探索
解空間:O(N^2)個の区間
DP状態:あまり
連想配列(setやmap)
連続部分列を扱う問題
典型要素を詰め合わせた教育的問題
そのまま覚えたい典型問題
【問題集】累積和
AGC 023 A - Zero-Sum Ranges とほぼ同じ問題になってる。ただし、バケットを愚直に確保すると 109 サイズになってしまうので map とか連想配列が必要になる。 問題へのリンク 問題概要 個の整数 の連続する部分区間のうち、その総和が の倍数となっているも…
