TopCoder

SRM433

まだ結果は出てないけど0点確定でここ一年ぐらいで最悪の出来. Interval中に250の最も大きいケースをテストしてみたらTLEが帰ってきて愕然とした.手元のテストでは2秒弱で答えが返ってきてたので気付かなかった. 追記:Rate 2010->1893まで落ちた. あと,問…

SRM 431

ここ2連続ほど500を落としている. 250 Math.atan2を使うだけ,期待値なので各線分ごとに当たる確率をもとめて足すだけ. 500 15分ぐらい読んだけど,問題の意味が全く分からなかった 1000 ある点を左上にして右下方向に長方形を作ることを考えると極大なも…

SRM 429

250 個々のセルに対して何個の部分長方形に含まれているのかを数えればよい 500 全部の係数をかけた値をどれか一個の変数に代入して、一次式を解いていけばよい.

SRM 428

250 nextPermutationするだけ 500 解法は思いついたけど時間内にバグが取れなかった。まず高々k種類の文字列を用いて長さnまでの回文の合計を とおく。つぎにちょうどk種類だけ用いて作れる回文の数をg(k)とかくと となる。求める解は となる。 行列乗算でや…

SRM427

250 いろいろと計算するとgcdをとればよいことが分かる. 600 実験するとdig(x)は循環する*1ことが分かるので、剰余をとるだけなんだけど初期化をミスしてSystem testで落ちる 900 Pでの余りの個数に注目してやると、残り個数の状態(個数に関してソートした…

SRM 426

250 シャッフルをシミュレーションして、出現頻度の高い順にK個とっていけばよい. 500 三分探索.最初EPSを1.0E-9にとってたけどよく考えると結果には×2000できいてくるのに気づいて、アドホックに1.0E-15に訂正して再提出.Challengeフェイズでだれも三分探…

SRM 425

250 状態空間が4^14ありそうだけど,実際はループができない経路というのはそんなにはないのでdfsするだけ. 500 状態空間が25C5=53130通りしかないので幅優先で通るのだけど、なぜか終了状態を定めてそことの距離の最小のものを出すというアルゴリズムを書い…

SRM424

600より900の方が簡単だったような気がする. 250 9から2まで順番に割っていくだけ. 900 x[i]の取りうる値は多くないので,区間の合計をFenwick木を使って問い合わせればよい.

SRM 422

250 二つの独立な事象A,Bのどちらかがおこる確率は 1-(1-事象Aがおこる確率)*(1-事象Bがおこる確率)で出る 500 まず最初に移動可能な集合とその移動にかかる時間を計算する。あとは入口にいる人の集合と地図がどちらにあるかの状態に関してダイクストラすれ…

SRM421

250 二分探索。 500 異なる長さの n とりあえず、切るときは等分割にすればよいというのは分かったのだが、そこから最大の長さのピースの部分を固定してとか考えていたら50^2 * 10^5 = 25 * 10^7でJavaだと終わらないよなと思っていた。あとであっている人の…

SRM420

250 やるだけのはず。実は最長のループがどの程度になるかは見積もれてなかったりするけど。 500 DP。ただし5000*5000の配列を確保しようとするとメモリの確保に失敗して落ちる。 1000 ある金額以上の払い方に関してはとりあえずは最大価値のもので減らして…

SRM 419

250 undoが来たら現在の状態をいままでの状態の中でundoの指定時間より前の最も遅いものの状態に変更すればよい。 500 残りの石と現在のプレイヤーの状態に対して、このままだとどのプレイヤーたちが勝つかという値を返す。注意すべきこととしてゲームが強制…

SRM 418

250 N個の数からM個選ぶくじを買ったときK個以上あたっている確率を求めよという問題。N 500 次数2以下のグラフの最大重み独立集合を求めよという問題。次数2以下のグラフは孤立点か直線か円しかなくて、孤立点は単に重みを足してやればよくて、円は適当な一…

SRM417

250 文字列処理。トータルのスコアを更新するときにprefixのスコアを更新するのを忘れて落とされた。 500 与えられた平面図が立方体の展開図かどうか判定しろという問題。立方体の展開図の形は合同なものも含むと11通り(cf:http://www004.upp.so-net.ne.jp/s…

SRM416

250 2進数Nが与えられた時にNと1のビットの数の個数が等しいNより大きい最小の数を返せという問題。 数字を配列に直してnextPermutationするだけ。 500 要約すると与えられた数M( 今6つの数を とおく、このとき総和は となり、 とおくと、s

SRM415

250 重い荷物から順にクレーンに割り当てるというのを繰り返せばよい 500 n( なるSを求めよという問題になり、これは になるため、ナップザック問題と等価になる。だから全探索するしかないんだが適当な枝刈りをしただけでは間に合わなくて、n個の集合を半分…

SRM413

250 各項の値からdが入る区間が求まるので、すべての区間の共通部分の左端の値を返す。 500 与えられたi , p , q , x , yに対して を計算しろという問題。ただし p >= 2 , q >= 2 , i そのまま計算するとp=q=2のときiに比例するだけの時間がかかるので sqrt(…

SRM 410

Rateが1969->2000で2000点台に 250 連結している部分はすべて完全グラフに直して、頂点が一個の部分に関しては最大連結成分のところに合わせればよい。 500 開始アドレスの候補となる位置は与えられるアドレスの部分かk個前で、高々100個程度なので100^3のDP…

SRM409

250 本質的には先頭からできるだけ重ねて連結するだけ、ただし連結するときにx_i 600 要約するとn,m 900 正解しているひとのコードを見ると非常にわかりやすい。要は一回の試行時にあるマスが塗られる確率がpならばK回の試行で塗られる確率は1-(1-p)^Kなので…

SRM 408

250 毎回ソートして、高さが高いものから使っていく。 500 ターゲットの点をルートとした木を考えたときに、リーフ以外の点に飴がk個置かれているという状態がokならばその点の飴を全部除いて、子供に2k+1個置いた状態もokなのでなるべく深い部分に飴が集中…

SRM407

250 上司、部下関係のグラフが与えられた時に、部下を一人も持たない人の給与を1,そうでない人の給与を自分の部下の給与の合計と定義するとき、支払われる給与の総計を求めよという問題。メモ化再帰を書くだけ。 500 状態空間は3^12しかないので、これもメ…

SRM406

250 8!個のすべての順列に対して何本線が引けるかを計算して最大のものをとればよい. 500 高々12*12ぐらいの数字(-100から100)が書かれた紙を折っていく、折った時に重なった数字は合計する。折ってった時のセルの数字が最大となるように折れという問題。 …

SRM404

順位があまり良くなかったためRateが1880->1775へと下がった 250 三角形の下から値を決めていく.もしくは全部の要素を見ていって決定できるところがあったら決定するを繰り返して,全部埋まるまでループする. 500 長さが3000までのintの配列 A が与えられ…

SRM402

250 大きさがn(A[j]となっているペアに対してのみ行う)。たとえば(1,4,3,2)で4と2を交換すると(1,2,3,4)となって一回で終了するが、3と2を交換した場合(1,4,2,3)で終了しない。このとき交換の回数の期待値を求めよという問題。 ここで配列Aに関して交換の回…

SRM401

250 与えられたn(= a_2 >= a_3 >= ... >= a_n, a_i 再帰、もしくはDPで解ける。 550 次の二つの媒介変数表示の曲線が与えられたとする。ここで2つのt,sは独立に動く、またt,s以外の変数は与えられる。 このとき、二つの曲線が交わるかどうかを判定して、交わ…

SRM400

250 n(素数、q>=2)の形で表せるかどうか答えよ、表せるならば{p,q}も求めよという問題。 qを固定したらp=exp(log(n)/q)で求まるので、これで出して素数かどうか確認する。 500 1,0からなる文字列s1,s2が与えられたときにs1の部分文字列をひっくり返していく…

最大流

今日のSRM399で最大流の問題が出てて、結構よく出てライブラリと持っていないとその場で書くのは難しいのでコードをここに張っておく。 class MaximumFlow { int size; int flow[][]; int capacity[][]; int q[]; public MaximumFlow(int capacity[][]){ siz…

SRM398

250 数字の位置の場合の数は高々6通りで、演算子の場合の数は3^3通りで6*3^3通りに対してすべて試す。 500 DP。行列の位置、パスの長さ、前通ったパスの番号をキーとする。本番で書いたコードは端の部分の埋め方が間違っていたせいでSystem Testで落ちた。 1…

SRM397

賞金付きで人が多かったせいか、サーバの不調で20分遅く始まる。 250 高々長さが8の配列に対して、k個の連続する区間を反転させるという操作を繰り返したとき、最短何回でソートされた状態にできるかを返せという問題。 状態空間が8!=40320しかないことに気…

SRM396

250 周期pの場合は文字列をp文字おきに取った物に対してはその中で最も多く出てくる文字に変換したときの変換数となるので,それを各周期に対して計算し最小値を返す. 500 同じブロックの2点が同一軸上に乗りかつ間に空白がある時に空白を"#"で埋めるという…