第105回【JavaScript】特殊な2項間漸化式 1、特殊な2項間漸化式 2

現在取り組んでいるのは、paiza ラーニング問題集「DPメニュー」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

JavaScript をゼロから勉強してみよう、のコーナー 105 回目です。

正直なところ、何か問題があった場合でも、他人よりは快適に過ごせてしまうと思います。それは長年のキャンプの経験や、そのために揃えたギアがベースにあるからです。実際は、パニックになってオロオロしてしまうのでしょうけれど、気持ちを強く持つ訓練はしておこうと思っています。

それでは、今日も頑張ってみようと思います。

特殊な2項間漸化式 1 (paizaランク B 相当)

整数 x, d_1, d_2, k が与えられます。
次のように定められた数列の k 項目の値を出力してください。

・ a_1 = x 
・ a_n = a_{n-1} + d_1 (n が奇数のとき、n ≧ 3) 
・ a_n = a_{n-1} + d_2 (n が偶数のとき)

(ヒント)

添字の偶奇によって漸化式の形が変わっていますが、やることはこれまでと同じです。a_1 ~ a_{k-1} が求まっているとして、a_k をどのように計算すればよいかを考えてみましょう。計算するときに、添字の偶奇による場合分けを行えばよいです。

入力される値

x d_1 d_2 k

入力値最終行の末尾に改行が１つ入ります。

期待する出力

数列の k 項目の値を出力してください。

a_k

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

すべてのテストケースにおいて、以下の条件をみたします。

・ -1,000 ≦ x ≦ 1,000

・ -1,000 ≦ d_1 ≦ 1,000

・ -1,000 ≦ d_2 ≦ 1,000

・ 1 ≦ k ≦ 1,000

入力例

5 -7 10 5

出力例

11

これを手計算で求めろ、最大値である 1000 の場合は幾つだ、と言われたら泣きます。

JavaScript
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
  const [x,d1,d2,k] = lines[0].split(/\s/).map(Number);
  const a = [];
  a[1] = x;
  for (let i = 2; i <= k; i++) {
      if (i % 2 === 0) {
          a[i] = a[i-1] + d2;
      } else {
          a[i] = a[i-1] + d1;
      }
  }
  console.log(a[k]);
});
Python
x,d1,d2,k = map(int,input().split())
A = [x] * (k+1)
for i in range(2,k+1):
    if i % 2 == 0:
        A[i] = A[i-1] + d2
    else:
        A[i] = A[i-1] + d1
print(A[k])

特殊な2項間漸化式 2 (paizaランク B 相当)

整数 x, d_1, d_2, Q と Q 個の整数 k_1, k_2, … , k_Q が与えられます。

次のように定められた数列の k_i 項目の値を順に出力してください。

・ a_1 = x 
・ a_n = a_{n-1} + d_1 (n が奇数のとき、n ≧ 3) 
・ a_n = a_{n-1} + d_2 (n が偶数のとき)

入力される値

x d_1 d_2
Q
k_1
k_2
...
k_Q

・ 1行目では、数列の初項 x と公差 d_1, d_2 が与えられます。

・ 2行目では、3行目以降で与えられる入力の行数 Q が与えられます。

・ 続く Q 行のうち i 行目では、k_i が与えられます。

入力値最終行の末尾に改行が１つ入ります。

期待する出力

Q 行出力してください。

i 行目には、数列の k_i 項目の値を出力してください。

a_{k_1}
a_{k_2}
...
a_{k_Q}

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

すべてのテストケースにおいて、以下の条件をみたします。

・ -1,000 ≦ x ≦ 1,000

・ -1,000 ≦ d_1 ≦ 1,000

・ -1,000 ≦ d_2 ≦ 1,000

・ 1 ≦ Q ≦ 1,000

・ 1 ≦ k_i ≦ 1,000 (1 ≦ i ≦ Q)

入力例

3 7 -4
5
1
2
3
4
10

出力例

3
-1
6
2
11

最大値が 1000 なので、とりあえず 1000 個の解答を用意しておく。

JavaScript
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
  const [x,d1,d2] = lines[0].split(/\s/).map(Number);
  const a = Array(1001);
  a.fill(x);
  for (let i = 2; i < 1001; i++) {
      if (i % 2 === 0) {
          a[i] = a[i-1] + d2;
      } else {
          a[i] = a[i-1] + d1;
      }
  }
  const Q = Number(lines[1]);
  for (let i = 2; i <= Q + 1; i++) {
      const k = Number(lines[i]);
      console.log(a[k]);
  }
});
Python
x,d1,d2 = map(int,input().split())
A = [x] * (1001)
for i in range(2,1001):
    if i % 2 == 0:
        A[i] = A[i-1] + d2
    else:
        A[i] = A[i-1] + d1
Q = int(input())
for _ in range(Q):
    print(A[int(input())])

最後に

1000 個くらいであれば、JavaScript でも問題なく解くことが出来ます。しかし、速度的にはどうなんでしょう。こういった計算をするのに適した言語であるかどうかはよく分かりません。

Array や fill といったメソッドを使いこなせるようになれば、コードの幅が広がりそうなので、しっかり学習を続けようと思います。

引き続き、よろしくお願いいたします！

Python の第105回はこちら

JavaScriptJavaScript,学習,paiza

Posted by LeoSaki