11
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@tttmmmyyyy

自作言語FixがAtCoderで使えるようになったので使い方を解説

11
Posted at

はじめに

学びやすくて使いやすい関数型言語Fixを作っています。

2025年10月の言語アップデートにおいて、AtCoderでFixを使えるようになりました。
寛容にもマイナー言語を導入してくださるAtCoder社、および、言語アップデートに携わっていた有志の方々（特にFixを推薦してくださった方）に心より感謝申し上げます。

Fixはまだまだ発展途上の言語ですが、おそらく、ほとんどの問題を制限時間内に解くことができるのではないかと思います。
本記事では、AtCoderでFixを使うための環境構築の方法と、いくつかの問題の解答例を紹介します。

Fixについてのバグ報告や質問があれば、リポジトリのIssueやDiscordサーバまでお気軽にどうぞ。

環境構築

動作環境

Fixは主に

  • Linux (x86_64)
  • MacOS (Apple SiliconおよびIntel)
    で動作確認をしています。

Linuxについては、具体的にはUbuntuでの動作を確認しています。
Windowsをネイティブサポートはしていないため、Windowsを使用している方は、WSL2上のUbuntuでFixを使うことをお勧めします。

Fixをインストールする

AtCoderの言語アップデート2025で導入されたFixのバージョンはv1.1.0-alpha.12です（1）。

バイナリをダウンロードしてインストールする

FixのバイナリはGitHubで配布しています。
以下のコマンドで、FixをGitHubからダウンロードしてインストールできます。
お使いの環境に合わせて、FIX_PLATFORM変数を設定してください。

~/.local/bin に既にfixという名前のファイルがある場合は、上書きされるので注意してください！

# Linux (x86_64)
FIX_PLATFORM=x86_64-unknown-linux-gnu

# MacOS (Intel)
# FIX_PLATFORM=x86_64-apple-darwin

# MacOS (Apple Silicon)
# FIX_PLATFORM=aarch64-apple-darwin

mkdir -p ~/.local/bin
pushd /tmp
AC2025_FIX_VERSION=v1.1.0-alpha.12
curl -L -o fix https://github.com/tttmmmyyyy/fixlang/releases/download/${AC2025_FIX_VERSION}/fix-${AC2025_FIX_VERSION}-${FIX_PLATFORM}
chmod +x fix
mv fix ~/.local/bin/fix
popd

インストール後、~/.local/binにPATHが通っていない場合は、以下を~/.bashrcまたは~/.zshrcに追加してください。

export PATH="$HOME/.local/bin:$PATH"

fix versionコマンドでインストールが成功したか確認してください。

fix 1.1.0 (415a1bd)

と表示されれば成功です。

