アルゴリズム忘備録

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

AtCoder Grand Contest 016 C: +/- Rectangle

agc016.contest.atcoder.jp

 

H行W列の整数値のテーブルで、h行w列の部分区画の和はすべて負、かつテーブル全部の要素の和が正であるようなテーブルは存在するか?するなら具体例を示せ。

 

具体的な構成を色々試すと、右下の角1マスだけ負、それ以外は正であるようなテーブルを作ることで作れそうである。この時、hがHの約数、かつwがWの約数であると、テーブルをすべて部分区画でダブりなく敷き詰めることができるため、絶対に全区画の和は負になってしまう。それ以外の場合で具体的に構成してみる。

 

ある数Vを仮定して、右下の角が -V*(w*h - 1) - 1, それ以外のマスがVであるようなh x wの部分区画を考えると、この範囲での合計は-1であり、負になる。これを横方向にw+1, w+2, と伸ばしていった時、範囲内の合計が最も小さいものはw+1のときであり、具体的にはV*h -1になる。一番右上からh x wの区画が合計N個あった時、上のようなとり方をするとその合計値は-Nとなる。これがV*h - 1の値より絶対値で小さければ、全体の合計値は必ず正となる。ここではWもHも500以下であるため、例えばV=1000とすることで目的のテーブルが構成できる。O(WH)。

 

この手の発想力が求められる問題は結構苦手かもしれない。

AtCoder Grand Contest 016 B: Colorful Hats

agc016.contest.atcoder.jp

 

N匹の猫が色付き防止をかぶっている。それぞれの猫は自分以外の猫の帽子の色がa[i]種類あるといっている。このような組み合わせは存在するか?

 

ある猫に注目したときにその猫をカウントする・しないで最大1種類しか違わない。よってa[i]はすべてある数xがあって、xまたはx + 1のみである。この条件に当てはまらないものはまず除外する。

 

次に、x+1が存在しない、つまりすべてのa[i]が同一の数の時を考える。これは全体でN色あって、a[i] = N - 1のとき、またはa[i] * 2 <= Nで、各色の帽子が2匹以上の猫によってかぶられているときである。

 

次にx+1が存在する場合を考える。この時、2匹以上の猫によってかぶられている帽子の色については、その猫が他の猫のかぶってる帽子の色の数をカウントしても全体の数と変わらない。一方でそうでない猫は全体の数 - 1個の色の種類しか見えない。

Type1. x+1: 2匹以上の猫が同じ帽子をかぶっている…p匹

Type2. x: それぞれが違う色の帽子をかぶっている...q匹

となる。ここでそれぞれp匹、q匹とする。 この条件を考えると、Type1の猫はType2の猫が全部みえており、Type2の猫は全部違う種類なので、Type1の猫がType1の他の猫のかぶっている帽子の種類として、x+1-q種類の色が見える。この色がそれぞれ2匹以上かぶっているので、(x+1-q) * 2 <= p を満たす。

また、Type2についてはq匹がそれぞれ違う色なので、x >= q  を満たす 。この条件をともに満たすときにYesである。

AtCoder Grand Contest 016 A: Shrinking

agc016.contest.atcoder.jp

 

アルファベット小文字からなる文字列がs[i]で与えられる。新しい文字列のi番目の文字をs[i] or s[i + 1] のいずれかを選んで構成する、という作業を行う。この作業を何回か繰り返して全ての文字が単一のアルファベットで構成されるようにしたい。最短回数を求めよ。

 

Nが最大100までであり、一回の作業でN文字がN-1文字になる。よって最後の一文字に慣れば必ず単一のアルファベットになるため、文字を固定してしまえばO(N^2)でシミュレーションできる。最短回数は貪欲に目的のアルファベットにしてしまえばよい。アルファベットの数をAとするとO(AN^2)。

交渉をするAI

code.facebook.com

 

Facebook Research Blogに面白いAIの記事が出ていました。自然言語(英語)で交渉をするAIを作ってみたという記事です。シチュエーションとしては、2者がそれぞれ何個かのアイテムを所持しており(公開情報)、それぞれのアイテムに2者それぞれが価値を持っています(非公開情報)。これらの前提のもとでアイテムのやりとりをする、という交渉をするAIを作ってみたよ、というものでした。

 

