TopCoder

こんにちはtatsyです。 最近はというと、少し研究の方に集中しようということでSRMをさぼっておりましたが、最近練習をぼちぼちやっております。 というわけでSRM607の問題を解きましたので軽く解説をしたいと思います。 この回の問題は Easy: DP (期待値) Medium: 条件整理 という感じの解法になっております。 とはいってもMediumは問題の条件をいかに同値な条件に置き換えるかというところなので、整理とはちょっと違うかも ...

さっき前回のものを解説したばかりですが、595回も解説します。 ちなみに今回は30分でEasyだけ通したけどレート全然あがらず。 やはり連続でEasy通さないとダメなのか。 気を取り直して解説行きます。 Easy (250点) この問題ではボールが何個か用意されていて、色塗りロボットがこのボールに白か黒かの色をつけます。 色をつける作業はM回行われて、それぞれの回では位置L[i]と位置R[i]の間にあるボールが黒か白 ...

今回はSRMに寝落ちして出ていない(Registrationもしてない)のですが、Easyだけ備忘録的に解説します (遅い)。 Easy (250点) この問題はある太陽系を調べていて、現在AとBの二つの調査結果が得られているという前提。 この調査結果には惑星の大きさと太陽からの距離が記録されていて、記録順は太陽から近い順になっている。 このときに2つの調査結果から考えうる最小の惑星の数を答えるというのが問題の目的 ...

今回のSRMはEasyが結構実装量が多かったです。最後まで答えがなかなか合わなくて提出できたけどChallengeされてしまいました。気を取り直して解説行きます。 今回の問題は Easy: 探索 + 条件把握 Medium: DP という感じの問題構成でした。 Easy (250点) この問題は最大50×50のボード上のマスのいくつかにXが書かれていて、Xと書かれたマスを隣り合ったマスが違う色で塗られるように塗った時、必要な色は何色かを答える問題 ...

今回の問題は Easy: 貪欲 + ひらめき？ Medium: 動的計画法 てな感じでした。Easyは思いつけばすぐですが、Mediumはさっぱりですね。 それでは解説行きます。 Easy (300点) この問題はR,G,Bの三色のボールを決められた順番でテーブルに1列に置いていくゲームに関する問題です。 ボールをテーブルに置いた時に得られる点数には次のような規則があります。 ボールを既に置いてある列の端に置く場合、得られる点数はすでにある列の中の ...

はい、では今日もさっそく行ってみましょう。 今日のEasyのみ解説します。 Easy (250点) この問題は横一列のマス目がいくつかあって、そこに右にしか動けない駒と左にしか動けない駒がいくつか置いてあります。 その駒を動かして初期配置beginから目的配置targetに変更できるかどうかを答えます。 まず、注意したいのが駒の順番は入れ替わらないということです。 ですから、beginとtargetの両方で左から順に ...

今回のSRMはEasyでなかなかのChallenge祭りになっていました。 僕も何とか参加して100点稼ぎました。肝心の解答の方は他の人にChallengeされてしまいましたが、レートが上がったので良しとします。 今回の問題はEasyが貪欲法、Mediumがグラフの問題です。それでは、さっそく解説します。 Easy (250点) この問題は与えられた文字列をある方法にしたがって変更して回文になるようにするというも ...

最近、Div1の底辺で迷走中のtatsyです。 今日は久しぶりにSRMの解説をやりたいと思います。 今回はEasyとMiddleの2問を解説します。問題のカテゴリとしては、 Easy (単純計算) Middle (幾何) です。 それでは、見ていきましょう。 Easy (250点) この問題は、あらかじめターンごとに進める歩数の決まった状況下で一番遠くに行ける場所はどこかを探す問題です。 ある数Nが与えられて、Nターンにわたりiターン目にはi ...

今日はひさしぶりにSRMにでました。 Easyの問題は見るからに二分探索で絶対あってると思って書いた解法がなぜか例3を通してくれず、結果1問もできませんでした。 いや、間違っていたのは非常に単純で、単にソートをするときにStrengthとCountを対応させるのを忘れてただけなんですが。 こんなイージー・ミスをしてついにDiv2に落ちてしまいました。はぁ、なにやってんだろ自分。 気を取り直して、今日も解説 ...

少し遅くなりましたが、今回のSRM579も解説をしていきたいと思います。 今回はEasyとMiddleを解説します。僕はどちらもSystem Testで落ちましたが。 この記事に書かれているコードはちゃんと通るコードなので、そこはご心配なく。 Easy (250点) この問題はウィンドウとバッファがあるテキストエディタを扱う問題です。 あなたが文字を打っていくとバッファに文字がたまっていき、Enterを押すとウィンド ...