JAGSummer2014Day2F Directions
バグらせがち
問題概要(原文)
$2$ 次元のベクトル $u,v$ と非負整数 $a,b$ を選んで $au + bv$ なる新しいベクトルを作れる． $N$ 個の $2$ 次元ベクトルがある．最初に何種類か購入した上で，先程示した操作を用いて全方向に移動できるようにしろ．
考察
実は $4$ 種類か $3$ 種類買えば十分． 買うパターンは
- 十字になるようにして $4$ 種類
- Y字上になるようにして $3$ 種類
Y字というのをもう少しちゃんというと，T字とI字の間，ということ．
$1$ 本足を固定して残り $2$ をRMQで探す．
計算量は $O(N \log N)$
ソースコード
using System;
using System.Linq;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
//using System.Numerics;
//using Point = System.Numerics.Complex;
using Number = Pair<long, int>;
namespace Program
{
public class Solver
{
public void Solve()
{
var n = sc.Integer();
var a = Enumerate(n, x => sc.Integer(3));
var xs = new List<double>();
var T = new double[n];
var V = new double[n];
var U = new double[n];
var W = new double[n];
for (int i = 0; i < n; i++)
{
if (a[i][0] == 0 && a[i][1] == 0) continue;
var t = Math.Atan2(a[i][1], a[i][0]);
var u = Math.Atan2(-a[i][1], -a[i][0]);
if (t < 0) t += 2 * Math.PI;
if (u < 0) u += 2 * Math.PI;
T[i] = t; U[i] = u;
V[i] = t + Math.PI / 2;
W[i] = u + Math.PI / 2;
if (V[i] >= 2 * Math.PI) V[i] -= 2 * Math.PI;
if (W[i] >= 2 * Math.PI) W[i] -= 2 * Math.PI;
xs.Add(t);
xs.Add(u);
xs.Add(V[i]);
xs.Add(W[i]);
}
xs = xs.Distinct().ToList(); xs.Sort();
var m = xs.Count;
var mext = new int[m];
var next = new int[m];
var oext = new int[m];
var p = Enumerate(m * 2, x => 1L << 60);
for (int i = 0; i < n; i++)
{
if (a[i][0] == 0 && a[i][1] == 0) continue;
var q = xs.BinarySearch(T[i]);
p[q] = Math.Min(p[q], a[i][2]);
p[q + m] = Math.Min(p[q + m], a[i][2]);
var r = xs.BinarySearch(U[i]);
var s = xs.BinarySearch(V[i]);
mext[q] = s;
next[q] = r;
oext[q] = xs.BinarySearch(W[i]);
if (mext[q] < q) mext[q] += m;
if (next[q] < q) next[q] += m;
if (oext[q] < q) oext[q] += m;
}
var rmq = new RMQSegmentTree(2 * m);
for (int i = 0; i < 2 * m; i++)
rmq.Update(i, new Number(p[i], i));
var min = 1L << 60;
for (int i = 0; i < m; i++)
{
var l = next[i]; var r = i;
if (l > r) r += m;
//4ko
{
var v = p[i] + p[next[i]];
v += rmq.Query(i + 1, next[i]).x;
v += rmq.Query(l + 1, r).x;
min = Math.Min(min, v);
}
//3ko
{
var ll = mext[i]; var rr = next[i];
if (rr < ll) rr += m;
var lll = next[i]; var rrr = oext[i];
if (rrr < lll) rrr += m;
if (ll >= m) { ll -= m; rr -= m; }
if (lll >= m) { lll -= m; rrr -= m; }
var v = p[i];
var x = rmq.Query(ll + 1, rr);
var y = rmq.Query(lll + 1, rrr);
min = Math.Min(min, v + x.x + y.x);
}
}
if (min >= 1L << 60) min = -1;
IO.Printer.Out.WriteLine(min);
}
public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
}
}
#region main
static class Ex
{
//static public string AsString(this IEnumerable<char> ie) { return new string(System.Linq.Enumerable.ToArray(ie)); }
//static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); }
static public void Main()
{
var solver = new Program.Solver();
solver.Solve();
Program.IO.Printer.Out.Flush();
}
}
#endregion
#region Ex
namespace Program.IO
{
using System.IO;
using System.Text;
using System.Globalization;
public class Printer: StreamWriter
{
static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; }
public static Printer Out { get; set; }
public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { }
public void Write<T>(string format, T[] source) { base.Write(format, source.OfType<object>().ToArray()); }
public void WriteLine<T>(string format, T[] source) { base.WriteLine(format, source.OfType<object>().ToArray()); }
}
public class StreamScanner
{
public StreamScanner(Stream stream) { str = stream; }
public readonly Stream str;
private readonly byte[] buf = new byte[1024];
private int len, ptr;
public bool isEof = false;
public bool IsEndOfStream { get { return isEof; } }
private byte read()
{
if (isEof) return 0;
if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } }
return buf[ptr++];
}
public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; }
public string Scan()
{
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
sb.Append(b);
return sb.ToString();
}
public string ScanLine()
{
var sb = new StringBuilder();
for (var b = Char(); b != '\n'; b = (char)read())
if (b == 0) break;
else if (b != '\r') sb.Append(b);
return sb.ToString();
}
public long Long()
{
if (isEof) return long.MinValue;
long ret = 0; byte b = 0; var ng = false;
do b = read();
while (b != 0 && b != '-' && (b < '0' || '9' < b));
if (b == 0) return long.MinValue;
if (b == '-') { ng = true; b = read(); }
for (; true; b = read())
{
if (b < '0' || '9' < b)
return ng ? -ret : ret;
else ret = ret * 10 + b - '0';
}
}
public int Integer() { return (isEof) ? int.MinValue : (int)Long(); }
public double Double() { var s = Scan(); return s != "" ? double.Parse(s, CultureInfo.InvariantCulture) : double.NaN; }
private T[] enumerate<T>(int n, Func<T> f)
{
var a = new T[n];
for (int i = 0; i < n; ++i) a[i] = f();
return a;
}
public char[] Char(int n) { return enumerate(n, Char); }
public string[] Scan(int n) { return enumerate(n, Scan); }
public double[] Double(int n) { return enumerate(n, Double); }
public int[] Integer(int n) { return enumerate(n, Integer); }
public long[] Long(int n) { return enumerate(n, Long); }
}
}
#endregion
#region gcd,lcm
static public partial class MathEx
{
static public int GCD(int n, int m)
{
bool f = true;
for (; n != 0 && m != 0; f ^= true)
{
if (f)
m %= n;
else n %= m;
}
return n == 0 ? m : n;
}
}
#endregion
#region Compair
static public class Pair
{
static public Pair<FT, ST> Create<FT, ST>(FT f, ST s)
where FT : IComparable<FT>
where ST : IComparable<ST>
{ return new Pair<FT, ST>(f, s); }
static public Pair<FT, ST> Min<FT, ST>(Pair<FT, ST> p, Pair<FT, ST> q)
where FT : IComparable<FT>
where ST : IComparable<ST>
{ return (p.CompareTo(q) <= 0) ? p : q; }
static public Pair<FT, ST> Max<FT, ST>(Pair<FT, ST> p, Pair<FT, ST> q)
where FT : IComparable<FT>
where ST : IComparable<ST>
{ return (p.CompareTo(q) >= 0) ? p : q; }
}
public struct Pair<FT, ST>: IComparable<Pair<FT, ST>>
where FT : IComparable<FT>
where ST : IComparable<ST>
{
public FT x;
public ST y;
public Pair(FT f, ST s) : this() { x = f; y = s; }
public int CompareTo(Pair<FT, ST> other)
{
var cmp = x.CompareTo(other.x);
return cmp != 0 ? cmp : y.CompareTo(other.y);
}
public override string ToString() { return string.Format("{0} {1}", x, y); }
}
#endregion
#region RMQ Segment Tree
public class RMQSegmentTree
{
readonly Number ZERO = new Number(1L << 60, 10000000);
int n;
Number[] data;
public RMQSegmentTree(int size)
{
n = 1;
while (n < size)
n <<= 1;
data = new Number[n << 1];
for (int i = 0; i < data.Length; i++)
data[i] = ZERO;
}
public void Update(int k, Number v)
{
k += n;
data[k] = v;
k >>= 1;
while (k > 0)
{
data[k] = merge(data[k << 1], data[(k << 1) + 1]);
k >>= 1;
}
}
public Number Query(int a, int b) { return query(a, b, 1, 0, n); }
private Number query(int a, int b, int k, int l, int r)
{
if (r <= a || b <= l)
return ZERO;
if (a <= l && r <= b)
return data[k];
else
{
var vl = query(a, b, k << 1, l, (l + r) >> 1);
var vr = query(a, b, (k << 1) + 1, (l + r) >> 1, r);
return merge(vl, vr);
}
}
Number merge(Number l, Number r)
{
return Pair.Min(l, r);
}
public Number[] Items
{
get
{
var ret = new Number[n];
for (int i = 0; i < n; i++)
ret[i] = data[i + n];
return ret;
}
}
}
#endregion
コメント
- ソースコードがクッソ汚い
