読者です 読者をやめる 読者になる 読者になる

アルゴリズム忘備録

競技プログラミングとかデータ分析とか

AGC015 C - Nuske vs Phantom Thnook

agc015.contest.atcoder.jp

 

N * M のグリッドに0または1が書いてあり、1をノード、1が隣同士になっているときにはエッジが張ってあるとみなすと、1の集合はTreeになる。領域(x[1,i],y[1,i], x[2, i], y[2,i])がQ個与えられるので、その領域でTreeの部分集合をとった時、領域内の連結成分の数を答えよ。

 

Treeの部分集合は一般に森(複数の木)になる。木は一般に「頂点数 - エッジ数 = 1」を満たすため、領域内の「頂点数 - エッジ数」がそのまま連結成分の数になる。エッジ数は各点ごとに上下左右を見ておき、その累積和を作っておく。また、領域の途中で切れた分を除くために、縦方向及び横方向での累積和も作っておく。また、頂点数は単に1の数で累積和を作っておく。すると領域が指定された時の「頂点数 - エッジ数」はO(1)で計算可能。全体ではO(N M)。

AGC015 B - Evilator

agc015.contest.atcoder.jp

 

各階に上または下のボタンしかないエレベーターがある。最上階は下、1階は上であるときに、i階からj階に移動する全組み合わせについて移動の最低回数の合計値を求めよ。

 

移動の最低回数は多くても2回。なので、すべての組み合わせ N * (N - 1) に2回の移動が必要な組み合わせの数を足せばよい。移動に2回必要な移動というのはi階において上ボタンしかない場合は1~i-1階まで、下ボタンしかない場合はi+1~N階までであり、各階が上か下かによって、i-1 または N-i を足していけばよい。O(N)。

Kerasによる深層強化学習(DQN)

最近はDeep Learningのモデルを書くときは大体Kerasを使っています。理由は

  1. Outputの次元を定義するだけで書ける
  2. Layer型のDNNライブラリでめんどくさそうなRNNやLSTMなどは標準で入ってる
  3. 学習が簡単(ミニバッチの生成などを余り考えなくてもかける)
  4. BackendがTensorflow

などです。Kerasを知らない人はこちら。

Keras Documentation

 

Tensorflow自体はDNNのライブラリというよりも行列演算と誤差のバックプロパゲーションのライブラリというのが正しいので、実際に使うと若干冗長になってしまいます。ただ逆に言えば、論文にしかないような最新のモデルなんかを書く時でも対応できる柔軟性があるとも言います。しかし私が書くのはそういう最新のモデルというよりは古典的なCNNとかAuto EncoderがメインですのでこういうKerasは大変助かるわけです。

 

さて、タイトルに有るDQNについて、Keras自体はサポートしてないもののKeras対応のDQNライブラリで使いやすい物がありましたのでご紹介します。

 

github.com

 

使い方は簡単で、Kerasインストール後、「pip install keras-rl」とやるだけ。

さらに「pip install h5py」でHDF5形式のファイルのアクセスライブラリを入れてから以下のスクリプトを実行すると、Open AI Gymの一つでDQNによる学習ができるようなデモが実行できます。

 

keras-rl/dqn_cartpole.py at master · matthiasplappert/keras-rl · GitHub

 

DQN自体は本来は24時間ぐらい学習させないとあまり進化しないので微妙なところですが、可視化の画面もついてるので結構わかりやすいかと。

 

そもそもDQNとはなんぞやという人は、まず強化学習の一つであるQ学習について一通り見たあとにDeepMindで配っている論文を見るとよいです。要はQ学習のQ関数としてDeep Learningを使用したものになります。

第16回日本情報オリンピック 予選 E - 尾根 (Ridge)

joi2017yo.contest.atcoder.jp

 

H*Wの高度マップが与えられる。水をあるマスに流すと、低い高度で隣接するマスに流れ、自マスからは水が消滅する。そのようなマスが2個以上隣接してる場合は、そのようなマス全てに水が流れる。周りがすべて自マスより高い高度の場合はそのマスに水がたまり、それ以上他に流れない。水を流したときに、最終的に2マス以上に水が貯まるマスを尾根と定義するときに、尾根は何個あるか?

 

2次元dp。マスをナンバリングし、マスごとに最終的に1個に流れるならばそのマスの番号(>0)、2個に流れるならば-1としてあるマスからdfsで状態を埋めていく。最初に流すマスを(1, 1)から(H, W)まですべて計算しても、dpテーブルは使いまわして良いので計算量はO(HW)になる。

