問題 TopCoder Statistics - Problem Statement 解法 区間dpる。 dp[L][R] := LからRまでの区間にて、シーケンスをcorrectにする消し方の場合の数 初期化 L == Rの場合、その一文字を消すしかcorrectにする方法はないので1 更新 Rのカッコに着目し、こいつを…

問題 TopCoder Statistics - Problem Statement 解法 A[i]の増加の仕方は2のべき乗ぐらいに凄く、A[90]ぐらいにはもうxの最大値である10^18を超える。 探索範囲は広くなさそうということで、枝刈り探索しました。 事後 Editorialを見ると、大きいものから順…

問題 TopCoder Statistics - Problem Statement 解法 こちらを参考にしましたm(_ _)m mayokoex.hatenablog.com参考先でも言っているように、開きカッコ閉じカッコのペアが成立しているものを取り除いていくと、最終的には「））））（（」とか「）（（（（（…

問題 TopCoder Statistics - Problem Statement 解法 それぞれの色の花において、その数がガーデンの幅（rowの長さ）を超えているものがあれば、どう配置しても隣り合ってしまうため配置不可となる。 逆にそうでない場合、以下のようにすれば必ず配置可能と…

問題 リンク無し！ 訳 狼のSotheと猫のSnukeがカードゲームで遊んでいる。このゲームはちょうど100枚のカードを使う。カードには1から100の数字が書かれている。ゲームの遊び方については以下の通り。 1. 初めに、猫のSnukeが1から100の中から数字のNを選び…

問題 TopCoder Statistics - Problem Statement 解法 下の記事を参考にしました。m(_ _)m kmjp.hatenablog.jp有効グラフで考えたときに、頂点を以下のように色分けする。 A・・・0,1どちらからも到達できる頂点 B・・・0からのみ到達できる頂点 C・・・1から…

問題 TopCoder Statistics - Problem Statement 解法(一番早かった人のをカンニング) 通過する辺の重みにて、下回ってはいけない最小値ラインを決め打ちする。 ↓ 辺それぞれの重みから、決め打ちした最小値を差し引く。 ↓ 0 -> 1へ移動するために通る最大の…

問題 TopCoder Statistics - Problem Statement 解法 w1[i]を消すとw2[i-1]とw2[i]が消せなくなり、w2[i]を消すとw1[i], w1[i+1], w2[i-1], w2[i+1]が消せなくなる。 で、w1とw2を交互に、iの小さいものから消すか？消さないかを順に考えていけば、 w1[1]->w…

問題 TopCoder Statistics - Problem Statement 解法 dpる。 dp[i] := i-1番目の人までの、番号の振り方の場合の数 初期化 まだ誰にも番号を振っていないときは１パターンなので、 dp[0] = 1; 更新 i番目の人に1からi+1までの番号を振って、それぞれの場合の…

問題 TopCoder Statistics - Problem Statement 解法 dpる。 まず全員をteam1に加入させておく。 それから、生徒ごとに着目していき、team2及びteam3に移籍させる場合を考えていく。 team2及びteam3それぞれのチーム力とすることが可能かどうか記録しておき…

問題 TopCoder Statistics - Problem Statement 解法 最終的に使用するconstantの長さとその数について、実は一意に定まる。 以下を見て欲しい。 constantの長さ | 1 2 3 4 数 | 11 8 5 2 ↓ constants 4 を1回使うと残るのは ↓ constantの長さ | 1 2 3 4 数 …

問題 TopCoder Statistics - Problem Statement 考えたこと むずい！Div1 Easyってこんなにむずかったっけ！？ １時間考えてもできない・・ せや！他の人のソースコードを見て何やってるか考えたろ！ 解法 ヒーローは頂点を色で塗っていく流れだが、それを逆…