2015-07-19から1日間の記事一覧
Problem - E - Codeforces そもそも counting sort というのを初めて知った。使用制限があるが O(n) でソートできる高速ソート。それでも O(N*Q) になってしまう計算量をどう落とすか? 想定解法は segment tree を使うやつらしいけど、segment tree まだち…
Problem - D - Codeforces 「[x,y] の区間に含まれている」という条件から区間を絞るのは簡単なんだけど、「[x,y]に含まれていない」という条件から区間を絞るのは大変。(区間が分割されてしまう可能性があるから。) 下のコードは他の人のものを参考にした。…
Problem - C - Codeforces 本番これ以降の問題は溶けなかった...。なかなか C 問題の壁を超えられない...。 実は全探索+枝刈りっぽい話。 bfs + メモ化でなんとかなってしまうのか...。 solve2,solve3 は Codeforces Round #312 (Div. 2) Editorial - Codef…
Problem - B - Codeforces 本番は下のコードの cnt のかわりに map を使った O(n*log(n)) の解法で通した。ソッチのほうがバグも少なくてすむと思うけど、勉強のため O(n) のコードを書いてみた。 要は beauty となる a[i] の値の先頭と末尾を見つけておいて…
Problem - A - Codeforces 復習。本番通ったけどコードが汚かったので書き直し。無駄に dfs とかしてたけど単なる足し算で住む話だった。 書き直しして WA になったりしたあたり本当に実装力が足りないと思った。 class Div2A { public: void solve(void) { …