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

サイコロの目の最長連続

サイコロで同じ目が続いた最長の区間がどこから始まり、何回続いたかを求めます。

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

  • 同じ値の連続がどこで終わるかを見つける
  • 最良の連続の開始位置と長さを記録する
  • 同じ長さなら先に始まった連続を選ぶ

問題

原文(英語)を表示

サイコロシミュレーターは、6面のサイコロを振った結果をすべてリストに記録します。ここでいう「連続」とは、同じ目が続けて出たひとまとまりのことで、1回だけ出た目も長さ1の連続です。最長の連続を見つけてください。最長の長さの連続が複数あれば、最初に始まるものを答えます。

longest_run_of_rolls(rolls) を実装してください。

入力

rolls: 出た順に並べた目。それぞれ1から6です。

出力

最長の連続が始まる0始まりの添字と、その長さを [start, length] として返してください。リストが空なら [-1, 0] を返します。

制約

0 ≤ 振った回数 ≤ 10,000

1 ≤ 目 ≤ 6

例

例 1
入力:
rolls = [1, 4, 4, 2, 6, 6, 6, 3]

期待される出力:
expected = [4, 3]
入力:
std::vector<long long> rolls = {1, 4, 4, 2, 6, 6, 6, 3};

期待される出力:
std::vector<long long> expected = {4, 3};
入力:
long[] rolls = new long[] {1, 4, 4, 2, 6, 6, 6, 3};

期待される出力:
long[] expected = new long[] {4, 3};

解説

添字4から始まる3つの6が、2つの4より長いので [4, 3] です。

例 2
入力:
rolls = [5, 5, 2, 2, 3]

期待される出力:
expected = [0, 2]
入力:
std::vector<long long> rolls = {5, 5, 2, 2, 3};

期待される出力:
std::vector<long long> expected = {0, 2};
入力:
long[] rolls = new long[] {5, 5, 2, 2, 3};

期待される出力:
long[] expected = new long[] {0, 2};

解説

どちらのペアも長さ2で、5の方が添字0から先に始まるので [0, 2] です。

解き方のヒント

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

ヒント 1

現在の連続がどこから始まったかを覚えておきましょう。

ヒント 2

値が変わったとき(またはリストが終わったとき)、終わった連続をそれまでの最良のものと比べます。

ヒント 3

新しい連続のほうが真に長いときだけ、最良のものを置き換えます。

目安の計算量

時間 O(n)、追加メモリ O(1)

参考資料

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

ランキング

全体ランキング

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

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

他の人の解答から学ぶ

コミュニティの解答

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