箱とボール《スタック・キュー 応用》

スタック・キューメニュー【2つのキュー・最大の区間和・逆ポーランド記法・括弧列・エスカレーター・箱とボール】

問題【STEP: 1】2 つのキュー
Task
各クエリに応じて値を出力してね。

【2 つのキュー】コード

reader.on('close', () => {
   const Q = Number(lines[0]);
   const A = [[],[]];
   for (let i = 1; i <= Q; i++) {
      const query = lines[i].split(' ');
      switch (query[0]) {  // query[0]の値で処理を振り分け
      case '1':  // PUSH
         A[query[1] - 1].push(query[2]);  // A[query[1] - 1] に query[2]を追加
         break;
      case '2':  // POP(SHIFT)
         console.log(A[query[1] - 1].shift());  // A[query[1] - 1]
         break;
      case '3':  // SIZE
         console.log(A[0].length, A[1].length);  // 各要素数を出力
         break;
      }
   }
});
hogeちゃんの画像
2つの キュー を二次元配列 A に設置。A[0].length, A[1].lengthで 各要素数を出力。

 

top
問題【STEP: 2】最大の区間和
Task
数列 A の連続した X 個の要素の和の最大値とその区間の左端の値は?

【最大の区間和】コード 1/4 (50 点)

  // タイムオーバーで 50 点 になったコード
reader.on('close', () => {
   const [N, X] = lines[0].split(' ').map(Number);
   const A = lines[1].split(' ').map(Number);
   const Q = [];
   for (let i = 0; i < X; i++) {
      Q.push(A[i]);
   }
   let max = Q.reduce((a, b) => a + b);
   let left = A[0];
   for (let i = X; i < N; i++) {
      Q.push(A[i]);
      Q.shift();
      const sum = Q.reduce((a, c) => a + c);
      if (max < sum) {
         max = sum;
         left = Q[0];
      }
   }
   console.log(max, left);
});
hogeちゃんの画像

タイムオーバーで 50 点 でした。

top

【最大の区間和】コード 2/4  (75 点)

  // タイムオーバーで 75 点(C++の実装例参照)
reader.on('close', () => {
   const [N, X] = lines[0].split(' ').map(Number);
   const A = lines[1].split(' ').map(Number);
   let sum = 0;
   let max = 0;
   let left = A[0];
   const Q = [];
   for (let i = 0; i < N; i++) {
      sum += A[i];
      Q.push(A[i]);
      if (Q.length === X) {
         if (sum > max) {
            left = Q[0];
            max = sum;
         }
         sum -= (Q.shift());
      }
   }
   console.log(max, left);
});
hogeちゃんの画像

C++の実装例を参照しましたが タイムオーバーで 75 点 でした。

top

【最大の区間和】コード 3/4 (100 点・リスト)

  // 100点(Python3の 実装例参照)
reader.on('close', () => {
   const [N, X] = lines[0].split(' ').map(Number);
   const A = lines[1].split(' ').map(Number);
   let sum = 0;
   let max = 0;
   let left = A[0];
   for (let i = 0; i < X; i++) {
      sum += A[i];
   }
   max = sum;
   for (let i = X; i < N; i++) {
      sum += A[i];
      sum -= A[i - X];
      if (max < sum) {
         max = sum;
         left = A[i - X + 1];
      }
   }
   console.log(max, left);
});
hogeちゃんの画像

 Python3の 実装例 を見ながらコードを書き換えました。これはリストを使った方法…。( ˘ω˘  )なんだかなぁ。。

top

【最大の区間和】コード 4/4 (100点・累積和)

  // 100点(累積和)
reader.on('close', () => {
   const [N, X] = lines[0].split(' ').map(Number);
   const A = lines[1].split(' ').map(Number);
   const S = [0];
   let max_sum = 0;
   let left = 0;
   for (let i = 0; i < N; i++) {
      S.push(A[i] + S[i]);
   }
   for (let i = X; i <= N; i++) {
      const sum = S[i] - S[i - X];
      if (sum > max_sum) {
         max_sum = sum;
         left = A[i - X];
      }
   }
   console.log(max_sum, left);
});
hogeちゃんの画像

