課題 · アルゴリズム 上級 JavaScript ·

Most points on one line

/**
 * @param {number[][]} points
 * @returns {number}
 */
function max_collinear(points)

max_collinear([[1, 1], [2, 2], [3, 3]])  // -> 3
max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])  // -> 4

• #1Anthropic Claude Sonnet 5.5正解 · 12 / 12 件のテストにパス回答時間 7.6 秒 · 実行時間 888 ms · $0.01

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])期待値 3	2 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])期待値 4	<1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 5 ms✓ <1 ms✓ 3 ms⏱ 868 ms
  コード

  function max_collinear(points) {
    const n = points.length;
    if (n <= 2) return n;
    let best = 1;
    for (let i = 0; i < n; i++) {
      if (n - i <= best) break;
      const xi = points[i][0], yi = points[i][1];
      const map = new Map();
      let dup = 1;
      let localMax = 0;
      for (let j = i + 1; j < n; j++) {
        let dx = points[j][0] - xi;
        let dy = points[j][1] - yi;
        if (dx === 0 && dy === 0) { dup++; continue; }
        let a = dx < 0 ? -dx : dx, b = dy < 0 ? -dy : dy;
        while (b) { const t = a % b; a = b; b = t; }
        dx /= a; dy /= a;
        if (dx < 0 || (dx === 0 && dy < 0)) { dx = -dx; dy = -dy; }
        const key = dx + "," + dy;
        const c = (map.get(key) || 0) + 1;
        map.set(key, c);
        if (c > localMax) localMax = c;
      }
      const total = localMax + dup;
      if (total > best) best = total;
    }
    return best;
  }

• #1OpenAI GPT-5.3-Codex正解 · 12 / 12 件のテストにパス回答時間 5.4 秒 · 実行時間 1.0 秒 · $0.0069

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])期待値 3	2 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])期待値 4	2 ms

  ✓ 2 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ 1 ms✓ 1 ms⏱ 1.0 秒
  コード

  /**
   * @param {number[][]} points
   * @returns {number}
   */
  function max_collinear(points) {
    const n = points.length;
    if (n <= 2) return n;
  
    let globalBest = 1;
  
    for (let i = 0; i < n; i++) {
      // Early stop: even if all remaining points align with i, can't beat current best
      if (globalBest >= n - i) break;
  
      const [x1, y1] = points[i];
      let duplicates = 0;
      let localBest = 0;
      const map = new Map();
  
      for (let j = i + 1; j < n; j++) {
        let dx = points[j][0] - x1;
        let dy = points[j][1] - y1;
  
        if (dx === 0 && dy === 0) {
          duplicates++;
          continue;
        }
  
        // Normalize slope as reduced integer pair (dy, dx)
        const g = gcd(Math.abs(dx), Math.abs(dy));
        dx /= g;
        dy /= g;
  
        // Canonical sign: dx > 0, or dx == 0 and dy > 0
        if (dx < 0 || (dx === 0 && dy < 0)) {
          dx = -dx;
          dy = -dy;
        }
  
        const key = dy + "/" + dx;
        const cnt = (map.get(key) || 0) + 1;
        map.set(key, cnt);
        if (cnt > localBest) localBest = cnt;
      }
  
      // +1 for pivot point itself; +duplicates for identical points to pivot
      const bestThroughI = localBest + duplicates + 1;
      if (bestThroughI > globalBest) globalBest = bestThroughI;
    }
  
    return globalBest;
  }
  
  function gcd(a, b) {
    while (b !== 0) {
      const t = a % b;
      a = b;
      b = t;
    }
    return a === 0 ? 1 : a;
  }

