# Gori#018(ABC038)

問題セット

# B - ディスプレイ

# 概要

(高さ, 幅) = (H1,W1H_1, W_1), (H2,W2H_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 - 単調増加

# 概要

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

  • *: lrl \leq rであって, ai<ai+1a_i < a_{i+1}を満たす区間[l,rl,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;
}

提出コード

# D - プレゼント

# 概要

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

# 解法

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

# RMQ解法(Editorial解)

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

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

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

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

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

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

という訳で, 実装.

  • どうやってやるんだ?
  • 片方の要素でソートしていって, 値が来たら更新?
  • セグ木が良くわかってないので, あとで時間がある時にやります(少なくとも今日中に)
  • というか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;
}

# 参考資料

Last Updated: 2019-2-15 04:38:05