なお、Linuxで /lib/x86_64-linux-gnu/libc.so.6: version `GLIBC_2.39' not found (required by fix) 等と表示された場合は、システムのGLIBCのバージョンを更新するか、「ソースコードからビルドする」を行ってください。

ソースコードからビルドする

「バイナリをダウンロードしてインストールする」の作業を取り消す場合は、rm ~/.local/bin/fixしてください。

FixはRustで実装されています。
まずは、Rustの公式サイトのコマンドを叩いて、RustとCargoをインストールしてください。

cargo --versionが成功することを確認したら、以下のコマンドでFixをインストールできます（LLVMをダウンロードするので時間がかかります）。

Linuxの場合：

pushd /tmp
curl -L -o llvm-17.0.6.tar.xz https://github.com/llvm/llvm-project/releases/download/llvmorg-17.0.6/clang+llvm-17.0.6-x86_64-linux-gnu-ubuntu-22.04.tar.xz
mkdir llvm-17.0.6
tar -xvf llvm-17.0.6.tar.xz -C llvm-17.0.6 --strip-components=1
export LLVM_SYS_170_PREFIX=/tmp/llvm-17.0.6
git clone https://github.com/tttmmmyyyy/fixlang.git
cd fixlang
git checkout v1.1.0-alpha.12
cargo install --locked --path .
popd

MacOSの場合：
まず、HomebrewでLLVMをインストールしてください。

brew install llvm@17

その後、以下のコマンドでFixをソースコードからビルドしてインストールできます。

export LLVM_SYS_170_PREFIX=$(brew --prefix llvm@17)
pushd /tmp
git clone https://github.com/tttmmmyyyy/fixlang.git
cd fixlang
git checkout v1.1.0-alpha.12
cargo install --locked --path .
popd

最後に、fix versionコマンドでインストールが成功したか確認してください。

fix 1.1.0 (415a1bd)

と表示されれば成功です。

libgmpのインストール

多倍長整数・多倍長有理数型の内部実装にはGMP (GNU Multi-Precision)を使っているので、libgmpをシステムにインストールする必要があります。

多倍長整数・多倍長有理数型などを使わない、という場合は、このステップを飛ばして、後のテンプレートプロジェクトを作成するでgmp-fixを依存関係からカットしてもよいです。

Linuxの場合

sudo apt-get install libgmp-dev

MacOSの場合

Homebrewで以下のコマンドでインストールできます。

brew install gmp

また、これだけではリンカーがlibgmpを見つけられない場合があります。
~/.bashrcまたは~/.zshrcに以下がまだ書かれていない場合は、追記してください。

export LIBRARY_PATH="/opt/homebrew/lib:$LIBRARY_PATH"

（オプション）VSCode拡張機能のインストール

VScodeでFixのコードを書く場合、以下の拡張機能をインストールすると便利です。どちらも拡張機能のMarketplaceで「fixlang」で検索するとヒットします。

テンプレートプロジェクトを作成する

AtCoderのサーバには、Fixのコンパイラだけではなく、多数のFixのライブラリもインストールされています。
以下のコマンドは、AtCoder（言語アップデート2025時点）で使えるFixのライブラリがすべてインストールされたテンプレートプロジェクトを作成します。
問題を解くときは、このテンプレートプロジェクトをコピーして使うと便利です。

mkdir fix-atcoder-template
cd fix-atcoder-template
fix init atcoder
fix deps add \
character@=1.0.1 \
hash@=1.1.0 \
hashmap@=1.1.3 \
hashset@=1.1.1 \
math@=1.2.0 \
random@=1.1.1 \
regexp@=1.1.1 \
time@=1.0.2 \
binary-heap@=0.1.2 \
bool-array@=0.1.1 \
cp-library@=0.6.8 \
ring-buffer@=0.1.1 \
gmp-fix@=0.6.0 \
minilib-common@=0.6.1 \
minilib-text@=0.5.2 \
minilib-binary@=0.5.1 \
minilib-collection@=0.6.0 \
minilib-monad@=0.6.0 \
minilib-comonad@=0.5.1 \
minilib-random@=0.5.2 \
minilib-math@=0.6.1 \
minilib-crypto@=0.5.1 \
minilib-app@=0.5.1 \
minilib-json@=0.5.1 \
minilib-xml@=0.5.1

なお、cp-libraryについて、AtCoderのサーバにインストールされているのは0.6.6ですが、上では0.6.8に更新しています。
0.6.6に対し、0.6.8は以下の改善が行われています。

  • 関数のドキュメンテーションコメントが改善されている
  • MacOSでのみ再現するバグが修正されている

Welcome to AtCoder を解く

Welcome to AtCoderで動作確認をしてみましょう。

cp -r fix-atcoder-template welcome-to-atcoder
code welcome-to-atcoder # emacsでもnvimでもお好きなエディタでどうぞ

main.fixに回答を実装します。

module Main;

import CPLib.IO;

main : IO () = (
    let a = *read_i;
    let b = *read_i;
    let c = *read_i;
    let s = *read_s(100);

    ((a + b + c).to_string + " " + s).println;;
    pure()
);

ターミナルでfix runしてから、サンプル入力を貼り付けます。

$ fix run
1
2 3
test

6 testと表示されれば成功です。

チュートリアルを読む

Fixの基本的な使い方については、以下のチュートリアルを参照してください。

ライブラリのドキュメント

AtCoder（言語アップデート2025時点）で使えるFixのライブラリのドキュメントは、こちらのページから参照できます。
問題を解いている間はブラウザで開いておくと便利です。

いくつかの問題の解答例

以下のコンテストから、問題の解答例を示します。

ほとんどのコードでimportされているCPLibは、Fixの競技プログラミング用のライブラリです。リポジトリはこちら。
CPLibは、AtCoder Library Practice Contest の問題を全て解ける程度には充実しています
（が、ac-libraryの機能を完全にカバーできているわけではありません）。

Welcome to AtCoder 

module Main;

import CPLib.IO;

main : IO () = (
    let a = *read_i;
    let b = *read_i;
    let c = *read_i;
    let s = *read_s(100);

    ((a + b + c).to_string + " " + s).println;;
    pure()
);

提出

  • read_i : IO I64は、64ビット整数を読み込みます。
  • read_s : I64 -> IO Stringは、指定された数を最大長とする文字列を読み込みます。
  • to_string : [a : ToString] a -> Stringは、型aの値を文字列に変換します。
  • println : String -> IO ()は、文字列を出力します。
  • pure : a -> IO aは、任意の値を受け取って、その値をそのまま返す、という「実際には入出力しない」IO aを作成する関数です。

Fixでは、関数fに引数xを与えて呼び出す方法として、以下の3つの書き方があります。

  • f(x)
    • 基本。
  • x.f
    • 「メソッド呼び出し風関数適用演算子」.を使う。
    • x.fよりf(x)の方が結合優先度が高いので、argとselfを引数に取る関数method : Arg -> Obj -> Ret がある場合は、 self.method(arg) と書けます。
      • よって、関数を定義するときは、Pythonのself的な引数を 最後 に置くべきです。
  • f $ x
    • 「右結合・優先順位が低い関数適用演算子」$を使う。
    • f $ g $ xはf(g(x))という風に結合する。括弧を減らしたいときに便利です。

((a + b + c).to_string + " " + s).printlnの.to_stringや.printlnの部分で、演算子.を使っています。
例えば、println $ to_string(a + b + c) + " " + sと書いても同じ意味です。

このコードで独特なのは、read_iの前についている*や、printlnの後ろについている;;、そしてpure()でしょう。以下で、これについて説明します。

Fixには「入出力操作を表す値」や、それらを集めた集合である「入出力操作を表す型」というものがあります。
多くの言語ではprintln("Hello, World!")は「命令」ですが、Fixではこれは「値」であって、変数に代入したり、演算子を使って他の入出力操作と結合したりできます。

入出力操作を表す型は、IO aという形で表されます。aはその入出力操作の結果の型です。

  • read_i : IO I64は、64ビット整数を読み込む入出力操作を表す値です。
  • println : String -> IO ()は、Stringを受け取って、それを出力するという入出力操作を作成する関数です。出力操作により得られる情報はないため、結果の型は()（Unit型）です。

グローバルに定義しているmainは、型IO ()を持つ入出力操作を表す値です。
Fixプログラムを起動すると、mainの値（入出力操作を表す値）をコンピュータへの命令として実行します。

*と;;は、複数の入出力操作を結合してより大きな入出力操作を作成するための演算子（あるいは構文）です。
入出力の結果の値を受け取りたいときは*を使い、入出力の結果の値を無視して次の入出力操作と結合したいときは;;を使います。

pure : a -> IO aは、任意の値を受け取って、その値をそのまま返す、という「実際には入出力しない」IO aを作成する関数です。
pure()は、ユニット型の唯一の値()をpureに渡したものです（pure(())と書いてもよいですが、より短くpure()と書けます）。

より理解していただくために、最後の2行

((a + b + c).to_string + " " + s).println;;
pure()

を複数の方法で書いてみます。どれも同じ動作をします。

;;ではなく*を使い、出力操作の（情報のない）結果をunitという名前で受け取る：

let unit = *((a + b + c).to_string + " " + s).println;
pure()

分けて出力する。改行しない標準出力print : String -> IO ()を使う：

(a + b + c).to_string.print;;
" ".print;;
s.println;;
pure()

println(str)の出力が()なので、実は;; pure()はカットしても同じだったりします：

(a + b + c).to_string.print;;
" ".print;;
s.println

入出力のコードをより深く理解するためには（悪名高き？）モナドを理解する必要があります。
Fixを使ったモナドの解説は、チュートリアルのモナドのセクション（トレイトの知識が前提になっています）に詳しく書かれています。
この解説は私なりに分かりやすく書いたつもりなので、ぜひ読んでみてください。

Product 

module Main;

import CPLib.IO;

main : IO () = (
    let a = *read_i;
    let b = *read_i;
    if a * b % 2 == 0 {
        println("Even")
    } else {
        println("Odd")
    }
);

提出

Fixのifは値を返します。よって、else節は必ず必要で、then節とelse節は同じ型の値を返さなければなりません。
上のコードでは、if式は、条件によって異なるIO ()の値を返しています。

ifで文字列だけを分岐させ、その結果をprintlnに渡すように書くこともできます。

module Main;

import CPLib.IO;

main : IO () = (
    let a = *read_i;
    let b = *read_i;
    println $ if a * b % 2 == 0 { "Even" } else { "Odd" }
);

提出

Placing Marbles

色々な解き方を紹介します。

loopを使う

loop関数には、

  • 様々なループの方法の中でloopが最も汎用性が高い（使える場面が多い）
  • 関数型言語らしくない書き方ができる。手続き型言語に慣れている人は、思考のリソースを節約できる

というメリットがあります。

しかし、loop関数を使うとコードが長くなりがちです。
Fixに慣れてきたら他の方法も試してみてください。

module Main;

import CPLib.IO;

main : IO () = (
    let cs = *read_cs(3);
    let cnt = loop((0, 0), |(cnt, i)|
        if i == cs.get_size { break $ cnt };
        let cnt = cnt + if cs.@(i) == '1' { 1 } else { 0 };
        continue $ (cnt, i + 1)
    );
    cnt.to_string.println
);

提出

  • read_cs : I64 -> IO (Array U8): 指定された数の非空白文字を読み込み、Array U8として返します。
  • loop : s -> (s -> LoopState s a) -> a
    • sはループの状態の型、aはループの結果の型です。
    • LoopState s aは、break : a -> LoopState s aとcontinue : s -> LoopState s aという2つの関数で作成することができます。
    • loopは、初期状態sと、ループボディ関数s -> LoopState s aを受け取り、ループボディ関数がcontinueを返す限り、ループを継続します。ループボディ関数がbreakを返したらループを終了します。
    • continueに渡された値が次のループの状態になります。
    • breakに渡された値が、loopの返す結果になります。
  • |(cnt, i)| ...の部分は関数を作る文法です（いわゆるラムダ式）。
  • @ : I64 -> Array a -> a
    • 配列のインデックス参照演算子です。arr.@(i)はarrのi番目の要素を返します。
  • get_size : Array a -> I64
    • 配列の要素数を返します。

foldを使う

fold関数は、イテレータの要素を畳み込む関数です。

module Main;

import CPLib.IO;

main : IO () = (
    let cs = *read_cs(3);
    let cnt = cs.to_iter.fold(0, |c, cnt|
        if c == '1' { cnt + 1 } else { cnt }
    );
    cnt.to_string.println
);

提出

  • to_iter : Array a -> (イテレータ a): 配列をイテレータに変換します。
  • fold : b -> (a -> b -> b) -> (イテレータ a) -> b
    • aはイテレータの要素の型、bは畳み込みの結果の型です。
    • fold は、初期値bと、「要素aと現在の畳み込み結果bを受け取り、新しい畳み込み結果bを返す関数」を受け取ります。

イテレータの型を「イテレータ a」と書いているのは、Fixのイテレータは特定の型ではなく、型の集合（トレイト）であるためです。
「イテレータ a」には、Iteratorトレイトを実装している様々な型が入り得ます。
コードによっては、きわめて複雑な型が入ることもあります。
基本的に、イテレータの型は型推論によって自動で決まっていくので、プログラマがイテレータの型を意識する必要はありません。

イテレータの詳細については、以下を参照してください。

filterを使う

module Main;

import CPLib.IO;

main : IO () = (*read_cs(3)).to_iter.filter(|c| c == '1').get_size.to_string.println;

提出

  • filter : (U8 -> Bool) -> (イテレータ a) -> (イテレータ a): 要素に対する条件関数を用いて、イテレータの要素をフィルタリングします。
  • get_size : (イテレータ a) -> I64: イテレータの要素数を返します。

Shift only

それぞれの数が2で割れる回数を再帰関数を使って求めてから、その最小値を求めます。

イテレータの最小値を求める関数がまだライブラリにない（すみません！）ので、I64::maximumを初期値とするfoldで最小値を求めます。

module Main;

import CPLib.IO;

num_div_by_2 : I64 -> I64 = |n| (
    if n % 2 == 1 {
        0
    } else {
        1 + num_div_by_2(n / 2)
    }
);

main : IO () = (
    let n = *read_i;
    let as = *read_is(n);
    as.to_iter.map(num_div_by_2).fold(I64::maximum, min).to_string.println
);

提出

  • min : [a : LessThan] a -> a -> a: 2つの値のうち、より小さい方を返す関数です。
  • read_is : I64 -> IO (Array I64): 指定された個数の64ビット整数を読み込み、Array I64として返します。

Coins 

module Main;

import CPLib.IO;

main : IO () = (
    let a = *read_i; let b = *read_i; let c = *read_i; let x = *read_i;

    range(0, a+1).product(range(0, b+1)).product(range(0, c+1))
        .filter(|((a, b), c)| a*500 + b*100 + c*50 == x)
        .get_size.to_string.println
);

提出

  • range : I64 -> I64 -> (イテレータ I64): [start, end)の範囲の整数を生成するイテレータを返します。
  • product : (イテレータ a) -> (イテレータ b) -> (イテレータ (a, b)): 2つのイテレータを受け取り、その直積を表すイテレータを返します。

Some Sums

桁の和をloopや再帰関数で求めることもできますが、ここではStringへの変換を使ってみます。

module Main;

import CPLib.IO;

sum_of_digits : I64 -> I64 = |n| (
    let chars = n.to_string.get_bytes.pop_back; // null terminatorを取り除く
    chars.to_iter.map(|c| (c - '0').to_I64).sum
);

main : IO () = (
    let n = *read_i; let a = *read_i; let b = *read_i;
    range(1, n+1).filter(|x| 
        let s = x.sum_of_digits;
        a <= s && s <= b
    ).sum.to_string.println
);

提出

  • get_bytes : String -> Array U8: 文字列の内部データ（バイト列）を取り出します。このバイト列にはnull terminatorも含まれます。
  • pop_back : Array a -> Array a: 配列の最後の要素を取り除いた配列を返します。
  • to_I64 : (数値型) -> I64: 数値を64ビット整数に変換します。

ここで、デバッグ出力の方法を紹介します。eval debug_eprintln(文字列); を挿入してください。

module Main;

import CPLib.IO;

sum_of_digits : I64 -> I64 = |n| (
    let chars = n.to_string.get_bytes.pop_back; // null terminatorを取り除く
    chars.to_iter.map(|c| (c - '0').to_I64).sum
);

main : IO () = (
    let n = *read_i; let a = *read_i; let b = *read_i;
    range(1, n+1).filter(|x| 
        let s = x.sum_of_digits;
        eval debug_eprintln("Number:" + x.to_string + ", Sum of digits:" + s.to_string);
        a <= s && s <= b
    ).sum.to_string.println
);

提出

  • debug_eprintln : String -> (): デバッグ用の標準エラー出力関数です。
    • 純粋関数のインターフェースで副作用を起こす危険な関数です。最適化レベルによって動作が変わる可能性があります。
    • AtCoderのジャッジでは標準エラー出力は無視されるため、提出コードに残しても問題ありません。
  • eval ...;：式を評価するための構文です。

Card Game for Two

ソートの練習問題という解釈であっているのでしょうか。

昇順ソートして、反転して、交代和を計算します。

module Main;

import CPLib.IO;
import Math;

main : IO () = (
    let n = *read_i;
    let as = *read_is(n);

    let as = as.sort.reverse;
    let diff = range(0, n).fold(0, |i, diff|
        diff + as.@(i) * if i % 2 == 0 { 1 } else { -1 }
    );
    diff.to_string.println
);

提出

  • sort : [a : LessThan] Array a -> Array a: 配列を昇順にソートします。
  • reverse : Array a -> Array a: 配列の要素の順番を反転します。

Kagami Mochi 

module Main;

import CPLib.IO;

main : IO () = (
    let n = *read_i; 
    let ds = *read_is(n);
    let ds = ds.sort.dedup;
    ds.get_size.to_string.println
);

提出

  • dedup : [a : Eq] Array a -> Array a: 配列から連続する等しい要素を取り除きます。

Otoshidama 

module Main;

import CPLib.IO;

main : IO () = (
    let n = *read_i;
    let y = (*read_i) / 1000;
    // 10a + 5b + c = y, a + b + c = n
    let ans = range(0, n+1).product(range(0, n+1)).map(|(a, b)|
        let c = y - 10 * a - 5 * b;
        (a, b, c)
    ).filter(|(a, b, c)|
        if c < 0 { false };
        if a + b + c != n { false };
        true
    ).get_first;
    match ans {
        some((a, b, c)) => (
            "{} {} {}".populate([a, b, c].map(to_string)).println
        ),
        none() => (
            "-1 -1 -1".println
        )
    }
);

提出

標準ライブラリにfilter_mapがない（すみません！）ので、mapとfilterを組み合わせています。

  • get_first : (イテレータ a) -> Option a
    • イテレータが空であればnone()を、要素があればsome(要素)の形で返します。
    • 戻り値の型Option aはユニオン型で、match式を使ってバリアントごとに分岐することができます。
  • populate : Array String -> String -> String
    • プレースホルダ{}に文字列を挿入する関数です。

白昼夢 

module Main;

import CPLib.IO;

main : IO () = (
    let keywords = ["dream", "dreamer", "erase", "eraser"];
    let s = *read_s(1e5);
    loop_m(s.get_size, |end|
        if end == 0 {
            println $ "YES";;
            break_m $ ()
        };
        let ok_kws = keywords.to_iter.filter(|kw|
            s.get_sub(end - kw.get_size, end) == kw
        );
        match ok_kws.get_first {
            none() => (
                println $ "NO";;
                break_m $ ()
            ),
            some(kw) => (
                continue_m $ end - kw.get_size
            )
        }
    )
);

提出

  • loop_m : [m : Monad] s -> (s -> m (LoopState s r)) -> m r
    • loopのモナド版です。
    • ループボディの中でモナドの実行（IOの実行）を行うことができます。
    • break_m/continue_mを使ってループを制御します。
  • get_sub : I64 -> I64 -> String -> String
    • 文字列の部分文字列を取得します。s.get_sub(start, end)はsの[start, end)の部分文字列を返します。

if ... { ... } else { ... } の代わりに、if ... { ... }; ... と書くことができます。
つまり、elseの代わりに;を使い、中括弧を省略できます。
この文法は、早期脱出パターンを使うときに、インデントを深くせずに済むので便利です。

Traveling 

module Main;

import CPLib.IO;

main : IO () = (
    let n = *read_i;

    let plan = [(0, 0, 0)];
    let plan = *range(0, n).fold_m(plan, |_, plan|
        let t = *read_i;
        let x = *read_i;
        let y = *read_i;
        plan.push_back((t, x, y)).pure
    );

    let ok = range(1, n+1).loop_iter_s((), |i, _|
        let (t1, x1, y1) = plan.@(i - 1);
        let (t2, x2, y2) = plan.@(i);
        let dt = t2 - t1;
        let dx = x2 - x1;
        let dy = y2 - y1;
        let d = dx.abs + dy.abs;
        if dt < d || dt % 2 != d % 2 {
            break $ ()
        } else {
            continue $ ()
        }
    );
    let ok = ok.is_continue;

    if ok {
        "Yes"
    } else {
        "No"
    }.println
);

提出

  • fold_m : [m : Monad] b -> (a -> b -> m b) -> (イテレータ a) -> m b
    • foldのモナド版です。
    • 畳み込み関数の中でモナドの実行（IOの実行）を行うことができます。

L - Deque

動的計画法の問題です。

2次元配列ライブラリがないため、「配列の配列」で2次元配列を表現しています。

module Main;

import CPLib.IO;

main : IO () = (
    let n = *read_i;
    let as = *read_is(n);

    // dp[x][y] = フロントからx, バックからy取られている状態で自分のターンが来たとき、
    // そこから稼げる(自分の得点) - (相手の得点)の最大値。
    // 0 <= x + y <= n
    // dp[x][y] = 0 if x + y == n
    // dp[x][y] が求まったら、
    // ・dp[x-1][y] max= -dp[x][y] + as[x] 
    // ・dp[x][y-1] max= -dp[x][y] + as[n-y]

    let dp = Array::fill(n+1, Array::fill(n+1, I64::minimum));
    let dp = range(0, n+1).fold(dp, |x, dp|
        let y = n - x;
        dp.mod(x, set(y, 0))
    );
    let dp = range_step(n, -1, -1).product(range_step(n, -1, -1)).fold(dp, |(x, y), dp|
        if x + y > n { dp };

        let dp = if x > 0 {
            let v = -dp.@(x).@(y) + as.@(x-1);
            dp.mod(x-1, mod(y, max(v)))
        } else { dp };

        let dp = if y > 0 {
            let v = -dp.@(x).@(y) + as.@(n-y);
            dp.mod(x, mod(y-1, max(v)))
        } else { dp };

        dp
    );

    dp.@(0).@(0).to_string.println
);

提出

  • fill : I64 -> a -> Array a
    • 指定された要素で初期化された配列を作成します。
    • Array::fillのArrayはfillの属している名前空間です。省略しても動作しますが、明示的に書くことで「Arrayを作っている」ことがわかりやすくなります。
  • set : I64 -> a -> Array a -> Array a
    • 指定されたインデックスの要素を指定された値に置き換えた新しい配列を返します。
  • mod : I64 -> (Array a -> Array a) -> Array a -> Array a
    • 指定されたインデックスの要素に対して、指定された関数を適用した新しい配列を返します。
  • max : [a : LessThan] a -> a -> a
    • 2つの値のうち、より大きい方を返す関数です。
    • max(v)は引数に渡された値とvのうち大きい方を返す、型I64 -> I64を持つ関数です。
  • range_step : I64 -> I64 -> I64 -> (イテレータ I64)
    • ステップ幅を指定して範囲を生成します。range_step(start, end, step)はstart, start + step, start + 2*step, ...という列で、endに到達するか飛び越えたら終わります。

setやmodは「新しい配列を返す」と説明しましたが、実際に配列のコピーが発生するかどうかは、状況によります。
大雑把に言えば、配列を更新する時点で、その配列への参照を一つだけ持っているようにコードを書けば、コピーは発生しません。
具体的には、上のコードのように、dpを受け渡していくスタイルでコードを書けば、コピーは最小限に抑えられ（2）、DPで期待される計算量になります。

「配列の配列」を更新するときは、dp.mod(i, set(j, x))やdp.mod(i, mod(j, f))と書く必要があり、やや煩雑です。
Fixの次のバージョン（1.2.0）では、これをdp[i][j].iset(x)やdp[i][j].imod(f)と書けるようになります。

よくある質問・ありそうな質問

構文エラーになる。特にセミコロンの使い方がよくわからない。

主なセミコロンの使用箇所は以下の通りです。

  • value : Type = ...;: グローバル値の定義の終わり。
  • let x = ...; ...: let構文の一部。
  • if ... { ... }; ...: if構文の一部。if ... { ... } else {...}と同じ。
  • eval ...; ...: eval構文の一部。
  • action1;; action2: モナド（IOなど）の結合。

コード

f : I64 -> I64 = |x| (
    if x == 0 { 0 };
    let z = 42;
    x + z
);

において、

  • 一つ目のセミコロンはif構文の一部です。
  • 二つ目のセミコロンはlet構文の一部です。
  • 三つ目のセミコロンはグローバル値fの定義の終わりです。

上のコードでは、改行・括弧・インデントを適切に使っているので、各セミコロンの意味は分かりやすくなっています。
しかし、Fixにおいて、改行とインデントは意味を持たず、関数定義の本体部分を囲う括弧は冗長（何の結合順序も変更していない）です。
よって、改行・インデント・括弧をすべて取り除き、

f : I64 -> I64 = |x| if x == 0 { 0 }; let z = 42; x + z;

と書いても、同じコードです。
各セミコロンの意味も同じです。

コードを書いている途中に何かミスしていても、まともなエラーメッセージが表示されない / 識別子上でマウスホバーしても型情報が表示されない

module Main;

main : IO () = (
    let a = *read_i;
    if a == 0 {
        // 今からここを書く
    } else {
        // 今からここを書く
    }
);

この書きかけのソースコードは、構文的に不完全であるため、診断処理のかなり初期の部分でエラーになっており、その先の診断（型チェックなど）が行われていません。
「何か間違いを犯していても、関数を書き終えるまではまともなエラーメッセージが出てこない」というのは、Fixの（関数型言語の？）UXの大きな欠点です。

これに対するworkaroundとして、まだ書いていない個所にundefined("")と書いておく、というテクニックがあります。
undefined : String -> aは、どんな型の値も作り出すことができる関数です。
実際に呼び出されたときは、与えられた文字列をエラーメッセージとして出力して、プログラムをエラー終了させます。

関数を実装させているときに「そろそろエラーが欲しいな」と思ったら、まだ書いていない場所にundefined("")を置きます。
これで、とりあえず構文的に正しいコードになり、診断処理が先に進むようになります。

module Main;

main : IO () = (
    let a = *read_i;
    if a == 0 {
        undefined("")
    } else {
        undefined("")
    }
);

これで診断を走らせる（プラグインを入れたVSCodeでファイルを保存する）と、
read_iのところに「Unknown name read_i」と表示されます。
import CPLib.IO;を忘れていました。

Fixの今後について

AtCoderで動くようになったFixのバージョンは1.1.0です。
現在、1.2.0を開発中です。1.2.0では以下のような更新が行われる予定です。
AtCoderの次の言語アップデートは2027年でしょうか。

  • インデックス構文
    • L - Dequeでも言及しましたが、arr.mod(i, set(j, x))やarr.mod(i, mod(j, f))の代わりに、arr[i][j].iset(x)やarr[i][j].imod(f)と書けるようになります。「配列の配列」に限らず「構造体の配列」に対する「要素のフィールド」へのアクセスも短く書けるようになります。
  • キャスト関数の名称変更（短縮形の追加）
    • 解答例でU8からI64への変換に「to_I64」が出てきましたが、キャストという頻出するコードの割にはタイプ数が多いな、と思われた方もいるかもしれません。1.2.0ではより短くx.i64と書けるようになります。
  • get_sizeの名称変更（短縮形の追加）
    • arr.get_sizeの代わりにarr.@sizeと書けるようになります。str.get_sizeの代わりにstr.@sizeと書けるようになります。（イテレータの個数をカウントする関数の名称は変らない予定です。）
  • 配列の境界チェックなど、ランタイムチェックをオフにするオプションの追加
    • AtCoderのジャッジではランタイムチェックをオフにすれば、速度を稼げます。REがWAに変わってしまうリスクはありますが。
  • 最適化の追加
    • 引き続き、高い性能を出すべく最適化の実装を頑張っています。

  1. alphaとあって不穏な感じがしますが、これは私のバージョン付けが下手なだけであり、特に問題なく使えるバージョンです。もちろん、バグが一切ない訳ではないので、あしからず。 ↩

  2. 2次元配列の初期化処理Array::fill(n+1, Array::fill(n+1, I64::minimum))において、内側の配列Array::fill(n+1, I64::minimum)は一つだけ作成されます。外側の配列の各要素は、この一つの配列を参照するように初期化されます。よって、dpの初期状態では、内側の配列に対する多重参照が生じています。実際、この時点ではメモリはO(n)しか消費されていません。そのあとのsetやmodで内側の配列が更新されるときに、必要に応じて配列のコピーが発生し、徐々にO(n^2)のメモリを占める真の「2次元配列」が完成します。そのあとは、setやmodでコピーが生じることはありません。 ↩

11
6
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
11
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?