Zig 言語の練習に AtCoder 202308 新ジャッジテストコンテスト A-E を解いてみた

はじめに

AtCoder 2023年8月の 新ジャッジコンテストから、Zig 0.10.1 が使えるようになりました。

• ホーム ⚡ Zig Programming Language

普段 Rust で AtCoder ABC に参加しています。 Zig 言語は Rust 同様に高速なバイナリ出力を狙った、Rust とは違うアプローチのモダンな言語と言うことで、気になっていました。

Zig 言語は Bun の開発で使われていることでも話題です。今月 Bun 1.0 になりました。

• Bun — A fast all-in-one JavaScript runtime

というわけで、AtCoder 202308 新ジャッジテストコンテスト -Algorithm- の問題を Zig 言語で解いてみて、感想を書こうという記事です。超初心者ですので変なところも多いかもしれませんがご了承ください。

対象読者

• Zig 言語に興味のある方
• コンパイル型の言語でプログラミングすることがある方
• 競技プログラミング経験者

本記事の対象外

• 問題の解き方解説は、コードを読む参考となる簡単なものにとどめています。公式解説などをどうぞ。
• Zig 言語の説明はしません。公式サイトや良質な説明をどうぞ。
  • Documentation - The Zig Programming Language
  • Chapter 0 - Getting Started | ziglearn.org
  • zig note
  • [全編無料] 他言語習得者がとりあえず使えるようになるZig
  • Zig の文書読んで所感を記す - Qiita
  • Zig 標準ライブラリで用意されているコレクション型をざっくり押さえる

TL;DR

• Zig の感想
  • モダン。ミニマリスト。better C。
  • 読みやすいコードになる。代わりに長くなりがち。
  • ヒープ管理が手動。「これってスタックで良いのでは」と考える癖がつきそう。auto_ptr が無い時代の C++ ぽくありつつも、defer で十分扱えそうです。
  • Zig を使うだけでは速くなりません。
• 競技プログラミングで Zig を使うのはどう？ → 現時点では微妙
  • Zig 言語は 1.0 になっていません。言語のバージョンアップによる仕様変更で、ビルドが通らなくなることがあります。 AtCoder 実行環境の 0.10.1 と、最新の 0.11.0 でも。提出コードが CE だとがっかりします。
  • ライブラリが足りなく感じることがあります。標準入力の処理が手間とか、UnionFind がないとか。言い換えると、自分用ライブラリを育てれば C++, Rust と同じくらいのパフォーマンスを目指せそうです。

環境構築

Windows + VS Code で行っています。

• winget install -e --id zig.zig
• Zig Language - Visual Studio Marketplace

環境構築後、以下のコマンドを実行します。

行いたいこと	コマンド
プロジェクト作成	zig init-exe
ビルド	zig build
ビルドして実行	zig build run
ビルドしてテスト	zig build test

A "atcoder".substr()

A - 方針

標準入力から 2つの数値を受け取り、"atcoder" 7文字から部分文字列のスライスを取り出します。

A - Rust 回答例

a.rs

use proconio::input;

fn main() {
    input! {
        l: usize,
        r: usize,
    }
    let result = &"atcoder"[(l - 1)..r];
    println!("{result}");
}

"atcoder"[(l - 1)..r] でだいたい終わります。

A - Zig 回答例

a.zig

const std = @import("std");

fn nextToken(reader: anytype, buffer: []u8) []const u8 {
    return reader.readUntilDelimiter(
        buffer,
        ' ',
    ) catch unreachable;
}

fn nextLine(reader: anytype, buffer: []u8) []const u8 {
    const line = reader.readUntilDelimiterOrEof(
        buffer,
        '\n',
    ) catch unreachable;

    if (@import("builtin").os.tag == .windows) {
        return std.mem.trimRight(u8, line.?, "\r");
    } else {
        return line.?;
    }
}

fn parseUsize(buf: []const u8) usize {
    return std.fmt.parseInt(usize, buf, 10) catch unreachable;
}

