Zenn
💾

AtCoder×Typesciprt コードメモ

2024/05/22に公開
TypeScript
AtCoder
tech

概要

ここ最近、TypescriptでAtCoderに参加している。
流用できそうなコードの備忘録をここに残す。順次追加予定。

階乗

コード
// 階乗を計算する
export const factorial = (n: number): number | null => {
  if (n < 0) return null;
  let rtn = 1;
  for (let index = n; index > 1; index--) {
    rtn *= index;
  }
  return rtn;
};

Deque(両端キュー)

TypescriptのArrayでは、shift()とunshift()の計算時間がO(n)と時間がかかる（push()とpop()はO(1)。）
AtCoderではこの計算量がネックになるときがあるが、TSではDequeは用意されていないため、自前で実装した。（たぶんO(1)でできてるはず）
と、言ってもこちらの素敵な記事から真似て作ったので、元記事のコードのほうが見やすい。
https://note.com/kuri_tter/n/nfdc782e07a88

下記コードは前述の記事を見ながら、自分で勉強がてら実装したDeque。

コード
class Node<T> {
  public prev: Node<T> | undefined = undefined;
  public next: Node<T> | undefined = undefined;

  constructor(public value: T) {}
}

class Deque<T> {
  private head: Node<T> | undefined = undefined;
  private tail: Node<T> | undefined = undefined;
  private length = 0;

  public push(value: T): void {
    const node = new Node(value);

    // push前のtailの処理
    if (this.tail !== undefined) this.tail.next = node;
    node.prev = this.tail;

    // 空だった場合はheadを設定
    if (this.head === undefined) this.head = node;

    this.tail = node;
    this.length++;
  }

  public pop(): T | undefined {
    const node = this.tail;

    if (node !== undefined) {
      this.tail = node?.prev;
      this.length--;

      // 新しいtailのnextを消去
      if (this.tail !== undefined) this.tail.next = undefined;

      // 空になったらheadを消去
      if (node.prev === undefined) this.head = undefined;
    }
    return node?.value;
  }

  public shift(): T | undefined {
    const node = this.head;
    if (node !== undefined) {
      this.head = node?.next;
      this.length--;

      // 新しいheadのprevを消去
      if (this.head !== undefined) this.head.prev = undefined;

      // 空になったらtailを消去
      if (node.next === undefined) this.tail = undefined;
    }
    return node?.value;
  }

  public unshift(value: T): void {
    const node = new Node(value);

    // unshift前のheadの処理
    if (this.head !== undefined) this.head.prev = node;
    node.next = this.head;

    // 空だった場合はtailを設定
    if (this.tail === undefined) this.tail = node;

    this.head = node;
    this.length++;
  }

  public getHead(): T | undefined {
    return this.head?.value;
  }

  public getTail(): T | undefined {
    return this.tail?.value;
  }

  public getLength(): number {
    return this.length;
  }

  public toArray(): T[] {
    const result: T[] = [];
    let current = this.head;
    while (current) {
      result.push(current.value);
      current = current.next;
    }
    return result;
  }
}

OrderedSet(順序付き集合)

要素の追加、削除、最小値や最大値の取得がO(logN)で済む（済んでいるはず）集合。AVL木で実装。ChatGPTに書いてもらって精査はできてない。

コード
class AVLNode<T> {
  value: T;
  height: number;
  left: AVLNode<T> | null;
  right: AVLNode<T> | null;

  constructor(value: T) {
    this.value = value;
    this.height = 1; // 新しいノードの高さは1
    this.left = null;
    this.right = null;
  }
}

class AVLTree<T> {
  root: AVLNode<T> | null = null;
  private nodeCount: number = 0;

  // ノードの高さを取得するヘルパー関数
  private getHeight(node: AVLNode<T> | null): number {
    return node ? node.height : 0;
  }

  // ノードのバランスファクターを取得するヘルパー関数
  private getBalanceFactor(node: AVLNode<T> | null): number {
    return node ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
  }

  // 右回転
  private rotateRight(y: AVLNode<T>): AVLNode<T> {
    const x = y.left!;
    const T2 = x.right;

    x.right = y;
    y.left = T2;

    y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1;
    x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1;

    return x;
  }

  // 左回転
  private rotateLeft(x: AVLNode<T>): AVLNode<T> {
    const y = x.right!;
    const T2 = y.left;

    y.left = x;
    x.right = T2;

    x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1;
    y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1;

    return y;
  }

  // 挿入
  insert(value: T): void {
    this.root = this.insertNode(this.root, value);
  }

