貪欲に貪欲を出し続ける出題者...。 250 でかい素数が与えられて、部分的に素因数分解の結果が与えられるので、残りを復元せよ、という問題。 部分的に分かっているので割ってから、素因数分解するだけでいいらしい。やたらと大きい数が出てくる場合に、どこ…

問題が枯渇しているからつまらないのかも知れないけれど、今日のは出題者の悪意しか感じない。 250 N個のものを確率に従って抽選するという操作を延々と繰り返す。抽選結果に応じて、次の抽選までの時間が決まる。抽選を開始した時刻から経過した時刻が与え…

最近の問題はつまらない。多分情熱が冷めたんでしょうね。 250 点が適当に与えられるので、原点を中に含む三角形になるような点の選び方は何通りか答えよ、という問題。 適当に角度でソートして、180度よりも大きくならない範囲で選択してやればいいらしい。…

変なセット？ 250 グラフが与えられるので、ツリーになっている部分グラフの、枝の重みの合計値の最小値を答えよ、という問題。 枝の重みでソートして、適当にMST作るだけのような気がする。 550 二部グラフの右側の点の数と左側の点の数と、最大マッチング…

変なセット？ 250 グラフが与えられるので、ツリーになっている部分グラフの、枝の重みの合計値の最小値を答えよ、という問題。 枝の重みでソートして、適当にMST作るだけのような気がする。 550 二部グラフの右側の点の数と左側の点の数と、最大マッチング…

TopCoderってこんなにつまらなかったっけ？(出題センス的な意味で) 250 1,3,5,7,9,...を二人に分けたときの、合計値として正しいか答えよ、という問題。正しいときには、一人目はいくつの数字を割り当てられているか、その可能な最小値を答えよ、という問題…

Adminは問題の難易度をもう少しまじめに把握した方が良いと思う。 300 N*N*Nの領域に1*1*1のキューブが適当に連結に詰んである。各方面から見たときに、見える見えないの情報が与えられるので、そんな積み方は可能か答えよ、という問題。 取り敢えず明らかに…

実装大変な問題。 250 1から2Nまでの整数をN個ずつ二人に分ける。自分の持っている整数が分かっていて、相手がどういう風に並べているかも部分的に分かる。自分の持ってる整数を並び替えて、相手の並べている整数と順番に比較して、大きくなる回数をできるだ…

500が解けるか解けないか。 250 2次元テーブルに整数値が入っているので、矩形領域の和を高速に求める下準備をしなさい、という問題。 やるだけ。コピペの人が多いんだろうな。 500 二次元平面上に、ランダムにK個の点を配置して、一番近い点同士に辺をはっ…

めんどくさい... 250 折れ線が与えられるので、一部オーバーラップしてもいいので、二つの部分折れ線を見比べたとき、相似形になっているもので、一番長いものを答えよ、という問題。 愚直にやるだけ。一部だけ傾き見ていると、全体として相似形じゃなくなる…

なんかめんどくさいだけに見えた。 250 商品の買われた個数が与えられる。それぞれの人が高々一個しか各商品について購入していない。N人の人がいるとき、K個以上の商品を購入した人の数の最小値を答えよ、という問題。 K個以上買った人は全部一個ずつ買った…

よくもまぁここまでひどい問題を...。 250 整数配列が与えられるので、各要素の値だけ現在位置から二次元平面状の任意の方向に移動するという操作を延々と繰り返して、目的地を目指すとき、最小の移動回数を答えよ、という問題。 ステップ数がやたらと多い場…

ゆるめのセット。 300 配列が与えられるので、特定の整数からK個連続で拾ってきて、それぞれを2で割り切れる回数に変換した配列であるか答えよ、という問題。 偶奇が交互に出てくるので、偶数側を拾って、二で割ってから再帰呼び出しするだけ。一番大きいや…

愚直にやるだけ気味なセット。 250 N*Nのマス目が白か黒に塗られている。特定の行を白または黒に染める操作を行って、どの列を見ても同じ色がN/2+1個以上続いていないようにしたい。必要な操作の最小回数を答えよ、という問題。 とにかく真ん中の二列を白と…

嫌いじゃないけれど、セットとして良かったのかは微妙。 250 トポロジーが木のグラフが与えられるので、二点間の距離が同じ集合のうち、ノード数が最大のもののノード数を答えよ、という問題。 トポロジーが木なので、三つ以上の点で、そういう条件を満たす…

