Rubyで解説 C - Robot Factory トヨタシステムズプログラミングコンテスト2025 アルゴリズムシリーズ 第3話

初めに

　本記事はアルゴリズムをRubyを使って解説を行なっております。
　今回は トヨタシステムズプログラミングコンテスト2025のC - Robot Factory これをテーマに解説しています。

アルゴリズムシリーズ第3話

このチームに入って1日目、メンバーはパッと見た感じ平均年齢27歳ほどで若いイメージがある。しかし、幹部の人々には髭を生やし、眉間に皺が寄っていて、コワモテな人がちらほらいる。俺はここでやっていけるのだろうか。。。そんなことを思っていると1人の27歳くらいの女性が声をかけてきた。

先輩の女性：君が新入りのオペレーターかな？よろしく〜！

俺：よろしくお願いします。

先輩の女性：今からここら辺の軍事兵器と場所の説明をするからついてきて。他の先輩にあったら挨拶してくるといいよ！あと、最後に私たちのチームリーダーのところにいくからね。

俺：わかりました。
気さくな感じのこの女性にこれからしばらく指導してもらうのだろうか。
しばらく歩き、軍事兵器が置かれているエリアについた。そこには大量の有人操縦型ロボットがあった、その近くでは有人操縦型ロボットの訓練場のような場所があり、実際に動いているロボットをちょうど見ることができた。そのロボットが急に止まり上半身が開き、中に座っている人が声をかけてきた。

ロボットの中にいる男性：お！君が今日入った子か。よろしく！

俺：よろしくお願いします。

先輩の女性：あっ！ちなみにね〜、この人が操縦しているのがタンク型有人操縦型ロボットってやつで、一番最前線で戦うんだよ！

まだこの基地に来てから実感が湧いていなかったが、実際に動いているロボットを間近に見たことで、ついに日本のために最前線で戦う特別軍事基地のオペレーター部隊に所属されたという実感が湧いてきた。オペレーターとはここにある有人操縦型ロボットを操作する人間のことである。第三次世界大戦が始まって一年ほど経つが去年までが夢だったかのように今の日本は変わってしまった。今までWebエンジニアとして働いていた俺は怪我をすることもなく安全な場所で仕事ができていた。そんな平和な世界で生活していたはずなのに、戦争が始まって間もなく召集令状が渡され軍事訓練を受けてから、このオペレーター部隊に派遣された。今まで自分の命が脅かされるような仕事をしたことなんてなかったのに、これから始まるこの基地での仕事はミスをすれば命を失う。怖い！信じられない！なんで国民のために戦って死ななきゃならないんだ！何でここにいる人たちはそれを受け入れたような顔していられるんだ！！死にたくない！！逃げたい！！

という夢をこの前見たんですよね。怖かった〜。実はこの夢まだ続きがあってこの後、同期のオペレーターとかに会って、そのオペレーターの中に小学校から高校まで同じだった友達がいて〜、みたいに続いてくんですけど長いからここらへんで終わりにしときます。

アルゴリズムシリーズの第2話からだいぶ時間が空いてしまいました。最近は卒制が終わり就活の準備を進めているのですが、初めての就活ということもあり結構追われてる気分なんですよね。こういう時に見る夢も何だか追われてる感じがするんですよねぇ〜。同期の人たちも何人か就活終わってるみたいで、なるべく早く仕事見つかるといいなーと思ってます。

問題

問題文
高橋くんは、頭パーツを 1 個と体パーツを 1 個組み合わせてロボットを 1 体作ることができます。 ロボットは頭パーツの重さが体パーツの重さより大きいと倒れてしまいます。

現在、高橋くんは頭パーツを N 個と体パーツを M 個持っています。 
高橋くんが持っている i 番目 (1≤i≤N) の頭パーツの重さは Hiグラム、i 番目(1≤i≤M) の体パーツの重さは Biグラムです。

高橋くんは、持っているパーツを適切に組み合わせることで、倒れないロボットを合計 K 体作りたいです。 うまくパーツを組み合わせることで高橋くんが目標を達成することができるか判定してください。

ただし、
1 個のパーツを複数のロボットを作るために利用したり、1 体のロボットを作るために頭パーツを 2 個以上（もしくは体パーツを 2 個以上）利用することはできません。

詳しくは問題文

考え方