pub fn main() !void {
    const stdin = std.io.getStdIn();
    var buffer: [1024]u8 = undefined;

    const l = parseUsize(nextToken(stdin.reader(), &buffer));
    const r = parseUsize(nextLine(stdin.reader(), &buffer));

    const result = "atcoder"[(l - 1)..r];

    const stdout = std.io.getStdOut();
    try stdout.writer().print("{s}", .{result});
}

……Rust に比べてとても長くないですか？

× 標準入力の受け取りが手間

標準入力から "3 6\n" を受け取ったときに const l = 3; const r = 6; したいだけなのに、なんだか長いです。

• scanf() みたいな安全でない読み取りは、Zig では行えない
• l はスペースまで文字列を読み取り、std.fmt.parseInt(usize) する
• r は改行文字 \n まで文字列を読み取り、std.fmt.parseInt(usize) する
  • Windows ではこれだけでは 6\r が取れてしまうので、\r を切り落とす

Chapter 2 - Standard Patterns | ziglearn.org にこのような OS による分岐が書いていました。 AtCoder 採点環境は Linux ですから、手元で Windows を使っていなければ \r のことは忘れて良いのかもしれません。これは面倒……。

まあ、Rust でも本当は標準入力の扱いは面倒で、proconio がマクロを使ってうまく処理しているということなのだと思います。

それと、catch unreachable や .? を多用するのは、 Rust で .unrwap() を多用するような後ろめたさがあります。

△ 読みやすいコードになる。代わりに長くなりがち

標準入力の受け取りの簡潔さとどちらを取るか、という話でしょうけれど。

Rust で proconio を使うと、 proconio を使わない人にとってはマクロ input! ってなにもの？ となってしまいます。C++ で for の代わりに競技プログラミングで rep マクロを使うのも、人によっては読みづらいと感じます。同じプログラミング言語なのに違うものを書いているようです。

Zig はマクロなし、シャドウイングなしなど、書き方に制限をかけています。コードが長めになります。けれど、変わった書き方を防いでいるということは、読みやすいコードということでもあります。コードは一般には書く時間より読む時間の方が長いですから、読みやすさ重視と言うのは一理あると思います。

ただし、競技プログラミングは制限時間内に素早く書くこと重視ですから、コードが長めというのはそれだけで不利になります。

○ 文字列のスライスは簡単

const result = "atcoder"[(l - 1)..r]; これは直感的です。スライスや C++ std::string_view みたいな。

C 言語のように \0 を書き込む必要はありません。better C。

○ 単体テストも簡単

実装の横に単体テストを書けます。問題の横に書いているテストケースを持ってきて、事前に zig build test すれば安心です。

a-1.zig

fn solve(l: usize, r: usize) []const u8 {
    return "atcoder"[(l - 1)..r];
}

test "a-1" {
    try std.testing.expectEqualStrings(solve(3, 6), "code");
}

test "a-2" {
    try std.testing.expectEqualStrings(solve(4, 4), "o");
}

test "a-3" {
    try std.testing.expectEqualStrings(solve(1, 7), "atcoder");
}

実装もこの solve() 関数を呼ぶ形にしておきます。これで main だけにある実装は標準入出力部分と言うことに。

a-2.zig

-   const result = "atcoder"[(l - 1)..r];
+   const result = solve(l, r);

Rust で AtCoder コンテストに参加するときは cargo compete test することで、テストコードを一行も書かなくても公開テストケースすべての動作確認ができます。それに比べるとコードを書く手間かかりますが、まあ十分 TDD しやすいと思います。

• qryxip/cargo-compete: A Cargo subcommand for competitive programming

B Broken Rounding

B - 方針

書いている通り実装します。

• X の $10^0$ の位以下を四捨五入する ($10^0$ で割って 1の位で四捨五入して $10^0$ をかける)
• X の $10^1$ の位以下を四捨五入する ($10^1$ で割って 1の位で四捨五入して $10^1$ をかける)
• :
• X の $10^{k-1}$ の位以下を四捨五入する ($10^{k-1}$ で割って 1の位で四捨五入して $10^{k-1}$ をかける)

B - Rust 回答例

b.rs

use proconio::input;

