アルゴリズム · 26
シミュレーションと全探索
話のとおりに一歩ずつ実行し、候補を一つも飛ばさずに試します。
アルゴリズムの第一歩は、工夫をしないことです。
下の例のロボットは 1 番から n 番までのマスがある廊下にいて、L（左）・R（右）の命令どおりに 1 マスずつ動き、壁に当たるとその場にとどまります。
命令が終わったとき goal 番のマスに立っている出発マスをすべて表示し、最後にその個数を表示します。
n, goal = map(int, input().split())moves = input().strip()count = 0for start in range(1, n + 1): # 모두 해 보기: 출발 칸 후보 n개 pos = start # 후보마다 처음부터 다시 for m in moves: # 그대로 따라 하기: 명령 하나에 한 걸음 if m == "L" and pos > 1: pos -= 1 elif m == "R" and pos < n: pos += 1 if pos == goal: print(start) count += 1print(count)const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, goal] = lines[0].split(" ").map(Number);const moves = lines[1].trim();let count = 0;for (let start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 let pos = start; // 후보마다 처음부터 다시 for (const m of moves) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m === "L" && pos > 1) pos--; else if (m === "R" && pos < n) pos++; } if (pos === goal) { console.log(start); count++; }}console.log(count);import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, goal] = lines[0].split(" ").map(Number);const moves: string = lines[1].trim();let count: number = 0;for (let start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 let pos: number = start; // 후보마다 처음부터 다시 for (const m of moves) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m === "L" && pos > 1) pos--; else if (m === "R" && pos < n) pos++; } if (pos === goal) { console.log(start); count++; }}console.log(count);import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), goal = sc.nextInt(); String moves = sc.next(); int count = 0; for (int start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 int pos = start; // 후보마다 처음부터 다시 for (char m : moves.toCharArray()) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m == 'L' && pos > 1) pos--; else if (m == 'R' && pos < n) pos++; } if (pos == goal) { System.out.println(start); count++; } } System.out.println(count); }}using System; class Program{ static void Main() { string[] first = Console.ReadLine().Split(' '); int n = int.Parse(first[0]), goal = int.Parse(first[1]); string moves = Console.ReadLine().Trim(); int count = 0; for (int start = 1; start <= n; start++) // 모두 해 보기: 출발 칸 후보 n개 { int pos = start; // 후보마다 처음부터 다시 foreach (char m in moves) // 그대로 따라 하기: 명령 하나에 한 걸음 { if (m == 'L' && pos > 1) pos--; else if (m == 'R' && pos < n) pos++; } if (pos == goal) { Console.WriteLine(start); count++; } } Console.WriteLine(count); }}#include <iostream>#include <string> int main() { int n, goal, count = 0; std::string moves; std::cin >> n >> goal >> moves; for (int start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 int pos = start; // 후보마다 처음부터 다시 for (char m : moves) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (m == 'L' && pos > 1) pos--; else if (m == 'R' && pos < n) pos++; } if (pos == goal) { std::cout << start << '\n'; count++; } } std::cout << count << '\n';}#include <stdio.h> int main(void) { int n, goal, count = 0; char moves[1001]; scanf("%d %d %1000s", &n, &goal, moves); for (int start = 1; start <= n; start++) { // 모두 해 보기: 출발 칸 후보 n개 int pos = start; // 후보마다 처음부터 다시 for (int i = 0; moves[i] != '\0'; i++) { // 그대로 따라 하기: 명령 하나에 한 걸음 if (moves[i] == 'L' && pos > 1) pos--; else if (moves[i] == 'R' && pos < n) pos++; } if (pos == goal) { printf("%d\n", start); count++; } } printf("%d\n", count); return 0;}first = コンソール.数読み();n = first[0];goal = first[1];moves = コンソール.行読み().空白除去();count = 0;繰り返す (start = 1; start <= n; start++){ pos = start; // 후보마다 처음부터 다시 それぞれ (m の中 moves) { もし (m == "L" && pos > 1) { pos -= 1; } でなければ もし (m == "R" && pos < n) { pos += 1; } } もし (pos == goal) { コンソール.書く(start); count += 1; }}コンソール.書く(count);6 3 LLLRR
1 2 3 4 4
ポイント
- シミュレーションは、問題の話を順番どおりにコードへ移します。
今の状態を変数に持ち（ここではロボットの位置pos）、一歩ごとにルールどおりに書き換えます。
壁があるので「右の数 − 左の数」のような式では答えが出ません。
実際に歩かせるのがいちばん確実です。 - 全探索は、答えになりうる候補を一つも飛ばさずに試し、条件に合うものだけを選びます。
ここでの候補は出発マス 1 番から n 番です。
飛ばした候補がなければ、見逃す答えもありません。 - 候補ごとに状態を最初に戻します。
例でpos = startが外側の繰り返しの中にあるのはそのためです。 - 書く前に何歩になるか数えます：候補の数 × 候補一つにかかる歩数。
この例は n × 命令の数です。
n 個から二つ選ぶと n × (n − 1) ÷ 2 組（n が 200 なら 19,900 組）、入れるか入れないかを n 回決めると 2ⁿ 通り（n が 20 なら約 100 万）、一列に並べる順番は n!
通り（n が 10 なら約 360 万）です。 - ここでの 1 歩は、命令一つを 1 回実行すること（内側の繰り返し 1 周）です。
この例を私たちのジャッジで計ってみると、1 千万歩（1 万マス × 命令 1 千個）は 8 言語すべてが 1 秒以内に終わりました。
1 億歩（1 万マス × 命令 1 万個）では C・C++・Java・C# は 1 秒以内、JavaScript・TypeScript は約 1 秒で終わりましたが、Python は制限時間の 4 秒を超えました。
Craykon は 4 千万歩までは終わり、5 千万歩では「時間がかかりすぎます」と言って止まりました。 - 歩数に余裕があれば全探索で十分です。
多すぎるときに初めてもっと速い方法を探し、そのときも遅い解法は小さな入力で速い解法の答えを確かめるのに使います。
言語ごとの書き方
| Python | for start in range(1, n + 1): の中で pos = start と戻し、命令は for m in moves: で 1 文字ずつ。二つ選ぶ組は itertools.combinations(nums, 2)、すべての順番は itertools.permutations(nums) が作ってくれます |
|---|---|
| JavaScript | for (let start = 1; start <= n; start++) の中で let pos = start;、命令は for (const m of moves)。二つ選ぶときは内側の繰り返しを let j = i + 1 から |
| TypeScript | JavaScript と同じです |
| Java | int pos = start; を外側の繰り返しの中に置き、命令は for (char m : moves.toCharArray())。文字はシングルクォートで比べます（ m == 'L'） |
| C# | int pos = start; を外側の繰り返しの中に置き、命令は foreach (char m in moves)。文字は 'L' |
| C++ | 命令は for (char m : moves)、文字は 'L'。すべての順番は、並べ替えた vector に std::next_permutation(v.begin(), v.end()) を偽が返るまで繰り返します |
| C | 命令は for (int i = 0; moves[i] != '\0'; i++) — 文字列の終わりの印 '\0' まで番号で回します。文字は 'L' |
| Craykon | 繰り返す (start = 1; start <= n; start++) の中で pos = start;、命令は それぞれ (m の中 moves)。1 回の実行で回れる歩数には上限があり、超えると「時間がかかりすぎます(終わらないループ?)」と言って止まります |
よくある間違い
候補ごとに戻さなかった
let sum = 0;
for (let x = 10; x <= 12; x++) {
for (const d of String(x)) sum += Number(d);
console.log(x, sum);
}→ 10 1、11 3、12 6 — 各桁の和は 1、2、3 のはずですが、前の候補の和が残って積み上がります
let sum = 0; を外側の繰り返しの中へ移し、候補ごとに 0 から始めます。
二つ選ぶときに同じ組を二度数えた
int nums[] = {1, 2, 3, 4}, count = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (nums[i] + nums[j] == 4) count++;
printf("%d\n", count);→ 3 — 和が 4 になる組は (1, 3) だけなのに、逆向きの (3, 1) と、自分自身と組んだ (2, 2) まで数えました
内側の繰り返しを j = i + 1 から始めます。
組を一度だけ見て、自分自身とは組まないので 1 になります。
マスを書き換えながら隣を読んだ
cells = list("O..")
for i in range(3):
left = i > 0 and cells[i - 1] == "O"
right = i < 2 and cells[i + 1] == "O"
cells[i] = "O" if cells[i] == "." and left != right else "."
print("".join(cells))→ ... — 答えは .O. です。ルールは「点いているマスは消え、消えているマスは点いている隣がちょうど一つのときに点く」で（left != right が「ちょうど一つ」の意味です）、すべてのマスが同時に変わらなければなりません。ところが 0 番のマスを先に消してしまったので、1 番のマスが隣を見たときにはもう消えていました
次の状態は新しいリストに書き、書き終えてから入れ替えます。after = [] を作って after.append(...) で集め、繰り返しが終わったら cells = after。
すると .O. になります。
言語ごとの違い
問題に書かれた入力の大きさから、まず歩数を数える習慣をつけましょう。
その数に余裕があれば、いちばん単純な解法がいちばん良い解法です。
シミュレーションの答えが合わないときは、小さな入力を手で一歩ずつたどり、変数の値と比べます。
まず壁のような境界で 1 マスずれていないかを見ます。
問題に書かれた入力の大きさから、まず歩数を数える習慣をつけましょう。
その数に余裕があれば、いちばん単純な解法がいちばん良い解法です。
シミュレーションの答えが合わないときは、小さな入力を手で一歩ずつたどり、変数の値と比べます。
まず壁のような境界で 1 マスずれていないかを見ます。