累積和を使ったパターン。

top
問題【STEP: 3】逆ポーランド記法
Task
逆ポーランド記法 で書かれた数式の 計算結果を出力してね。

【逆ポーランド記法】コード 1/3

reader.on('close', () => {
   const N = Number(lines[0]);
   const A = lines[1].split(' ');
   const S = [];  // スタック
   for (let i = 0; i < N; i++) {
      if (A[i] !== '+' && A[i] !== '-') {  // A[i] が '+','-'以外なら…
         S.push(Number(A[i]));  // スタックにA[i]を保存
      } else {
         const num1 = S.pop();  // S の末尾の値を取出→num1 に代入
         const num2 = S.pop();  // S の末尾の値を取出→num2 に代入
         switch (A[i]) {  // A[i] が…
         case '+':  // '+' なら…
            S.push(num1 + num2);  // S に num1 + num2 を保存
            break;
         case '-':  // '-' なら…
            S.push(num2 - num1);  // S に num2 - num1 を保存
            break;
         }
      }
   }
   console.log(...S);
});
hogeちゃんの画像

逆ポーランド記法のプログラミングのへ応用については Wikipedia の解説が分かりやすかったです。

top

【逆ポーランド記法】コード 2/3

reader.on('close', () => {
   const N = Number(lines[0]);
   const A = lines[1].split(' ');
   const S = []; // スタック
   for (let i = 0; i < N; i++) {
      let Acc = 0;  // アキュムレータ
      switch (A[i]) {
      case '+':  // 足し算の場合…
         Acc += S.pop();  // S の末尾の値を取出→Accに加算
         Acc += S.pop();  // S の末尾の値を取出→Accに加算
         S.push(Acc);  // S に Acc を保存
         break;
      case '-':  // 引き算の場合…
         Acc += S.pop()*-1;  // S の末尾の値を取出→符号を反転→ Acc に加算
         Acc += S.pop();  // S の末尾の値を取出→ Acc に加算
         S.push(Acc);  // S に Acc を保存
         break;
      default:  // '+','-'以外
         S.push(Number(A[i]));  // S に A[i] を保存
      }
   }
   console.log(...S);
});
hogeちゃんの画像

アキュムレータに計算結果を保存してから スタック に追加…。

top

【逆ポーランド記法】コード 3/3

reader.on('close', () => {
   const N = Number(lines[0]);
   const A = lines[1].split(' ');
   const S = []; // スタック
   for (let i = 0; i < N; i++) {
      let Register = 0;  // レジスタ(データを記憶)
      switch (A[i]) {
      case '+':  // 足し算の場合…
         Register = S.pop();  // スタックからデータを下ろしレジスタに保存
         S[S.length - 1] += Register;  // スタックトップにレジスタの値を加算
         break;
      case '-':  // 引き算の場合…
         Register = S.pop();  // スタックからデータを下ろしレジスタに保存
         S[S.length - 1] -= Register;  // スタックトップからレジスタの値を減算
         break;
      default:  // '+','-'以外
         S.push(Number(A[i]));  // S に A[i] を保存
      }
   }
   console.log(...S);
});
hogeちゃんの画像

“+” または “-” の場合 スタックから 末尾の値を取出し その上で 新たな末尾の値に取り出した値を 加算 または 減算しています。

top
問題【STEP: 4】括弧列
Task
N 文字の 括弧列 S が与えられるので 正しい括弧列 かどうか判定してね。

【括弧列】コード 1/2

