配列
配列に対する便利メソッド群
作成にあたっては https://underscorejs.org/ を参考
使用方法はサンプル参照
code: Underscore.js
class Underscore {
sum(arr) { return arr.reduce((a,b)=>a+b); }
modSum(arr,mod) { if (mod == null) { mod = MOD.mod; } return arr.reduce((a,b)=>(a+b)%mod); }
min(arr, func) { if (func == null) {func = (a,b) => a - b} return arr.reduce((a,b) => func(a,b) < 0 ? a : b); }
max(arr, func) { if (func == null) {func = (a,b) => a - b} return arr.reduce((a,b) => func(a,b) > 0 ? a : b); }
sort(arr, func) { if (func == null) {func = (a,b) => a - b} return arr.sort(func) }
uniq(arr) {
arr.sort();
for(let i = 0; i < arr.length - 1; ++i) {
arri = arri+1 == arri ? null : arri;
}
return arr.filter(e => e != null);
}
range(start, stop, step) {
if (stop == null) {
stop = start || 0;
start = 0;
}
if (!step) {
step = stop < start ? -1 : 1;
}
const length = Math.max(Math.ceil((stop - start) / step), 0);
const range = Array(length);
for (var idx = 0; idx < length; idx++, start += step) {
rangeidx = start;
}
return range;
}
first (array, n) {
if (array == null || array.length < 1) return n == null ? void 0 : [];
if (n == null) return array0;
return this.initial(array, array.length - n);
};
initial (array, n) { return array.slice.call(array, 0, Math.max(0, array.length - (n == null ? 1 : n))); }
tail(array, n) { return array.slice.call(array, n == null ? 1 : n); }
last (array, n) {
if (n == null) return arrayarray.length - 1;
return this.tail(array, Math.max(0, array.length - n));
}
/* 累積和 */
sumArray (arr) { return this.tail(arr.reduce(((a,b,i) => {a.push(b + ai); return a}), 0)); }
diffArray (arr) { const s = []; for (let i = 1; i < arr.length; ++i) { s.push(arri - arri-1); } return s; }
/* 二分探索による配列検索 */
binarySearch (array, key, iteratee) {
const itr = (obj) => (typeof obj === 'object') ? objiteratee : obj;
const value = itr(obj);
let low = 0, high = array.length;
while (low < high) {
let mid = Math.floor((low + high) / 2);
if (itr(arraymid) < value) low = mid + 1; else high = mid;
}
return low;
};
}
const _ = new Underscore();
サンプル
code: sample.js
const arr = 1,2,3,4,5;
// 先頭要素
console.log(_.first(arr)); // => 1
// 最終要素
console.log(_.last(arr)); // => 5
// 和
console.log(_.sum(arr)); // => 15
// 累積和
console.log(_.sumArray(arr)); // => 1, 3, 6, 10, 15
// 指定した範囲の配列
console.log(_.range(0,10)); // => 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
// 指定した範囲の配列 (stepを指定)
console.log(_.range(0,20,3)); // => 0, 3, 6, 9, 12, 15, 18
// ソート済み配列に対してのバイナリサーチ
// key以上となる最初の要素のindexを返す
const arr2 = 10,20,30,40,50;
console.log(_.binarySearch(arr,2)); // => 1
console.log(_.binarySearch(arr2,25)); // => 2
const fib = 1,3,8,13,5,2;
// 最大値
console.log(_.max(fib)); // => 13
// 最小値
console.log(_.min(fib)); // => 1
// js通常のソートでは辞書順でソートされてしまう
console.log(fib.sort()); // => 1, 13, 2, 3, 5, 8
// 数値順をデフォルトとするソート
console.log(_.sort(fib)); // => 1, 2, 3, 5, 8, 13
配列の二分探索
ABC119 D
code: abc119_d.js
solve() {
const nums = input.nextIntArr();
const sLine = input.nextIntLine(nums0);
const tLine = input.nextIntLine(nums1);
const xLine = input.nextIntLine(nums2);
const largeNumber = 1e12;
sLine-1 = (-largeNumber);
tLine-1 = (-largeNumber);
sLine.push(largeNumber);
tLine.push(largeNumber);
console.log(xLine.map((x) => {
const si = _.binarySearch(sLine,x);
const ti = _.binarySearch(tLine,x);
const left = Math.max(x - sLinesi-1, x - tLineti-1);
const right = Math.max(sLinesi - x,tLineti - x);
const minS = Math.min(x - sLinesi-1, sLinesi - x);
const minT = Math.min(x - tLineti - 1, tLineti - x);
const both = minS + minT + Math.min(minS, minT);
return Math.min(left, right, both);
}).join('\n'));
}
配列の差分
ARC067 D - Walk and Teleport
code: arc067_d.js
solve() {
const nab = input.nextIntArr();
const seq = input.nextIntArr();
return _.sum(_.diffArray(seq).map(e => Math.min(e * nab1,nab2)));
}
Issue
便利メソッドの追加 (必要になり次第)
二つの配列の全組み合わせ配列 _.product(arr1,arr2,func)
RubyのArray#productに相当