実装重たい。というか面倒。 250 四角い穴を四角い板で塞ぎたい。板の角は全部穴の外にないといけない。必要な最小の板の枚数を答えよ、という問題。 穴よりも長い板を拾ってきて、できるだけ横幅広く塞いでいく感じ。やるだけ。 500 二種類のどれか分からな…

やるだけセットだったそうです。 250 整数Nが与えられるので、N=M^(Mの約数の数)なる最小のMを答えよ、という問題。 Nは2以上なので、約数の個数が1個という状況はあり得ない。ということで、2以上の根を拾ってきて(ここ間違えた)、後は約数の数をループする…

強実装はよそでやって欲しい。 250 文字列から、異なる二文字を除去していくという操作を繰り返していったときに、最後に残る可能性のある文字をすべて答えよ、という問題。 愚直にシミュレーションやるだけ。途中端折らないのが正解っぽい。 500 なんかグラ…

楽しくないな〜、をどうにかしたい。 300 文字列の一部を反転させて、辞書順で最初になるようにせよ、という問題。 先頭の位置を決めてしまえば、後は全部試すだけ。先頭の位置は、自分よりも後ろの文字でもっといいのがあるかないかで、決められる。 500 な…

思考停止してたので解けるわけない。 250 なんか変なサイコロを二人が振るので、Aさんの目の合計の方が大きかったよ、という情報から、Aさんの目の期待値を求めよ、という問題。 条件付確率の問題。やるだけ。 600 有向グラフが与えられるので、目的地までの…

最近のSRMは問題がつまらない。答え自明なのに実装できなくて解けないからだけど。 250 文字列が入力で与えられるので、ランダムに文字を並べ替えたときに、回文になっている確率を求めよ、という問題。 実装あるのみ...。とても重たい...。 500 二次元盤面…

なんかイマイチなセットだった。 250 長さがまちまちのものがあって、長くすることはできる状況で、K本同じ長さのものを作るときに、必要な長さの追加量の最小値をそれぞれのKについて求めて、XORした結果を返せという問題。 適当に最適化してやるだけ。 450…

相変わらず良く分からない問題を出すなぁ...。 350 スイッチのオンオフをして、目的の状態を順番に作っていきたい。最小何回のオンオフが必要か答えよ、という問題。 なんか頑張れば良さそうに見える。切り替えるときに、いかについでに切り替えておくか、み…

出題意図が分からない...。 300 N*Nの盤面に二種類の果物がいくつか置いてある。果物を空いているマスに動かすことにより、矩形領域の中を特定の果物だけにしたい。そのような矩形領域の面積の最大値を答えよ、という問題。 取り敢えず矩形領域を全部探索し…

久し振りに普通のセットに見えたが、簡単だとそういう扱いになるのだろうか？ 250 N都市間の接続状況が与えられる。任意の二都市間の移動を最短路ですることを考えるとき、同じ距離の場合はランダムに道が選択されるとして、使用される回数の最大値がK以上の…

余計な問題はいらない...。 275 円がいくつか与えられるので、それぞれの円について、全部含むか、まったく含まないようにして円を配置したい。そのような円の半径の値は、指定された区間にどれくらいの割合で存在するか答えよ、という問題。 出てくる座標を…

なんかひどいセットだった。他のコンテストで使うならまだしも...。 250 16本の柱を4x4に敷き詰めて並べたときに、地面とか他の柱とかに接してない部分の表面積の合計の最大値を答えよ、という問題。 位置ごとにスコア決めて、適当に配置していけば良いらし…

スタックオーバーフローを久し振りに観測した。 250 整数ペアを、一方を他方に足し込むという方式で更新していく。二つの整数ペアが与えられるので、元は同じ整数ペアで合った可能性があるか答えよ、という問題。 逆向きに戻るのはユニークなので、合流する…

スピード勝負セットってわけでもなかったのだが、英文が読めなかったので、結局そっちに巻き込まれた。 250 2個以上の石が積んである山を捕まえて、二つに分けて、他の二つの山にくっつける、という操作を交互にやっていて、先にできなくなった方が負けとい…

普通のセット。時間が時間だからかな？ 250 DAGが与えられる。親が二つかないかのどちらかのノードになっている。このDAGに色をつけるとき、あるノードの親が必ず色違いになるような配色はできるかどうか答えよ、という問題。 要はあるノードの親になってい…