こんにちはtatsyです。 今回はTCOのRound2Aを解説します。 Easy (250点) 問題 4×4のボードがある。16個のブロックが用意されていて、それぞれのブロックは底面が1×1、高さがheight[i]である。このブロックをボード上に並べるとき、外側に見えている面の面積を最大にしたい。その最大の面積を答えよ。 解法 テストケースの1が結構ヒントになる。1が8個、2が8個あるときには2が互いに隣り合わない ...
こんにちはtatsyです。 今回はノンパラメトリックベイズ法の中で、ガウス過程についてご紹介しようと思います。 なお、ウェブ上には非常にわかりやすく有用な情報が数多く存在しておりまして、今回の記事は、少し実験的な側面からガウス過程の内容理解の助けになればと思っております。 ガウス過程の定義 まず、少し複雑ながら、ガウス過程の定義を確認しておきたいと思います。 ガウス過程では、とある集合$\mathcal{X ...
こんにちはtatsyです。 今回はノンパラメトリックベイズ法の中で、ガウス過程についてご紹介しようと思います。 なお、ウェブ上には非常にわかりやすく有用な情報が数多く存在しておりまして、今回の記事は、少し実験的な側面からガウス過程の内容理解の助けになればと思っております。 ガウス過程の定義 まず、少し複雑ながら、ガウス過程の定義を確認しておきたいと思います。 ガウス過程では、とある集合$\mathcal{X ...
こんにちはtatsyです。 GCJ2014のRound1Aの解説します。今回は普通にAとBをSmallとLarge両方通して800位台でした。去年もRound1は突破できてたし、実力は格段に伸びてるはずなので、通過できてよかったです。 一応全て解説しますが、自力で出来たのはA、Bだけなのでコードはその2問分だけのせます。Cについてはやり方のみ説明しますので、詳しくは他の方のコードを公式から見ていただけ ...
こんにちは、あいかわらずSRMの調子は低調のtatsyです。 今回はSRM617です。問題はEasyが割り算ゲー、Mediumが貪欲＋深さ優先となっております。それでは早速いきます。 Easy (250点) 問題 横幅がnのケーキがある。あなたはこれから来る友人に平等にケーキを切り分けたいが、友人が何人来るかは定かではない。友人が来る人数はnの約数のうち1とnを除いた数のどれかであることが分かっている。このとき、 ...
こんにちはtatsyです。 本日はTCO2014のAlgoRound 1Bを解説します。 Easy (200点) 問題 メールが良い行と悪い行から構成されている。良い行の場合にはG点を加算し、悪い行の場合にはB点を減算する時、メールを上から読んでいって途中で点数が負になったら、そのメールをスパムだと扱う。もし途中で一度も負にならなければ、そのメールはスパムではない。与えられたメールがスパムかどうかを判定せよ。 解法 と ...
こんにちはtatsyです。今回もSRMの解説やります。 Easy (250点) 問題 アメーバがいて、アメーバのエサとなるゼリーが列になって最大200個並んでいる。アメーバは自分と同じ大きさのゼリーと出会うと、そのゼリーを食べて大きさが2倍になる。このとき、任意の大きさのアメーバからスタートして、ゼリーの列を通過後に現れることのないアメーバの大きさの場合の数を答えよ。 解法 まず、単純なポイントとして、ゼリーの列に ...
こんにちはtatsyです。 MCMCの記事も終盤ですが、今回はスライス・サンプリングです。なお、これまでの記事はこちらです。 はじめてのMCMC (メトロポリス・ヘイスティングス法) はじめてのMCMC(ギブス・サンプリング) はじめてのMCMC(ハイブリッド・モンテカルロ) スライス・サンプリングとは？ スライス・サンプリングは前回紹介したハミルトニアン・モンテカルロと同様に拡張変数を用いるハイブリッド・モン ...
こんにちはtatsyです。 はじめてのMCMCも早くも3記事目ですが、自分的にはもう少し書きたいことがある感じです。というわけで今回はハイブリッド・モンテカルロです。 ちなみにこれまでの記事はこちらです。 はじめてのMCMC (メトロポリス・ヘイスティングス法) はじめてのMCMC(ギブス・サンプリング) ハイブリッド・モンテカルロとは？ ハイブリッド・モンテカルロは今までのM-H法やギブス・サンプリングと違い ...
こんにちはtatsyです。 前回のメトロポリス・ヘイスティングス法に引き続きギブス・サンプリングについて解説したいと思います。どうでも良い話ですが、「ギブズ」サンプリングではなく「ギブス」サンプリングなんですね。いや、本当どうでもいい話です。 ちなみに前回の記事はこちらです。 はじめてのMCMC (メトロポリス・ヘイスティングス法) ギブス・サンプリングとは？ M-H法ではガウス関数などのサンプリングが容易な ...
