ABC038
問題元 →
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)