2016-07-01から1ヶ月間の記事一覧
問題 agc001.contest.atcoder.jp 考察 ・直径がとなる木を考えた時の、中心となる木の頂点を中心点と呼ぶ。・中心点から距離が以下となる頂点の数を最大になるような中心点を選べば、削除する点が少なくて済む。・が奇数の時は、中心点の隣接する頂点一つを…
codeforces.com この問題の想定解法がSparse Tableを使ったもので、ちゃんと理解したいなと思ったので忘備録的な感じで書きます。 色々調べながら書いているので、間違っているところがあったら指摘して頂けるとありがたいです。 Sparse Tableとは まず、Spa…
問題 No.390 最長の数列 - yukicoder やったこと まず最初に考えたのは「よい数列」というのはa[i] 再帰をしましたが、 計算量はO(N^2)であるので、TLEでした。 N = int(input()) x = sorted([int(i) for i in input().split()]) dp = [[-1 for j in range(N…