AtCoder Grand Contest 013 C - Ants on a Circle
本番解けず。ありがぶつかるとき、方向を反転させるのではなく互いにすれ違い方向はそのまま直進と考えるのが定石の問題(参照：蟻本)
ただこの問題の場合、今仮想的に直進している「1番」の蟻(実際は反転を繰り返しているので1番ではない可能性がある)が何番なのかを計算する必要がある。
重要なのは以下の2点
・回転させれば1からNの順番は変わらない→つまり一匹の蟻だけ計算すればよい
・蟻が1回ぶつかるたびに番号が1増減する
本番中気づけなかったポイントは後者。つまり、1番の蟻をシミュレートして、反対方向に歩いてくるアリがT秒間でぶつかる回数を求めればよい。O(N)
Mo's Algorithm
前これを使う問題をCodeforcesでみた(解けなかった)のでメモ。
a[1] ... a[N] (N=O(10^6)) に対し区間クエリQ(l, r)がO(10^6)個発行される。このクエリは先読み可能である。Q(l, r)の結果がわかっているときに隣接クエリQ(l±1, r), Q(l, r±1) の結果はO(1)とか(O(logN)も定数倍軽ければいけるけど)で計算可能、という状況で汎用的に使えるアルゴリズム。
一般にO(10^6)のクエリを発行する場合、O(QN)では間に合わないので、O(Q logQ + N logN)とかO(Q√N + N √N)といった計算量を目指す。前者はセグメント木や後者は平方分割であるが、これらの方法で単純にやると単位元付き半群の構造を入れる必要がある。そして結構思いつかないことも多い。(max-plus ringとか知らなかったら詰む)
一方でMo's Algorithmは純粋に計算量だけで判断可能なのでごくたまに役立つときがある。
さて、具体的なアルゴリズムの手順であるが、まずNを平方分割し、√Nのバケットを作る。次にクエリを先読みして、次の基準でソートする。
sort(query, (a, b) -> bucket[a.l] != bucket[b.l] ? bucket[a.l] - bucket[b.l] : a.r- b.r)
これはつまり、まずクエリのleft側をバケットに入れ、バケット別にソートし、更にバケットの中でright側の基準でソートするという2段階ソートである。
int i = 0, j = 0
for (q : queries) {
while (i < l) Q[i, j] から Q[i + 1, j]を計算
while (i > l) Q[i, j] から Q[i - 1, j]を計算
while (j < r) Q[i, j] から Q[i, j + 1]を計算
while (j > r) Q[i, j]からQ[i, j - 1]を計算ret[q.index] = 上のループの最後の結果
}
forの中に更にwhile文が4個あるが、これらよるループの総回数は最初のソートのお陰でO(N√N + Q√N)回になるのである。whileで計算したクエリは後で再利用するわけではないので、全て保存するわけではなく、実際には次のように書くことが多い。
int i = 0, j = 0
now = Q[0, 0] の結果
for (q : queries) {
while (i < l) remove(now, a[i ++])
while (i > l) add(now, a[-- i])
while (j < r) add(now, a[++j])
while (j > r) remove(now, a[j--])
ret[q.index] = now
}
addやremoveは最新のクエリの計算結果から隣接クエリの結果を計算する関数である。
2017 TCO Marathon Round 1 が始まります
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&compid=55119&rd=16903
競技プログラミングには短時間で100％正解を求めるアルゴリズムマッチ(正式名称しらない)と、長時間でなるべく高い得点を稼ぐマラソンという分野があります。マラソンは大抵最適解が求まるような問題ではなく、ある程度のヒューリスティックなアルゴリズムを組んでギリギリまで高い解を狙う、と言った感じです。
そのマラソンにおける権威のあるイベントがTopCoder Open Marathon Matchと言われるものであり、上の問題はその2017年度版Round 1になります。
今回の問題は意訳すると以下のような感じです。
ノードの数及び、エッジ(接続元、先)及びそのエッジの長さといったグラフの構造が与えられる。このグラフのノードをを700x700の平面の格子座標上の任意の場所に配置する。ただし点の重複は認められない。このとき、元のエッジの長さと平面においた時のエッジの長さがなるべく変わらないような配置を求めよ。
スコアの計算式は Min(平面上での長さ / 元の長さ) / Max(平面上での長さ / もとの長さ) * 100万 という式で与えられます。
開催中なので個別の問題に対する方針等の説明は書けないのですが、マラソンは一般的に競技プログラミングに慣れていなくても長時間開催されるので結構とっつきやすい印象があります。なので、ぜひ参加してみましょう。
AtCoder Grand Contest 012 D - Colorful Balls
ボールが一列に並んでいる。異色の場合、重さの合計がY以下なら任意の2個を入れ替えることができる。同色の場合、重さの合計がX以下なら任意の2個を入れ替えることができる。色の並び順として何通りあるか？
自力で解けなかった。考察ではAとBが交換可能かつBとCが交換可能ならAとCが交換可能ということで、互いに任意の2個が交換可能な集合が元のボールの部分集合になるというところまで出来た。ただし、そのような部分集合で元が2個以上あるものはたかだか1個しかない、というところまで考察がいかなった。とりあえず以下ではそのような部分集合をXとおく。
さて、そのような考察ができた場合、同色であればその色の中で重さが最小のボールとの関係だけを考えればよい。異色であれば重さが最小のボール及び、そのボールと色が異なる次に重さが最小のボールの2個との関係だけを考えれば良い(色が2種類あることで、同色の場合は2番めに最低のものと比較してXに含まれるかどうかを判断すればよい)
そのような部分集合が特定できたら、その中での色の並び替えの総数が答えになる。
サルでもわかる因果関係推論
データ分析をしていると、分析要件として因果関係の分析をすることになるケースが結構あったりします。そこでやりがちなのが、相関関係を因果関係と誤解してしまうケースです。例えば以下のようなケース。
例えばデータXが勉強時間、データYが成績のとき、XとYに因果関係があるというのは自然な結論です。ところが、データXが年度、データYがあるグループの年ごとの運動能力テストの成績だとします。この場合、年が進むに連れ運動能力テストの成績が上がっているため、年ごとの体育のカリキュラム改定が功を奏した・・・と言うのは正しくありません。
このデータYのグループがもし小学生であった場合、年齢による身体能力の向上という隠れファクターがあるからです。この隠れファクターのことを交絡といったりします。一般に因果関係推論ではこの交絡をいかに見つけるか、というのが一つの鍵になっています。すべてを洗い出すのは困難でも、ここはできるだけ頑張るべきです。
逆に元データを生成する段階で、この交絡という要素を極限まで排除したデータを生成するのが実験研究といわれる方法で、代表的な例では新薬の実験です。ところが一般のデータ解析では実験研究というのはコスト的な関係や、顧客要件的に無理な場合がほとんどでしょう。どちらかというと、データは既にある、そこから何らかの因果関係を導け、という課題ばかりです。
さて、その方法としては真面目にやるのであれば、バックドア基準や傾向スコアと言った方法があるのですが、単純なデータでもデータ数が十分確保できているのであれば適用機会が多く、私が気に入っているのが「回帰分断デザイン」です。
例えばですが、次のグラフを見てみます。
横軸はある装置の運用日数で、50日たったら定期メンテナンスををするという運用をしているとき、縦軸は不具合が起きた数を示しています。この時定期メンテナンス(これを介入と言います)が効果があるかどうか(つまり因果関係)を調べたいとします。上の図だけで見ると、効果があるようにも見えますが、そもそも日数がたってくると不具合の数も増えてくるため全体傾向にまぎれてわかりにくくなってしまっています。
そこで、この介入の効果を見る簡単な方法として回帰分断デザインという方法があります。次の図を見てください。
これは先程の図で、定期メンテナンスが行われたところで「分断」が起きていると仮定し、その前後のみに注目することでほぼ実験研究に近い現象になっている(準実験といったりします)といえるわけです。ここでは青線の範囲で示しています。ここに注目すると介入の前後の分断の大きさが介入の効果というわけです。本来はちゃんと有意差があるかどうかを計算しますが、上の図を見て感覚でもわかるかと思います。
この辺結構難しいのですが、岩波データサイエンスシリーズのVol3という名著がありましてとてもわかり易く書いてあるのでおすすめです。
(しかも1500円なんですよ！)
Yukicoder 483 マッチ並べ
Google Code Jam 2017 Qualification Round
Dashboard - Qualification Round 2017 - Google Code Jam
無事通過。でも全部解きたかったなあ。
A: 1次元ライツアウト。
右から貪欲にそろえていけばよい。O(length S)
B: 左から数字が増加していくようなもの(1111222255566とか)をTidiy Numberと呼ぶ。N以下で最大のTidy Numberを求めよ。
最初N以下のTidy Numberの総数を求めよかと思い、桁DPを組むとかやってしまった。左の桁からみていって減少する桁を探す。減少する桁が見つかった場合は、直前にある真に増加する桁の数字を1個減らし、更に1を引いたものが答え。
C: 両脇が常に使用中のN+2個ロッカーの列がある(つまり最初の空きはN個)。人が来るたびに両脇の空きロッカーの数が一番多くなるようにロッカーを専有していく。この時、K人目がロッカーを専有したときに両脇の空きはいくつになるか。
いわゆる人からなるべく離れて座りたいという電車の椅子問題(？)。
1人→2人→4人→8人・・・という感じで人を分割して、その時のロッカーの空きを観察すると、ロッカーの空きの連続列は各段階で実はある数xが存在して、xとx+1という2通りしかないことがわかる。このxをシミュレーションで求めていく。
1+2+4+…がKを超えたところでその時のシミュレーション結果が答え。+1とか+2とかがややこしい。
D: Nクイーン問題の発展版。コマx, +, oが合って、縦横にある任意の2個のコマの片方が+、または斜めにある任意の2個のコマの片方がxでなければならない配置に制限するときに、x1点、+1点、o2点でスコアを決める。このスコアの最大値を求めよ。
本番解けなかった。実はこの問題、xと+で独立して考察することが可能。そうして求めた配置のうち、+とxが同じ場所に合った場合にoに変えれば良い。
xの方は単純に貪欲にN個おけばそれが最大配置。+の方はちょっと複雑だがN個おける。2部グラフのマッチングを使うか、複雑な貪欲でもいけるらしい。Editorialは貪欲の説明をしていた。ただ市松模様にした時に、色違いのところは独立に考えられるなどそうやって計算量を減らすことでできそうではある。
