ardririyの足跡
競プロMoonbit

MoonbitでAtCoder 過去問精選 10 問

2026/09/22
MoonbitでAtCoder 過去問精選 10 問

こんばんは。最近全私の中で話題になっているMoonbitに入門してみようと思いました。新しい言語を学ぶときにまずすることは何でしょうか？そうですね、AtCoderです。ということで、AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～で紹介されている10問をMoonbitで解きました。

先に感想を書くと、とにかく書きやすくて、表現したいことが自然に表現できるなという印象を受けました。雑に書きたいな～というところを雑に書けるのも好印象。つまりとてもとても好きです。

競プロで (ライブラリを書くわけでもなしに) 使う範疇の構文しか書いていないので、実際のところアプリケーションに採用するのはどうなの？というのはわかりません。それはまた、今度の機会に。

事前準備

実際に解いていく前に、AtCoderをするためにいくつか確認しておくべきことがあります。

標準入力を受け取る

入力を受け取らねば (ほとんどの問題で) 始まらないわけですが、どうやら標準入力を受け取る手段が標準ライブラリになさそうなので、ここはjavascriptの力を借ります。

moonbitlang/asyncパッケージを使うのがおそらく一番良い手法ですが、Javascriptにトランスパイルする必要があり (後述) 、それを満たせないので致し方なく、です。

extern "js" fn read_stdin() -> String =
  #| () => require("fs").readFileSync(0, "utf8")

fn main {
  println(read_stdin())
}
❯ echo "test
1 2" | moon run cmd/main
test
1 2

AtCoderで実行可能な形式にする

残念ながら (？) MoonbitはAtCoderで利用可能な言語に入っておらず、また言語アップデートもしばらく先になりそうなため、このままでは提出すらできません。幸いなことに、Javascriptへのトランスパイル手段が用意されているので、これを使って提出することにします。

❯ moon build --target js --release
Finished. moon: ran 2 tasks, now up to date

❯ cat _build/js/release/build/cmd/main/main.js
const _M0FP48username17moonbit__tutorial3cmd4main11read__stdin = () => require("fs").readFileSync(0, "utf8");
function _M0FPB7printlnGsE(input) {
  console.log(input);
}
(() => {
  _M0FPB7printlnGsE(_M0FP48username17moonbit__tutorial3cmd4main11read__stdin());
})();

以下のように実行できます。これだけで40msかかっているのが気がかりですが、そこはまあ、Javascriptなので……。

image.png

問題を解く

準備ができて実行ができることを確認したので、実際に解いていきます。

A - Product

二数a, bを受け取って、その積の偶奇を判定する問題です。素直に掛け算をする代わりに、入力を" " で分けた配列の末尾一文字の偶奇を見てあげるのが軽そうです。Charに対するto_int はASCII (unicode?) で割り当てられている値が帰ってくる気がしますが、いずれにせよ偶奇にしか興味がないので問題ないです。

AtCoderの入力には通常末尾に改行文字が入るので、入力のtrimをしてあげる必要があります (一敗) 。提出

///|
extern "js" fn read_stdin() -> String =
  #| () => require("fs").readFileSync(0, "utf8")

///|
fn main {
  let s = read_stdin().trim()
  println(
    if s
      .split(" ")
      .map(fn(s) { s.iter().last().unwrap() })
      .any(fn(c) { c.to_int() % 2 == 0 }) {
      "Even"
    } else {
      "Odd"
    },
  )
}

A - Placing Marbles

1 の個数を数えてあげればよいです。提出 このあたりはRustに似た書き味で、かつRustよりも軽く書けて扱いやすく良いなぁという印象を受けます。

///|
extern "js" fn read_stdin() -> String =
  #| () => require("fs").readFileSync(0, "utf8")

///|
fn main {
  let s = read_stdin().trim()
  println(
    s.iter()
      .filter(fn (c) {
        c == '1'
      })
      .count()
  )
}

B - Shift only

各数それぞれに対して2で割れる回数を数えて、その最小値が答えです。提出

なんとMoonbitはfor式なので「2で割れるまで割って、何回割れたかを返す」のような手続き的に書きたいコードを以下のように、非常に簡潔に書けます。他にもIterに対するfor-inループや、C言語スタイルのfor なども書けるみたいです (参考) 。すごい。

///|
extern "js" fn read_stdin() -> String =
  #| () => require("fs").readFileSync(0, "utf8")

///|
fn parse_to_int(s : StringView) -> Int {
  let mut res = 0
  for c in s {
    res *= 10
    res += c.to_int() - '0'.to_int()
  }
  res
}