fn main() {
    input! {
        mut x: usize,
        k: u32,
    }
    for i in 0..k {
        let k = 10usize.pow(i);
        x /= k;
        let m = x % 10;
        x -= m;
        if m >= 5 {
            x += 10;
        }
        x *= k;
    }
    println!("{x}");
}

書いている通り実装しました。10 の累乗で割って、1の位で四捨五入して、再度掛け算。 f64 にして round() でも良いです。

B - Zig 回答例

b.zig

fn solve(x: usize, k: usize) usize {
    var result = x;
    var i: usize = 0;
    while (i < k) {
        const y = (result / std.math.pow(usize, 10, i)) % 10;
        const z = std.math.pow(usize, 10, i + 1);
        if (y < 5) {
            result = (result / z) * z;
        } else {
            result = (result / z + 1) * z;
        }
        i += 1;
    }
    return result;
}

test "b-1" {
    try std.testing.expectEqual(solve(2048, 2), 2100);
}

test "b-2" {
    try std.testing.expectEqual(solve(1, 15), 0);
}

test "b-3" {
    try std.testing.expectEqual(solve(999, 3), 1000);
}

test "b-4" {
    try std.testing.expectEqual(solve(314159265358979, 12), 314000000000000);
}

pub fn main() !void {
    const stdin = std.io.getStdIn();
    var buffer: [1024]u8 = undefined;

    const x = parseUsize(nextToken(stdin.reader(), &buffer));
    const k = parseUsize(nextLine(stdin.reader(), &buffer));

    const result = solve(x, k);

    const stdout = std.io.getStdOut();
    try stdout.writer().print("{}", .{result});
}

定型句

common.zig

const std = @import("std");

fn nextToken(reader: anytype, buffer: []u8) []const u8 {
    return reader.readUntilDelimiter(
        buffer,
        ' ',
    ) catch unreachable;
}

fn nextLine(reader: anytype, buffer: []u8) []const u8 {
    const line = reader.readUntilDelimiterOrEof(
        buffer,
        '\n',
    ) catch unreachable;

    if (@import("builtin").os.tag == .windows) {
        return std.mem.trimRight(u8, line.?, "\r");
    } else {
        return line.?;
    }
}

fn parseUsize(buf: []const u8) usize {
    return std.fmt.parseInt(usize, buf, 10) catch unreachable;
}

だいたい同じような感じです。while ループを除いて。

× カウンターを使ったループを while で行う

i を 0 から k-1 までループしたいとき、ほかの言語では for を使いたくなりません？ for でない場合は、ループカウンターの更新を言語におまかせしたいです。

言語	ループのコード例
C++	for (int i = 0; i < k; ++i) { ... }
Rust	for i in 0..k { ... }
Python	for i in range(k): ...
Ruby	k.times do |i| ...

zig 0.10 の for は ranged for 相当のみです。また Rust や Python のように range を直接辿ることはできません。カウンダーを使いたい場合は while にしましょうとのことです。

var i: usize = 0;
while (i < 10) {
    i += 1;
}

……これはバグのもとでしょう。今回のサンプルを書く間に何回も i += 1 を書き忘れました。ちょっと言語仕様がミニマリストというかストイックすぎません？

ちょうど 0.11.0 の更新点に、今後はこんなコードを書けますという紹介がありました。 AtCoder で使いたい場合、次の言語更新を待ちましょう。

• https://ziglang.org/download/0.11.0/release-notes.html#Multi-Object-For-Loops

for (0..20) |i| {
    try std.testing.expectEqual(val, i);
    val += 1;
}

C Yamanote Line Game

C - 方針

インタラクティブ問題の練習です。最大で 1001 回整数を探せば良いということで、毎回全探索しても十分間に合います。

v[0]	v[1]	v[2]	v[3]	v[4]	入力	出力
F	F	F	F	F
T	F	F	F	F		1 (一番左の F)
T	F	F	F	T	5
T	T	F	F	T		2 (一番左の F)
T	T	T	F	T	3
T	T	T	T	T		4 (一番左の F)
T	T	T	T	T	0 (負け)

C - Rust 回答例

c.rs

use proconio::input_interactive;