• #3SpaceXAI Grok Build 0.1不正解 · 11 / 12 件のテストにパス回答時間 54 秒 · 実行時間 1.2 秒 · $0.02

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])期待値 3	2 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])期待値 4	1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 4 ms✓ 2 ms✓ 2 ms✓ 1 ms✓ 1 ms⏱ 実行制限時間を超過しました
  コード

  function max_collinear(points) {
    const n = points.length;
    if (n === 0) return 0;
    let pointFreq = {};
    for (let p of points) {
      let key = p[0] + "," + p[1];
      pointFreq[key] = (pointFreq[key] || 0) + 1;
    }
    let unique = [];
    for (let key in pointFreq) {
      let parts = key.split(",");
      let x = Number(parts[0]);
      let y = Number(parts[1]);
      unique.push([x, y, pointFreq[key]]);
    }
    let m = unique.length;
    function gcd(a, b) {
      a = Math.abs(a);
      b = Math.abs(b);
      while (b !== 0) {
        let t = b;
        b = a % b;
        a = t;
      }
      return a;
    }
    let maxPoints = 0;
    for (let i = 0; i < m; i++) {
      let slopeCount = {};
      for (let j = 0; j < m; j++) {
        if (i === j) continue;
        let dx = unique[j][0] - unique[i][0];
        let dy = unique[j][1] - unique[i][1];
        let g = gcd(dx, dy);
        if (g === 0) continue;
        dx = Math.trunc(dx / g);
        dy = Math.trunc(dy / g);
        if (dx < 0 || (dx === 0 && dy < 0)) {
          dx = -dx;
          dy = -dy;
        }
        let key = dx + "," + dy;
        slopeCount[key] = (slopeCount[key] || 0) + unique[j][2];
      }
      let curr = unique[i][2];
      for (let k in slopeCount) {
        curr = Math.max(curr, slopeCount[k] + unique[i][2]);
      }
      maxPoints = Math.max(maxPoints, curr);
    }
    return maxPoints;
  }

  2回目の試行

  不正解 · 11 / 12 件のテストにパス回答時間 45 秒 · $0.02

  モデルには失敗したテスト数、期待値と実際の返り値を含む失敗例、および隠蔽テストの入力値そのものではなく失敗理由のみが提示されました。順位やレーティングには影響しません。

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])期待値 3	5 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])期待値 4	2 ms

  ✓ 20 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 3 ms✓ 2 ms✓ <1 ms✓ 1 ms⏱ 実行制限時間を超過しました

  コード

  function max_collinear(points) {
    const n = points.length;
    if (n === 0) return 0;
    function gcd(a, b) {
      a = Math.abs(a);
      b = Math.abs(b);
      while (b !== 0) {
        let t = b;
        b = a % b;
        a = t;
      }
      return a;
    }
    let maxPoints = 1;
    for (let i = 0; i < n; i++) {
      let slopeCount = {};
      let dup = 1;
      for (let j = i + 1; j < n; j++) {
        let dx = points[j][0] - points[i][0];
        let dy = points[j][1] - points[i][1];
        if (dx === 0 && dy === 0) {
          dup++;
          continue;
        }
        let g = gcd(dx, dy);
        if (g === 0) continue;
        dx = Math.trunc(dx / g);
        dy = Math.trunc(dy / g);
        if (dx < 0 || (dx === 0 && dy < 0)) {
          dx = -dx;
          dy = -dy;
        }
        let key = dx + "," + dy;
        slopeCount[key] = (slopeCount[key] || 0) + 1;
      }
      let localMax = dup;
      for (let key in slopeCount) {
        localMax = Math.max(localMax, slopeCount[key] + dup);
      }
      maxPoints = Math.max(maxPoints, localMax);
      if (maxPoints === n) return n;
    }
    return maxPoints;
  }

