HackerEarth December Circuits '17 参加日記
2017年最後のプロコン。57位/5713人で風邪を引いていた割には悪くない。長期型プロコンだと、二桁順位がたまに取れるくらいの実力にはなったようだ。
同じ長さnの整数列X, Yについて、マッチング数を以下のように定義する。
・X[i] = Y[j], (1 <= i, j <= n)となるインデックス(i, j)のペアの数
整数Kと、長さNの整数列A、および長さMの整数列Bが与えられる。AとBから同じ長さの部分列を抜き出し、マッチング数がK以上になるパターン数を答えよ。
1 <= N, M <= 2000
1 <= A[i] <= 1000000000
1 <= B[i] <= 1000000000
1 <= K <= NM
次のような二次元配列を用意する。
table[i, j] = A[i] とB[j]が等しいなら1、それ以外なら0
すると、table[,]の正方形(i, j)～(k, l)は、A[i, k]とB[j, l]でマッチする組み合わせに等しくなる(1の部分がマッチするところ)。
よって、すべてのi,jの組み合わせについて、(i, j)を左上とした正方形をどんどん大きくしていって、中の1の数がK以上になったところから、限界までの正方形の数を足したものが答えとなる。これは累積和と二分探索で効率よく求めることができる。
https://www.hackerearth.com/submission/13789952/
国Xには、0からN-1で番号付けされるN個の都市があり、サイクルのようにつながれている(都市iは、都市(i + 1)%Nと都市(i - 1 + N)%Nとつながっている）。また、各都市にはタイプA[i]がある。次のQ個のクエリに答えよ。
タイプ１： 都市YからタイプZの都市まで、左回りで移動したときの最小ステップ数
タイプ２： 都市YからタイプZの都市まで、右回りで移動したときの最小ステップ数
たどり着けないときは-1を返すこと。
1 <= N <= 3000
1 <= Q <= 500000
0 <= Y < N
1 <= A[i], Z <= 200000
都市のタイプごとに、位置をリストでもてばよい。それぞれYの位置をLowerBound()で求め、その次または前のIndexとの差分を返す。
https://www.hackerearth.com/submission/13790214/
数列Aについて、A[i] > A[j]かつi < jなら、そのペアはinversionである。すべてのinversionであるペアの合計をinversion countと呼ぶ。長さNの整数列Aが与えれたとき、Aを左にiだけローテーションしたときのinversion countを求めよ。iは1からNのすべての数である。
1 <= N <= 100000
1 <= A[i] <= 1000000
Aに重複する要素はない
ある状態Aのinversion countがすでに求められていたとする。Aを左に1つローテーションしたもののinversion countは、
現在の値 - (A[0]の順位 - 1) + (N + A[0]の順位)
となる(『A[0]の順位』はAを昇順ソートしたときの要素A[0]の位置）。
あとは、初期状態のinversion countを求めれば良い。これはBITを使って効率よく求められる。
https://www.hackerearth.com/submission/13828080/
N個の都市があり、それらをつなぐ道は全体でツリーを構成している。M種類のコンテストが各都市で開催される（１つのコンテストが複数の都市で開催されうる。ある都市では、あるコンテストが開催されないこともある）。ここで、
・連結したサブグラフを選び
・選んだサブセットで開催されるすべてのコンテストタイプに出場する
とする。この時、コンテストタイプの種類数kだけパスを購入しなければならない。
すべてのサブセットについてこのルールを適応したとき、パス数に対するサブセットの数を、すべてのkについて答えよ。
1 <= N <= 5000
1 <= M <= 10
解けそうで解けなかった問題。
dp[i, j] := 根をiとする木で、状態jになるサブグラフ数
と定義する。初期値を
dp[i, (開催されるコンテストマスク)] = 1
として、葉以外のノードについて、
のようにマージしていけば求められる。
計算は次のテクニックを使ってスピードアップできるらしい。
http://codeforces.com/blog/entry/45223（整数列のすべてのサブセットに対して、その合計を効率的に求める方法）
ノード数nの有向グラフ上を、Botがk個のインストラクションにそって移動する。インストラクションは、「現在地がノードxならノードyに移動せよ」というものであり、始めBotはノード1にある。ただし、移動中1回のみ、ランダムに隣のノードへBotが移動してしまうことがある。これは、インストラクションの前後いずれでも起こり得る（1度も起こらないこともある）。
このとき、最終到達地点としてありえるノードを答えよ。
1 <= n <= 100000
1 <= m, k <= 100000
本番ではDFS+メモ化で部分点だった。
ランダム変化がない場合の、ステップごとの位置を最初に算出する。そして、「現在のステップで最終的に到達する場所」をノードごとに保持しながら、うしろから処理していく。
（実装は省略）