fn main() {
    input_interactive! {
        n: usize,
    }
    let mut v = vec![false; 2 * n + 1];

    loop {
        let i = v.iter().position(|&b| !b).unwrap() + 1;
        println!("{i}");
        v[i - 1] = true;

        input_interactive! {
            i: usize,
        }
        if i == 0 {
            return;
        }
        v[i - 1] = true;
    }
}

今回の本題ではありませんが、2023 言語更新で proconio が新しくなり、 proconio::input_interactive が使えるようになりました。source の指定と言うおまじないはたぶんもう不要です。

C - Zig 回答例

c.zig

pub fn main() !void {
    const stdin = std.io.getStdIn();
    const stdout = std.io.getStdOut();
    var buffer: [1024]u8 = undefined;

    const n = parseUsize(nextLine(stdin.reader(), &buffer));

    var v = [_]bool{false} ** 2001;

    while (true) {
        var x: usize = 0;
        while (x < 2 * n + 1) {
            if (!v[x]) {
                break;
            }
            x += 1;
        }
        try stdout.writer().print("{}\n", .{x + 1});
        v[x] = true;

        const y = parseUsize(nextLine(stdin.reader(), &buffer));
        if (y == 0) {
            return;
        }
        v[y - 1] = true;
    }
}

定型句

common.zig

const std = @import("std");

fn nextToken(reader: anytype, buffer: []u8) []const u8 {
    return reader.readUntilDelimiter(
        buffer,
        ' ',
    ) catch unreachable;
}

fn nextLine(reader: anytype, buffer: []u8) []const u8 {
    const line = reader.readUntilDelimiterOrEof(
        buffer,
        '\n',
    ) catch unreachable;

    if (@import("builtin").os.tag == .windows) {
        return std.mem.trimRight(u8, line.?, "\r");
    } else {
        return line.?;
    }
}

fn parseUsize(buf: []const u8) usize {
    return std.fmt.parseInt(usize, buf, 10) catch unreachable;
}

△ ヒープを使わずに書きたくなる

var v = [_]bool{false} ** 2001;

C++ で最初競技プログラミングのコードを見ていた時、「なにこの制約の最大値でも大丈夫なように大きくガリっと確保するコード。必要十分なメモリーサイズを vector などで動的に割り当てれば良いじゃない。」と思っていました。

手動で動的メモリー (ヒープ) 割り当てを管理する zig を触っていて、考えを改めました。手動開放が面倒で、忘れると簡単にメモリーリークします。ボローチェッカーもスマートポインターも使えないとこうなるのですか、と。スコープを抜けるときに後処理を実行できる defer は便利で、手動でもなんとかなるようになっていますけれど。

bool 2001 個くらいなら固定サイズのスタックで十分すぎます。

△ コンテナー操作の道具が少ない

配列の中でまだ使われていない数字を探したいとき、 Rust なら

let i = v.iter().position(|&b| !b).unwrap() + 1;

このように標準のイテレーターや itertools を使って簡単に探せます。

zig の場合、while ループを回して探します。

var x: usize = 0;
while (x < 2 * n + 1) {
    if (!v[x]) {
        break;
    }
    x += 1;
}

言語仕様がコンパクトなためか、単に私の検索が足りないのかは分かりません。

D Add One Edge

D - 方針

エッジを1本増やすことで、一番小さなノードと一番大きなノードをつなぐ距離を最大どこまで伸ばせるか、という問題です。

1からもっとも離れたノードと、7からもっとも離れたノードが分かれば、それをつなげば答えです。この離れたノードはダイクストラ法で 01-BFS などすれば求まります。

D - Rust 回答例

d.rs

use std::collections::VecDeque;

use proconio::{input, marker::Usize1};

fn dijkstra(i: usize, graph: &[Vec<usize>]) -> usize {
    let mut visited = vec![false; graph.len()];
    visited[i] = true;
    let mut max_step = 0;
    let mut queue = VecDeque::new();
    queue.push_back((0, i));

    while let Some((step, i)) = queue.pop_front() {
        for &i in &graph[i] {
            if visited[i] {
                continue;
            }
            visited[i] = true;
            let step = step + 1;
            queue.push_back((step, i));
            max_step = step;
        }
    }

    max_step
}