第16回日本情報オリンピック 予選 D - ぬいぐるみの整理 (Plush Toys)

joi2017yo.contest.atcoder.jp

 

M種のぬいぐるみをN個並べる。N個の中から一斉に幾つか取り出し、順番を変えて元に戻した時同一種類のぬいぐるみは全部隣り合う用に並べたい(11112222223333 のように) 取り出す数の最小値を求めよ。

 

Mが20程度なのでBitDPを疑う。M種の中からK種を選び、そのK種が左から順番に並んでいる状況を考えると、これはK-1種(これはK通り)を順番に並べた時からもう一種追加した、という遷移に等しい。このようなdpで取り出すぬいぐるみの数の最小値を計算する。

 

左のlからrにかけてある1種のぬいぐるみを並べるときに取り上げなくてはならないぬいぐるみの数は累積和などをあらかじめ計算しておくことでO(1)で計算可能。よってdpの遷移はO(M)で行える。総計算量はO(2^M * M)。

ちなみにdpでやる方法は難しい(ビットがk個立ってるという順列を作る方法が難しい)のでメモ化再帰でもいいかもしれない。

 

追記

こういうbit DPを組むときは一つ前を考えるのではなく、一つあとを考えると良いらしい。つまりdp[s] = ~~~ではなく、dp[s | (1 <<i)] = Math.min(dp[s | 1(<<i)], dp[s] + x)のように遷移させると、0~1<<M までの遷移が順番に並ぶ。これは覚えておきたい。

ARC074 F - Lotus Leaves

arc074.contest.atcoder.jp

 

2次元マップ上の複数の場所oとスタートとゴールが与えられる。が与えられる。x軸またはy軸が等しい場所o及びスタート、ゴールはワープすることができる。このとき、スタートからゴールにたどり着けなくするためにoを取り除きたい(スタートとゴールは取り除けない)。取り除くoの数の最小値はいくつか。全部取り除いてもたどり着けてしまう場合は-1を出力せよ。

 

取り除く最小値なので、互いに行き来できるo及びスタート、ゴールにエッジをつなぐことで何らかのグラフを構成し、最小カットという方針がうかぶ。

ただし、例えばoをノードにして同じ行や列にあるノードをクリークにする、という方針では最小カットで考えにくい(最小カットはあくまでもエッジをカットするということであり、ノードの除去はこの方針に対応しない。

そこで、[1, ... , H]及び[1, ..., W]という列及び行という(H+W)要素をノードとして、o間の移動はこの要素を経由して移動するという考え方をする。すると、これらのノード間に対して、oをエッジだと思いグラフを構成すると、辺のコスト1とした時の最小カットの数が答えになる。辺の貼り方は両方向、スタート・ゴールのみ一方通行とすればよい。O(HW)。

ARC074 E - RGB Sequence

arc074.contest.atcoder.jp

 

(l[i], r[i], x[i])の組がM個与えられる。Nマスを赤 緑 青で塗り分ける時、[l[i], r[i]]の範囲はx[i]色になるという制限を課す。塗り分け方は何通りか。

 

何通りか、なのでdpで考える。

n番目まで色を塗って、一番最後に塗った色と初めて異なる色が塗られたところがp, もう一つ異なる色が塗られた場所がq(つまりp>q)とするとき、dp[n][p][q] 通りの塗り分け方があったとする。これについて次の色を塗った時 dp[n+1][p][q], dp[n+1][n][p], dp[n+1][n][q] の三通りの遷移が存在する。特に色数の制限がないときは単純に配るdpをすればよい。n番目まで色を塗った時、[l[i], r[i]=n] が x[i]色という制限があったとする。このとき、上の3通りのうち、pやqとl, rの大小関係でその範囲内にある色数が決定するので、その範囲を満たさない場合は遷移が出来ない(配るdpができない)

 

これを繰り返した後、dp[N][i][j]のうち、i、jを動かした総和が答え。O(N^3)。

 

注意点としてdp[N+1][N+1][N+1]をやると空間計算量もO(N^3)になるが、これは3000万ほどの配列であり、JavaだとMLEになる。(おそらくC++なら大丈夫なのだろうが)

そこで、dp[2][N+1][N+1]で計算する。

また、n=r[i]の制限を発見するために線形探索は絶対にしてはいけない。ハッシュでも良いが、処理計算量1000万ほどであるため、かなり高速にしておく必要がある。