問題 TopCoder Statistics - Problem Statement 解法 二分探索で答えを求めていきます。ok(x) = (x 個の spaceship を作ることが出来るか？) とします。b の小さいのから順にパーツを作っていくと, 後ろのパーツを作るのになるべく余裕をもたせられるように…

問題 TopCoder Statistics - Problem Statement 解法 問題見てすぐに dp[n] = (残り n 枚の時, card をソートし終えるのにかかる回数の期待値) というのが思いつきますが, 素直に遷移を書くと面倒なので, もう少し考えます。n 枚のカードが残っている際に, …

問題 TopCoder Statistics - Problem Statement 解法 box i に色を残しておけない際に, ボールが逃げる場所を作っておかなければなりません。各色が逃げる場所を r, g, b とした時, ボールを動かす回数は, i==r の時は, green, blue を動かす回数 i==g の時…

問題 TopCoder Statistics - Problem Statement 解法 topcoder の解説を参考にしました。 http://apps.topcoder.com/wiki/display/tc/SRM+593こっち読むほうが絶対わかりやすいので, 概要しか書きません。下に書いてあるのも, この解説に書いてある変数を普…

問題 TopCoder Statistics - Problem Statement 解法 tA = sum(A), tB = sum(B) とします。すると, ある集合 S を決めたとして, maxdiff(S, T) は, max(, ) となります。これを簡単化すると, max(, )となります。よって, のあり得る値がなにかに関する dp を…

問題 TopCoder Statistics - Problem Statement 解法 4 色定理とかあるので, せいぜい 4 色あれば塗りきれることがわかりますが, 実は今回の場合はせいぜい 3 色あれば塗りきれることがわかります。例えば n = 4 の場合は, 以下のようにすれば良いです。RBGR…

問題 TopCoder Statistics - Problem Statement 解法 頂点数が 1 の場合を除いて, とりあえず 1 つのビーコンを置く必要があります。最初にビーコンを置いた場所を root にした木で, あと最低いくつのビーコンを置かなければならないか, というように考えま…

簡単じゃない？ 問題 TopCoder Statistics - Problem Statement 解法 ゲーム始まった直後に Ciel が勝てる(d そうでない場合に, Ciel がどこへ逃げても Liss が勝てる場合(d+mov1 これ以外は, どちらかがじりじり攻めていく感じで勝つしかない まず, じりじ…

問題 TopCoder Statistics - Problem Statement 解法 mov1 >= abs(d) なら, 一回で Ciel さんが Liss さんに追いつけるので, Ciel の勝ち そうでない場合, mov1 > 2*mov2 なら, 最初に近づいた時, mov2 以内に近づかないでかつ次に相手がどう動こうと mov1 …

サンプルがすごく丁寧。 問題 TopCoder Statistics - Problem Statement 解法 ビンの大きさが 300 で固定であり, かつ入れる品物の大きさが 100 〜 300 で固定されているので, 200 より大きい品物は一つで入れるしかない 101 以上 200 以下の品物は それより…

問題 tdpc.contest.atcoder.jp 解法 普通に dp[k][i] = (i が k 回戦まで勝ち抜く確率) とやれば良いんですが, 微妙に遷移で迷ったので書いておきます。i が k 回戦で戦う可能性がある競技者を考えます。p = 1= med であるとすると, いままでは [med, maxi) …

問題(というかトップページ) snuke21.contest.atcoder.jp 解法 t を作って, そこから s を作ることを考えます。例えば t が 11001 とかだったとすると, s は, (0...0)1(0...0)1(1...1)0(1...1)0(0...0)1(適当な文字列) というようにして構成できます。t[i] =…

うーん, これは… 問題 codeforces.com 解法 結局 log を一回取るだけで良かったようです。ﾅﾆｺﾚ一応学んだこととしては, long double が扱える範囲が結構大きいことですね。@mayoko_ 64bitの小数が10^308位じゃなかったですかね。80bitの小数型は指数分に2^16…

これ難しい…(というか気づけばやるだけ系は難易度の判定が難しそう)(競プロの問題の 8 割は気づけばやるだけ) 問題 TopCoder Statistics - Problem Statement 解法 頂点 i について, 0 -> i に到達可能でかつ i -> n-1 に到達可能である, という条件を満たす…

問題 TopCoder Statistics - Problem Statement 解法 切り取られていなければならない部分を左上から探索します。 class GogoXCake { public: string solve(vector <string> cake, vector <string> cutter) { int H = cake.size(), W = cake[0].size(); int n = cutter.size(</string></string>…

解法 bitDP します。dp[s] = (s で表される集合は既に優先順位が上になることが決まっていて, 新しく別の種類の食品を食べることが出来ないと決まっている月である時, まだ追加することの出来る食品の種類の数) とします。mask[i] = (食品 i が売られている…

問題(というかトップページ) snuke21.contest.atcoder.jp 解法 's' を消せるので, 's' が連続した部分文字列の直後の文字 c が c 's' を満たすなら, なるべく消したくないですが, 消さないといけないとしたら, 辞書順に影響を与えにくい後ろから消していくの…

問題 TopCoder Statistics - Problem Statement 解法 暗号化する前の文字列を str0, 一回暗号化した後の文字列を str1, もう一回暗号化した後の文字列を str2 とします。 入力として与えられるのは str2 ですが, str2 から str1 を求めるのは, O(N^2) の dp …

Codeforces Round #341 (Div. 2) に参加しました。 E 解けないのはダメだ… 問題 codeforces.com 解法 dp[i][j] = (上から数えて i 桁目の時点で, x で割った余りが j になっているような場合の数) とします。すると, dp の遷移は dp[i+1][(j*10+a)%x] += dp[…