fn main() {
    input! {
        n1: usize,
        n2: usize,
        m: usize,
        ab: [(Usize1, Usize1); m],
    }

    let mut graph = vec![vec![]; n1 + n2];
    for &(a, b) in &ab {
        graph[a].push(b);
        graph[b].push(a);
    }

    let step1 = dijkstra(0, &graph);
    let step2 = dijkstra(n1 + n2 - 1, &graph);
    let result = step1 + step2 + 1;
    println!("{result}");
}

重みなしのグラフの距離計算ですから、01-BFS のキューとして VecDeque を使いました。

petgraph にダイクストラ法を解かせる方針にして、組み立てるだけ、という方針もありそうです。

D - Zig 回答例

d.zig

const Node = struct {
    i: usize,
    step: usize,
};

fn lessThan(context: void, a: Node, b: Node) std.math.Order {
    _ = context;
    return std.math.order(a.step, b.step);
}

fn dijkstra(i: usize, graph: *std.ArrayList(std.ArrayList(usize)), allocator: std.mem.Allocator) !usize {
    var queue = std.PriorityQueue(Node, void, lessThan).init(allocator, {});
    defer queue.deinit();

    var visited = [_]bool{false} ** 300000;
    visited[i] = true;

    var max_step: usize = 0;
    try queue.add(Node{ .i = i, .step = 0 });

    while (queue.count() > 0) {
        const node = queue.remove();
        for (graph.items[node.i].items) |j| {
            if (visited[j]) {
                continue;
            }
            visited[j] = true;
            try queue.add(Node{ .i = j, .step = node.step + 1 });
            max_step = node.step + 1;
        }
    }
    return max_step;
}

pub fn main() !void {
    const stdin = std.io.getStdIn();
    var buf_reader = std.io.bufferedReader(stdin.reader());
    var reader = buf_reader.reader();

    const stdout = std.io.getStdOut();
    var buffer: [1024]u8 = undefined;

    const n1 = parseUsize(nextToken(reader, &buffer));
    const n2 = parseUsize(nextToken(reader, &buffer));
    const m = parseUsize(nextLine(reader, &buffer));

    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    var graph = std.ArrayList(std.ArrayList(usize)).init(allocator);
    defer {
        for (graph.items) |*e| e.deinit();
        graph.deinit();
    }

    var i: usize = 0;
    while (i < n1 + n2) {
        i += 1;
        var adjacents = std.ArrayList(usize).init(allocator);
        try graph.append(adjacents);
    }

    i = 0;
    while (i < m) {
        i += 1;
        const a = parseUsize(nextToken(reader, &buffer)) - 1;
        const b = parseUsize(nextLine(reader, &buffer)) - 1;
        try graph.items[a].append(b);
        try graph.items[b].append(a);
    }

    const step1 = try dijkstra(0, &graph, allocator);
    const step2 = try dijkstra(n1 + n2 - 1, &graph, allocator);
    const result = step1 + step2 + 1;
    try stdout.writer().print("{}\n", .{result});
}

test "d-1" {
    const allocator = std.testing.allocator;

    var graph = std.ArrayList(std.ArrayList(usize)).init(allocator);
    defer {
        for (graph.items) |*e| e.deinit();
        graph.deinit();
    }

    var i: usize = 0;
    while (i < 7) {
        i += 1;
        var adjacents = std.ArrayList(usize).init(allocator);
        try graph.append(adjacents);
    }

    var a = [_][2]usize{ .{ 1, 2 }, .{ 2, 3 }, .{ 4, 5 }, .{ 4, 6 }, .{ 1, 3 }, .{ 6, 7 } };
    i = 0;
    while (i < a.len) {
        try graph.items[a[i][0] - 1].append(a[i][1] - 1);
        try graph.items[a[i][1] - 1].append(a[i][0] - 1);
        i += 1;
    }

    const step1 = try dijkstra(0, &graph, allocator);
    try std.testing.expectEqual(step1, 1);

    const step2 = try dijkstra(6, &graph, allocator);
    try std.testing.expectEqual(step2, 3);
}

