Problem - C - Codeforces Problem - E - Codeforces 復習。本番普通に DP しようとして MLE した。 よく読むと h,w の制限が 10^5 とかなんで座標圧縮とかしないとダメなのかなー、座標圧縮ってどうやるのか？とか思っていたがそもそも方針が違った。 総経…

Problem - B - Codeforces Problem - D - Codeforces 復習。TLE するかもなぁ。と思いつつも他に解法が思いつかず提出して、案の定 TLE した問題。SRM なら撃墜されてんだろうな。 各再帰での 4 通りの分岐を事前の正規化で回避する。できる人には自然に出て…

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) { …

Problem - 557E - Codeforces editorial を見て解くも TLE しまくった問題。結局他の人コードを参考に Trie の add 関数を修正して解いた。 コメントにあるように int と size_t を比較して意図どおりに動かないというバグに見舞われた。 class Div2E { publ…

Problem - 557D - Codeforces 他の人のコードを見て union find を使う方法を知った。グラフの二色塗り分けを union find でやるなんて発想に目から鱗が落ちた。 以下は dfs と union find を使う2つの実装。 class Div2D { public: void solve_dfs(void) { …

Problem - 557C - Codeforces復習、復習。 足の長い方から処理する方針は立ったけど、ある長さの足よりも小さいものからなる最小のエネルギー値を高速で計算する方法が思いつかなかった。 d の上限が小さいことを利用して dcnt を使うのがミソ。 class Div2C…