2019-05-12から1日間の記事一覧
AtCoder
AtCoder800点
ARC-E
数え上げ問題
数列
XOR
DP
DP高速化
DP高速化:累積和
ランレングス圧縮
区間
区間分割型ナップサックDP
場合分け
非自明な線形時間
橙色diff
ARC-like
区間分割の仕方を走査する問題
制約条件:各グループの何かが等しい
累積和テク:区間の総和を累積和で高速に求める
Zero-Sum Ranges
時間かかりすぎた。シンプルで面白い。 問題へのリンク 問題概要 要素からなる 0 以上の整数列 が与えられる。 これをいくつかの連続した部分列に分割する 通りの方法のうち、各連続区間の XOR 和が互いに等しくなるものが何通りあるか、1000000007 で割った…
楽しかった 問題へのリンク 問題概要 正の整数 が与えられる。 以下の条件を満たす正の整数 の個数を求めよ: を で割ったときの商と余りが一致する 制約 考えたこと とりあえず について手元で計算しているうちに、商と余りとが一致した値 として考えられる…
AtCoder
AtCoder400点
文字列
グルーピング(算数)
最適化テク:自明な上界が最適解
緑色diff
ARC-like
ARC-C
文字列のconcatを考える問題
グルーピングの最適化
順列の最適化問題
N個の文字列の問題
禁止文字列
解空間:O(N!)通りの選択肢
ペアリングを場合分けしてルールベースで頑張る系の問題、過去に何度もやらかしていて苦手意識が強い 問題へのリンク 問題概要 個の文字列 が与えられる。 これらを任意の順序で連結してできる 通りの文字列のうち、その中に "AB" を連続部分列として含んで…