AtCoder Grand Contest 016 B: Colorful Hats
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
アルファベット小文字からなる文字列がs[i]で与えられる。新しい文字列のi番目の文字をs[i] or s[i + 1] のいずれかを選んで構成する、という作業を行う。この作業を何回か繰り返して全ての文字が単一のアルファベットで構成されるようにしたい。最短回数を求めよ。
Nが最大100までであり、一回の作業でN文字がN-1文字になる。よって最後の一文字に慣れば必ず単一のアルファベットになるため、文字を固定してしまえばO(N^2)でシミュレーションできる。最短回数は貪欲に目的のアルファベットにしてしまえばよい。アルファベットの数をAとするとO(AN^2)。
交渉をするAI
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
数列が与えられる。連続部分列の平均値が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
魔物の体力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]))。
Educational Codeforces Round 22 C. The Tag Game
木の2個の頂点にAさん及びBさんがいる。AさんがBさんを追いかけ、BさんはAさんから逃げるという目的で行動を最適化するとき、AさんがBさんに追いつく手数を求めよ。その場にとどまるのもありとし、Bさんが先手とする。
Aさん及びBさんがいる地点からの距離を全列挙する。この時、木の性質としてある2個の地点間の最短距離はただひとつのルートしかいない、という性質を使うと、ある頂点pに於いて、d(A, p) > d(B, p) であれば、その頂点にBさんは来ることが可能になる。なぜならそこまでの経路上の点qに於いて、d(A, q) <= d(B, q)という点があったとすると、先述の性質によりqはB-p間の最短経路上の点になりえず、Bさんがまっすぐそこに向かえばqは通らないからである。
なので、Bさんとしてはd(A, p) < d(B, p) であるような点のうち、最長の点に行くという行動を取るのが最適になり、Aさんはそこにまっすぐ向かい追いついた時点でゲーム終了となる。O(N)。
コーナーケースとして、初期位置からAとBが重なっている場合は0になる。
