すべてのチャレンジ
中級 0件解決済み 正答率0%

グリッド内の最大の積

グリッド上で一直線に並ぶ k 個の数の積の最大値を求めます。

このチャレンジで学べること

  • 移動量の組を使ってグリッドを4方向に走査できる
  • 並びを読む前に範囲外でないかを確認できる
  • 最大値を更新しながら記録できる

問題

原文(英語)を表示

グリッド上で一直線に並んだ k 個のマスの並びを考えます。向きは、行に沿って左から右、列に沿って上から下、または2方向の斜めのいずれかです。並びに含まれる数を掛け合わせ、積が最大になる並びを見つけてください。

largest_product_in_grid(grid, k) を実装してください。

入力

grid:数が並んだ長方形のグリッド。どの行も同じ長さです。

k:並びの長さ。

出力

長さ k のすべての並びについて、積の最大値を返してください。どの方向にも長さ k の並びがグリッドに収まらない場合は、0 を返します。

制約

1 ≤ 行数, 列数 ≤ 20; 0 ≤ grid[r][c] ≤ 99; 1 ≤ k ≤ 5

例

例 1
入力:
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
k = 2

期待される出力:
expected = 72
入力:
std::vector<std::vector<long long>> grid = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
long long k = 2;

期待される出力:
long long expected = 72;
入力:
long[][] grid = new long[][] {
    new long[] {1, 2, 3},
    new long[] {4, 5, 6},
    new long[] {7, 8, 9}
};
long k = 2;

期待される出力:
long expected = 72;

解説

最良の並びは最下行の 8 と 9 で、8 × 9 = 72 です。斜めの 5, 9 では 45 にしかなりません。

例 2
入力:
grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
k = 3

期待される出力:
expected = 504
入力:
std::vector<std::vector<long long>> grid = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};
long long k = 3;

期待される出力:
long long expected = 504;
入力:
long[][] grid = new long[][] {
    new long[] {1, 2, 3},
    new long[] {4, 5, 6},
    new long[] {7, 8, 9}
};
long k = 3;

期待される出力:
long expected = 504;

解説

最下行の 7 × 8 × 9 = 504 が、右端の列の 3 × 6 × 9 = 162 やどの斜めよりも大きくなります。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

方向は右、下、右下、左下の4つで十分です。それ以外は同じ並びを逆にたどるだけです。

ヒント 2

各開始マスから、並びの最後のマスがまだグリッド内にあるかを確認します。

ヒント 3

0 を返すのは、長さ k の並びが1つも収まらないときだけです。

目安の計算量

時間 O(rows × cols × k)、追加メモリ O(1)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。