定型句

common.zig

const std = @import("std");

fn nextToken(reader: anytype, buffer: []u8) []const u8 {
    return reader.readUntilDelimiter(
        buffer,
        ' ',
    ) catch unreachable;
}

fn nextLine(reader: anytype, buffer: []u8) []const u8 {
    const line = reader.readUntilDelimiterOrEof(
        buffer,
        '\n',
    ) catch unreachable;

    if (@import("builtin").os.tag == .windows) {
        return std.mem.trimRight(u8, line.?, "\r");
    } else {
        return line.?;
    }
}

fn parseUsize(buf: []const u8) usize {
    return std.fmt.parseInt(usize, buf, 10) catch unreachable;
}

× アロケーターが難しい

graph[ノード番号] = [隣接ノード番号1, 隣接ノード番号2, ...] のような無向グラフ構造を持つことにします。二重配列。隣接ノードの数が実装中には分かりませんから、ここでは動的にメモリーを確保したくなります。

var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
defer arena.deinit();
const allocator = arena.allocator();

複数回メモリーを確保するときには ArenaAllocator がおすすめのようです。単純な page_allocator でノード回数分メモリー確保したところ、ページ単位のメモリー確保で足りなくなりました MLE エラーが出ました。

細かくメモリーを開放しなくても defer arena.deinit(); で最後にまとめて行えば良い、というのは楽です。

× VecDeque がない

VecDeque 相当がありません。競技プログラミングでは 01-BFS などでよく使います。

今回の実装では PriorityQueue を使いました。優先度にステップ数を渡せば同じ結果になります。少しだけ遅いです。

または、固定長配列を使って、リングバッファー管理みたいなことを自前で行うこともできます。エッジ数の制約以上にキューが溜まることはありません。

c-2.zig

fn dijkstra(i: usize, graph: *std.ArrayList(std.ArrayList(usize))) !usize {
    const SIZE = 300000;

    var queue = [_]usize{0} ** SIZE;
    var q0: usize = 0; // front index
    var q1: usize = 1; // back index
    queue[0] = i;

    var steps = [_]usize{SIZE} ** SIZE;
    steps[i] = 0;
    var max_step: usize = 0;

    while (q0 < q1) {
        const j = queue[q0];
        q0 += 1;
        for (graph.items[j].items) |k| {
            if (steps[k] < SIZE) {
                continue;
            }
            steps[k] = steps[j] + 1;
            max_step = steps[k];
            queue[q1] = k;
            q1 += 1;
        }
    }
    return max_step;
}

……ほかの言語では気軽に行えるところに、こんなに手間をかけたくない感じがします。

△ 標準入力がストリームを使わないと遅い

この問題から入力方法を変えました。

const stdin = std.io.getStdIn();
+var buf_reader = std.io.bufferedReader(stdin.reader());
+var reader = buf_reader.reader();

-const a = parseUsize(nextToken(reader, &stdin.reader())) - 1;
+const a = parseUsize(nextToken(reader, &buffer)) - 1;

実行時間はこちら:

言語	I/O	ダイクストラ法	時間
Zig	stdin.reader	BFS	1156 ms
Zig	bufferedReader	BFS	180 ms
Zig	bufferedReader	01-BFS	159 ms
Rust	proconio	01-BFS	67 ms

最初通した実装では Zig が Rust の 10倍遅く、だいたい同じアルゴリズムなのにと不思議に思っていました。アルゴリズム以前の問題でした。

競技プログラミングをインタプリタ系の言語で取り組んでいると実行時速度が出なそうだから、コンパイルを行う言語への乗り換えを試すこともあるかもしれません。でも読み込み速度が遅いコードの書き方になってしまっていると残念です。

まあこれは、競技プログラミングでよく使われている言語では道路が整備されているという話だと思います。 Rust ではノウハウの詰まった proconio に感謝と言うことで。

E Good Graph

E - 方針

エッジを1本増やすことで、つながってはいけない組み合わせができてしまうかを確認する問題です。

