久しぶりにAtCoderの参加記録を書こうと思う。

結果はA-Eの５完６ペナ。E問題はChatGPTで通してしまったので、自力ではまだ解いていない。

そのため、今回の記事ではA-Dまでの４問を振り返る。言語はTypescript。

本戦時はPythonで参加しているが、たまに練習を兼ねてTypescriptで解き直すということを行っている。

A - Penalty Kick

https://atcoder.jp/contests/abc348/tasks/abc348_a

数字が与えられ3の倍数の時はx、そうじゃないときはoをつなげた文字を出力する。

例えば6だったらooxoox。いわゆる「やるだけ」という問題だ。

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


function main() {
    const n = nextNum()
    let ans = ''
    for (let i = 1; i <= n; i++) {
        if (i % 3 == 0) {
            ans += 'x'
        } else {
            ans += 'o'
        }
    }
    console.log(ans)
}

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

let outputBuffer = "";

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;
}

function print(out: string | number | bigint): void;
function print<T>(out: Array<T>, separator: string): void;
function print<T>(out: string | number | bigint | Array<T>, separator?: string) {
    if (Array.isArray(out)) {
        outputBuffer += out.join(separator);
    } else {
        outputBuffer += out;
    }
}

function println(out: string | number | bigint): void;
function println<T>(out: Array<T>, separator: string): void;
function println<T>(out: string | number | bigint | Array<T>, separator?: string) {
    if (Array.isArray(out)) {
        print(out, separator || "");
    } else {
        print(out);
    }
    print("\n");
}

function flush() {
    console.log(outputBuffer);
}

// デバッグ環境が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();
        flush();
    });
} else {
    inputs = fs.readFileSync("/dev/stdin", "utf8");
    inputArray = inputs.split(/\s/);
    main();
    flush();
}

B - Farthest Point

https://atcoder.jp/contests/abc348/tasks/abc348_b

N個の点の座標が与えられる。各点について、その点からの距離が最大である点を求めてその点の番号を出力する。 ただし、距離が最大である点が複数ある場合はその中で最も番号が小さい点の番号を出力する。

距離はユークリッド距離で計算する。正確な距離ではなく大小の比較だけでいいので、２乗した値のまま比較をする。

function calcDist(x1: number, y1: number, x2: number, y2: number) {
    const x = Math.abs(x1 - x2);
    const y = Math.abs(y1 - y2);
    return x ** 2 + y ** 2
}

function main() {
    const n = nextNum()
    const pos: number[][] = []
    for (let i = 0; i < n; i++) {
        const [x, y] = nextNums(2)
        pos.push([x, y])
    }
    const ans: number[] = []
    for (let i = 0; i < n; i++) {
        let maxDist = 0
        let ansPos = 100
        for (let j = 0; j < n; j++) {
            if (i == j) continue
            const x1 = pos[i][0]
            const y1 = pos[i][1]
            const x2 = pos[j][0]
            const y2 = pos[j][1]
            const dist = calcDist(x1, y1, x2, y2)
            if (dist > maxDist) {
                maxDist = dist
                ansPos = j + 1
            } else if (dist == maxDist) {
                ansPos = Math.min(ansPos, j + 1)
            }
        }
        ans.push(ansPos)
    }
    console.log(ans.join("\n"))
}

B問題ということを考えると難易度が高いと思った。

C - Colorful Beans

https://atcoder.jp/contests/abc348/tasks/abc348_c

N種類のビーンズがあり、それぞれおいしさと色が与えられる。

ビーンズが配られたあと、色を一つ選び、その色のビーンズを食べる。

食べる可能性のあるビーンズのおいしさの最小値を最大化して出力せよ、という問題。

一瞬よく意味が分からなかったが、要はこういうことをやる問題。

• 各色ごとに最小のおいしさを調べる
• 最少のおいしさの最大値を出力する

色々とやり方はありそうだが、オブジェクトを活用して最小値を保持するのが簡単か。

