2019-12-25から1日間の記事一覧
AtCoder
有志コン
文字列
気付き系
信じる心
Yes/No判定問題
操作
最適化テク:探索候補を絞る
制約:複数系列の長さの合計が10^5以下
必要条件を列挙したら十分条件になる
文字列のconcatを考える問題
操作を好きな回数だけ行える
部分列
信じる心が大切ですね 問題へのリンク 問題概要 組の文字列 が与えられる。 これらの組を好きな順序で好きな回数だけ選んで、 側と 側とをそれぞれ連結した文字列 ができる。 このとき、 が の部分文字列 (連続でなくてよい) とすることができるかどうかを判…
AtCoder
AtCoder200点
AGC-A
累積和
前処理
解空間:O(N^2)通りの選択肢
数列
nC2
数え上げ問題
区間
緑色diff
集計処理
Zero-Sum Ranges
思わず解きたくなる興味深い良問
そのまま覚えたい典型問題
【問題集】累積和
200 点問題で最も難しい問題として名高い問題ですね。 これについては、以下の「累積和」について特集した記事で詳しく解説しました! qiita.com
AtCoder
AtCoder1200点
ARC-F
ローリングハッシュ
データ構造
差分更新
区間
解空間:O(N^2)通りの選択肢
文字列
二分探索
分けて解いてまとめる
数列
操作列が文字列で与えられる
集計処理
赤色diff
Zero-Sum Ranges
解空間:O(N^2)個の区間
楽しかった。こういうのでロリハ使うの楽しい。発想自体は Zero-Sum Ranges (200 点) と似てる。 問題へのリンク 問題概要 高橋君は、いつも頭の中に長さ 2000000001 の数列 と、整数値 を思い浮かべている。初期状態では、数列の各要素値と、 の値はすべて …