見出し画像
Photo by フィンセント・ファン・ゴッホ / メトロポリタン美術館

AtCoder Beginner Contest 320 A-EをTypeScriptで解く。

Qlitre

AtCoder Beginner Contest 320に参加をしました。
コンテスト自体はPythonで参加をしたのですが、Typescriptで振り返り記事を書いていきます。


結果

A-Eの5完でした。
今回はC問題でちょっと躓いて、A,B,D,C,Eという流れで解きました。

それでは早速コンテストを振り返っていきます。

A - Leyland Number

A,Bが与えられるので、AのB乗 + BのA乗を足す問題です。
珍しくやるだけかな？という感じでした。

import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";


function main() {
    const [a, b] = nextNums(2);
    log(a ** b + b ** a);
}

let inputs = "";
let inputArray: string[];
let currentIndex = 0;

function next() {
    return inputArray[currentIndex++];
}
function nextNum() {
    return +next();
}
function nextBigInt() {
    return BigInt(next());
}
function nexts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = next();
    return arr;
}
function nextNums(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextNum();
    return arr;
}
function nextBigInts(length: number) {
    const arr = [];
    for (let i = 0; i < length; ++i) arr[i] = nextBigInt();
    return arr;
}

// デバッグ環境がWindowsであれば条件分岐する
if (process.env.OS == "Windows_NT") {
    const stream = createInterface({
        input: process.stdin,
        output: process.stdout,
    });
    stream.on("line", (line) => {
        inputs += line;
        inputs += "\n";
    });
    stream.on("close", () => {
        inputArray = inputs.split(/\s/);
        main();
    });
} else {
    inputs = fs.readFileSync("/dev/stdin", "utf8");
    inputArray = inputs.split(/\s/);
    main();
}

B - Longest Palindrome

文字列が与えられて、回文であるような部分文字列の最大の長さを出力する問題です。
長さが100までと短いので、愚直に全探索をして回文かどうか判定すれば答えがだせます。

import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";


/**
 * 
 * @param s 文字列
 * @returns 回文ならtrueを返す
 */
export const isPalindrome = (s: string): boolean => {
    const normalized = s.toLowerCase().replace(/[^a-z0-9]/g, '');
    const reversed = normalized.split('').reverse().join('');
    return normalized === reversed;
}

function main() {
    const s = next();
    let ans = 0;
    for (let i = 0; i < s.length; ++i) {
        for (let j = i; j < s.length; ++j) {
            const sub = s.substring(i, j + 1);
            if (isPalindrome(sub)) {
                ans = Math.max(ans, sub.length);
            }
        }
    }
    log(ans);
}

C - Slot Strategy 2 (Easy)

0～9までの数字がランダムに振られたスロットリールが３つあります。
ある時刻にスロットリールのボタンを一つ押すことができて、押すとスロットの数字が確定します。数字３つ揃えるのに最小の時間を求める、という問題です。

けっこう難しいなーと思いました。
スロットリールの長さは最大で100ほどと短いので、早い段階で全探索かな？と気づきました。しかし、その後の実装でバグがなかなか消えませんでした。

スロットは同時に押すことができないので、押す順番次第ではリールが一周回ってしまいます。
例えば

0123
0231


みたいなリールがあって、２で揃えたいとします。
このとき上のリールを押して先に確定させると、下のリールの２の位置よりも進んでいるので一周した後に確定することになります。

このあたりの周回の管理でバグらせてしまい時間を溶かしてしまいました。

考え方としては、３つ揃えるということはスロットが回るのは最大でも３週ほどでしょうか。なので、予めリールをちょっと多めに伸ばしておくと、判定が楽になります。

上の例で２倍に伸ばした場合：

01230123
02310231

このようにすると、周回を気にしなくても良いのでぐっと見通しが良いです。今回は安全マージンをとって、５倍に拡張して解いてみました。

import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";

// 5倍に拡張する
function getExpanded(s: string): string {
    let res = "";
    for (let i = 0; i < 5; ++i) {
        res += s;
    }
    return res;
}

