問題 TopCoder Statistics - Problem Statement 解法 まず, t9 の各文字列の k 文字目までを作るのにかかるコストを計算します。 これには, t9 の各文字列 s について, s の k 文字目以下の番号(問題文の D というやつ) が一致しているやつを列挙し, それら…

問題 TopCoder Statistics - Problem Statement 解法 問題の制約から, x 方向, y 方向にずらす候補 dx, dy はそれぞれ -80 から 80 までしかありません。dx, dy としてあり得るものをすべて調べて, それぞれの場合に重なる線分の長さがどれだけになるかを調…

問題 TopCoder Statistics - Problem Statement 解法 count[i][j] から, cnt[i][j] = (別のバッグから j というカードを取り出した時, バッグ i から あるカード k を取り出して j + k が Good な数になるような場合の数) を作ります。j+k の候補がたかだか …

SRM 679 に参加しました。easy がめっちゃ簡単だったんですが英弱パワーを発揮して点数が低かったです。 問題 木構造になっている社員関係が与えられる。各社員 v は, productivity[v] - salary[v] だけの利益を挙げられる。利益を最大化するために社員を首…

問題 TopCoder Statistics - Problem Statement 解法 実際の迷路は無限に縦に続いていますが, 入力で与えられる一つの迷路のことを「パターン」と呼ぶことにします。まず, r1 と r2 が同じパターンに属する場合を考えます。一つ注意というか, そこがこの問題…

IOI 問題 TopCoder Statistics - Problem Statement 解法 IOIString でない string の数を数えることにします。まず, 全部 O で構成されているような string は IOIString ではないです。 また, I がひとつだけ存在する string も IOIString ではないです。 …

問題 TopCoder Statistics - Problem Statement 解法 roads[i][j] == 'Y' だったら頂点 i と頂点 j の間に辺を貼ってみます。すると, それによっていくつかの連結成分が出来ます。その連結成分の中に, 次数が 3 以上の頂点 v があると, v に 2 回以上通らな…

問題 TopCoder Statistics - Problem Statement 解法 石を置く場所を o, 置かない場所を x とすると, ooxxooxxoo ooxxooxxoo xxooxxooxx xxooxxooxxのように, 2 マスおきに見た時市松模様っぽくなるようにするのが最適です。理由を考えてみます。単純な問題…

問題 TopCoder Statistics - Problem Statement 解法 ある整数集合 S について, S の任意の要素 el がすべての実験で同じ switch の入力をするとすると, それらのスイッチはどうやっても区別することは出来ないので, 「すべての実験で同じスイッチの入力をす…

450pt だったけど確かにこれは簡単。 問題 TopCoder Statistics - Problem Statement 解法 二分探索でやります。ok(x) = (C 回カットした後の K 番目の数が x 以上になるような切り方が存在するか) というチェック関数を作れればハッピーです。sticks[i] が …

こういうの苦手っす。 問題 TopCoder Statistics - Problem Statement 解法 近いところでどう動くのが最適かを調べるのは面倒なので, 銀がゴール付近に近づいたら, あとは幅優先探索でごまかす, という方針で解きます。ゴール付近に近づくまでは, 斜めに動き…

未だに Nisoku ってどういう意味かよくわかってないんですがどういう意味なんでしょう? 問題 TopCoder Statistics - Problem Statement 解法 入力される数が 1.5 以上なので, 大抵の場合 a+b とするより a*b としたほうが得な感じがします。 a 後は, どのよ…

問題 TopCoder Statistics - Problem Statement 解法 数字を小さい順に並べると, i+1 番目の数字は, i 番目の数字が取れる数字はもちろん取れるし, それより大きな数字も取りうる可能性があります。よって, 数字を小さい順に並べて i 番目の数が取りうる数字…

問題 TopCoder Statistics - Problem Statement 解法 まず入力の性質に注目します。カードの枚数を n として, 1, 2, ..., n の n 頂点からなるグラフを考えます。taro[i] から hanako[i] に辺を引く, ということを考えると, 各頂点は必ず次数が 2 になるので…

問題 TopCoder Statistics - Problem Statement 解法 半分全列挙します。N を与えられる文字列 s の長さであるとして, n = N/2 とします。最後の n 文字を, red と blue のどちらにするかは O(2^n) で決められますが, この時 red の文字列のほうが長い場合は…