function main() {
    const n = nextNum();
    const dic: Record<number, number> = {}
    for (let i = 0; i < n; i++) {
        const [a, c] = nextNums(2)
        if (dic[c] == undefined) {
            dic[c] = a
        } else {
            dic[c] = Math.min(dic[c], a)
        }
    }
    let ans = 0
    for (const key in dic) {
        const a = dic[key]
        ans = Math.max(ans, a)
    }
    console.log(ans)
}

D - Medicines on Grid

https://atcoder.jp/contests/abc348/tasks/abc348_d

グリッドが与えられ、以下のルールで始点から終点まで移動をする。

• 最初のエネルギーは０
• エネルギーが残っていれば上下左右に１エネルギーを使って移動できる
• 薬のマスで、エネルギーをEにするかどうか選べる
• 薬は一回つかうとなくなる

以上のルールで始点から終点まで移動をできるか判定する、という問題。

難しかった。問題を誤読していて、ずっとエネルギーを「E増やせる」だと思ってはまっていた。反省である。

さて、たどり着けるかどうか、というとBFSが思い浮かぶ。

ただし、今回の場合は薬があるので、「遠回りして得点の高い薬をゲットすればゴールできる」みたいな状況もあるのが難しい。

単純に最短距離で探索しても正解にならないだろうという気はする。

そこで「エネルギーを最大にするようにマスを移動する」というようなBFSを書くとACをすることができた。

計算量が気になるところではあるが、盤面の制約が大きくない（最大縦横200マス）、かつ薬の数も300までなので、多少、無駄な動きをしても間に合うかな？という気がしていた。

また、ちゃんと探索ができるか、という点も気になる。薬を使っても値が増えるわけではなく、「値がEになる」というのがミソ。

そのためそのマスで最大のエネルギーを保持するように貪欲に動くのはロジックとしては正しい。例えば後で使おうと思ってエネルギーが増えるにも関わらず薬を使わなかったとした場合、必ずそのマスから移動できる範囲は減る。そのため、貪欲にエネルギーを増やして移動していけばいい。

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 [h, w] = nextNums(2)
    // gridを受け取る
    const grid: string[] = []
    for (let i = 0; i < h; i++) {
        const s = next()
        grid.push(s)
    }
    // 薬を記録する配列
    const medicines: number[][] = []
    for (let i = 0; i < h; i++) {
        const arr = new Array(w).fill(0)
        medicines.push(arr)
    }
    const n = nextNum()
    for (let i = 0; i < n; i++) {
        let [r, c, e] = nextNums(3)
        r--
        c--
        medicines[r][c] = e
    }
    const di = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    // エネルギーを記録
    const energies: number[][] = []
    const inf = -100000
    for (let i = 0; i < h; i++) {
        const arr = new Array(w).fill(inf)
        energies.push(arr)
    }
    // スタートとゴールを調べる
    let sr = 0
    let sc = 0
    let gr = 0
    let gc = 0
    for (let i = 0; i < h; i++) {
        for (let j = 0; j < w; j++) {
            if (grid[i][j] == 'S') {
                sr = i
                sc = j
            }
            if (grid[i][j] == 'T') {
                gr = i
                gc = j
            }
        }
    }
    energies[sr][sc] = 0
    // 両端キューをインスタンス化
    const que = new Deque<number[]>()
    // ポジション、エネルギーを格納
    que.append([sr, sc, 0])
    // BFSする
    while (que.getLength() > 0) {
        const arr = que.popleft()
        if (!arr) continue
        const nowR = arr[0]
        const nowC = arr[1]
        let ene = arr[2]
        // 薬を取ったら増える場合は増やす
        if (medicines[nowR][nowC] > ene) {
            ene = medicines[nowR][nowC]
            // 薬を取り除く
            medicines[nowR][nowC] = 0
        }
        // 移動できない
        if (ene === 0) continue
        // 移動する
        for (const d of di) {
            const nxtR = d[0] + nowR
            const nxtC = d[1] + nowC
            if (0 <= nxtR && nxtR < h && 0 <= nxtC && nxtC < w) {
                if (grid[nxtR][nxtC] === '#') continue
                // エネルギーを増やせる場合は次のマスへ
                const newEne = ene - 1
                if (newEne > energies[nxtR][nxtC]) {
                    energies[nxtR][nxtC] = newEne
                    que.append([nxtR, nxtC, newEne])
                }
            }
        }
    }
    // 答えの出力
    if (energies[gr][gc] === inf) {
        log('No')
    } else {
        log('Yes')
    }
}