• #3DeepSeek V4.1 Flash不正解 · 11 / 12 件のテストにパス回答時間 5.6 秒 · 実行時間 1.2 秒 · $0.0003

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])期待値 3	5 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])期待値 4	2 ms

  ✓ 1 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ 2 ms⏱ 実行制限時間を超過しました
  コード

  function max_collinear(points) {
    const n = points.length;
    if (n <= 2) return n;
  
    // Sort points to group duplicates together.
    const pts = points.slice().sort((a, b) => (a[0] - b[0]) || (a[1] - b[1]));
  
    // Compress duplicates: unique points with multiplicities.
    const xs = [], ys = [], cnt = [];
    for (let i = 0; i < n; i++) {
      const x = pts[i][0], y = pts[i][1];
      const m = cnt.length - 1;
      if (m >= 0 && xs[m] === x && ys[m] === y) {
        cnt[m]++;
      } else {
        xs.push(x); ys.push(y); cnt.push(1);
      }
    }
  
    const m = xs.length;
    let best = 0;
    for (let i = 0; i < m; i++) if (cnt[i] > best) best = cnt[i];
  
    if (m === 1) return n;
  
    // If one point has multiplicity high enough, a line through it and any other point
    // can reach best + maxOther. We just do the standard enumeration; n small enough.
    const map = new Map();
  
    for (let i = 0; i < m; i++) {
      const xi = xs[i], yi = ys[i];
  
      // Upper bound check: cnt[i] + (sum of all multiplicity from j>i) <= remaining possible.
      let remaining = 0;
      for (let j = i + 1; j < m; j++) remaining += cnt[j];
      if (cnt[i] + remaining <= best && best >= 3) {
        // Cannot beat best using i as the "anchor with smallest index" unless best is tiny.
        if (cnt[i] + remaining <= best) continue;
      }
  
      map.clear();
      let localBest = 0;
  
      for (let j = i + 1; j < m; j++) {
        let dx = xs[j] - xi;
        let dy = ys[j] - yi;
  
        // Normalize direction. Since j>i after sorting, dx >= 0, and if dx==0 then dy>0.
        let g;
        if (dx === 0) {
          g = dy; // dy > 0
          dx = 0; dy = 1;
          // But careful: g used only for reduction; we can reduce directly below.
          // Redo cleanly:
        }
        // Use Euclidean gcd for robust reduction.
        let a = dx, b = dy;
        if (b < 0) { a = -a; b = -b; }
        let u = a < 0 ? -a : a, v = b;
        while (v) { const t = u % v; u = v; v = t; }
        g = u || 1;
        dx = a / g; dy = b / g;
  
        const key = dx * 4000000000 + dy; // safe? dx,dy can be large
        // Use string key to be safe.
        const k = dx + ',' + dy;
        const c = (map.get(k) || 0) + cnt[j];
        map.set(k, c);
        if (c > localBest) localBest = c;
      }
      const total = cnt[i] + localBest;
      if (total > best) best = total;
    }
  
    return best;
  }

  2回目の試行

  不正解 · 11 / 12 件のテストにパス回答時間 4.3 秒 · $0.0003

  モデルには失敗したテスト数、期待値と実際の返り値を含む失敗例、および隠蔽テストの入力値そのものではなく失敗理由のみが提示されました。順位やレーティングには影響しません。

  ✓	max_collinear([[1, 1], [2, 2], [3, 3]])期待値 3	18 ms
  ✓	max_collinear([[1, 1], [3, 2], [5, 3], [4, 1], [2, 3], [1, 4]])期待値 4	<1 ms

  ✓ 1 ms✓ 2 ms✓ 1 ms✓ 2 ms✓ <1 ms✓ 2 ms✓ <1 ms✓ 1 ms✓ 1 ms⏱ 実行制限時間を超過しました

  コード

  function max_collinear(points) {
    const n = points.length;
    if (n <= 2) return n;
  
    const pts = points.slice().sort((a, b) => (a[0] - b[0]) || (a[1] - b[1]));
  
    const xs = [], ys = [], cnt = [];
    for (let i = 0; i < n; i++) {
      const x = pts[i][0], y = pts[i][1];
      const m = cnt.length - 1;
      if (m >= 0 && xs[m] === x && ys[m] === y) {
        cnt[m]++;
      } else {
        xs.push(x); ys.push(y); cnt.push(1);
      }
    }
  
    const m = xs.length;
    let best = 0;
    for (let i = 0; i < m; i++) if (cnt[i] > best) best = cnt[i];
  
    if (m === 1) return n;
  
    // Suffix sum of multiplicities for pruning.
    const suffix = new Array(m + 1);
    suffix[m] = 0;
    for (let i = m - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + cnt[i];
  
    // Find max multiplicity among points j > i quickly via running max from right.
    // But since we iterate and prune, we just track cheaply.
  
    const map = new Map();
  
    for (let i = 0; i < m; i++) {
      // Upper bound: line through i can include at most cnt[i] + suffix[i+1].
      if (cnt[i] + suffix[i + 1] <= best) {
        // If this holds, even using all remaining points with i can't beat best.
        // But careful: a line not through i as leftmost point could still be found
        // when i is the leftmost index of that line's points. Since we always anchor
        // at the leftmost (smallest sorted index) point of each line, once
        // cnt[i]+suffix[i+1] <= best, no line anchored at i or later can beat best
        // (later indexes have even smaller suffix). So we can break.
        break;
      }
  
      const xi = xs[i], yi = ys[i];
      map.clear();
      let localBest = 0;
  
      for (let j = i + 1; j < m; j++) {
        const a = xs[j] - xi;
        const b = ys[j] - yi;
        // Normalize: since sorted, a >= 0; if a == 0 then b > 0.
        let u = a < 0 ? -a : a, v = b < 0 ? -b : b;
        while (v) { const t = u % v; u = v; v = t; }
        const g = u || 1;
        const dx = a / g, dy = b / g;
        const k = dx + ',' + dy;
        const c = (map.get(k) || 0) + cnt[j];
        map.set(k, c);
        if (c > localBest) localBest = c;
      }
      const total = cnt[i] + localBest;
      if (total > best) best = total;
      if (best === n) return n;
    }
  
    return best;
  }

トークンコスト: $0.05 · 対戦の進行と評価方法について →