mayoko’s diary

プロコンとかいろいろ。

2016-03-23から1日間の記事一覧

AtCoder Regular Contest 024 D - バス停

なんとなくマラソンマッチっぽい問題だと思いました。 問題 arc024.contest.atcoder.jp 解法 解説を参考にして解きました。 AtCoder Regular Contest 024 解説 from AtCoder Inc. www.slideshare.net今, [xl, xr) の間で条件を満たそうとしているとします。…

東京大学プログラミングコンテスト2013 D - 壊れかけのヒープ

問題 utpc2013.contest.atcoder.jp 解法 N const int INF = 1e9+7; bool ok(const vector<int>& A, int m) { int n = A.size(); set<int> S; vector<int> B(m+1, INF); for (int i = 0; i < n; i++) { B[m-n+i] = A[i]; S.insert(A[i]); } for (int i = m-1; i >= 1; i--) {</int></int></int>…

東京大学プログラミングコンテスト2013 C - 直径

問題 utpc2013.contest.atcoder.jp 解法 2 つのグラフの直径, 半径を求めて, 最大値については, (直径1) + (直径2) + 1 最小値については, max((半径1) + (半径2) + 1, max((直径1), (直径2))) を求めれば良いです。直径, 半径は O(nm) で求められるので計算…