第111回【JavaScript】最長増加連続部分列、【連続列】最長減少連続部分列
現在取り組んでいるのは、paiza ラーニング問題集「DPメニュー」になります。
https://paiza.jp/worksはじめに
猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。
JavaScript をゼロから勉強してみよう、のコーナー 111 回目です。
あれやりたい、これやりたい、と欲はあるのですが、時間が足りません。さらに欲が高まっているタイミングに限って、業務が重なったり LunaSaki（嫁）が体調崩したり。
それでは、今日も頑張ってみようと思います。
最長増加連続部分列 (paizaランク B 相当)
https://paiza.jp/works/mondai/dp_primer/dp_primer_lis_contin...n 人が横一列に並んでいます。左から i 番目の人を人 i と呼ぶことにします。人 i の身長は a_i [cm]です。
人 l ,人 l+1, … , 人 r からなる区間 [l, r] について、すべての l ≦ i < r に対して a_i ≦ a_{i+1} が成り立っているとき、区間 [l, r] は背の順であると呼ぶことにします。また、区間 [l, r] の長さを r-l+1 とします。
背の順であるような区間のうち、最長であるものの長さを出力してください。
(ヒント)
元の問題を解くために、部分問題としてどのような問題を考えればよいでしょうか。
dp[n] を、人 n が右端となっているような背の順区間のうち、最長であるような区間の長さとしてみましょう。dp[1] ~ dp[k-1] が既に求まっているとして、dp[k] がどうなるかを考えてみましょう。dp[k-1] に注目すると、dp[k-1] は人 k-1 を右端とする背の順区間の長さですから、もし a_{k-1} ≦ a_k なら、その区間の右端に人 k をくっつけることで新しく長さ dp[k-1]+1 の背の順区間を作ることができ、この区間の長さは人 k を右端として持つ背の順区間のうち最長であることがわかります。逆に、もし a_{k-1} ＞ a_k なら、人 k が右端となるような背の順区間は人 k のみからなる長さ1の区間しか存在しないことがわかります。
以上の考察により、dp[k-1] と dp[k] の関係が明らかになりました。自信のある人は自分で漸化式を立ててみましょう。以下の疑似コードに従って、自分の得意な言語で実装してみましょう。
dp[1] <- 1
for i = 2 to n
if a[i-1] <= a[i] then
dp[i] <- dp[i-1]+1
else
dp[i] <- 1
print max({dp[1], ... ,dp[n]})入力される値
n
a_1
a_2
...
a_n・ 1行目に、横一列に並んでいる人の人数 n が与えられます。
・ 続く n 行のうち i 行目では、人 i の身長 a_i が与えられます。
入力値最終行の末尾に改行が１つ入ります。
期待する出力
背の順であるような区間のうち、最長であるものの長さを出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 200,000
・ 100 ≦ a_i ≦ 200
入力例
5
160
178
170
190
190出力例
3やり方を知っていないと、なかなか解答に辿り着けないのではないでしょうか。
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 n = Number(lines[0]);
const a = [];
for (let i = 1; i <= n; i++) {
a.push(Number(lines[i]));
}
const dp = Array(n+1).fill(1);
for (let i = 1; i <= n; i++) {
if (a[i-1] <= a[i]) {
dp[i] = dp[i-1] + 1;
} else {
dp[i] = 1;
}
}
const max = dp.reduce((a,b) => Math.max(a,b));
console.log(max);
});Python
n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1] * n
for i in range(1,n):
if A[i-1] <= A[i]:
dp[i] = dp[i-1] + 1
else:
dp[i] = 1
print(max(dp))【連続列】最長減少連続部分列 (paizaランク B 相当)
https://paiza.jp/works/mondai/dp_primer/dp_primer_lis_contin...n 人が横一列に並んでいます。左から i 番目の人を人 i と呼ぶことにします。人 i の身長は a_i [cm]です。
人 l ,人 l+1, … , 人 r からなる区間 [l, r] について、すべての l ≦ i < r に対して a_i ≧ a_{i+1} が成り立っているとき、区間 [l, r] は逆背の順であると呼ぶことにします。また、区間 [l, r] の長さを r-l+1 とします。
逆背の順であるような区間のうち、最長であるものの長さを出力してください。
入力される値
n
a_1
a_2
...
a_n・ 1行目に、横一列に並んでいる人の人数 n が与えられます。
・ 続く n 行のうち i 行目では、人 i の身長 a_i が与えられます。
入力値最終行の末尾に改行が１つ入ります。
期待する出力
逆背の順であるような区間のうち、最長であるものの長さを出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 200,000
・ 100 ≦ a_i ≦ 200
入力例
5
187
192
115
108
109出力例
3今度は逆背の順。さっきと逆になっただけかな。でも、ちゃんと手打ちして書いてみよう。それが大事。
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 n = Number(lines[0]);
const a = [];
for (let i = 1; i <= n; i++) {
a.push(Number(lines[i]));
}
const dp = Array(n+1).fill(1);
for (let i = 1; i <= n; i++) {
if (a[i-1] >= a[i]) {
dp[i] = dp[i-1] + 1;
} else {
dp[i] = 1;
}
}
const max = dp.reduce((a,b) => Math.max(a,b));
console.log(max);
});Python
n = int(input())
A = [int(input()) for _ in range(n)]
dp = [1] * n
for i in range(1,n):
if A[i-1] >= A[i]:
dp[i] = dp[i-1] + 1
else:
dp[i] = 1
print(max(dp))最後に
200000 件のデータで、0.16 秒。やはり、JavaScript は早いですね。同じデータで Python で試してみると、0.33 秒かかりました。
LeoSaki（旦那）としては、書きやすいのはやはり Python ですが、速度の違いを見せつけられてしまうと、JavaScript を更に極めたくなってしまいます。
引き続き、よろしくお願いいたします！