モデルとしては自然言語をLSTM系のモデルを使って自然言語を入力するとそれに対して自然言語で応答する、というものを作った後これを強化学習や、新しく開発したdialogue rolloutという方法で戦略も学ばせた、というものらしいです。LSTM系はほとんどわからないので途中のネットワークがどういう構造になってるのかいまいちピンときませんでした。

 

また、面白かった点としては教師データである交渉会話ログをAmazon Mechanical Turkというクラウドソーシングサービスによって集めた、という点です。会話1個に対し0.15ドル、交渉で勝ったら0.05ドルのボーナスという形で集めたとのこと。ラベル付きデータはコストが高い、というのは機械学習系ではよく話題になるので巷では半教師あり学習とかが流行ってるようですがこういうアプローチもあるのかと思いました。

 

自然言語のNNによる解釈、生成は若干敷居が高いと感じるものの、その後の戦略の強化学習やrolloutは結構単純なモデルなので実装してみると面白いかもしれません。

AtCoder Regular Contest 075 E - Meaningful Mean

arc075.contest.atcoder.jp

 

数列が与えられる。連続部分列の平均値がK以上であるような部分列は何通りあるか?

 

まずすぐ分かることはすべての要素からKを引くと、部分列の和が0以上になるような組み合わせをカウントすればよい。これはO(N^2)であれば、累積和を使ってカウントできる。

 

ただし計算量の問題があるので、累積和をsum[i]などと書くと、sum[0]~sum[i - 1]までにsum[i]以下の物が何通りあるか、というのをO(logN)以下で計算する必要がある。これは結構よく見るテクで、値そのものをIndexに持つセグメント木 or BITを使うと良い。ただし、値をIndexに持つので、値自体はO(10^6)以下でなければならないため座標圧縮を用いる。

 

すると、例えばBITを用いて、BIT.sum(sum[i])の和を取りつつ、sum[i]番目のBITにどんどん1を足していく、というループを回すと答えになる。O(N logN)。

 

このBITやセグメント木に配列の値そのものをインデックスとして持つ、みたいなテクニックは以前見たことあったのだけど、思い出せなかった。

画像認識 (機械学習プロフェッショナルシリーズ) レビュー

 

画像認識 (機械学習プロフェッショナルシリーズ)

画像認識 (機械学習プロフェッショナルシリーズ)

 

 

比較的新しい画像認識の本。ただ構成が独特で、画像認識の一般論といった基礎を一通り解説したあとに具体的なアルゴリズムの品揃えが定番から最新のものまで幅広く載っている本。

 

画像に限らないパターン認識の名著としては「はじめてのパターン認識」という本があるのですが、こちらは一般的な概念等は学習済みとして、アルゴリズムの解説にに特化した本です。一方で本書はまず概念を説明し、その上で各種アルゴリズムの解説をするので一応ゼロから始める人でも理論的には読めてしまう内容。ただし、結構真面目にかいてあるので、いわゆる「何となく概念が分かる系」の解説本のつもりでは読まないほうがいいかもです。

 

厳密に言えば画像認識ではないですが、画像生成として最近DCGANというモデルが流行っています(すでに過去形かも?)これについても軽く触れてあり、画像認識をだいたい俯瞰できるとてもいい本です。

 

最近のディープラーニング系の本は解説が適当であったり、概念しか説明していなかったりといった本が結構出ているので、真面目にこういう本を読んでみるのはおすすめです。

AtCoder Regular Contest 075 D - Widespread

arc075.contest.atcoder.jp

 

魔物の体力s[1]~s[N]が与えられる。一回の魔法攻撃で、特定の一つの魔物の体力をA削り、その他すべての魔物の体力をB削る。ただしA>Bとする。全滅させるには魔法攻撃を最低何回打てばよいか?

 

 

C=A-Bとする。魔法攻撃の回数をkとした時、すべての魔物は少なくともkBの体力が削られている。s[i] - kB > 0 であるような各iについて、(s[i] - kB) / C (ただし切り上げ)を計算して和を取ると、その敵に対してAの攻撃を何回当てれば体力が0になるかが算出される。この回数の合計がkより少なければ少なくともk回の魔法攻撃では魔物の全滅させることが可能である。そこで、kを二分探索する。O(N log(max(s[i]))。