問題 TopCoder Statistics - Problem Statement 解法 入力の名前が長いので, n, m とします。 見た目からして行列累乗っぽい感じがします。具体的には, まず dp[i][j] = (i 日目に場所 j にいるような場合の数) というのを i で, それを調べ終わったら m/n …

問題 TopCoder Statistics - Problem Statementn 頂点の無向グラフが与えられる。このグラフから辺をいくつか選ぶとき, 以下の条件を満たす選び方の場合の数を求めよ。条件: 選んだ辺上の頂点を 2 次元平面上でどのように配置しても(ただし 3 頂点が同一直線…

med にしてはかなり簡単ですね。復帰戦だったのでちょうど良いけど。 問題 TopCoder Statistics - Problem StatementU さんと K さんがゲームをする。ゲームは S = {L, L+1, ..., R-1, R} という数の集合を使って行う。そして, 集合 S の中から何らかの数 X …

院試が終わりました。受かったらそれについてもなんか書きます。 問題 TopCoder Statistics - Problem Statement0 ～ N-1 番までの商品を順番に買っていく。それぞれの商品には値段と重さがあり, 値段は 1 か 2 である。 あなたは, 今までに買った商品の重さ…

問題 TopCoder Statistics - Problem Statement白い頂点と黒い頂点が与えられる。白い頂点からなる線分と黒い頂点からなる線分で, 交差するものは存在するか。 解法 実は, 線分が交差する場合, 白い頂点の線分か黒い頂点の線分のいずれかはその凸包のいずれ…

問題 TopCoder Statistics - Problem Statementクリップボードが与えられる。これは H*W 個のセルがあり, それぞれのセルは透明か RGB いずれかの色をしている。このクリップボードを, 左上が(0, 0), (1, 1), ..., (T-1, T-1) になるように (0, 0) が一番下…

問題 TopCoder Statistics - Problem StatementAlice と Bob がゲームをする。ゲームは交差しないいくつかの円が書かれた平面上で行う。 まだ円内に赤点がない円を選ぶ。 その円内に赤点をいれる。 赤点を入れることができないほうが負け。 両者が最適に動い…

問題文長すぎな。 問題 TopCoder Statistics - Problem StatementN 種類のボールがある。これらは以下のような特徴がある。 大きさが決まっている(medium と large の 2 種類がある) 種類ごとにいくつあるか決まっている 種類ごとに色が異なることは保証され…

問題 TopCoder Statistics - Problem Statementあなたは K 回コインを投げるゲームをする。コインは表裏がそれぞれ 1/2 の確率で出る。ルールは以下のとおりである。 コインを投げてまだ何も書いてない面が出たら, その面に好きな数字を書く。 出た面に書か…

問題 TopCoder Statistics - Problem Statementグラフが与えられる。各頂点にはスコアがある。 このグラフから K 本の辺を選び, 以下のようにスコアを計算する。頂点から少なくとも 1 本の選ばれた辺が伸びている場合, その頂点のスコアを得られ, その和がス…

問題の勘違いはな。 問題 TopCoder Statistics - Problem Statement 以下の条件を満たす文字列を求めよ。ただし, 解が複数ある場合は辞書順最小のものを求めよ。 文字列の長さは N 文字列は 'a', 'b' のみで構成される 配列 x が与えられる。長さ i+1 の部分…

問題 TopCoder Statistics - Problem Statement頂点の接続関係が与えられる。 以下の性質を持つような木の場合の数を求めよ。 葉を除くすべての頂点は, 子を 1 つか 2 つ持つ 木の根からの距離を rank とすると, rank = k の場所には 2^k 個(ただし rank が…

問題 TopCoder Statistics - Problem Statementチェスのナイトのようなものを考える。チェスのナイトは今いる位置から (+1, +2), (+1, -2), (-1, +2), (-1, -2), (+2, +1), (+2, -1), (-2, +1), (-2, -1) と動くことができるが, 今回のナイトは (+a, +2), (+…

珍しく秒で解ける問題でした(ここまで簡単じゃなくていいけどこういうの 1 つある方が参加する方も楽しくて良いです)。 問題 TopCoder Statistics - Problem Statementn 人の人がいる。それぞれの人には強さ s[i] が定義されている。n 人を 3 グループに分け…

問題 TopCoder Statistics - Match OverviewDAG が与えられる。次の条件を満たす頂点集合 S の最大の大きさを求めよ。 条件: 任意の異なる 2 つの頂点 i, j S について, i から j へのパスも j から i へのパスもない。 解法 この問題に関して, dilworth の…

問題名がめっちゃヒント。 問題 TopCoder Statistics - Problem StatementH 行 W 列のグリッドが与えられる。最初グリッド上のセルはすべて 0 であるが, rowCount 回どこかの行を選んでそこのすべての 0 を 1 に変え, 1 を 0 に変える, という作業をしたのち…

問題 TopCoder Statistics - Problem Statement無向グラフが 2-edge-connected とは, 任意の頂点の組(u, v) について, グラフ上のどの辺 e を削除しても, いまだ u から v へのパスが存在することを言う。 n 頂点の無向グラフ G が与えられ, 以下の条件を満…

問題 TopCoder Statistics - Problem StatementN*M のグリッドを考える。セルのいくつかはすでに黒色か白色に塗られている。残りの箇所を, 以下の性質を満たすように塗りたい。 各色のセルは連結である。 各色のセルは凸である。ここで, 凸とは, 各行, 各列…

問題 TopCoder Statistics - Problem Statement最初に十分たくさん 0 が詰まっているスタックがある。これに次のような操作をする。 スタックに数 p を入れる スタックから 2 つの数 p, q を取り出し, p+q を入れる このような操作を順番にするプログラムが…

いろんな意味で嫌らしい問題だった… 問題 TopCoder Statistics - Problem Statementi 行目に i 個のボールを並べるようにして N 行の三角形を作る。この三角形に色を塗るが, 塗る色は R, G, B の 3 種類のみ 三角形内の任意のボールについて, 隣り合ったボー…

問題 TopCoder Statistics - Problem Statementあるオオカミは, 毎夜毛の色を変える。毛は colormap[i][j] = Y のとき i -> j に色を変えることができる。毛を変えるアルゴリズムは, colormap[i][j] = Y を満たす 最小の j に毛の色を変える, というものであ…

問題 TopCoder Statistics - Problem Statementn 文字の文字列が与えられる。maxSwap 回以内の隣り合った文字の交換を許すとき, 「同じ文字が連続して p 個並んでいる」という性質を満たす最長の部分文字列の長さを求めよ。 解法 真ん中の文字を決めます。で…

問題 TopCoder Statistics - Problem Statement 解法 素直に実装するだけです。あんまりおもしろくない… const int SIZE = 1000; bool done[SIZE][SIZE]; class RotatingBot { public: int minArea(vector <int> moves) { int n = moves.size(); if (n == 1) retu</int>…

はぁ… 問題 TopCoder Statistics - Problem StatementA, B, C が与えられる。1 解法 三角形の辺の組としてあり得ないものを数え, それを A*B*C から引く, というように考えます。あり得ない辺の組としては, a が最大のもの(a >= b+c を満たす) b が最大のも…

問題 TopCoder Statistics - Problem Statement魔法使いとあなたがゲームで勝負をする。ゲームでは, 二次元座標上にいくつかの帽子を置き, そのいくつかの帽子の中にはコインを隠しておく。 あなたは, numGuess 回だけ, 好きな帽子の中身を見ることができる…

問題 TopCoder Statistics - Problem Statement円錐のセットを 2 つ用意する。2 つのセット Top, Bottom は次のように使う。 Top の円錐を Bottom の円錐の上にかぶせるように乗せる。 ここで, Top の円錐の半径は Bottom の円錐の半径より小さくなければな…

オーダー落とせずに死んでました。 問題 TopCoder Statistics - Problem Statement1 ～ X の目が書いてあり, 面が N 個あるさいころを二つ用意する。この二つのさいころの目はすべてバラバラである(よって 2*N このさいころを使って簡単なゲームをする。さい…

問題 TopCoder Statistics - Problem Statementn 本の木が与えられ, それぞれは高さ h[i] である。レベル X の魔法を使うと, それぞれの木の高さを, [max(1, h[i]-X), h[i]+X] の範囲に変化させることが出来る(ただし高さは整数にしなければならない)。この…

問題 TopCoder Statistics - Problem StatementH*W の長方形に, 以下のように数字が書いてある。 (1 行目): 0, 1, ..., W-1 (2 行目): W, W+1, ..., 2*W-1 ... (H-1 行目): (h-2)*W, (h-2)*W+1, ..., (h-1)*W-1ここからうまいこと長方形の区間を取って, その…

問題 TopCoder Statistics - Problem Statementw だけ離れて二本の柱が立っている。 一方の長さは 1, 2, ..., x の長さを等確率で取り, もう一方の長さは 1, 2, ..., y の長さを等確率で取る。二本の柱の先端距離の期待値を求めよ。 解法 1 本目の柱と 2 本…