HackerRank Week of Code - 26 参加日記
398位/6951人でレート減してしまった。いつも数学の問題が多いと順位を落としてしまう。以下Easy問は省略。
整数iとjがいずれも素数、かつ距離が2のとき、これらをペアであるとする。整数nとmが与えられたとき、区間[n,m]にはいくつのペアが存在するか。ただし、(i, j)と(j, i)は同じペアと扱う。
1 <= n <= m <= 10^9
m - n <= 10^6
あらかじめエラトステネスの篩を使って区間内の素数を列挙し、あとはi=n..m-2でループしてiとi+2が両方素数の場合をカウントすればよい。
// n, m <= 10^9, m - n <= 10^6 public static int GetAns(int n, int m) { var isPrime = new bool[m - n + 1]; SegSieve(n, m + 1, isPrime); var ret = 0; for (int i = n; i <= m - 2; i++) { if (isPrime[i - n] && isPrime[i - n + 2]) ret++; } return ret; } // returns primes in [a, b) public static void SegSieve(int a, int b, bool[] isPrime) { for (int i = 0; i < isPrime.Length; i++) isPrime[i] = true; for (int i = 0; i < isPrime.Length; i++) { if (i + a < 2) isPrime[i] = false; } var sqrtb = (int)Math.Ceiling(Math.Sqrt(b)); // prime table of [0, sqrt[b]) var primeTable_0_b = new int[sqrtb]; var primeTable_0_b_is = new bool[sqrtb]; Sieve(primeTable_0_b, primeTable_0_b_is); foreach (var p in primeTable_0_b) { if (p == -1) continue; var st = (a / p) * p; if (st == 0) st = p; if (st == p) st += p; while (st < b) { if (st >= a) isPrime[st - a] = false; st += p; } } } public static void Sieve(int[] prime, bool[] isPrime) { for (int i = 0; i < prime.Length; i++) prime[i] = -1; for (int i = 0; i < isPrime.Length; i++) isPrime[i] = true; isPrime[0] = isPrime[1] = false; var idx = 0; for (int i = 2; i < isPrime.Length; i++) { if (isPrime[i]) { prime[++idx] = i; for (int j = 2 * i; j < isPrime.Length; j += i) isPrime[j] = false; } } }
無限に長いストリート上に、ポイントa_0、a_1、... a_nが設置されている。a_0より前のストリートではある曲のジャンルが、a_0とa_1の間ではまた別の曲のジャンルが演奏されている（a_nからあとも同様）。ある人がある地点からポイントが大きくなる方向に時速1マイルでmマイル歩くとき、同じジャンルの曲をh_min時間以上、h_max時間以内だけ聞きたい。これを満足するスタート地点のいずれかを求めよ。
1 <= n <= 10^6
abs(a_i) <= 10^9、a_iは昇順で与えられる
1 <= h_min <= h_max <= 10^9
1 <= m <= 10^9
スタート地点の候補は限られているので、そのすべてで条件に合致するかトライする。予めボーダー間がすべて条件を満たすかどうかを管理する区間木を作っておけばよい。また、歩き始めのIndexや終点のIndexを求めるにはLowerBoundとUpperBoundも必要になる。
本番ではRmq内の配列サイズが足りず、1問RLEになっていた。
class Program { public static long n; public static List<long> a; public static long m; public static long hmin; public static long hmax; public static Rmq _rmq; static void Main(string[] args) { n = long.Parse(Console.ReadLine()); a = ReadLine().Split().Select(v => long.Parse(v)).ToList(); var str = Console.ReadLine().Split(); m = long.Parse(str[0]); hmin = long.Parse(str[1]); hmax = long.Parse(str[2]); Console.WriteLine(GetAns()); } public static long GetAns() { // from left for (int i = 0; i < a.Count(); i++) { if (Ok(a[i] - hmin)) { return a[i] - hmin; } if (Ok(a[i] - hmax)) { return a[i] - hmax; } if (Ok(a[i])) { return a[i]; } } //from right for (int i = a.Count() - 1; i >= 0; i--) { if (Ok(a[i] + hmin - m)) { return a[i] + hmin - m; } if (Ok(a[i] + hmax - m)) { return a[i] + hmax - m; } if (Ok(a[i] - m)) { return a[i] - m; } } return -1000; } public static bool Ok(long pos) { var stIdx = (int)UpperBound(a, pos); if (stIdx >= a.Count() - 1) stIdx = a.Count() - 1; if (stIdx < 0) stIdx = 0; // check current pos to next bound if (!OkDist(pos, a[stIdx])) return false; var edIdx = (int)LowerBound(a, pos + m); edIdx--; if (edIdx >= a.Count() - 1) edIdx = a.Count() - 1; if (edIdx < 0) edIdx = 0; // check last bound to last pos if (!OkDist(a[edIdx], pos + m)) return false; // check intervals are all OK return OkIntervals(stIdx, edIdx); } public static bool OkIntervals(int idx1, int idx2) { if (idx1 == idx2) return true; if (idx1 + 1 == idx2) return OkDist(a[idx1], a[idx2]); if (_rmq == null) { _rmq = new Rmq(); _rmq.Init((int)n + 1); for (int i = 0; i < n - 1; i++) { if (!OkDist(a[i], a[i + 1])) { _rmq.Update(i, 0); } else { _rmq.Update(i, 1); } } } return _rmq.Query(idx1, idx2) == 1; } public static bool OkDist(long pos1, long pos2) { var gap = pos2 - pos1; if (gap == 0) return true; return gap >= hmin && gap <= hmax; } public static long LowerBound(List<long> ar, long val) { long lb = -1; long ub = ar.Count(); while (ub - lb > 1) { var mid = (lb + ub) / 2; if (ar[(int)mid] >= val) { ub = mid; } else { lb = mid; } } return ub; } public static long UpperBound(List<long> ar, long val) { long lb = -1; long ub = ar.Count(); while (ub - lb > 1) { var mid = (lb + ub) / 2; if (ar[(int)mid] <= val) { lb = mid; } else { ub = mid; } } return lb + 1; } } public class Rmq { const int MAX_N = 2000005; int _n; int[] _dat = new int[2 * MAX_N - 1]; public void Init(int n) { _n = 1; while (_n < n) _n *= 2; for (int i = 0; i < _dat.Length; i++) _dat[i] = Int32.MaxValue; } public void Update(int k, int a) { k += _n - 1; _dat[k] = a; while (k > 0) { k = (k - 1) / 2; _dat[k] = Math.Min(_dat[k * 2 + 1], _dat[k * 2 + 2]); } } public int Query(int a, int b) { return Query(a, b, 0, 0, _n); } int Query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return Int32.MaxValue; if (a <= l && r <= b) return _dat[k]; else { var vl = Query(a, b, k * 2 + 1, l, (l + r) / 2); var vr = Query(a, b, k * 2 + 2, (l + r) / 2, r); return Math.Min(vl, vr); } } }
正の整数nが与えられたとき、ax + bx = n に解が存在する(a, b)のパターン数を求めよ(a < b、x,yは正の整数）。
4 <= n <= 3x10^5
axでイテレートし、その内部でax・byの約数の組み合わせを作って、該当するものを合算していけばよい。
public static int GetAns(int n) { // 使う約数を準備 var divs = new List<int>[n + 1]; for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j += i) { if (divs[j] == null) divs[j] = new List<int>(); divs[j].Add(i); } } int ct = 0; for (int xa = 1; xa < n; xa++) { int yb = n - xa; foreach (var a in divs[xa]) { foreach (var b in divs[yb]) { var x = xa / a; // x <= b / gcd(a, b) は // 同じ(a,b)ペアでxが最小のもののみをカウント if (a < b && x <= b / gcd(a, b)) { ct++; } } } } return ct; } public static int gcd(int a, int b) { while (b > 0) { int c = a; a = b; b = c % b; } return a; }