  private insertNode(node: AVLNode<T> | null, value: T): AVLNode<T> {
    if (node === null) {
      this.nodeCount++;
      return new AVLNode(value);
    }

    if (value < node.value) {
      node.left = this.insertNode(node.left, value);
    } else if (value > node.value) {
      node.right = this.insertNode(node.right, value);
    } else {
      return node; // 重複する値は無視する
    }

    node.height =
      1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));

    const balance = this.getBalanceFactor(node);

    // 左左ケース
    if (balance > 1 && value < node.left!.value) {
      return this.rotateRight(node);
    }

    // 右右ケース
    if (balance < -1 && value > node.right!.value) {
      return this.rotateLeft(node);
    }

    // 左右ケース
    if (balance > 1 && value > node.left!.value) {
      node.left = this.rotateLeft(node.left!);
      return this.rotateRight(node);
    }

    // 右左ケース
    if (balance < -1 && value < node.right!.value) {
      node.right = this.rotateRight(node.right!);
      return this.rotateLeft(node);
    }

    return node;
  }

  // 削除
  delete(value: T): void {
    this.root = this.deleteNode(this.root, value);
  }

  private deleteNode(node: AVLNode<T> | null, value: T): AVLNode<T> | null {
    if (node === null) {
      return node;
    }

    if (value < node.value) {
      node.left = this.deleteNode(node.left, value);
    } else if (value > node.value) {
      node.right = this.deleteNode(node.right, value);
    } else {
      if (node.left === null || node.right === null) {
        const temp = node.left ? node.left : node.right;

        if (temp === null) {
          node = null;
        } else {
          node = temp;
        }
        this.nodeCount--;
      } else {
        const temp = this.getMinValueNode(node.right);
        node.value = temp.value;
        node.right = this.deleteNode(node.right, temp.value);
      }
    }

    if (node === null) {
      return node;
    }

    node.height =
      1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));

    const balance = this.getBalanceFactor(node);

    // 左左ケース
    if (balance > 1 && this.getBalanceFactor(node.left) >= 0) {
      return this.rotateRight(node);
    }

    // 左右ケース
    if (balance > 1 && this.getBalanceFactor(node.left) < 0) {
      node.left = this.rotateLeft(node.left!);
      return this.rotateRight(node);
    }

    // 右右ケース
    if (balance < -1 && this.getBalanceFactor(node.right) <= 0) {
      return this.rotateLeft(node);
    }

    // 右左ケース
    if (balance < -1 && this.getBalanceFactor(node.right) > 0) {
      node.right = this.rotateRight(node.right!);
      return this.rotateLeft(node);
    }

    return node;
  }

  private getMinValueNode(node: AVLNode<T>): AVLNode<T> {
    let current = node;
    while (current.left !== null) {
      current = current.left;
    }
    return current;
  }

  private getMaxValueNode(node: AVLNode<T>): AVLNode<T> {
    let current = node;
    while (current.right !== null) {
      current = current.right;
    }
    return current;
  }

  // ノードを検索
  search(value: T): boolean {
    return this.searchNode(this.root, value) !== null;
  }

  private searchNode(node: AVLNode<T> | null, value: T): AVLNode<T> | null {
    if (node === null || node.value === value) {
      return node;
    }

    if (value < node.value) {
      return this.searchNode(node.left, value);
    }

    return this.searchNode(node.right, value);
  }

  getSize(): number {
    return this.nodeCount;
  }

  getMin(): T | null {
    if (this.root === null) {
      return null;
    }
    return this.getMinValueNode(this.root).value;
  }

  getMax(): T | null {
    if (this.root === null) {
      return null;
    }
    return this.getMaxValueNode(this.root).value;
  }
}

class OrderedSet<T> {
  private tree: AVLTree<T>;

  constructor() {
    this.tree = new AVLTree<T>();
  }

  add(value: T): void {
    if (!this.contains(value)) {
      this.tree.insert(value);
    }
  }

  remove(value: T): void {
    this.tree.delete(value);
  }

  contains(value: T): boolean {
    return this.tree.search(value);
  }

  // 集合の要素を昇順に取得
  toArray(): T[] {
    const result: T[] = [];
    this.inorderTraversal(this.tree.root, result);
    return result;
  }

  // 順に要素を取得するためのヘルパー関数
  private inorderTraversal(node: AVLNode<T> | null, result: T[]): void {
    if (node !== null) {
      this.inorderTraversal(node.left, result);
      result.push(node.value);
      this.inorderTraversal(node.right, result);
    }
  }

  size(): number {
    return this.tree.getSize();
  }

  getMin(): T | null {
    return this.tree.getMin();
  }

  getMax(): T | null {
    return this.tree.getMax();
  }
}

全順列

コード
// 全順列を列挙する
export const allPermutations = <T>(list: T[]) => {
  if (list.length < 2) {
    return [list];
  }

  const rtnList: T[][] = [];
  for (let i = 0; i < list.length; i++) {
    const val = list[i];
    const rest = list.slice();
    rest.splice(i, 1);
    allPermutations(rest).forEach((p) => {
      rtnList.push([val].concat(p));
    });
  }

  return rtnList;
};

計算量

入力要素数nの入力に対しO(n!)かかるはず。（実際に計測などはしていない。）
10^{10}あたりが限界とすると、使えるのはだいたい12個くらいまで。

要素数n n! 位
1 1 10^0
5 120 10^2
10 3,628,800 10^6
11 39,916,800 10^7
12 479,001,600 10^8
13 6,227,020,800 10^9
14 87,178,291,200 10^{10}

Discussion