///|
fn main {
  let s = read_stdin().trim().split("
")
  let _n = parse_to_int(s.next().unwrap())
  let a = s.next().unwrap().split(" ").map(parse_to_int)

  println(
    a
    .map(fn(ai) {
      for cnt = 0, val = ai {
        if val % 2 == 0 {
          continue cnt + 1, val / 2
        } else {
          break cnt
        }
      }
    })
    .minimum()
    .unwrap(),
  )
}

B - Coins

３つの硬貨を何枚使うかをそれぞれ三重ループ全探索すれば、O(ABC)O(ABC)で十分高速に解けます。提出

rangeの書き方の閉区間/開区間を明示的に<と<=で書き分けるのは好みが分かれそうです。変ではないので特に気になりませんでしたが。あとは構造化束縛の書き方が少し癖があるかも。

それから、ちょっとバグらせたときに気づいたのですが、Array[T]のvに対して debug(v) と書いたときにvの所有権がdropされないのが競プロ的には地味にありがたいです (所有権自体の概念は存在するはず; ref) 。

///|
extern "js" fn read_stdin() -> String =
  #| () => require("fs").readFileSync(0, "utf8")

///|
fn parse_to_int(s : StringView) -> Int {
  let mut res = 0
  for c in s {
    res *= 10
    res += c.to_int() - '0'.to_int()
  }
  res
}

///|
fn main {
  let s = read_stdin().trim().split("
")
  let v = s.map(parse_to_int).collect()
  guard v is [a, b, c, x, ..] else { panic() }

  let mut ans = 0
  for ai in 0..<=a {
    for bi in 0..<=b {
      for ci in 0..<=c {
        ans += if ai * 500 + bi * 100 + ci * 50 == x { 1 } else { 0 }
      }
    }
  }

  println(ans)
}

B - Some Sums

桁和が指定された範囲内に収まっているかを答える問題です。愚直に計算すれば良くて、桁和の計算はfor式として書けるのが役立ちますね。提出

///|
extern "js" fn read_stdin() -> String =
  #| () => require("fs").readFileSync(0, "utf8")

///|
fn parse_to_int(s : StringView) -> Int {
  let mut res = 0
  for c in s {
    res *= 10
    res += c.to_int() - '0'.to_int()
  }
  res
}

///|
fn main {
  let s = read_stdin().trim().split(" ")
  let v = s.map(parse_to_int).collect()
  guard v is [n, a, b] else { panic() }

  let ans = [
      for i in 1..<=n => i
    ]
    .iter()
    .filter(fn(i) {
      let ds = for ds = 0, val = i {
        match val {
          0 => break ds
          _ => continue ds + val % 10, val / 10
        }
      }

      a <= ds && ds <= b
    })
    .fold(init=0, (acc, val) => acc + val)
  println(ans)
}

B - Card Game for Two

後半戦です。二人とも自分の点数の最大化を目指すので、残りから一番多いものを取るのが最適です。降順にソートして、index付きのfoldでtupleを返してあげるのが良さそうです。提出

///|
extern "js" fn read_stdin() -> String =
  #| () => require("fs").readFileSync(0, "utf8")

///|
fn parse_to_int(s : StringView) -> Int {
  let mut res = 0
  for c in s {
    res *= 10
    res += c.to_int() - '0'.to_int()
  }
  res
}

///|
fn main {
  let s = read_stdin().trim().split("
")
  let _ = s.next()
  let mut v = s.next().unwrap().split(" ").map(parse_to_int).collect()
  v.sort()
  v = v.rev()

  let (a, b) = v
    .iter2()
    .iter()
    .fold(init=(0, 0), (acc, v) => {
      if v.0 % 2 == 0 {
        (acc.0 + v.1, acc.1)
      } else {
        (acc.0, acc.1 + v.1)
      }
    })

  println(a - b)
}

iter2 だったり、ラムダ引数でタプルが展開できないのが気になるところではあります。が、多分こういう書き方のより良い代替があるんだろうな～などと思ってLLMに投げてみたところ、for式で書く方が良さそうと言われ、確かに……となりました。

B - Kagami Mochi

uniqueなものの個数を取ってあげれば良いです。実装上は@set.Set に突っ込んでそのサイズを取るのが良さそうですね。このあたりは標準ライブラリで提供されているのはありがたいです。提出

なお、ドキュメントに以下の記載がある通りHash setなので、もしCFなどで使う場合は注意が必要そうです (誰向け？) 。

Mutable linked hash set that maintains the order of insertion, not thread safe

///|
extern "js" fn read_stdin() -> String =
  #| () => require("fs").readFileSync(0, "utf8")

///|
fn parse_to_int(s : StringView) -> Int {
  let mut res = 0
  for c in s {
    res *= 10
    res += c.to_int() - '0'.to_int()
  }
  res
}

///|
fn main {
  let s = read_stdin().trim().split("
").collect()
  guard! s is [_, .. sv]
  let st = Set::from_iter(sv.iter())
  println(st.length())
}

C - Otoshidama 

dpi,j:=\text{dp}_{i, j} := jj枚組み合わせて合計ii円になる組み合わせ(x,y,z)(x,y,z) とするDPが思いつきます。 空間が大きすぎそうな気もしますが、1円, 5円, 10円をN枚組み合わせてY/1000円を作ると考えれば、Y/1000の最大値が2×1042\times10^4なのでなんとかなりそう。

…素直に多次元配列を持ったらMLEしてしまいました。これはトランスパイルなどは関係なく、単純に非想定解を無理やりDPで殴ろうとしたからっぽいです。next dpに書き換えてAC、とはいえ1101msでかなりギリギリ。提出

///|
extern "js" fn read_stdin() -> String =
  #| () => require("fs").readFileSync(0, "utf8")

///|
fn parse_to_int(s : StringView) -> Int {
  let mut res = 0
  for c in s {
    res *= 10
    res += c.to_int() - '0'.to_int()
  }
  res
}

///|
fn main {
  let s = read_stdin().trim().split(" ").map(parse_to_int).collect()
  guard! s is [n, y]

  let y = y / 1000

  let mut dp = Array::make(y + 1, (-1, -1, -1))
  dp[0] = (0, 0, 0)
  for i in 0..<n {
    let ndp = Array::make(y + 1, (-1, -1, -1))
    for j in 0..<y {
      if dp[j].0 == -1 {
        continue
      }

      let (a, b, c) = dp[j]
      if j + 10 <= y {
        ndp[j + 10] = (a, b, c + 1)
      }
      if j + 5 <= y {
        ndp[j + 5] = (a, b + 1, c)
      }
      if j + 1 <= y {
        ndp[j + 1] = (a + 1, b, c)
      }
    }
    dp = ndp
  }

  let (x, y, z) = dp[y]
  println("\{z} \{y} \{x}")
}

想定解は10000円札と5000円札の枚数の組み合わせを全探索する、らしいです。水色コーダーさん？

C - Daydream

Sの末尾から指定された文字列を消していけばよいです。「いくつかの候補のうち少なくとも一つにマッチしたか？」を、for式で返せるのが気持ち良いなぁと感じます。提出

///|
extern "js" fn read_stdin() -> String =
  #| () => require("fs").readFileSync(0, "utf8")

///|
fn parse_to_int(s : StringView) -> Int {
  let mut res = 0
  for c in s {
    res *= 10
    res += c.to_int() - '0'.to_int()
  }
  res
}

///|
fn main {
  let s = read_stdin().trim().iter().collect()

  let v = ["dream", "dreamer", "erase", "eraser"].map(fn(c) {
    c.iter().collect()
  })

  while !s.is_empty() {
    let len = for vi in v.iter() {
      if s.length() < vi.length() {
        continue
      }
      if s[s.length() - vi.length():] == vi {
        break vi.length()
      }
    } nobreak {
      -1
    }

    if len == -1 {
      println("NO")
      return
    }

    for _ in 0..<len {
      let _ = s.pop()
    }
  }

  println("YES")
}

C - Traveling

ラストです。すべての予定に対して、時間の差分と、マンハッタン距離の偶奇が一致していて、かつ時間の差分がマンハッタン距離以上であれば達成可能です。t=0で(0,0)が目標地点になっていると考えると自然に書けます。提出

地味ですが、Array[T]に対して加算が定義されているのがありがたいなぁと思うところです。Rustだとちょっと悩むので。

///|
extern "js" fn read_stdin() -> String =
  #| () => require("fs").readFileSync(0, "utf8")

///|
fn parse_to_int(s : StringView) -> Int {
  let mut res = 0
  for c in s {
    res *= 10
    res += c.to_int() - '0'.to_int()
  }
  res
}

///|
fn main {
  let s = read_stdin().trim().split("
")
  let _ = s.next()

  let v = [(0, 0, 0)] +
    s
    .map(fn(sl) {
      guard! sl.split(" ").map(parse_to_int).collect() is [t, x, y, ..]
      (t, x, y)
    })
    .collect()

  println(
    if v
      .windows(2)
      .all(fn(v) {
        let diff = v[1].0 - v[0].0
        let dist = (v[1].1 - v[0].1).abs() + (v[1].2 - v[0].2).abs()

        dist % 2 == diff % 2 && diff >= dist
      }) {
      "Yes"
    } else {
      "No"
    },
  )
}
← 一覧へ