事前に隣接関係のあるノードを UnionFind でまとめておきます。
"2-6" など 1本増やしたときに UnionFind の単位としてはどこがつながり、それは「つながってはいけない組み合わせ」にあたらないか、ということを確認すれば良いです。

E - Rust 回答例

e.rs

use std::collections::HashSet;

use petgraph::unionfind::UnionFind;
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        m: usize,
        uv: [(Usize1, Usize1); m],
        k: usize,
        xy: [(Usize1, Usize1); k],
        q: usize,
        pq: [(Usize1, Usize1); q],
    }

    let mut uf = UnionFind::new(n);
    for &(u, v) in &uv {
        uf.union(u, v);
    }
    let mut set = HashSet::new();
    for &(x, y) in &xy {
        let (x, y) = (uf.find(x), uf.find(y));
        set.insert((x, y));
        set.insert((y, x));
    }
    for &(p, q) in &pq {
        let (p, q) = (uf.find(p), uf.find(q));
        let yes = !set.contains(&(p, q));
        println!("{}", if yes { "Yes" } else { "No" });
    }
}

petgraph::unionfind を使います。「つながってはいけない組み合わせ」を set で用意しておきます。実装量は少ないです。

2023 言語アップデートで Rust でも Atcoder Library がそのまま使えるようになりました。 petgraph::unionfind の代わりに Atcoder Library の Dsu (Disjoint Set Union) を使うのも良さそうです。

• rust-lang-ja/ac-library-rs: ac-library-rs is a rust port of AtCoder Library (ACL).

E - Zig 回答例

d.zig

const UnionFind = struct {
    const SIZE: usize = 200000;
    parents: [SIZE]usize,

    fn init(n: usize) UnionFind {
        var parents = [_]usize{0} ** SIZE;
        var i: usize = 0;
        while (i < n) {
            parents[i] = i;
            i += 1;
        }
        return UnionFind{
            .parents = parents,
        };
    }

    fn find(self: *UnionFind, i: usize) usize {
        if (self.parents[i] == i) {
            return i;
        }
        self.parents[i] = self.find(self.parents[i]);
        return self.parents[i];
    }

    fn merge(self: *UnionFind, a: usize, b: usize) bool {
        var a0 = self.find(a);
        var b0 = self.find(b);
        if (a0 == b0) {
            return false;
        }
        self.parents[b0] = a0;
        return true;
    }

    fn equiv(self: *UnionFind, a: usize, b: usize) bool {
        var a0 = self.find(a);
        var b0 = self.find(b);
        return (a0 == b0);
    }
};

const NodePair = struct {
    x: usize,
    y: usize,
};

pub fn main() !void {
    const stdin = std.io.getStdIn();
    var buf_reader = std.io.bufferedReader(stdin.reader());
    var reader = buf_reader.reader();

    const stdout = std.io.getStdOut();
    var buffer: [1024]u8 = undefined;

    const n = parseUsize(nextToken(reader, &buffer));
    const m = parseUsize(nextLine(reader, &buffer));
    var uf = UnionFind.init(n);

    var i: usize = 0;
    while (i < m) {
        i += 1;
        const u = parseUsize(nextToken(reader, &buffer)) - 1;
        const v = parseUsize(nextLine(reader, &buffer)) - 1;
        _ = uf.merge(u, v);
    }

    const allocator = std.heap.page_allocator;
    var set = std.AutoHashMap(NodePair, void).init(allocator);
    defer set.deinit();

    const k = parseUsize(nextLine(reader, &buffer));
    i = 0;
    while (i < k) {
        i += 1;
        const x = parseUsize(nextToken(reader, &buffer)) - 1;
        const y = parseUsize(nextLine(reader, &buffer)) - 1;
        try set.put(NodePair{ .x = uf.find(x), .y = uf.find(y) }, {});
        try set.put(NodePair{ .x = uf.find(y), .y = uf.find(x) }, {});
    }

    const q = parseUsize(nextLine(reader, &buffer));
    i = 0;
    while (i < q) {
        i += 1;
        const x = parseUsize(nextToken(reader, &buffer)) - 1;
        const y = parseUsize(nextLine(reader, &buffer)) - 1;
        if (set.contains(NodePair{ .x = uf.find(x), .y = uf.find(y) })) {
            try stdout.writer().print("No\n", .{});
        } else {
            try stdout.writer().print("Yes\n", .{});
        }
    }
}

