Created by
cia_rana
last modified
| #include <iostream>
#include <list>
using namespace std;
#define SKIP_NUM 2 + 1
#define INPUT_SUP 100
void solve() {
// SKIP_NUM個前までの入力，最大値を保存するリスト
list<int> inputs, each_combo;
for(int i = 0; i < SKIP_NUM; i++) {
inputs.push_back(INPUT_SUP);
each_combo.push_back(0);
}
int n;
cin >> n;
int current_input, current_combo, combo_max = 0;
for(int i = 0; i < n; i++) {
cin >> current_input;
current_combo = 1;
std::list<int>::iterator inputs_itr = inputs.begin();
std::list<int>::iterator each_combo_itr = each_combo.begin();
for(int j = 0; j < SKIP_NUM; j++) {
if(*inputs_itr < current_input && current_combo <= *each_combo_itr) {
current_combo = (*each_combo_itr) + 1;
}
inputs_itr++;
each_combo_itr++;
}
combo_max = max(combo_max, current_combo);
each_combo.pop_front();
each_combo.push_back(current_combo);
inputs.pop_front();
inputs.push_back(current_input);
}
cout << combo_max;
}
int main(void){
solve();
return 0;
}
|
| #include <iostream>
#include <list>
using namespace std;
#define SKIP_NUM 2 + 1
#define INPUT_SUP 100
void solve() {
// SKIP_NUM個前までの入力，最大値を保存するリスト
list<int> inputs(SKIP_NUM, INPUT_SUP), each_max(SKIP_NUM, 0);
int n;
cin >> n;
int current_input, current_combo, combo_max = 0;
for(int i = 0; i < n; i++) {
cin >> current_input;
current_combo = 1;
auto inputs_itr = inputs.begin();
auto each_max_itr = each_max.begin();
for(int j = 0; j < SKIP_NUM; j++) {
if(*inputs_itr < current_input && current_combo <= *each_max_itr) {
current_combo = *each_max_itr + 1;
}
inputs_itr++;
each_max_itr++;
}
combo_max = max(combo_max, current_combo);
inputs.pop_front();
inputs.push_back(current_input);
each_max.pop_front();
each_max.push_back(current_combo);
}
cout << combo_max;
}
int main(void){
solve();
return 0;
}
|
| // 幅制約付き最長増加部分列問題(Range-Constrained Longest Increasing Subsequence)として解く．
// n: 入力数，m: スキップ数としたとき，
// 時間計算量O(nlong(m))，空間計算量O(n)のアルゴリズムが存在するが，
// 今回のn，mは比較的小さく，事前計算のオーバーへッドが大きいので，
// 今回は時間計算量O(nm)，空間計算量O(m)のアルゴリズムを採用している．
using System;
using System.Linq;
using System.Collections.Generic;
class Solver
{
private static readonly int SKIP_NUM = 3; // 何個前まで見るか
private static readonly int INPUT_SUP = 100; // 入力値の上限
public void solve()
{
// 入力数は使わないので破棄
Console.ReadLine();
var inputs = new List<int>(); // SKIP_NUM個前までの入力を格納
var eachCombo = new List<int>(); // SKIP_NUM個前までのコンボを格納
foreach (int _ in Enumerable.Range(0, SKIP_NUM))
{
inputs.Add(INPUT_SUP);
eachCombo.Add(0);
}
// 最大コンボを見つける
int comboMax = 0;
foreach (int currentInput in Console.ReadLine().Split(' ')
.Select(int.Parse).ToArray())
{
int currentCombo = 1;
foreach (int skip in Enumerable.Range(0, SKIP_NUM))
{
if (inputs[skip] < currentInput && currentCombo <= eachCombo[skip])
{
currentCombo = eachCombo[skip] + 1;
}
}
comboMax = Math.Max(comboMax, currentCombo);
inputs.RemoveAt(0);
inputs.Add(currentInput);
eachCombo.RemoveAt(0);
eachCombo.Add(currentCombo);
}
Console.Write(comboMax);
}
}
class Program
{
static void Main(string[] args)
{
var solver = new Solver();
solver.solve();
}
}
|
| // 幅制約付き最長増加部分列問題(Range-Constrained Longest Increasing Subsequence)として解く．
// n: 入力数，m: スキップ数としたとき，
// 時間計算量O(nlong(m))，空間計算量O(n)のアルゴリズムが存在するが，
// 今回のn，mは比較的小さく，事前計算のオーバーへッドが大きいので，
// 今回は時間計算量O(nm)，空間計算量O(m)のアルゴリズムを採用している．
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.List;
import java.util.LinkedList;
import java.util.stream.Stream;
import java.util.stream.Collectors;
import java.util.Iterator;
import java.lang.Math;
class Solver {
private static final int SKIP_NUM = 3; // 何個前まで見るか
private static final int INPUT_SUP = 100; // 入力値の上限
public void solve() throws Exception {
try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
// 入力数は使わないので破棄
br.readLine();
// SKIP_NUM個前までの入力を格納
List<Integer> inputs = Stream.generate(() -> INPUT_SUP)
.limit(SKIP_NUM)
.collect(Collectors.toCollection(LinkedList::new));
// SKIP_NUM個前までの最大コンボを格納
List<Integer> eachMax = Stream.generate(() -> 0)
.limit(SKIP_NUM)
.collect(Collectors.toCollection(LinkedList::new));
// 最大コンボを見つける
int comboMax = 0;
for (int currentInput : Stream.of(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray()) {
int currentCombo = 1;
Iterator<Integer> inputsItr = inputs.iterator();
Iterator<Integer> eachMaxItr = eachMax.iterator();
for (int i = 0; i < SKIP_NUM; i++) {
int input = inputsItr.next();
int max = eachMaxItr.next();
if (input < currentInput && currentCombo <= max) {
currentCombo = max + 1;
}
}
comboMax = Math.max(comboMax, currentCombo);
inputs.add(currentInput);
inputs.remove(0);
eachMax.add(currentCombo);
eachMax.remove(0);
}
System.out.println(comboMax);
}
}
}
public class Main {
public static void main(String[] args) throws Exception {
Solver solver = new Solver();
solver.solve();
}
}
|
| // 幅制約付き最長増加部分列問題(Range-Constrained Longest Increasing Subsequence)として解く．
// n: 入力数，m: スキップ数としたとき，
// 時間計算量O(nlong(m))，空間計算量O(n)のアルゴリズムが存在するが，
// 今回のn，mは比較的小さく，事前計算のオーバーへッドが大きいので，
// 今回は時間計算量O(nm)，空間計算量O(m)のアルゴリズムを採用している．
(function() {
const SKIP_NUM = 3; // 何個前まで見るか
const NUM_SUP = 100; // 入力値の上限
function solve(n, nums) {
// SKIP_NUM個前までの入力を格納
var preNums = new Array(SKIP_NUM);
// SKIP_NUM個前までのコンボを格納
var eachCombo = new Array(SKIP_NUM);
for (var i = 0; i < SKIP_NUM; i++) {
preNums[i] = NUM_SUP;
eachCombo[i] = 0;
}
// 最大コンボを見つける
var comboMax = 0;
nums.forEach(function(currentNum) {
var currentCombo = 1;
for (var i = 0; i < SKIP_NUM; i++) {
if (preNums[i] < currentNum && currentCombo <= eachCombo[i]) {
currentCombo = eachCombo[i] + 1;
}
}
comboMax = Math.max(comboMax, currentCombo);
preNums.push(currentNum);
preNums.shift();
eachCombo.push(currentCombo);
eachCombo.shift();
});
return comboMax;
}
function main(args) {
var n = Number(args[0]);
var nums = args[1].split(" ").map(Number);
console.log(solve(n, nums));
return;
}
// あらかじめ標準入力を全て読み込み，main functionを起動
(function() {
var lines = [];
var reader = require("readline").createInterface({
input: process.stdin,
output: process.stdout,
terminal: false
});
reader.on("line", function(line) {
lines.push(line);
});
process.stdin.on("end", function() {
main(lines);
});
})();
})();
|
| <?php
const SKIP_NUM = 3;
const INPUT_SUP = 100;
$n = trim(fgets(STDIN));
$inputs = array(); // 入力されるランダムな整数列を格納
$each_combo = array(); // SKIP_NUM前までのコンボ数を格納
for($i = 0; $i < SKIP_NUM; $i++) {
array_push($inputs, INPUT_SUP);
array_push($each_combo, 0);
}
$inputs = array_merge($inputs, explode(" ", trim(fgets(STDIN))));
$combo_max = 0;
for($i = 0; $i < $n; $i++) {
$current_combo = 1;
$input = $inputs[$i + SKIP_NUM];
for($skip = 0; $skip < SKIP_NUM; $skip++) {
if($inputs[$i + $skip] < $input && $current_combo <= $each_combo[$skip]) {
$current_combo = $each_combo[$skip] + 1;
}
}
$combo_max = max($combo_max, $current_combo);
array_push($each_combo, $current_combo);
array_shift($each_combo);
}
print($combo_max);
|
