bouzuya.hatenablog.com

ぼうずやのにっき

ARC126 の B を解いた

ARC126 : AtCoder Regular Contest 126 の B を解いた。

  • B - Cross-free Matching https://atcoder.jp/contests/arc126/tasks/arc126_b
    • 提出: https://atcoder.jp/contests/arc126/submissions/32143961
    • a_i と b_i を結ぶ線分があり、両端の点を含めて交わらないように選べる最大の個数を求める
    • 線分の順番は問題にならないので a_i, b_i の昇順でソートしておく
    • まず a_i < a_{i+1} で考えてみる
      • a_i の昇順に走査すれば a_i 側は条件を満たすので、残りは b_i 側が昇順に並んでいることに注意すれば良い
      • 昇順にならないものは選べない
      • これだと選べるのか選べないのかを判断するのが難しいのである b_i を含む線分を選んだ時点での最大の K を保持する
      • つまり dp[j] := b_i として j への線分を選んだときの MAX(K) とする
      • あとは線分を選ぶ or 選ばないで遷移すればいい
      • 選ばない場合は何も影響を与えないので気にしなくて良い
      • 選ぶ場合は b_i 未満の範囲の MAX(K) + 1 になる
      • MAX(dp[0..j]) のようなものの取得を単純にやると O(N2) になって間に合わない
      • 区間の MAX を取るのでセグメント木を使う
      • これで O(N log ...) 程度になるはず
    • あとは a_i <= a_{i+1} を含むケースを考える
      • a_i = a_{i+1} のとき a_i ごとにひとつしか選べない
      • a_i が同じとき b_i はどれも異なるので a_i で更新した dp を再度参照することさえなければ最大値に影響はない
      • つまり a_i ごとに b_i をまとめておき b_i ごとの最大値を求める間は dp の更新を避けてあとでまとめて更新すれば良い
    • dp[0..n] の最大値が答えになる

IntelliJ IDEA の nullability-annotations-inspection Plugin を入れてみた。 @NotNull のついていないものなどに警告が出るようになった。

https://plugins.jetbrains.com/plugin/9418-nullability-annotations-inspection

バスタオルを買った。

今日のコミット。