# Gori#018(ABC038)

# B - ディスプレイ

# 概要

(高さ, 幅) = ( $H_1, W_1$ ), ( $H_2, W_2$ )というディスプレイがある.
ディスプレイを回転させて置ける場合, 高さを揃えて置けるか判定せよ.

# 解法

高さが同じペアを探せば良い.

#include <bits/stdc++.h>
using namespace std;

int main() {
  int h1,w1,h2,w2;
  cin >> h1 >> w1 >> h2 >> w2;

  cout << ((h1 == h2 || h1 == w2 || w1 == w2 || w1 == h2) ? "YES" : "NO") << endl;
  return 0;
}

# C - 単調増加

# 概要

$N$ 個の要素からなる数列 $a$ について, 単調増加となる部分列の区間(*)の数を求めよ.

*: $l \leq r$ であって, $a_i < a_{i+1}$ を満たす区間[ $l,r$ ]のこと

# 解法

隣の要素と毎回比較するので, しゃくとり法を用いればよい.
(言い換えると, 範囲が1ずつ変化するので)

しゃくとり法については, 以下の資料が参考になるかも.

しゃくとり法のテンプレは以下の通りなので, それに従って書けばよい.

// 区間は[lb, ub)である.
int ub = 0;
for(int lb=0;lb<n;++i){
  // 今一度, 区間を正しく設定する.
  ub = max(ub, lb+1);
  while(ub<n && (条件式)){
    // 条件を満たす時は, 右端を増やす.
    ++ub;
  }
  // 条件を満たさなくなった時に, それが伸ばせる最大の区間.
  ans += ub - lb;
}

提出コード (opens new window)

# D - プレゼント

# 概要

高さが $h_i$ , 幅が $w_i$ である $N$ 個の長方形がある.
この長方形を入れ子にする時, 最大何重に出来るかを求めよ.

# 解法

RMQ解法とLIS解法があるらしいので, 両方紹介したい.

# RMQ解法(Editorial解)

こちらは, 部分点解法解法からの派生.
部分点解法は,

dp[i] := i番目の箱を最も外側とする時, 最大で何重の入れ子と出来るか

ただし, 入れ子を確認するためには, ( $h_i, w_i$ )の両方で探索しなければならなかった( $O(N^2)$ ).

そこで, 片方の任意の区間で, 入れ子を何重に出来るかをメモすればよいという発想に行き着く(解説放送を見ると良いかも (opens new window))

以上をメモするデータ構造がRMQである.
RMQは以下の特性がある.

任意の区間の和を持つ
[1, $k$ ]の最小値を求める操作
任意の区間に含まれる要素の値の更新

という訳で, 実装.

どうやってやるんだ?
片方の要素でソートしていって, 値が来たら更新?
セグ木が良くわかってないので, あとで時間がある時にやります(少なくとも今日中に)
というかRMQとBITの違いを忘れてしまったので, スニペットの見直しが必要かも

# LIS解法

こちらは, 片方の要素でソートして, もう片方の要素でLISを取れば良いよねというお話.
ソートの時に, 片方の要素で昇順ソートして, もう片方の要素は降順ソートにすることがポイント. ( $\because$ 降順ソートにしてlower_boundを取ることで, LISが上手く求められる. 昇順ソートにすると, 同じ要素を何度も選んでしまう)

#include <bits/stdc++.h>
using namespace std;
using PAIR = pair< int, int >;

int main(){
  int n; cin >> n;
  vector< PAIR > d(n);
  for(int i=0;i<n;++i) cin >> d[i].first >> d[i].second;
  
  sort(d.begin(), d.end(), [](const PAIR &p1, const PAIR &p2){
    if (p1.first == p2.first) return p1.second > p2.second;
    return p1.first < p2.first;
  });

  vector< int > dp(n, 1e9+1);
  for(int i=0;i<n;++i){
    *lower_bound(dp.begin(), dp.end(), d[i].second) = d[i].second;
  }
  int ans = lower_bound(dp.begin(), dp.end(), 1e9+1) - dp.begin();
  cout << ans << endl;
  return 0;
}

# Gori#018(ABC038)

# B - ディスプレイ

# 概要

# 解法

# C - 単調増加

# 概要

# 解法

# D - プレゼント

# 概要

# 解法

# RMQ解法(Editorial解)

# LIS解法

# 参考資料