問題 TopCoder Statistics - Problem Statement 解法 りんごさんのソースコードを参考にしましたm(_ _)m石取りゲームにありがちなdpをする。（現在の状態から遷移できる状態の中で、勝てるものがあれば勝ち というやつ） だが、石の数が半端ないのでもう一工…

問題 TopCoder Statistics - Problem Statement 解法 コチラを参考にしました。m(_ _)m kmjp.hatenablog.jpセル(i, j)に置いた時のスコアを出して、それが大きい順にセルをソートしておく。１個目の基地を任意の位置に置いた時の、２個目の基地のベストな置…

問題 TopCoder Statistics - Problem Statement 解法 N + 1 ～ Mの中に、1 ～ Nの素因数を全て持っている必要がある。 例えばN = 10であれば、1 ～ 10に2^3, 3^2, 5^1, 7^1の素因数がある。 それぞれ11(N + 1)以上で、どの数であればその素因数を持つかを見…

問題 TopCoder Statistics - Problem Statement 解法 以下の通りです。orz mayokoex.hatenablog.com 事後 D=1～1000まで全探索すればいいや。 ↓ 実装に手間取る ↓ ふぅ・・・なんとか時間ぎりぎりにコミット ↓ WA ↓ SRM662でググる ↓ Greedyかよ！！ ソース…

問題 TopCoder Statistics - Problem Statement 解法 最終的にinitialが反転しないで終わったのか、反転して終わったのかを決め打つ。■反転しないで終わった時の条件 target = 左側の文字列 + initial + 右側の文字列 とすると、 ・左側と右側の文字列で、含…

問題 TopCoder Statistics - Problem Statement 解法 以下、参考にさせていただきました。m(_ _)m kmjp.hatenablog.jp 事後 実装がちょっと難しくなると頭が混乱するのなんとかして ソースコード const long long INF = 123456789012345LL; long long dp[20]…

問題 TopCoder Statistics - Problem Statement 解法 例のごとく他人だより。以下、参考にさせていただきました。m(_ _)m mayokoex.hatenablog.com 事後 あ^～あるはずのない周期性に賭けてしまったんじゃ^～ ソースコード class BearPlays { public: int pi…

問題 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のどれかの部屋に入っているだろう しか…

問題 TopCoder Statistics - Problem Statement 解法 N匹の狼がいて、何匹か飴を１つ持っている。ここで、それぞれの狼に「あなたを除く他の狼たちの飴を合計するとそれは奇数？偶数？」と聞く。狼たちは正直に答えるが、黙秘権を行使する狼もいる。この時、…

問題 TopCoder Statistics - Problem Statement 解法 とりあえず、一番目の戦士がそれぞれの馬を使った時を試してみる。残った戦士を降順に、残った馬を昇順にソートしておく。 あとはSample0のもので説明していく 戦士0(5)は馬1(40)を使うぜ！つまり戦闘力…

問題 TopCoder Statistics - Problem Statement 解法 こちらを完コピしました。。orzt8m8.hateblo.jp 事後 ソースが簡潔でいいですなぁ ソースコード class Procrastination { public: long long findFinalAssignee(long long n) { // nより小さい最大の素数…

問題 TopCoder Statistics - Problem Statement 解法 まず木グラフの特性より、辺の数はn - 1なので、そうなっているか確認。（インプットのnumは辺を２回ずつ数え上げているから、(n - 1) * 2 = num[i]の合計値なのか確認） 木グラフになっていたら、あとは…

問題 TopCoder Statistics - Problem Statement 考えた解法 0と1をとりあえず繋げる。 他の頂点は0または1にだけ繋げることを考えると、長さ3のシンプルパスの数は0に繋げた頂点の数 * 1に繋げた頂点の数になる。 9991とかの大きめの素数はこれだけだと丁度…

問題 TopCoder Statistics - Problem Statement 解法 outputの秒間流量を決め打って、溢れる溢れないを判定。それをにぶたん。 事後 誤差について理解できてないのでこういう問題怖い ソースコード int C; vector<int> T; vector<int> X; int N; class WaterTank { pub</int></int>…

問題 TopCoder Statistics - Problem Statement 解法 青いボタンを何回使ったかで全探索するとよい。 青いボタンをn回使ったとすると、aは2^n * aとなり、あとは、赤いボタンをnewA - 2^n * a 回だけ押せばよいことになる（この回数をxと置く） bの方も同じ…

問題 TopCoder Statistics - Problem Statement 解法 firstWeekからlastWeekへ、indexが遡るように、一番離れているようなシャツが、lastWeekを再現するのにボトルネックになっている。だからそのシャツをとにかく最優先に考えて、洗って乾いたら直ぐに着て…

問題 TopCoder Statistics - Problem Statement 解法 dfsして貪欲に。 自分を含めてマイナスになったら自ら首を切って0を返して会社に貢献しよう。（部下を道連れに） ソースコード vector<int> G[2550]; int P[2550]; class FiringEmployees { public: int fire(</int>…

問題 TopCoder Statistics - Problem Statement 解法 こちらをチラ見しました（dpの作り方だけ。・・・・まあほとんど解答のようなものだけど・・・） mayokoex.hatenablog.comありがとうございましたm(_ _)m 事後 チラ見してなお実装に75分かかるとはいった…

問題 TopCoder Statistics - Problem Statement 解法 宇宙船を作る数を決め打ちする。 するとどうだろう、ワークショップを貪欲に使用することが出来る。 今、パーツpを作りたいと思った時、パーツを作ることができ（a[i] 決め打ちの数はにぶたんで。 ソース…

問題 TopCoder Statistics - Problem Statement 考えた解法 普通にdfsで探索すると計算量がやばい。 特に下図のような構成となっているグラフで、赤い頂点から探索を進めた日にゃあスタート頂点１つにつき計算量がO(M^2)になる。やばい。 あれ待てよ・・・赤…

問題 TopCoder Statistics - Problem Statement Editorial https://apps.topcoder.com/wiki/display/tc/SRM+683 訳 まずは簡単に考えて、石の山が円状に並んでいないものとしよう。ちょうど、類題であるDiv2 Mediumでは石の山は直線状になっており、最後と最…

問題 TopCoder Statistics - Problem Statement 解法 配列を昇順にソートしておいて、サブセットに含める最小値a[L]と最大値a[R]の２つを決め打ちする。 すると、Dの最大値は「a[R] - a[L]」に固定される。Dの最小値も「Dの最大値 / k」に固定される。 あと…

問題 TopCoder Statistics - Problem Statement 解法 サブセットTにindex iを使うぞ！ と決めると、goodなTを作るために必要な他のindexを芋づる式に導き出すことができる。 なので、index 0～n-1を順に試して、必要なindexが一番少ないものを答えとすればよ…

問題 TopCoder Statistics - Problem Statement 解法 連続しない部分文字列の数え上げなので、基本的には以下のやり方で。 ekaing.hatenablog.comあとは、最終的に全ての左カッコに右カッコのペアが出来ていなければならないので、超過した左カッコの数を記…