E: Connected? - AtCoder Regular Contest 076
RxC の平面内に (x1[i], y1[i]) (x2[i], y2[i]) の座標のペアが幾つか与えられる。このペア同士で線を引きたいが、それぞれの線が交差してはならない。そのような引き方が可能かどうか判定せよ。
まず、両方の点のいずれかが周囲を除いた領域RxCの内部にある時、そのペアは無視してもよい。なので、両方の点が領域の周辺にあるものだけを考える。
これはある角から出発して辺を一周するような順序で点をソートし、順番にキューに入れていく。既にキューに入れたものが現れた場合、キューの先頭にもう片方のペアがあるならばキューから出す。そうでない場合は線が引けないのでNOを出力する。これを最後までやればよい。ソートが一番重く、O(N logN)。
D: Built? - AtCoder Regular Contest 076
座標(x[i], y[i])に街がある、街間に道路を引くためにはx座標の差またはy座標の差の小さいほうの距離だけコストがかかる。いくつか道路を引いて全部の街を行き来できるようにするための最小コストはいくつか？
最小全域木を求めれば良いのでKruskal法またはPrim法をする。ただし、全部の街の間にEdgeを引くと計算量がオーバーする。具体的にはO(N^2 logN)になる。
そのため、あらかじめx座標でソートした街、y座標でソートした街を作成しておき、その前後でしかEdgeがないようにしておくと、Edgeの数は(N-1)*2に抑えられる。そのため計算量がO(N logN)で計算できる。
C: Reconciled? - AtCoder Regular Contest 076
犬がN匹、サルがM匹いる。犬同士、サル同士が互いに隣り合わない並びかたは何通りか？
|N - M| > 1 の場合は0通り。
|N - M| == 1 のときは、xoxoxoxox という並び順しかありえないのでN! * M! 通り。
|N - M| == 0 のときは、oxoxoxox と xoxoxoxoいう並び順の2通りがあり、2*N! * M! 通り。
AtCoder Grand Contest 016 C: +/- Rectangle
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
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は結構単純なモデルなので実装してみると面白いかもしれません。
