25位/7510人の自己ベスト。Hardの1問を正答できたのと、Hard/Expertの部分点を取れたのが大きかった。以下、難易度Easyのものは省略する。
2次元上の座標(0,0)から(d,0)に移動する最小のステップ数を求めよ。ただし、1回のステップでは距離aまたは距離bのみ進むことができる。a,b,dの組み合わせはq個与えられるので、それぞれについて答えること。
1 <= q <= 10^5
1 <= a <= b <= 10^9
0 <= d <= 10^9
x座標軸上のみで考えると、(x1,0)から(x2,0)まで移動するステップ数は、
1、x2-x1がaまたはb:1
2、x2-x1がb*2より小さい:2
3、それ以外:(x1+b,0)から(x2,0)までのステップ数+1
となる。愚直に再帰で実装するとStackOverflowになるので、3の部分はループでbを足していく。
public static int GetAns(int a, int b, int d) { var ret = 0; if (d > 2 * b) { ret = (d - 2 * b) / b; d -= ret * b; } while (d > b * 2) { d -= a; ret++; } if (d == a || d == b) ret += 1; else if (d != 0) ret += 2; return ret; }
2人のプレーヤーが次のゲームを戦う。いずれも最善手を指したときに、勝利するのはどちらか。
・n個の石でできた山が1つある
・m個の一意なInt型の集合S = { }がある
・プレーヤーは交互に手を指す。手番では、Sから任意のと任意の山1つを選んで、その集まりを個の山に分割する。このとき、分割された集合は同数である必要がある
・指せる手がないプレーヤーが負けとなる
1 <= n <= 10^18
1 <= m <= 10
2 <= <= 10^18
NimやGrundy数の理解が前提。本番ではWL-Algorithmで解いて部分正答だった。
参考:grundy数を習得したかった - nanikakaのAOJ航海日誌
を1つの山にx個の石があるときのGrundy数とする。
xをkで割ったとき、Grungy数は
となる。よって、kが偶数のときは0、奇数のときはg(d)に一致する。(=kが偶数なら勝ち)
class Program { static List<long> s; static Dictionary<long, bool> dict = new Dictionary<long, bool>(); static void Main(string[] args) { var str = Console.ReadLine().Split(); var n = long.Parse(str[0]); var m = Int32.Parse(str[1]); s = Console.ReadLine().Split().Select(st => long.Parse(st)).ToList(); Console.WriteLine(GetAns(n) ? "First" : "Second"); } static bool GetAns(long n) { var ret = false; if (dict.ContainsKey(n)) return dict[n]; foreach (var k in s) { if (n % k != 0) continue; ret |= k % 2 == 0; if (ret) break; ret |= !GetAns(n / k); if (ret) break; } dict.Add(n, ret); return ret; } }
二次平面上に、n個の厳密な凸多角形と、m個の楕円(Ellipse)がある。すべての多角形と楕円が重なる点を求めよ。該当点は存在することが保障されている。また、該当するものであれば、どの点を答えても良い。
1 <= n <= 500
3 <= <= 1500 (多角形iの頂点数)
3 <= <= 1500
1 <= m <= 1500
各座標は[ -10^4, 10^4 ]の範囲にある
楕円のSemi Major Axisは10^4以下の整数
誤差は10^-4まで許容
本番でこれが解けたのはうれしい。
凸多角形と楕円が重なる部分は、かならず凸型の図形になる。よって、最終的な凸型図形までの距離をf(x, y)とすると、xおよびyを固定してできる関数f(A, y), f(x, B)はいずれも凹型の曲線になる。なのでXとYそれぞれで三分探索すれば解が求められる。
class Program { static void Main(string[] args) { //polygon var polygons = new List<Polygon>(); var n = Int32.Parse(Console.ReadLine()); for (int i = 0; i < n; i++) { var polygon = new Polygon(); var v = Int32.Parse(Console.ReadLine()); for (int j = 0; j < v; j++) { var str = Console.ReadLine().Split(); var x = Int32.Parse(str[0]); var y = Int32.Parse(str[1]); polygon.AddPoint(new Pt(x, y)); } polygons.Add(polygon); } //ellipses var ellipses = new List<Ellipse>(); var m = Int32.Parse(Console.ReadLine()); for (int i = 0; i < m; i++) { var str = Console.ReadLine().Split(); var x1 = Int32.Parse(str[0]); var y1 = Int32.Parse(str[1]); var x2 = Int32.Parse(str[2]); var y2 = Int32.Parse(str[3]); var a = Int32.Parse(str[4]); ellipses.Add(new Ellipse(x1, y1, x2, y2, a)); } var lx = -10001.0; var rx = 10001.0; var ly = -10001.0; var ry = 10001.0; // ternary search in x for (int i = 0; i < 48; i++) { var x1 = lx + (rx - lx) / 3; var x2 = rx - (rx - lx) / 3; var ly_x1 = -10001.0; var ry_x1 = 10001.0; var x1Score = GetScore_TernaryY(ref ly_x1, ref ry_x1, x1, ellipses, polygons); var ly_x2 = -10001.0; var ry_x2 = 10001.0; var x2Score = GetScore_TernaryY(ref ly_x2, ref ry_x2, x2, ellipses, polygons); if (x2Score > x1Score) { //remove right rx = x2; } else { //remove left lx = x1; ly = ly_x2; ry = ry_x2; } } Console.WriteLine(lx); Console.WriteLine(ly); } static double GetScore_TernaryY(ref double ly, ref double ry, double x, List<Ellipse> ellipses, List<Polygon> polygons) { var score = GetScore(x, ly, ellipses, polygons); for (int i = 0; i < 48; i++) { var y1 = ly + (ry - ly) / 3; var y2 = ry - (ry - ly) / 3; var y1Score = GetScore(x, y1, ellipses, polygons); var y2Score = GetScore(x, y2, ellipses, polygons); if (y2Score > y1Score) { //remove right ry = y2; } else { //remove left ly = y1; score = y2Score; } } return score; } static double GetScore(double x, double y, List<Ellipse> ellipses, List<Polygon> polygons) { return GetScore(new Pt(x, y), ellipses, polygons); } static double GetScore(Pt pt, List<Ellipse> ellipses, List<Polygon> polygons) { return ellipses.Sum(e => e.GetDist(pt)) + polygons.Sum(p => p.GetDist(pt)); } } public class Polygon { public List<Edge> Edges; List<Pt> _points; public Polygon() { Edges = new List<Edge>(); _points = new List<Pt>(); } public void AddPoint(Pt point) { _points.Add(point); if (_points.Count >= 2) { Edges.Add(new Edge(_points[_points.Count() - 2], _points[_points.Count() - 1])); } } public double GetDist(Pt pt) { double minDist = Double.MaxValue; var inside = true; for (int i = 0; i < Edges.Count(); i++) { if (!IsCcw(pt, Edges[i].p1, Edges[i].p2)) { inside = false; } minDist = Math.Min(minDist, Edges[i].Dist(pt)); } return inside ? 0 : minDist; } public bool IsCcw(Pt p, Pt p1, Pt p2) { return Pt.Ccw(p, p1, p2) == 1; } } public class Ellipse { public Pt P1; public Pt P2; public double A; public double D; public Ellipse(double x1, double y1, double x2, double y2, double a) { P1 = new Pt(x1, y1); P2 = new Pt(x2, y2); A = a; D = 2 * a; } public double GetDist(Pt pt) { var ret = P1.Dist(pt) + P2.Dist(pt); return ret <= D ? 0 : (ret - D) / 2; } }
PtとEdgeは個人ライブラリのもの。
頂点数n、辺数mのDAGが与えられる。すべての頂点vは値として整数a[v]持ち、これの初期値は0である。次のクエリの結果を答えよ。クエリは3タイプある。
1. 1 u x: 頂点uから訪れることのできる頂点vについて、a[v]をxに更新する
2. 2 u x: 頂点uから訪れることのできる頂点vについて、a[v]>xならa[v]をxに更新する
3. u: a[u]を出力する
2 <= n <= 10^5
1 <= m, q <= 10^5 (qはクエリの数)
0 <= x <= 10^9
すべてのクエリをため込んで出力のたびにa[v]を算出する方法も、クエリが来るたびに各a[i]を算出する方法もTLEになる。平方分割を使って解決する。
- すべてのクエリをローカル変数に保持
- クエリタイプ2について、くらいのブロックごとに、ブロックkの時点でクエリ2だけでa[v]の値がどうなるかの情報、type_2[k][v]を作成する
- クエリを最初から処理:(1)クエリ1はキューque1に入れていく。que1のサイズがを超えたらその時点でクエリ1だけで値がどうなるかの情報type_1[v]を作成する(2)クエリ3が来たらtype_2とtype_1を使って出力値を計算
Editorialによると、グラフすべてを計算しようとするとメモリが足りなくなるので、グラフを3つくらいに分割して3回処理を回す必要がある。
理屈はわかるのだが、C#で実装したらTLEになってしまった・・・。