SRM623D1Med CatchTheBeat
これは典型だけど苦手
問題概要(原文)
$N$ 個のものが格子点 $(x_i,y_i)$ にある． これらのものは自然落下し，$1$ 秒につき $1$ だけ $y$ 座標が小さくなる．
$(0,0)$ に人が立っていて，$1$ 秒につき $1$ だけ $x$ 座標を増減できる．
人とものが重なると $1$ 点もらえる．最大何点もらえるか？
考察
人が $1$ 秒につき $1$ だけ上に登っていくことにする．
すると，人は $(-1,1),(0,1),(1,1)$ のどれかの方向にだけ移動できることになる． ここで， $(x,y)$ を $(y-x,y+x)$ に回転させる．すると，人は $(2,0),(1,1),(0,2)$ 方向に移動できる． つまり，人は $(0,0)$ から自分の右上にあるものしか取れないことになる．
あとはこれらの点を $(x,y)$ 座標でソートしたあとに，典型的なLISを求める要領で最長非減少部分列を求めればよい．計算量は $O(NlogN)$．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class CatchTheBeat
{
public int maxCatched(int n, int x0, int y0, int a, int b, int c, int d, int mod1, int mod2, int offset)
{
var X = new int[n];
var Y = new int[n];
X[0] = x0; Y[0] = y0;
for (int i = 1; i < n; i++)
{
X[i] = (int)((Math.BigMul(X[i - 1], a) + b) % mod1);
Y[i] = (int)((Math.BigMul(Y[i - 1], c) + d) % mod2);
}
for (int i = 0; i < n; i++)
X[i] -= offset;
return f(X, Y);
}
int f(int[] X, int[] Y)
{
var n = X.Length;
var Z = new KeyValuePair<int, int>[n];
for (int i = 0; i < n; i++)
Z[i] = new KeyValuePair<int, int>(Y[i] - X[i], X[i] + Y[i]);
Array.Sort(Z, (l, r) =>
{
var cmp = l.Key.CompareTo(r.Key);
if (cmp != 0) return cmp;
return l.Value.CompareTo(r.Value);
});
var dp = new long[n + 50];
for (int i = 0; i < n + 50; i++)
dp[i] = 1000000000000;
foreach (var x in Z)
{
if (x.Key < 0 || x.Value < 0) continue;
var p = dp.UpperBound(x.Value);
dp[p] = x.Value;
}
for (int i = n; i >= 0; i--)
{
if (dp[i] < dp[n + 48]) return i + 1;
}
return 0;
}
}
static public partial class Algorithm
{
static private int binarySearch<T>(this T[] a, int idx, int len, T v, Comparison<T> cmp, bool islb)
{
int l = idx;
int h = idx + len - 1;
while (l <= h)
{
int i = l + ((h - l) >> 1);
int ord;
if (a[i] == null || v == null) return -1;
else ord = cmp(a[i], v);
if (ord < 0) l = i + 1;
else if (ord == 0)
{
if (!islb) l = i + 1;
else h = i - 1;
}
else h = i - 1;
}
return l;
}
static public int UpperBound<T>(this T[] a, int idx, int len, T v, Comparison<T> cmp) { return binarySearch(a, idx, len, v, cmp, false); }
static public int UpperBound<T>(this T[] a, T v) where T : IComparable<T> { return UpperBound(a, 0, a.Length, v, Comparer<T>.Default.Compare); }
}
コメント
- データ構造ゲーだと思ったら違った