// 次の数字を見つける
function findNum(s: string, startTime: number, num: string): number {
    let ret = 10**9;
    for (let i = startTime; i < s.length; i++) {
        if (s[i] === num) {
            ret = i;
            break;
        }
    }
    return ret
}

function main() {
    const m = nextNum();
    // 多めに五倍の長さで取っておく
    const s1 = getExpanded(next());
    const s2 = getExpanded(next());
    const s3 = getExpanded(next());
    const data: string[] = [s1, s2, s3]
    const perm = [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
    let ans = 10 ** 9;
    // 数字を全探索
    for (let i = 0; i < 10; ++i) {
        const num = String(i);
        for (const p of perm) {
            let time = 0;
            time = findNum(data[p[0]], time, num);
            time = findNum(data[p[1]], time + 1, num);
            time = findNum(data[p[2]], time + 1, num);
            if (time === -1) continue;
            ans = Math.min(ans, time);
        }
    }
    if (ans === 10 ** 9) ans = -1;
    log(ans);
}

D - Relative Position

座標平面上に1からNまでの番号がついたN人がいます。人1は原点に位置しています。以下のようなM個の情報が与えられます。

人 Ai​ から見て、人 Bi​ は、x 軸正方向に Xi​、y 軸正方向に Yi​ 離れた位置にいる

そうして、それぞれの人のポジションを求める、という問題です。

M個の情報は矛盾しないという制約があるので、人１のポジションがから順番にBFSで辿って、絶対的なポジションを確定させていけばいいです。
情報は相対的なものなので、人１から辿れない場合は位置が決まりません。その場合はundecidableを出力します。

import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";

class Node<T> {
    public value: T;
    public prev: Node<T> | null;
    public next: Node<T> | null;

    constructor(value: T) {
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

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

    public append(value: T): void {
        const node = new Node(value);
        if (!this.head) {
            this.head = node;
            this.tail = node;
        } else {
            node.prev = this.tail;
            this.tail!.next = node;
            this.tail = node;
        }
        this.length++;
    }

    public appendleft(value: T): void {
        const node = new Node(value);
        if (!this.head) {
            this.head = node;
            this.tail = node;
        } else {
            node.next = this.head;
            this.head!.prev = node;
            this.head = node;
        }
        this.length++;
    }

    public pop(): T | null {
        if (!this.tail) {
            return null;
        }
        const node = this.tail;
        if (this.head === this.tail) {
            this.head = null;
            this.tail = null;
        } else {
            this.tail = node.prev;
            this.tail!.next = null;
            node.prev = null;
        }
        this.length--;
        return node.value;
    }

    public popleft(): T | null {
        if (!this.head) {
            return null;
        }
        const node = this.head;
        if (this.head === this.tail) {
            this.head = null;
            this.tail = null;
        } else {
            this.head = node.next;
            this.head!.prev = null;
            node.next = null;
        }
        this.length--;
        return node.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;
    }
}


function main() {
    const [n, m] = nextNums(2);
    // graphを構築
    const graph: Record<number, number[][]> = {};
    for (let i = 0; i < m; ++i) {
        const [a, b, x, y] = nextNums(4);
        if (!graph[a]) graph[a] = [];
        if (!graph[b]) graph[b] = [];
        graph[a].push([b, x, y]);
        graph[b].push([a, -x, -y]);
    }
    // que  [now, x, y]
    const que = new Deque<number[]>();
    const vis = new Set();
    que.append([1, 0, 0]);
    vis.add(1);
    // undecidableで初期化
    const ans = new Array(n + 1).fill("undecidable");
    ans[1]="0 0";
    // BFSして確定させていく
    while (que.getLength() > 0) {
        const [now, x, y] = que.popleft()!;
        if (graph[now] == undefined) continue;
        for (const elm of graph[now]) {
            const [next, nx, ny] = elm;
            if (vis.has(next)) continue;
            const newX = x + nx;
            const newY = y + ny;
            vis.add(next);
            ans[next] = `${newX} ${newY}`
            que.append([next, newX, newY]);
        }
    }
    // 答えを出力
    for(let i=1;i<=n;++i){
        log(ans[i])
    }
}

E - Somen Nagashi

「そうめん流し」イベントにN人が参加し、1からNまでの番号が付けられて一列に並んでいます。
M回の出来事が起き、それぞれの出来事で特定の時刻Tiに量Wiのそうめんが流されます。列の先頭にいる人がそのそうめんを全て獲得し、時刻Ti + Siに列の元の位置に戻ります。M回の出来事後に各人が獲得したそうめんの量を計算する問題です。

人数の制約が200,000ほどと大きいので、効率的に管理しないとTLEしそうです。管理する情報を整理すると、

  • いま並んでいる人で最小の番号の人はだれか

  • 特定のイベント発生時に列に戻る人はだれか

Ti + Siは入力によって変わるので、先に順番待ちになった人が最初に列に戻るわけではないのが、問題のミソでしょうか。

優先度付きキューを用いて、並んでいる人と待っている人を管理して…と言う風にやりました。

import { createInterface } from "readline";
import * as fs from "fs";
import { log } from "console";
import { exit } from "process";

export class BinaryHeap<T> {
    public heap: T[];
    private compare: (a: T, b: T) => number;

    constructor(compareFn: (a: T, b: T) => number) {
        this.heap = [];
        this.compare = compareFn;
    }

    public push(value: T): void {
        this.heap.push(value);
        this.bubbleUp(this.heap.length - 1);
    }

    public pop(): T | undefined {
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            const result = this.heap[0];
            this.heap[0] = last!;
            this.sinkDown(0);
            return result;
        } else {
            return last;
        }
    }

    private bubbleUp(index: number): void {
        const element = this.heap[index];
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            const parent = this.heap[parentIndex];
            if (this.compare(element, parent) >= 0) {
                break;
            }
            this.heap[index] = parent;
            this.heap[parentIndex] = element;
            index = parentIndex;
        }
    }

    private sinkDown(index: number): void {
        const element = this.heap[index];
        const length = this.heap.length;
        while (true) {
            const leftChildIndex = 2 * index + 1;
            const rightChildIndex = 2 * index + 2;
            let leftChild: T, rightChild: T;
            let swapIndex = null;
            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (this.compare(leftChild, element) < 0) {
                    swapIndex = leftChildIndex;
                }
            }
            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if ((swapIndex === null && this.compare(rightChild, element) < 0) ||
                    (swapIndex !== null && this.compare(rightChild, leftChild!) < 0)) {
                    swapIndex = rightChildIndex;
                }
            }
            if (swapIndex === null) {
                break;
            }
            this.heap[index] = this.heap[swapIndex];
            this.heap[swapIndex] = element;
            index = swapIndex;
        }
    }

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


function main() {
    const [n, m] = nextNums(2);
    // 列に並んでいる人
    const pq = new BinaryHeap<number>((a, b) => a - b);
    for (let i = 0; i < n; ++i) {
        pq.push(i);
    }
    // 待っている人
    const waiting = new BinaryHeap<number[]>((a, b) => a[0] - b[0]);
    // 答え
    const ans = new Array(n).fill(0);
    for (let i = 0; i < m; ++i) {
        const [t, w, s] = nextNums(3);
        // 待っている人と今の時間を比較
        while (waiting.size() > 0) {
            const [nxt, person] = waiting.pop()!;
            if (nxt <= t) {
                // 列に戻る
                pq.push(person);
            } else {
                // 戻れる人がいないので終了
                waiting.push([nxt, person]);
                break
            }
        }
        if (pq.size() > 0) {
            const person = pq.pop()!;
            ans[person] += w;
            waiting.push([t + s, person]);
        }
    }
    // 答えの出力
    for (const num of ans) {
        log(num);
    }
}

おわりに

久しぶりにE問題までしっかりと解けたので良かったです。
ではでは。

この記事が気に入ったらサポートをしてみませんか？