ABC038

問題元 → 

abc038.contest.atcoder.jp

A - お茶

概要

末尾がTか判定しろ.

解法

やるだけ.

print("YES" if input()[-1] == "T" else "NO")

B - ディスプレイ

概要

ディスプレイが2枚ある. 片方はH_1 x W_1の大きさで,もう片方はH_2 x W_2の大きさ. ディスプレイは90度回転できる. 高さを合わせることはできるか?

解法

総当りを行う. 関数を作るのがお決まりだが,Pythonならfor-else構文でぱぱっと書ける.

今回はディスプレイ2枚で固定だったが,ディスプレイがN枚の時に最大何枚高さを合わせられる? と問われた場合にはどうすればいいのかがわからない. HとWが小さければDPでいけるが,もっと良い方法がありそうで気が気でない.

追記:何言ってるんだこいつ.酔っていたかもしれない.前から舐めていけば終わり.O(n).

from itertools import product
for n, m in product(map(int, input().split()), map(int, input().split())):
    if n == m:
        print("YES")
        break
else:
    print("NO")

C - 単調増加

概要

数列が与えられる.単調増加な部分数列の数を求めよ.

解法

全てを数え上げていると間に合わなくなることはすぐにわかる.

長さNの単調増加な数列には(N+1) * N / 2個の単調増加な部分数列が含まれる. この性質を利用すればすべてを数え上げる必要がなくなり,通る.

変数名関数名が悪すぎて怒られそうだなぁ...と思いながら書いていた. 「変数名関数名に使える単語帳」のようなものが欲しい.

def f(seq, idx):    
    for i, j in zip(range(idx, len(seq)), range(idx+1, len(seq))):
        if seq[i] >= seq[j]:
            return j
    return len(seq)

def g(seq):
    idx = 0
    ret = []
    while idx < len(seq):
        ret.append((idx, f(seq, idx),))
        idx = ret[-1][-1]
    return ret

def h(l, r):
    n = r - l + 1
    return n * (n - 1) // 2


N = int(input())
a = list(map(int, input().split()))
print(sum(h(l, r) for l, r in g(a)))

D - プレゼント

概要

H x W の大きさの箱がN個ある. 最大でいくつの箱を入れ子にできるか?

解法

漸化式は次のようになる.

DP[h][w] = max(DP[h-1][w-1], ..., DP[i][j], .. DP[1][1]) + 1

あとはhの小さい順にソートして漸化式を埋めていく.(これでDAGになる) maxについてはRangeMaximumQueryをSegmentTreeで実装すればO(logN).

「大丈夫でしょ?w」と思いPythonで書き,通らないことを確認してからC++で書き直した.随分時間をロスしてしまった. 計算量的にはO(NlogN)と十分そうだが,SegmentTreeのようなリストへのアクセスが頻繁に起こるデータ構造はPythonでは相当遅くなる.

コンテスト中は「あっ,LISだ」とならなかった.反省.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// RMQ
template<class T>
struct SegmentTree {
    int n;
    vector<T> dat;
    SegmentTree(int n_ = 0) : n(n_){
        n = 1;
        while(n < n_) n <<= 1;
        dat.resize(n*2, 0);
    }
    T query(int v, int w, int l, int r){
        if(r <= l || w == 0) return 0;
        if(r - l == w) return dat[v];
        T res = 0;
        res = std::max(res, query(v*2, w/2, l, min(r, w/2)));
        res = std::max(res, query(v*2+1, w/2, max(0, l-w/2), r-w/2));
        return res;
    }
    void update(int i, T x){
        i += n;
        dat[i] = x;
        while(i != 1){
          dat[i>>1] = std::max(dat[i], dat[i^1]);
            i /= 2;
        }
    }
    T query(int l, int r){
        return query(1,n,l,r);
    }
    size_t size() const {
        return n;
    }
};

int main(){
  int N;
  cin >> N;
  vector<pair<int, int> > HW(N);
  for(int i = 0; i < N; ++i){
    cin >> HW[i].first >> HW[i].second;
  }
  sort(HW.begin(), HW.end());
  SegmentTree<int> rmq(100001);
  int l = 0, r = 0;
  int ans = 1;
  while(l < HW.size()){
    while(r < HW.size() && HW[l].first == HW[r].first){
      ++r;
    }
    int n = r - l;
    vector<int> indices(n), values(n);
    for(int i = 0; i < n; ++i){
      int v = rmq.query(0, HW[i+l].second);
      indices[i] = HW[i+l].second;
      values[i] = v + 1;
    }
    for(int i = 0; i < n; ++i){
      rmq.update(indices[i], values[i]);
      ans = std::max(ans, values[i]);
    }
    l = r;
  }
  cout << ans << endl;
  return 0;
}
class SegmentTree(object):
  
    def __init__(self, size, op=min, init=float("inf")):
        self.size = 1
        self.op = op
        self.init = init
        while self.size < size:
            self.size *= 2
        self.data = [init] * (self.size*2+2)
  
    def update(self, idx, value):
        k = idx + self.size - 1
        self.data[k] = value
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self.op(self.data[k*2+1], self.data[k*2+2])
  
    def find(self, start, end):
        def query(k, left, right):
            if right <= start or end <= left:
                return self.init
            if start <= left and right <= end:
                return self.data[k]
            vl = query(k*2+1, left, (left+right)//2)
            vr = query(k*2+2, (left+right)//2, right)
            return self.op(vl, vr)
        return query(0, 0, self.size)

def compress(arr):
    dic = dict(zip(sorted(set(arr)), range(len(arr))))
    return [dic[v] for v in arr]

if __name__ == "__main__":
    N = int(input())
    H, W = [], []
    for _ in range(N):
        h, w = list(map(int, input().split()))
        H.append(h)
        W.append(w)
    H = compress(H)
    W = compress(W)
    HW = list(zip(H, W))
    HW.sort()
    rmq = SegmentTree(max(W)+1, max, 0)
    ans = 1
    l, r = 0, 0
    while l < len(HW):
        while r < len(HW) and HW[l][0] == HW[r][0]:
            r += 1
        tmp = []
        for h, w in HW[l:r]:
            tmp.append((w, rmq.find(0, w)+1))
        for i, v in tmp:
            rmq.update(i, v)
            ans = max(ans, v)
        l = r
    print(ans)