paizaの森練習問題コンテスト過去問題9

paizaの森練習問題

hogeちゃん

2023.05.03

paizaの森練習問題コンテスト(2023年4月開催)の過去問です。

問題【最大値と最小値】

Task

3 つの整数の中で最も小さい値と最も大きい値を求めてね。

【最大値と最小値】コード

reader.on('close', () => {
   const [a, b, c] = lines[0].split(' ').map(Number);
   console.log(Math.min(a, b, c), Math.max(a, b, c));
});

hogeちゃんの画像

Math.min() で最小値。Math.max() で最大値。

問題【卵の生産】

Task

1 日で a 個の卵を産むニワトリ。n 日間で何個産むかを求めてね。

【卵の生産】コード

reader.on('close', () => {
   const [a, n] = lines[0].split(' ');
   console.log(a * n);
});

hogeちゃんの画像

a 個 ✕n 日なので a * n。

問題【卵の最大の生産量】

Task

i 日目に a_i 個卵を産むニワトリから k 日連続で卵を貰えるとき最大何個貰える?

【卵の最大の生産量】コード

reader.on('close', () => {
   const [n, k] = lines[0].split(' ').map(Number);
   const A = lines[1].split(' ').map(Number);
   const S = [0];  // A の累積和
   for (let i = 0; i < n; i++) {
      S.push(S[i] + A[i]);  // A の累積和を S に保存
   }
   let ans = 0;
   for (let i = k; i < n; i++) {
      const eggs = S[i] - S[i - k];  // eggs は i - k + 1 日目 ~ i 日目に産んだ数
      if (eggs  > ans) {  // eggs が ans より多ければ…
         ans = eggs;  // ans を上書き
      }
   }
   console.log(ans);
});

hogeちゃんの画像

累積和を使っています。

問題【卵の最大の生産量 – その 2】

Task

i 日目に a_i 個卵を産むニワトリからk 日間連続で卵を貰えるとき最大何個貰える?

【卵の最大の生産量 – その 2】コード

reader.on('close', () => {
   const [n, k] = lines[0].split(' ').map(Number);
   const A = lines[1].split(' ').map(Number);
   const S = [0];  // A の累積和
   for (let i = 0; i < n; i++) {
      S.push(S[i] + A[i]);  // A の累積和を S に保存
   }
   let ans = 0;
   for (let i = k; i < n; i++) {
      const eggs = S[i] - S[i - k];  // eggs は i - k + 1 日目 ~ i 日目に産んだ数
      if (eggs  > ans) {  // eggs が ans より多ければ…
         ans = eggs;  // ans を上書き
      }
   }
   console.log(ans);
});

hogeちゃんの画像

その１と同じ…。(^_^;)

問題【卵をぴったり生産】

Task

ニワトリを自由に選択して卵の総和が k 個になる選び方は何通り？

【卵をぴったり生産】コード

reader.on('close', () => {
   const hen = lines[1].split(' ').map(Number);
   const [n, k] = lines[0].split(' ').map(Number);
   const dp = [1];  // index個にする方法のパターン数を保存する配列
   for (let i = 1; i <= k; i++) {
      dp.push(0);  // パターン数を0で初期化
   }
   for (let i = 0; i < n; i++) {
      for (let j = k; j >= hen[i]; j--) {
         dp[j] += dp[j - hen[i]];
  // j 個にするパターン数にj-hen[i]グラムにするパターン数を加算
      }
   }
   console.log(dp[k]);
});

hogeちゃんの画像

DPメニュー【部分和問題 1 〜 4 】のコードを応用しました。

【卵をぴったり生産】!失敗《54点》

reader.on('close', () => {
   function perfect_production(arr, n, k) {
      const combination = [];
      if (n === 1) {
         for (let i = 0; i < arr.length; i++) {
            combination[i] = [arr[i]];
         }
      } else {
         for (let i = 0; i < arr.length - n + 1; i++) {
            let row = perfect_production(arr.slice(i + 1), n - 1);
            for (let j = 0; j < row.length; j++) {
               combination.push([arr[i]].concat(row[j]));
            }
         }
      }
      return combination;
   }
   let ans = 0;
   const [N, K] = lines[0].split(' ').map(Number);
   const hen = lines[1].split(' ').map(Number);
   for (let i = 1; i <= N; i++) {
      const eggs = perfect_production(hen, i, K);
      for (let j = 0; j < eggs.length; j++) {
         if (eggs[j].reduce((a, c) => a + c) === K) {
            ans++;
         }
      }
   }
   console.log(ans);
});

hogeちゃんの画像

100点にならなかったけど一応残しておきます。

コメント