blog.bouzuya.net

2022-06-03 ARC133 の B を解いた

ARC133 : AtCoder Regular Contest 133 の B を解いた。

  • B - Dividing Subsequence https://atcoder.jp/contests/arc133/tasks/arc133_b
    • 提出: https://atcoder.jp/contests/arc133/submissions/32178116
    • 解説 AC
    • 最長共通部分列 (LCS : Longest Common Subsequence) 的な DP かと思った
    • 制約が N <= 2 * 10^5 なので間に合わない
    • 倍数の位置を探しておく……？　それをどう使う……？
    • 糸口を見いだせず解説を見た
    • 解法は倍数の位置のペアをつくり (i, -j) でソートし .1 について LIS の長さを求める
    • 解説を見てもなぜ (i, -j) なのか一瞬わからなかった
    • 理由は同じ i で j を 2 つを選ばないように i ごとに j を降順にしている

今日のコミット。