reader.on('close', () => {
   const N = Number(lines[0]);
   const S = lines[1];  // 括弧列
   const Stack = [];  // スタック
   for (let i = 0; i < N; i++) {
      if (N % 2) {  // N が奇数なら…
         Stack.push(1);  // スタックに１を追加して…
         break;  // ループを止める
      } else if (S[i] === '(') {  // '(' なら…
         Stack.push(1);  // スタックに１を追加
      } else if (S[i] === ')') {  // ')' なら…
         if(!Stack.length){  // スタックが空の場合は…
            Stack.push(1);  // スタックに１を追加して…
            break;  // ループを止める
         }else{  // スタックが空でなければ…
            Stack.pop();  // スタックの末尾の要素を取出
         }
      }
   }
   console.log(Stack[0] ? 'No' : 'Yes');  // Stack[0] が true→'No'・false→'Yes'
});
hogeちゃんの画像
if文 で条件分岐し  ‘(‘  なら Stack に1を追加。  ‘)’  なら Stack 末尾の1を取出。最後に 1 が残れば ″No″ を出力。何もなければ ″Yes″ を出力しています。
top

【括弧列】コード 2/2

reader.on('close', () => {
   const N = Number(lines[0]);
   const S = lines[1];
   let resurt = 0;
   for (let i = 0; i < N; i++) {
      if (N % 2 || resurt < 0) {  // N が奇数 または resurt が負の数なら…
         resurt--;  // resurt -１
         break;  // ループを止める
      } else {
         switch (S[i]) {  // S[i]が…
         case '(':  // '(' なら…
            resurt++;  // resurt + 1; 
            break;
         case ')':  //  ')' なら…
            resurt--;  // resurt - 1; 
            break;
         }
      }
   }
   console.log(!resurt ? 'Yes' : 'No');  // resurt が 0 →'Yes', 0 以外 → 'No'
});
hogeちゃんの画像
if文 と switch文 で条件分岐し  ‘(‘  なら resurt に 1 加算。  ‘)’  なら1 減算。N が奇数 だったり resurt  が負の数になれば resurt を減算してループを止めています。resurtが 0 で’Yes’, 0 以外 なら ‘No’。
top
問題【STEP: 5】エスカレーター
Task
1 秒で 1m 進む全長 K m のエスカレーター上にいる人数を答えてね。

【エスカレーター】コード

reader.on('close', () => {
   const [N, K] = lines[0].split(' ').map(Number);
   const A = lines[1].split(' ').map(Number);
   const ESC = new Array(K).fill(0);  // 全長 K の エスカレータ(キュー)
   const L = A[N - 1];  // 最後の社員がエスカレータに乗る時間
   for (let i = 1; i <= L; i++) {  // 1〜L秒までループ
      if (A[0] === i) {  // A の先頭が i なら…
         ESC.push(1);  // 1人乗る
         ESC.shift();  // 1人 または 0人降りる
         A.shift();  // A の先頭の値を削除
         console.log(ESC.reduce((a, c) => a + c));  // 乗っている人数を集計して出力
      } else {
         ESC.push(0);  // 0人乗る
         ESC.shift();  // 1人 または 0人 降りる
      }
   }
});
hogeちゃんの画像

ESC の初期値は すべて 0。L は最後の人が ESC に乗る時間。経過時間と A[0] が一致すれば ESC の末尾に １ を追加し ESC と A の先頭の要素を削除。一致しなければ ESC の末尾に 0 を追加し ESC  の先頭の要素を削除しています。

top
問題【FINAL】箱とボール
Task
数値が書かれた ボールを順に箱の底へ入れてると最終的にどうなる?
※同じ数値が隣合うと結合して数値が倍増します。

【箱とボール】コード

reader.on('close', () => {
   const N = Number(lines[0]);
   const A = lines[1].split(' ').map(Number);
   const S = [];  // ボールを入れる箱(スタック)
   for (let i = 0; i < N; i++) {
      S.push(A.shift());  // A からボールを取出し S に入れる
      let L = S.length;  // L は S の要素数
      while (L >= 2 && S[L - 1] === S[L - 2]) {  // 隣あったボールの数字が同じなら
         S[L - 2] += S.pop();  // 結合して数値が倍増
         L = S.length;  // L の値を更新
      }
   }
   while (S.length) {  // S に要素がある間
     console.log(S.pop());  // S からボールを取出し 出力
   }
});
hogeちゃんの画像

A の値を 順次 S に 積み上げて  S[L – 1] と S[L – 2] が同じであれば S の末尾の要素を取出し S[L – 2]に加算しています。

top

コメント