paizaラーニング レベルアップ問題集 新・Bランクレベルアップメニュー JavaScript 【全探索 3】+1, -1, '1'+, +'1'

【全探索 3】+1, -1, '1'+, +'1' (paizaランク B 相当)

考え方

2 ≦ N ≦ 8 と制約が小さいので、全探索できる。
Xについての５つの操作を先にして配列を作っておく。
2 つの自然数の全ての組み合わせ、それらについての操作方法の全ての組み合わせで、
絶対値の差を求め、最小値を更新していく。

解答例(C++の場合参考)

問題文通りに実装するとかえって複雑になるので、筋道を整理し、簡潔にする。

例えば、問題文の順序に沿って実装すると、２つの自然数を選んだ後に、５つの操作を行うと、操作が複数回出てきて処理が長くなるので、先に５つの操作を処理してしまう。

また、

2.操作後の 2 つの数の差の絶対値の最小値を求める。
3.2.で求めることができる値のうち最小の値をラッキーナンバーとする。

とあるが、全ての２つの自然数の組み合わせ、全ての操作の組み合わせを、一気にまとめて、絶対値の計算をし、最小値を求めてもよい。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [N] = lines[0].split(" ").map(Number);
let ans = Infinity;

//1.占い師が N 個の自然数 X_1, ..., X_N を宣言する。

//2-1.選んだ 2 つの各数字に対して、次のいずれかの操作を 1 回おこなうことができる。
//各数字について別々の操作をおこなうことができる。（おこわなくても良い）

//先にX_iそれぞれ、５つの処理をしてしまう.
const X = Array(N).fill().map(v => v = Array(5).fill().map(v => v = []));
for (let i = 0; i < N; i++) {
  X[i][0] = Number(lines[i + 1]);
  X[i][1] = X[i][0] + 1;
  X[i][2] = X[i][0] - 1;
  X[i][3] = Number("1" + String(X[i][0]));
  X[i][4] = Number(String(X[i][0]) + "1");
}

//一気にまとめて処理
//2.それらから 2 つの自然数を選ぶような全ての組み合わせについて
for (let i = 0; i < N; i++) { //iとjで２つの自然数の組み合わせ全て
  for (let j = i + 1; j < N; j++) {
    for (let k = 0; k < 5; k++) { //kとlで処理方法の組み合わせ全て
      for (let l = 0; l < 5; l++) {
        //2-2.操作後の 2 つの数の差の絶対値の最小値を求める。
        ans = Math.min(ans, Math.abs(X[i][k] - X[j][l]));//最小値更新
      }
    }
  }
}

//3.2. で求めることができる値のうち最小の値をラッキーナンバーとする。
console.log(ans);