線形探索メニュー【区間探索 1 〜 2・連続した要素の区間・連続した要素区間の最大長・大小関係 1 〜 2】
【区間探索 1】コード
reader.on('close', () => {
const [n, x] = lines[0].split(' ').map(Number);
const a = lines[1].split(' ').map(Number);
let ans = 1; // 出力値を 1 で初期化
for (let i = 0; n - i >= ans; i++) { // 最大長を求めるので a[i]〜a[n - 1]の要素数が ans 以下になればループ終了
let count = 0; // a[i]〜a[n - 1] のうち x 以上 となる区間長を 0 で初期化
if (a[i] >= x) { // a[i] が x 以上なら…
count = 1; // count の値を 1 で上書きし…
for (let j = i + 1; j < n; j++) { // i + 1 からループ開始して…
if (a[j] >= x) { // a[i]に連なる値が x 以上なら…
count++; // count の値を 加算
} else { // さもなくば…
break; // 処理を止める
}
}
if (ans < count) { // ans より count が大きければ…
ans = count; // ans を count で上書き
}
}
}
console.log(ans);
});
2重ループを使って a[i] から始まる 全ての連続する要素について x 以上 となるかどうか 調べています。
【区間探索 2】コード
reader.on('close', () => {
const [n, x] = lines[0].split(' ').map(Number);
const a = lines[1].split(' ').map(Number);
let ans = 1;
for (let i = 0; n - i > ans; i++) {
let count = 0;
if (a[i] < x) { // a[i] が x 未満なら…
count = 1; // count の値を 加算
for (let j = i + 1; j < n; j++) {
if (a[j] < x) { // a[i]に連なる値が x 未満なら…
count++; // count の値を 加算
} else { // さもなくば…
break; // 処理を止める
}
}
if (ans < count) { // ans より count が大きければ…
ans = count; // ans を count で上書き
}
}
}
console.log(ans);
});【STEP: 1】と ほぼ同じですが 求めたい値が x 未満 となる 区間の最大長 に変わったので (a[j] < x) になりました。
【連続した要素の区間】コード
reader.on('close', () => {
const [n, x, k] = lines[0].split(' ').map(Number);
const a = lines[1].split(' ').map(Number);
let ans = 0;
for (let i = 0; i <= n - k; i++) {
if (a[i] === x) { // a[i] が x と一致すれば…
let num_x = true; // a[i]〜a[i + k - 1] が x であるかどうかの真偽値を初期化
for (let j = 1; j < k; j++) { // k 個の値を順に調べて…
if (a[i + j] !== x) { // x と一致しなければ…
num_x = false; // num_x を false で上書き
break;
}
}
if (num_x) { // num_x が初期値 (true) なら…
ans++; // ans を加算
}
}
}
console.log(ans);
});こちらも 2重ループを使って a[i]〜a[i + k – 1] の値が 全て x と一致するかどうか 調べています。
【連続した要素区間の最大長】コード
reader.on('close', () => {
const n =Number(lines[0]);
const a = lines[1].split(' ').map(Number);
let ans = 1;
for (let i = 0; i < n - ans; i++) {
const x = a[i]; // a[i] を同じ要素の基準値として x に代入
let count = 1; // a[i] から始まる x が連続する区間を 1 で初期化
for (let j = 1; j < n - i; j++) {
if (a[i + j] !== x) {
break;
} else { // a[i]に連なる値を順に調べて x と一致すれば…
count++; // count (連続する区間値) を加算
}
}
// let j = 1;
// while (a[i + j] === x && j < n - i) {
// count++;
// j++;
// }
if (ans < count) { // count が ans より大きければ…
ans = count; // count で ans を上書き
}
}
console.log(ans);
});a[i] から始まる x と一致する値 が連続する区間 を count に保存しながら count が ans より大きければ ans の値を更新しています。
【大小関係】コード
reader.on('close', () => {
const n = lines[0] - 0;
const a = lines[1].split(' ').map(Number);
let ans = 0; // 条件に一致する区間の数
for (let i = 1; i < n - 1; i++) {
const [left, center, right] = [a[i - 1], a[i], a[i + 1]];
if ((left < center && center > right) || // 中央が左右より大きいか または
(left > center && center < right)) { // 中央が左右より小さければ…
ans++; // ans を加算
}
}
console.log(ans);
});3 つの連続した値の中央の値が 最大 または 最小になる区間の数を数えるので left, center, right に 左の値, 中央の値, 右の値を 保存して条件分岐しました。
【大小関係 2】コード
reader.on('close', () => {
const n = Number(lines[0]);
const a = lines[1].split(' ').map(Number);
let ans = 0; // 条件と一致する区間の個数
for (let l = 0; l < n - 2; l++) {
for (let r = l + 2; r < n; r++) {
let up_down = true; // 中央値が最大または最小になっているかどうかの真偽値
for (let i = l + 1; i < r; i++) {
const [left, center, right] = [a[i - 1], a[i], a[i + 1]];
if (!((left < center && center > right) || // ! で戻り値を反転させています
(left > center && center < right))) {
up_down = false;
break; // 1 箇所でも条件と合わなければ 処理を止める
}
}
if (up_down) {
ans++;
}
}
}
console.log(ans);
});全ての要素が条件と一致する 区間の個数 を求めなければならないので それぞれの区間 の 全ての値 が 条件と一致するかどうか 三重ループ で調べています。問題の意味を理解するまでに かなり時間を要しました。( ´ｰ`)
コメント