今回の問題は貪欲法というアルゴリズムを使っていきます。
貪欲法とは複数の配列を小さい順に並べてその小さい方からマッチングさせていくというものです。今回の問題で言うと、頭のパーツがいくつかあり、それを小さい順に並べる、そして体のパーツも同様に小さい順に並べ、小さい頭と小さい体をマッチングさせていく。なぜこのようにするかというと、小さい頭と大きい体をマッチングさせてもロボットは倒れることはないが、小さい頭にあまりにもでかい体をつけると大きな頭とつながるはずだった大きな体を無駄に使ってしまうことになり効率が非常に悪くなってしまうのである。

実際の動き

頭パーツ[1, 2, 3, 4]
体パーツ[2, 3, 4, 5]

indexの0(小さい方）から順番にマッチングしていく。
頭が1で体が2。つまりロボットが完成する。合計で４つのロボットが完成する。

そこでこの貪欲法を採用するのだが、1つ問題がある。

問題点

この方法だと、例えば小さい順に配列を並べたときに、
頭パーツ[2, 3, 4, 5]
体パーツ[1, 2, 3, 4]
このようになった場合、小さい順にマッチングしていくと[2,1], [3,2], [4,3], [5,4]といったように全ての組み合わせに失敗してしまう。しかし、パーツを自由に動かして見た場合、この配列だと、頭の2と体の2、頭の3と体の3、頭の4と体の4で合計3つの倒れないロボットができる。つまり、この単純な貪欲法だとこの些細なズレが重なった時に最も効率のいいパーツの組み合わせを見つけることができなくなってしまう。

ここで、このアルゴリズムに一手間を加える。
頭パーツ[2, 3, 4, 5]
体パーツ[1, 2, 3, 4]
この時に頭パーツが2で体パーツが1で、頭より小さいのなら体パーツのindexを1つ飛ばし、次のindexとマッチングさせるのである。
このようにすれば、1つの頭パーツに対し体パーツの最も適したサイズを見つけることができるのだ。
それでは次から実際にコードに書き起こしてみよう

入力処理

サイトの問題文にあるように
入力は

6 6 3       頭のパーツの数、体のパーツの数、倒れないロボットの数
2 7 1 8 2 8　　頭パーツの重さ＊頭パーツの数
1 8 2 8 4 5　　体パーツの重さ＊体パーツの数

このようになっている。
まずはこの入力を受け取るコードを書く

n, m, k = gets.split.map(&:to_i)
heads = gets.split.map(&:to_i)
bodies = gets.split.map(&:to_i)

getsで入力を１行受け取り、
splitで空白で区切る、
mapで各配列要素にto_i（文字列を整数に変換する）を適用する。

配列を小さい順にする

heads.sort!
bodies.sort!

sortメソッドはデフォルトで小さい順になる。
また、!は元の配列を直接書き換えると言う効果をもつ。

マッチングの処理

先ほど解説したように、現在最も小さい頭パーツに対して最適な現在最も小さい体パーツが来るまでスキップするという処理を作っていきます。

# 完成しているロボットの数は初めは0
rubot_count = 0 
# スキップした体パーツをカウントする初めは0
body_index = 0

# 頭パーツの数だけ処理を行う
heads.each do |head|
  # 頭パーツに合う体パーツを探す
  while body_index < m && bodies[body_index] < head
    body_index += 1 # この処理に該当するつまり体パーツが頭パーツより軽い場合body_indexを+1することでスキップする。
    # この体パーツは最も小さい頭パーツより小さいので、使われることはない。
    # ちなみにmというのは問題文にあるが体パーツの総数。body_indexが体パーツの総数を超えるとエラーになるためこの記述がある。
  end
  # 使える体が見つかった場合以下の処理に行く
  if body_index < m # body_indexが総数を超えるのはおかしいので
    rubot_count += 1
    body_index += 1 # 使用済みの体パーツも除外する
  end

  break if rubot_count >= k
  # kとは完成したロボットの数
  # kを超えたらYesなのでこれ以上続ける必要はない
end

# 判定
if rubot_count >= k
  puts "Yes"
else
  puts "No"
end

breakは繰り返し処理を強制終了させる

まとめ

それぞれのパーツを小さい順に並べ、頭パーツの最も小さいものから体パーツの小さいものを比較していき、そのパーツが適切かどうかを判断し、適切でなければスキップし、適切ならロボットが一つ増え、同時にそこで使われた体パーツも二度は使えないのでスキップする。この流れが今回の問題の解き方でした。

終わりに

この解説にどこか間違っているところなどあればコメントにて教えていただけるとありがたいです。