2021-06-19

JavaScriptで償却定数時間キュー

技術 JavaScript

class Queue {
    constructor() {
        this.front = [];
        this.back = [];
    }

    isEmpty() {
        return this.front.length == 0 && this.back.length == 0;
    }

    push(x) {
        this.back.push(x);
    }

    pop() {
        if(this.isEmpty()) { return undefined; }
        if(this.front.length == 0) {
            this.back.reverse();
            [this.front, this.back] = [this.back, this.front];
        }
        return this.front.pop();
    }
}

各要素ごとにreverse操作は高々1回しか行われないので償却してO(1)

github.com

2021-04-15

SICP 練習問題1.19 フィボナッチ数を対数時間で求める

技術 Lisp

$a \leftarrow a + b, b \leftarrow a$

から

また

から

よって

(define (even? x) (= (remainder x 2) 0))

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   (+ (* p p) (* q q))
                   (* q (+ (* p 2) q))
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

2021-01-25

office365のsmtpサーバについて

host: smtp.office365.com:587
encrypt: TLS
username: office365アカウントemail
pass: office365アカウントpassword

2020-12-08

アセンブリ言語で書いたサブルーチンをC言語から呼び出す

技術アセンブラ

メモ

str.h

int strlen(const char*);

str.asm

global strlen

section .text

; int strlen(const char*)
strlen:
    xor rax, rax
_L1:
    cmp [rdi], byte 0
    jz _L2
    inc rax
    inc rdi
    jmp _L1
_L2:
    ret

test.c

#include <stdio.h>
#include <str.h>

int main(void) {
    printf("%d\n", strlen("Hello, World!\n"));
    return 0;
}

ビルド

$ nasm -f elf64 str.h -o str.o
$ gcc -c -I . test.c -o test.o
$ gcc str.o test.o -o test
$ ./test

2020-12-04

ABC080 D - Recording

技術

問題

atcoder.jp

お気持ち

区間加算して最大値を求める問題
連続する区間は1つにするというところからxorを使いたくなる
チャンネル数が少ないので整数型に収まる
なのでxorでimos法をする

コード

fn main() {
    read_init!(buf);
    let (n, c): (usize, usize) = (read!(buf), read!(buf));
    let stc: Vec<(usize, usize, usize)> = (0..n)
        .map(|_| (read!(buf), read!(buf), read!(buf)))
        .collect();
 
    println!("{}", solve(n, c, stc));
}
 
fn solve(n: usize, c: usize, stc: Vec<(usize, usize, usize)>) -> usize {
    let t_max = stc.iter().map(|(s, t, c)| t).cloned().max().unwrap_or(0);
    let mut imos = Imos::new(t_max + 3);
    for &(s, t, c) in stc.iter() {
        imos.query(s, t + 1, 1 << (c - 1));
    }
    imos.apply()
        .into_iter()
        .map(|x| x.count_ones())
        .max()
        .unwrap_or(0) as usize
}
 
struct Imos {
    array: Vec<u32>,
    len: usize,
}
 
impl Imos {
    fn new(len: usize) -> Self {
        Self {
            array: vec![0; len],
            len: len,
        }
    }
 
    fn query(&mut self, left: usize, right: usize, value: u32) {
        assert!(left < right);
        self.array[left] ^= value;
        self.array[right] ^= value;
    }
 
    fn apply(&self) -> Vec<u32> {
        self.array
            .iter()
            .scan(0u32, |s, &e| {
                *s = *s ^ e;
                Some(*s)
            })
            .collect()
    }
}

atcoder.jp

2020-11-09

x86_64アセンブリでechoプログラム書いた

技術アセンブラ

環境

Ryzen 5 2600
Windows10 2004 WSL2 Ubuntu 20.04.1 LTS
NASM version 2.14.02
GNU ld (GNU Binutils for Ubuntu) 2.34

コード

global _start

section .text

_start:
    mov rbp, rsp
    jmp main

main:
    sub rsp, 0x100 ; char string[256];

    mov rax, rbp
    sub rax, 0x100

    push 0x100
    push rax
    call read
    add rsp, 0x10

    mov rax, rbp
    sub rax, 0x100

    push 0x100
    push rax
    call write
    add rsp, 0x10

    mov eax, 0
    jmp exit

; int read(char *string, int length)
read:
    push rbp
    mov rbp, rsp

    mov rax, 0 ; syscall read
    mov rdi, 0 ; stdin
    mov rsi, [rbp + 16]
    mov edx, [rbp + 24]
    syscall
    mov rsp, rbp
    pop rbp
    ret

; void write(char *string, int length)
write:
    push rbp
    mov rbp, rsp

    mov rax, 1 ; syscall write
    mov rdi, 1 ; stdout
    mov rsi, [rbp + 16]
    mov edx, [rbp + 24]
    syscall

    mov rsp, rbp
    pop rbp
    ret

; void exit(int status)
exit:
    mov edi, eax
    mov rax, 60 ; syscall exit
    syscall