こんにちはtatsyです。 最近はSRMの解説記事ばかりでしたが、たまにはもう少し実践的なことを書こうかと思います。というわけで特に理由はないのですがMCMCについて解説したいと思います。 MCMCとは？ マルコフ連鎖モンテカルロ法(MCMC)は多次元空間内の点を確率分布に基づいてサンプリングするための方法で、最もシンプルな応用例は適当な関数と確率密度関数のペアに対して期待値を計算するというものです。 積 ...

こんにちはtatsyです。 昨日行われましたSRM611の解説をしたいと思います。今回はEasyもMediumもコンテスト中にはよく分からずでした。まだまだ練習が足りません。では、早速Easyから。 Easy (250点) 問題 自然数からなる数列A, Bが与えられる。このときLCM(A)とはAに含まれる数の部分集合のLCM(最小公倍数)を全て含むような集合になっている。このときLCM(A)とLCM(B)が同じにな ...

こんにちは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と書かれたマスを隣り合ったマスが違う色で塗られるように塗った時、必要な色は何色かを答える問題 ...

最近Half-Edge構造のプログラムを書いていて、vectorの性質で気をつけるべきことがあることに気付いたので備忘録的に記しておきます。 Half-Edge構造のことをしっている人ならなんとなくわかると思うのですが、あるオブジェクトに何らかの別のオブジェクトを指すポインタを持たせておきたい場合があると思います。 今は分かりやすくするためにオブジェクト1とオブジェクト2と呼ぶことにしましょう。 オブジ ...

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