Paizaやその他、競プロでJavaScriptを使う時、他の言語と違って面倒なのは標準入力の受取である。全部一気に受け取ってしまって、それらを配列で管理しなければならない。この管理が非常に面倒なので、Python3みたいにinput()で一行ごとに受け取りたいと考えることしばしばである。ふと思ったが、標準入力を一気に受け取って、一行ずつ吐き出すオブジェクトをつくればよいのである。ということで早速実装

//classは巻き上げられないので最初に書く
class inputClass{
    constructor(){
        this.inputCounter = 0;
        this.list = [];
        this.len = 0
    }
    append (value){
        this.list.push(value);
        this.len++;
    }
    input(){
        if (this.inputCounter < this.list.length){
            return this.list[this.inputCounter++];
        }else{
            return '';
        }
    }
}
let data = new inputClass();
let reader = require("readline").createInterface({
    input: process.stdin,
    output: process.stdout
});
reader.on("line", (line) => {
    data.append(line.split(' '));
})
reader.on("close", () => {
    //読み込み行数を保持するlenプロパティで末尾まで取り出し
    for (let i=0; i < data.len; i++){
        console.log(data.input());
    }
});

入力
1 1
2 2
a
c
f g h

出力
[ '1', '1' ]
[ '2', '2' ]
[ 'a' ]
[ 'c' ]
[ 'f', 'g', 'h' ]

概ね期待通りに実装できた。イテレーターで実装したほうが便利だと作った後に気づいたがひとまず実装したのでよしとしたい。

Paizaの問題の解説がさっぱりしすぎてて頭を悩ませているのでメモ程度に自分なりの解説を作ってみる。

1. 概要

今回の問題

2-近似によるTSP (paizaランク A 相当)

https://paiza.jp/works/mondai/tsp_problems/tsp_problems__tsp_approx

Python 3で解答に従い書いたコードはこんな感じ

import math

n = int(input())
cities = [list(map(int, input().split())) for _ in range(n)]
routes = []
mst = [[] for _ in range(n)] #隣接行列
tour = []

def calc_dist(a, b):
    return math.sqrt(math.pow(a[0] - b[0], 2.0) + math.pow(a[1] - b[1], 2.0))

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        
    def get_parent(self, a):
        a = self.parent[a]
        while a != self.parent[a]:
            a = self.parent[a]
        return a
    
    def unite(self, a, b):
        a = self.get_parent(a)
        b = self.get_parent(b)
        self.parent[b] = a
    
    def same(self, a, b):
        return self.get_parent(a) == self.get_parent(b)


def dfs(mst, tour, now, before):
    tour.append(now)
    if now != before:
        for nxt in mst[now]:
            if nxt in tour:
                continue
            dfs(mst, tour, nxt, now)
    
for i in range(n):
    for k in range(n):
        tmp = calc_dist(cities[i], cities[k])
        routes.append((tmp, i, k))
        
routes.sort()
uf = UnionFind(n)
for d, i, k in routes:
    if uf.same(i, k):
        continue
    mst[i].append(k)
    mst[k].append(i)
    uf.unite(i, k)

dfs(mst, tour, 0, -1)
print(*tour)

2. 解法

問題を分割して考えていくと答えまでは3ステップ

ユークリッド距離をもとにルートの候補を選定
Union Findをつかって整理
深さ優先探索でルートを探索

一つ一つ見ていく

2.1 ルートの選定

とりあえず、入力座標の各点から各点までの点と距離を全部計算して、短い順にソートする。短い順にソートすると、最短ルートは、自分から自分に向かう点でユークリッド距離は0になる。

以下の処理がこれに該当する。

for i in range(n):
    for k in range(n):
        tmp = calc_dist(cities[i], cities[k])
        routes.append((tmp, i, k))
        
routes.sort()

2.2 Union Findを使って整理

このままだと、最小全域木はつくれないので、Union Findを使って同じ親を持つルートを排除していく。つまり、(0,0)→(0,0)といったものを消す。また、(0,0)→(0,1)及び(0,0)→(0,2)のうちユークリッド距離の短い方だけを残していく、(0,0) → (0,1)及び(0,1) → (0,0)の一方を消す。そうすることで、mstリストは、最小全域木の隣接リストとなる。

該当部分は以下の通り。

uf = UnionFind(n)
for d, i, k in routes:
    if uf.same(i, k):
        continue
    mst[i].append(k)
    mst[k].append(i)
    uf.unite(i, k)

親が同じならループの先頭に戻り、そうでなければ、隣接リストに情報を記録して、その後に親の情報をufインスタンスに格納していく。

そうすることで親がことなるノードだけの隣接リストが作られる。

3.3 深さ優先探索でルートをたどる。

隣接リストをたどっていく。スタートはどこでもいいが、ここでは0をスタートとしている。

そして出力して終了。

4. まとめ

この問題のポイントは、最小全域木を隣接リストに格納し、それを深さ優先探索でたどっていくとこにあると思う。

参考

公式ブログ

Pythonで「巡回セールスマン問題」を解いてみよう！8つの解法を例題で解説
https://paiza.hatenablog.com/entry/2022/10/07/130000

短い20世紀を超えて

2023年12月15日金曜日

JavaScriptで標準入力をPython3っぽく受け取る

2023年2月17日金曜日

Paizaのレベルアップ問題集『巡回セールスマン問題(近似)』の解説