これでACができる。

解説を見てると薬から薬にたどり着けるか、という判定を行って、最後にBFSをしてゴールにたどり着けるか判定する、という方法が紹介されていた。

確かにこちらの方が理解がしやすい。せっかくなので実装をしてみよう。

function main() {
    const [h, w] = nextNums(2)
    // gridを受け取る
    const grid: string[] = []
    for (let i = 0; i < h; i++) {
        const s = next()
        grid.push(s)
    }
    // 薬を記録する配列
    // -1で初期化するようにする
    const medicines: number[][] = []
    for (let i = 0; i < h; i++) {
        const arr = new Array(w).fill(-1)
        medicines.push(arr)
    }
    const n = nextNum()
    const queries: number[][] = []
    for (let i = 0; i < n; i++) {
        let [r, c, e] = nextNums(3)
        r--
        c--
        medicines[r][c] = e
        queries.push([r, c, e])
    }
    const di = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    // スタートとゴールを調べる
    let sr = 0
    let sc = 0
    let gr = 0
    let gc = 0
    for (let i = 0; i < h; i++) {
        for (let j = 0; j < w; j++) {
            if (grid[i][j] == 'S') {
                sr = i
                sc = j
            }
            if (grid[i][j] == 'T') {
                gr = i
                gc = j
            }
        }
    }
    // ゴール地点にエネルギー０の薬を置く
    medicines[gr][gc] = 0
    const graph: Record<number, number[]> = {}
    // BFSして薬から薬にエッジをつなぐ
    for (const [r, c, e] of queries) {
        const que = new Deque<number[]>()
        que.append([r, c, e])
        const vis: Set<number> = new Set()
        vis.add(r * w + c)
        while (que.getLength() > 0) {
            const arr = que.popleft()
            if (!arr) continue
            const [nowR, nowC, ene] = arr
            if (ene == 0) continue
            for (const d of di) {
                const nxtR = d[0] + nowR
                const nxtC = d[1] + nowC
                if (0 <= nxtR && nxtR < h && 0 <= nxtC && nxtC < w) {
                    if (grid[nxtR][nxtC] === '#') continue
                    if (vis.has(nxtR * w + nxtC)) continue
                    // 薬のマスに来たらエッジをつなぐ
                    if (medicines[nxtR][nxtC] > -1) {
                        const fr = r * w + c
                        const to = nxtR * w + nxtC
                        if (!graph[fr]) graph[fr] = []
                        graph[fr].push(to)
                    }
                    vis.add(nxtR * w + nxtC)
                    const newEne = ene - 1
                    que.append([nxtR, nxtC, newEne])
                }
            }
        }

    }
    //もう一回辿って判定する
    const vis: Set<number> = new Set()
    const stack: number[] = []
    const start = sr * w + sc
    const goal = gr * w + gc
    stack.push(start)
    while (stack.length > 0) {
        const now = stack.pop()
        if (now == goal) {
            log('Yes')
            exit()
        }
        if (now == undefined) continue
        if (!graph[now]) continue
        for (const adj of graph[now]) {
            if (vis.has(adj)) continue
            vis.add(adj)
            stack.push(adj)
        }
    }
    log('No')
}

重実装である。

おわりに

今回はDまでを自力で解いてE問題をChatGPTで解いたという形だった。結果オーライで水色に戻ることができてうれしい。さいきん難化が進んでいるので、「ChatGPTに投げるだけ」という問題が減ってきているような気もする。地力も高めていきたい。ではでは。