0Pricing
Competitive Programming Academy · レッスン

シミュレーションでのサイクル検出

状態が繰り返されたら先へスキップします

「シミュレーションでのサイクル検出」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

ステップが繰り返されるとき

シミュレーションによっては、1兆回のように非常に大きな回数の後の状態を求めます。1回ずつ進めていては、時間内に終わりません。⏳

状態は有限である

可能な状態の数が限られているなら、シミュレーションは必ずいつか同じ状態を再び訪れます。そこから先は、周期的に無限に繰り返します。

周期の形

経路には、周期へ入る尾と、その後に繰り返されるループがあります。ループを見つければ、何十億ものステップを飛ばせます。

訪れた場所を覚えておく

各状態を、初めて確認したステップ番号に対応付ける辞書に保存します。同じ状態を再び見つければ、周期が分かります。

seen = {}

繰り返しを検出する

各ステップの前に、現在の状態がすでにseenにあるか確認します。あれば、たった今ループが閉じたことになります。

if state in seen:
    start = seen[state]

周期の長さを測る

長さは、現在のステップから、その状態を初めて見たステップを引いた値です。その回数だけ進むと、状態がちょうど元に戻ります。

length = step - seen[state]

剰余で先へ飛ぶ

尾の長さを引き、残りのステップ数を周期の長さで割った余りにします。これで、残りのごく少数のステップだけをシミュレーションすれば済みます。

rem = (N - start) % length

残りのステップを完了する

周期の開始点から、残りのステップ数だけシミュレーションを実行します。最後の状態は、ステップNの状態と正確に一致します。

for _ in range(rem):
    state = step_fn(state)

状態をハッシュ可能に保つ

辞書のキーはハッシュ可能でなければならないため、保存する前にリストをタプルへ変換します。可変な状態はキーにできません。

key = tuple(row)

メモリを使わないFloyd法

状態が大きすぎて保存できない場合は、Floydの亀と兎法を使うと、2つのポインターとほとんど追加メモリなしで周期を見つけられます。

これで危機を救える理由

周期検出を使えば、不可能に見える1兆ステップのループを数千ステップに変えられます。繰り返しに気付くことが、この方法の核心です。

クイックチェック

現在の状態を初めて見たのはステップsで、今はステップtにいます。

まとめ

状態が繰り返されたら、それぞれをマップに記録し、周期の長さを求め、剰余で先へ進み、残りのステップだけをシミュレーションします。🚀

よくある質問

「シミュレーションでのサイクル検出」レッスンは無料ですか？

はい。「シミュレーションでのサイクル検出」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「シミュレーションでのサイクル検出」で何を学びますか？

状態が繰り返されたら先へスキップします ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「シミュレーションでのサイクル検出」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 状態をモデル化して一歩進める
  2. グリッド上の移動と方向ベクトル
  3. シミュレーションでのサイクル検出
  4. 難しいエッジケースを攻略する
← Competitive Programming Academyに戻る