Programming Contest

こんにちはtatsyです。 本日はSRM610に参加しました。結果はChallengeして、Challengeされ返され50ptどまり。Mediumは時間内に解けなかったですが、今回のMediumは下手したらEasyより簡単だったんじゃないかな？その辺も含めて解説していきたいと思います。 Easy (250点) 問題 小さなマス目で区切られた長方形のボードがある。各マス目には白か黒の色が塗られている。このボードの ...

こんにちはtatsyです。 本日はSRM609の解説をいたします。さっそく参ります。 Easy (250点) 問題 ある文字列がk個の連続する’>’で始まり、そのあとにk個の連続した’<‘が現れて終わる、というようなものを魔法の呪文と呼ぶ。たとえば”»>«<“は魔法の呪文である。ある’>’と’<‘からなる文字列が与えられたとき、適 ...

こんにちは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点) この問題は与えられた文字列をある方法にしたがって変更して回文になるようにするというも ...

こんにちは。tatsyです。 なんとも分かりづらいタイトルですが、この記事ではある配列が与えられたときに、各要素に対して自分より右(もしくは左)にある自分より大きいもののうち一番近いものを割り当てる問題を解きます。 やっぱり分かりづらい・・・つまり、例を示すなら、右にある自分より小さい数を見つけるとして、 入力: [4, 2, 3, 5, 1] 出力: [2, 1, 1, 1, -1] みたいになります。一番右の1は自分より小さい数がもう右にないので- ...