定型句

common.zig

const std = @import("std");

fn nextToken(reader: anytype, buffer: []u8) []const u8 {
    return reader.readUntilDelimiter(
        buffer,
        ' ',
    ) catch unreachable;
}

fn nextLine(reader: anytype, buffer: []u8) []const u8 {
    const line = reader.readUntilDelimiterOrEof(
        buffer,
        '\n',
    ) catch unreachable;

    if (@import("builtin").os.tag == .windows) {
        return std.mem.trimRight(u8, line.?, "\r");
    } else {
        return line.?;
    }
}

fn parseUsize(buf: []const u8) usize {
    return std.fmt.parseInt(usize, buf, 10) catch unreachable;
}

テスト省略しています。 UnionFind をスタックサイズを決め打ちにしました。

△ UnionFind がない

C++ では AtCoder Library で UnionFind (DSU) する方が多いと思います。 Zig には AtCoder Library がありません。もちろん標準ライブラリーに UnionFind はありません。コンテスト中に使えるように、スニペットなどで用意しておきたいです。

• atcoder/ac-library: AtCoder Library

△ 地味に予約語にひっかかりがち

今回はまったところ 2か所:

petgraph::unionfind の union(a, b) と関数名を揃えようとしたところ、union は予約語のため、コンパイルエラーになりました。merge(a, b) にしました。

i に対応した一時変数名を i0, i1 にしようとしたところ、 int-0bit, int-1bit という型のように見えて、コンパイルエラーになりました。a0 にしました。 Zig には変数名のシャドーイングがありませんので、名前付けに迷います。

これは言語への慣れだと思います。

最後に

TL;DR の通りの感想です。

• Zig の感想
  • モダン。ミニマリスト。better C。
  • 読みやすいコードになる。代わりに長くなりがち。
  • ヒープ管理が手動。「これってスタックで良いのでは」と考える癖がつきそう。auto_ptr が無い時代の C++ ぽくありつつも、defer で十分扱えそうです。
  • Zig を使うだけでは速くなりません。
• 競技プログラミングで Zig を使うのはどう？ → 現時点では微妙
  • Zig 言語は 1.0 になっていません。言語のバージョンアップによる仕様変更で、ビルドが通らなくなることがあります。 AtCoder 実行環境の 0.10.1 と、最新の 0.11.0 でも。提出コードが CE だとがっかりします。
  • ライブラリが足りなく感じることがあります。標準入力の処理が手間とか、UnionFind がないとか。言い換えると、自分用ライブラリを育てれば C++, Rust と同じくらいのパフォーマンスを目指せそうです。

Zig 言語のように 「言語仕様がどんどん変わっている」 場合も、古いコードを自動的に更新する仕組みが一緒に提供されていれば、製品コードのように長く使うつもりのものも大丈夫そうです。

けれど、「同じコードを数年間安定して採点し続けたい」 競技プログラミングとしては微妙です。言語バージョンが上がると昔 AC したコードがいつの間にか CE になってしまう、みたいなことに。提出したコードをシステム側で勝手に書き換えるわけにはいかないでしょうし。

そうなると、言語が安定するまでは競技プログラミングで使うのはおすすめではないのかな、という感想です。

Zig 言語自体は面白いです。C 言語よりは複雑ですが必要だから作られたものという感じ。 C++ や Rust に比べると言語仕様がシンプルでとっつきやすいです。C 言語などの低レベルも扱える言語を触ったことがある人には、書きやすさと安全性の両立を感じられそうです。本当に better C という感じで。

この記事を読んで、Zig 言語での競技プログラミングを試してみる方が現れましたら幸いです。AtCoder Beginners Selection がおすすめです。

• AtCoder Beginners Selection - AtCoder

+1

Zig, Nim, Codon などは実行速度が速く、競技プログラミングすると楽しいかも

半年前の宿題を 1つ片づけました。