問題 TopCoder Statistics - Problem Statement 解法 一番深い葉ノードへ直進して（復路を戻ることはしない！）歩き終わるのが一番効率的であろう。 これは１の頂点につき１ステップかかる。 残りの枝道はどうあがいても１つの頂点につき２ステップかかる。 …

問題 TopCoder Statistics - Problem Statement 解法 dpる。 dp[bit] := メモリの使用状態がbitとするときの、最小時間 dp初期化 メモリを全く使用しない場合、つまりプログラムを動かさないときの時間は0であるため、 dp[0] = 0; dp更新 現在考えている命令…

問題 TopCoder Statistics - Problem Statement 解法 まず、K = 1ならば必ず"Paint"となる。K >= 2であれば、R、C、どちらかが偶数であれば"Paint"となり、どちらも奇数であれば"Cannot paint"となる。 なぜどちらも奇数であれば"Cannot paint"であるかとい…

問題 TopCoder Statistics - Problem Statement 解法 スライムをn回斬ると決めたとき、最終的なミニスライムの大きさがなるべく均一になるように斬ると最もポイントが高くなる。 例えば、スライムの大きさが10、3回斬るとする。その時、ミニスライムは4つに…

問題 TopCoder Statistics - Problem Statement 解法 まず、文字列の長さをnとしたときに、LCSがn - 1なcorrect bracket sequenceは必ずある。 根拠は以下の通り ★任意の(を、それより前の位置にある)の前に持ってくることができる s=( ( ) ( ) ) ^ t=( ( ( …

問題 TopCoder Statistics - Problem Statement 解法 dpる。 dp[i][j][k] := i-1番目までの文字を考えた時に、 既にアンダーバーが付与しており、ペアが組まれていないセミコロンがj個あり アンダーバーが付与しておらず、ペアが組まれていないセミコロンがk…

問題 TopCoder Statistics - Problem Statement 解法 roomSize = 3 leaders = {1, 4, 6, 10} ■所在不明者2, 3はどの部屋？？ leaderが1の部屋に入っているだろう。 答え = 1 ■所在不明者5はどの部屋？？ leaderが1, 4のどれかの部屋に入っているだろう しか…