線形探索メニュー応用編【前後関係の基本・連続する k 要素・部分数列・部分列 ほか】
【前後関係の基本】コード
reader.on('close', () => {
const n = Number(lines[0]);
const A = lines[1].split(' ').map(Number);
let ans = 0; // ans(出力値)を 0 で 初期化
for (let i = 0; i < n - 1; i++) {
if (A[i] === A[i + 1]) { // A[i] と A[i + 1] が一致すれば
ans++; // ans を加算
}
}
console.log(ans);
});
ans を 0 で 初期化して A[i] と A[i + 1] が一致すれば ans を加算すればOKでした。
【連続する 3 要素】コード
reader.on('close', () => {
const n = Number(lines[0]);
const A = lines[1].split(' ').map(Number);
const S = [0]; // A の 各値の 累積和 を保存する配列
let ans = 1; // ans (出力値)を 1 で初期化
for (let i = 0; i < n; i++) {
S.push(S[i] + A[i]); // S に S[i] + A[i] (累積和) を追加
}
let MAX = S[3]; // MAX (連続する3要素の最大値)を S[3] で初期化
for (let i = 4; i <= n; i++) {
if (S[i] - S[i - 3] > MAX) { // S[i + 3] - S[i] が MAX より大きれば
MAX = S[i] - S[i - 3]; // MAX を上書き
ans = i - 2; // ans を i - 2 で更新
}
}
console.log(ans);
});- a の 累積和 を s に保存。
- MAX (連続する3要素の最大値)を s[3] で初期化。
- s[i ] – s[i – 3] が MAX より大きればMAX とans の値を更新。
【連続する k 要素 1】コード
reader.on('close', () => {
const [n, k] = lines[0].split(' ').map(Number);
const A = lines[1].split(' ').map(Number);
const S = [0];
let ans = 1;
for (let i = 0; i < n; i++) {
S.push(S[i] + A[i]);
}
let MAX = S[k]; // MAX (最大値)を S[k] で初期化
for (let i = k; i <= n; i++) {
if (S[i] - S[i - k] > MAX) {
MAX = S[i] - S[i - k];
ans = i - k + 1;
}
}
console.log(ans);
});【STEP: 2】は 連続する 3 要素でしたが 要素数が k になったので 3 を k に置き換えていますが それ以外は【STEP: 2】と同じです。
【連続する k 要素 2】コード
reader.on('close', () => {
const [n, k] = lines[0].split(' ').map(Number);
const A = lines[1].split(' ').map(Number);
const S = [0];
let ans = 1;
for (let i = 0; i < n; i++) {
S.push(S[i] + A[i]);
// console.log(S);
}
let MAX = S[k]; // MAX (最大値)を S[k] で初期化
for (let i = k; i <= n; i++) {
if (S[i] - S[i - k] >= MAX) {
MAX = S[i] - S[i - k];
ans = i - k + 1;
}
}
console.log(ans);
});【STEP: 3】と ほぼ同じコードですが 条件が i の 「大きい方の値」になったので s[i]- s[i – k]の値と MAX が同じ値でも ans の値が上書きされるよう 条件式が s[i]- s[i – k]>= MAX になっています。
【部分数列】コード
reader.on('close', () => {
const [n, m] = lines[0].split(' ').map(Number); // n = A の要素数, m = b の要素数
const A = lines[1].split(' ').map(Number);
const b = lines[2].split(' ').map(Number);
let ans = -1; // 等しい数列がない場合の出力値は -1 なので -1 で初期化
for (let i = 0; i <= n - m; i++) {
const a_slice = A.slice(i, i + m); // A の部分配列を生成し a_slice に保存
let same = true; // a_slice と b の各値が一致しているかどうかの真偽値
for (let j = 0; j < m; j++) {
if (a_slice[j] !== b[j]) { // a_slice[j] と b[j] が異なっていれば…
same = false; // same を false で上書き
break;
}
}
if (same) {
ans = i + 1;
break;
}
}
console.log(ans);
});A の一部分を切り取った各値と b の各値が全て一致していないとダメなので 2重ループを使って 先ず a から部分配列(a_slice)を取出した要素と b の要素が全て一致するかどうか調べました。
【部分列】コード
reader.on('close', () => {
const [n, m] = lines[0].split(' ').map(Number); // n = A の要素数, m = b の要素数
const A = lines[1].split(' ').map(Number);
const b = lines[2].split(' ').map(Number);
let ans = true;
for (let i = 0; i < m; i++) {
let a_index = -1; // b[i - 1]と一致した A の要素の添字
if (A.includes(b[i]) && a_index < A.indexOf(b[i])) {
// A に b[i] が含まれていて a_index が A.indexOf(b[i]) 未満の場合
a_index = A.indexOf(b[i]); // a_index の値をa.indexOf(b[i])で上書き
} else {
ans = false;
break;
}
}
console.log(ans ? 'Yes' : 'No');
});a に b[i] が含まれていれば 含まれていた場所の 添字 も 記録することで 元の順序で並んでいるかどうか 調べることができました。
コメント