問題 TopCoder Statistics - Problem Statement 解法 10 の倍数のうなぎは例えば 30 -> 20, 10 -> 10, 10, 10 というように, n*10 のうなぎは n-1 回の切断で n 個の長さ 10 のうなぎを錬成出来ます。ということで, 10 の倍数で短いうなぎから切断していくと…

問題 TopCoder Statistics - Problem Statement 解法 x 方向と y 方向の動きが独立であることを利用します(こういう系の AtCoder であったような気がするけどなんだっけ)。x 方向に動く回数を sx, y 方向に動く回数を sy とすると, 回数がこのようになる確率…

問題 TopCoder Statistics - Problem Statement 解法 結論を言うと, 5 で割った余りが 0 か 2 だと先手の負けで, それ以外は先手が勝ちます。勝ち負け表書いたら気づきました。理由は, Nim と同じような証明でいけます。 まず 0, 2 で必敗であることは明らか…

問題 TopCoder Statistics - Problem Statement 解法 N 個の箱とは別の箱 (another box) を「箱」と呼び, i 番目の箱を指すときは 「i 番目の box」とか言うことにします。この問題では, j 種類目のりんごを箱から取り出す確率を直接求めるのではなく, 箱か…

微妙に理由わかってないんですが解説ないのでうーん。ていうかこれ… 問題 TopCoder Statistics - Problem Statement 解法 理由がよくわからないんですが, ある集合 s を選んで, その集合同士でのみジュースのやり取りをした場合, 必ずジュースの量の割り当て…

問題 TopCoder Statistics - Problem Statement 解法 dp[n][r][g] = (n 個目の箱の時点で, 赤色のりんごが r 個, 緑色のりんごが g 個入っているような場合の数) という dp は簡単に解けます。これがわかれば, 求める確率は, dp[N][r][g]/(2^n-1) * r/(r+g) …

問題 TopCoder Statistics - Problem Statement 解法 8x+7 と 4x+3 ですが, 8x+7 = 2(4x+3)+1 です。 また, 4x+3 = 2(2x+1)+1 です。つまり, これらの数は, すべて 2x+1 という式を元につくられています。init に init = 2*init+1 という操作を繰り返して, i…

問題 TopCoder Statistics - Problem Statement 解法 ある状態において, ぷよを全消しにするためにあと必要な最低限のぷよの個数を考えます。 例えば, 今の状態が RRBBR とかだったら, 全消しにするためには, RRBR とすれば良いので, この状態では必要なぷよ…

div2 med のほうが難しい説ある。 問題 TopCoder Statistics - Problem Statement 解法 0, 2, 5, 7 を決めると, それ以外の頂点は 隣り合った要素と別ので Y ならどんな色を使っても OK です。よって, 0, 2, 5, 7 の色について全探索して, 残りの色が何通り…

問題 TopCoder Statistics - Problem Statement 解法 二乗した数はたかだか 18 桁で, 各数字は 最大 9 なので, 数字の和は 162 以下です。 なので, 二乗する前の数字の各桁の和は 12 以下でないとダメです。ということで, 桁の和が 12 より大きくなったら枝…

問題 TopCoder Statistics - Problem Statement 解法 各カードについて, あり得る数字がどれだけあるかを列挙することを考えます。 m = colors.size() としましょう。で, ok1[i][j] = (i 番目のカードが j という値をとる可能性があるかを 0 〜 i 番目のカー…

問題 TopCoder Statistics - Problem Statement 解法 区間 dp っぽく解くことが出来ます。まず前処理で, 各頂点間の最短距離を覚えておきましょう。この時, 頂点 0 と cities のどこかの頂点の距離が INF (要するに辿りつけない) だったらその頂点を調べるの…

問題 TopCoder Statistics - Problem Statement 解法 辺の重みの付け方は 2^(n-1) 通りしかないので, 雰囲気としては dp[v][d] = (頂点 v を root とする部分木で, 直径は d 以下である場合の数) とすれば, 直径が d である確率は, (dp[0][d] - dp[0][d-1]) …

SRM 677 に参加しました。easy かなり苦しかったけど通してレートが少し上がりました。最近 easy が解けなくてレート下がってたし, システムテスト通った時めっちゃ興奮しました。やっぱいいですね。 問題 整数の組 (a, b) および (newA, newB) が与えられる…

問題 TopCoder Statistics - Problem Statement 解法 ここに書く解法は, topcoder の解説を参考にして書いてます。 http://apps.topcoder.com/wiki/display/tc/SRM+527 こっちのほうが証明とかいろいろ丁寧です。英語面倒ですがこっち読むほうがオススメです…