JSスニペット
私はJS大好きマンなので、JSで好きなスニペットを書いていきます
別にJSでなくてもいい内容のコードも多々あります
即時無名関数
直書き
console.log("test")
のように書いてもすぐ実行されるが、以下のように
(() => {
// TODO 処理
})()
と書いて実行させる
標準入力受け取り
# これで呼ばれる前提
node main.js < input_file.txt
input = require("fs").readFileSync("/dev/stdin", "utf8");
[A, B] = input.trim().split(" ")
数値変換
a=+a
A=A.map(v=>+v)
a=~~a //これでもok
文字列変換
a=a+""
A=A.map(v=>v+"")
BigInt変換
a=BigInt(a)
A=A.map(BigInt)
ゼータ変換
A=[1,5,3,29,4,5,-2]
S=Array(A.length+1).fill(0), A.map((v,i)=>S[i+1]=S[i]+v)
GCD LCM
gcd=(x,y)=>x%y?gcd(y,x%y):y
lcm=(x,y)=>x*y/gcd(x,y)
切り上げ 切り捨て
a=5/2|0 // 切り捨て
a=5+1/2|0 // 切り上げ
グリッド転置
A=[
[1,2,3,4,5],
[1,2,3,4,5],
[1,2,3,4,5],
]
TX=A[0].map((_,i)=>A.map(v=>v[i]))
mod下での掛け算
桁数が精度溢れるけどBigInt遅くて使えないとき
prod=(a,b,mod) => {
ax=a/1e6|0, ay=a%1e6, bx=b/1e6|0, by=b%1e6
res=ax*bx*(1e12%mod)+(ax*by+ay*bx)*1e6+ay*by
return res%mod
}
連番
[...Array(100)].map((_, i) => i).forEach(...); // 0-indexed
[...Array(100).keys()].forEach(...); // 0-indexed
ブラウザ用 便利ワンライナー
const $$ = document;
const $ = v => v.startsWith('#') ? $$.getElementById(v.slice(1)) : $$.querySelector(v);
const _$ = (e = "div") => $$.createElement(e);
const DOM = str => new DOMParser().parseFromString(str, "text/html").body.firstElementChild;
const attr = (e, att) => Object.entries(att).map(([k, v]) => e[k] = v);
const css = (e, sty) => Object.entries(sty).map(([k, v]) => e.style[k] = v);
const event = (e, f, v = 'click') => e.addEventListener(v, f);
const sleep = (ms) => new Promise(r => setTimeout(r, ms));
const YYYYMMDD = new Date().toISOString().split("T")[0].replaceAll("-", "");
const rand = (min, max) => Math.floor(Math.random() * (max - min + 1) + min);
const uuid = () => crypto.randomUUID();
// yyyy-MM-DD HH:mm:ssで現在日時
const now = new Date();
const dt = now.getFullYear() + '-'
+ ('0' + (now.getMonth() + 1)).slice(-2) + '-'
+ ('0' + now.getDate()).slice(-2) + ' '
+ ('0' + now.getHours()).slice(-2) + ':'
+ ('0' + now.getMinutes()).slice(-2) + ':'
+ ('0' + now.getSeconds()).slice(-2);
DFT
exp = theta => [Math.cos(theta), Math.sin(theta)]
add = ([x1, y1], [x2, y2]) => [x1 + x2, y1 + y2]
sub = ([x1, y1], [x2, y2]) => [x1 - x2, y1 - y2]
mul = ([x1, y1], [x2, y2]) => [x1 * x2 - y1 * y2, x1 * y2 + y1 * x2]
//
dftc = (c, T) => [...Array(c.length).keys()]
.map(i => c.map((cn, n) => mul(cn, exp(T * n * i))).reduce(add, [0, 0]));
DFT = f => dftc(f, -2 * Math.PI / f.length)
IDFT = F => dftc(F, 2 * Math.PI / F.length).map(([r, i]) => [r / F.length, i / F.length])
//
discrete_tx = DFT(dat.map(r => [r, 0]));
discrete_rev = IDFT(discrete_tx).map(([r]) => r).map(Math.round);
FFT
※ビット反転で2冪丸めせずに$log_{2}N$しています、バタフライ演算は問題ないはず
exp = theta => [Math.cos(theta), Math.sin(theta)]
add = ([x1, y1], [x2, y2]) => [x1 + x2, y1 + y2]
sub = ([x1, y1], [x2, y2]) => [x1 - x2, y1 - y2]
mul = ([x1, y1], [x2, y2]) => [x1 * x2 - y1 * y2, x1 * y2 + y1 * x2]
//
fftc = (c, T, N) => {
const rec = c.map((_, n) => c[[...Array(Math.log2(N)).keys()].reduce((x, y) => (x << 1) | ((n >>> y) & 1), 0)]);
for (let Nh = 1; Nh < N; Nh *= 2) {
T /= 2;
for (let s = 0; s < N; s += Nh * 2) {
for (let i = 0; i < Nh; i++) {
const l = rec[s + i], re = mul(rec[s + i + Nh], exp(T * i));
[rec[s + i], rec[s + i + Nh]] = [add(l, re), sub(l, re)];
}
}
}
return rec;
}
FFT = f => fftc(f, -2 * Math.PI, f.length)
IFFT = F => fftc(F, 2 * Math.PI, F.length).map(([r, i]) => [r / F.length, i / F.length])
//
FFT_tx = FFT(dat.map(r => [r, 0]));
FFT_rev = IFFT(FFT_tx).map(([r]) => r).map(Math.round);
抽象非再帰セグ木
N=8
A=[1, 3, 2, 9, -10, 2, 1, 0]
// min monoid
e=1e9
op=(x,y)=>x<y?x:y
// build
seg=Array(N<<1).fill(e)
A.map((v,i)=>seg[i+N]=v)
for(i=N-1;i>=0;--i)seg[i]=op(seg[i<<1],seg[i<<1|1])
// upd
p=3,x=3
seg[p+=N]=x
while(p>>=1)seg[p]=op(seg[p<<1],seg[p<<1|1])
// prod
pd=e,l=2,r=6
for(l+=N,r+=N;l<r;l>>=1,r>>=1){
if(l&1)pd=op(pd,seg[l++])
if(r&1)pd=op(pd,seg[--r])
}
にぶたん
整数
test=x=>x>=30
L=0,R=1,MID=0
//指数探索
while(!test(R))R<<=1
while(Math.abs(R-L)>1){
if (test(MID=L+(R-L)/2)){
R=MID
}else{
L=MID
}
}
実数
test=x=>x>=31.4
L=0,R=1,MID=0
//指数探索
while(!test(R))R*=2
while(Math.abs(R-L)>1e-14&&Math.abs(R-L)/Math.max(R,L)>1e-14){
if (test(MID=L+(R-L)/2)){
R=MID
}else{
L=MID
}
}