【Ruby】ABC442のC問題を解いてみる

2026年8月31日Ruby,競技プログラミング関連

こんにちは、しきゆらです。
以前から度々話題にあげている競技プログラミングですが、A/B問題は割と解けることがわかってきました。
そこで、練習としてC問題を解いてみるようにしています。
その中で、今回はABC442のC問題をRubyで解いたので、自分の中の整理として解法まとめておきます。

C問題の練習について

C問題の練習として、AtCoder Problemsを使っています。
これは、自分のAtCoderのユーザIDを入力すると、過去回答した問題・正解した問題・未回答の問題を色分けして表示してくれるサイトです。

これからは過去のC問題を解いていき、その問題の中で使うアルゴリズムや考え方をまとめていきつつ、実際のコンテストでもC問題を時間内に正解できるようになるのが当面の目標です。
そのため、解いた問題や解法をまとめて記事にしていこうと思っているので、よろしくお願いします。

今回解いたC問題

ABC442は2026/01/24に開催されたABCコンテストです。
なお、この問題を選んだ理由は、C問題の列にカーソルを合わせて適当にスクロールして当たったのがこの問題だった、というだけのシンプルなものです。

C問題の具体的な内容は上記から確認いただくとして、ざっくり受け取る値は以下の通りです。

N: 研修者の人数
M: 利害関係の数
Ai, Bi: 研究者間の利害関係

上記の状況で、研究者iが単著者論文の査読者を3名選ぶとき、利害関係者を含まない組み合わせは何通り過求める、というのがこの問題です。

考え方

入力として受け取るAi, Biは研究者間の利害関係を表しています。
サンプルを使って例示すると以下の通りです。
まずは、サンプルの入力は入力例1の以下を使って考えてみます。

6 5
1 2
1 4
2 3
5 3
3 1

1行目の6 5は研究者数Nと利害関係の数Mを表しているので、その後を見ていきます。
2行目は研究者1と研究者2が利害関係にあることを示しています。
2行目以降の利害関係をもとに、全ての利害関係を図解すると以下のようになります。

図を見ると、研究者1は研究者2,3,4と利害関係があり、この中から３名を査読者として選ぶことはできないので0通り。
同様に、研究者2と利害関係がない研究者は研究者4,5,6なので、組み合わせは1通り。
研究者3と利害関係がない研究者は、研究者4,6のみなので、3名を査読者として選ぶことができないので0通り。
研究者4と利害関係がない研究者は、研究者2,3,5,6なので、4名から3名を選ぶので4C3の4通り。
研究者5と利害関係がない研究者は、研究者1,2,4,6なので、上記と同様に4通り。
研究者6は誰とも利害関係がないので、5C3の10通りです。

より一般化して考える

研究者がn人いる場合、研究者iと利害関係がある人数がmとすると、査読者としての選び方は自分意外の研究者の中から選ぶのでn-1、さらに利害関係がある人数mを除外するので(n-m-1)人の中から3名を選べば良いことになります。

そして、n-m-1の値が3より小さければ、選びようがないので0通りとなり、
n-m-1の値が3以上であれば(n-m-1)C3を計算すれば良い、というわけになります。
(n-m-1)がわかりにくいですが、これをxと置くと、組み合わせの計算はx~x-2までの積を3!で割るので、xC3はx * (x - 1) * (x - 2) / (3 * 2 * 1)となります。
あとは、これらをコードに落とし込めば良いだけですね。

念の為、組み合わせの計算については、以下あたりが参考になるかと思います。

解法

Rubyで実装すると以下のようになります。

def comb3(x)
  return 0 if x < 3

  x * (x - 1) * (x - 2) / 6
end

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

degree = Array.new(n + 1, 0)
m.times do
  a, b = gets.split.map(&:to_i)
  degree[a] += 1
  degree[b] += 1
end

puts degree[1, n].map { |i| comb3(n - i - 1) }.join(" ")

ほとんど、先ほどの「一般化して考える」の部分を愚直に実装した形です。
利害関係者数をdegreeという配列で管理し、利害関係者a, bを配列のインデックスとして処理しています。
すると、degreeの先頭要素は使わないので、0番目を無視した1番目からn番目までの部分配列を取得し、それぞれの利害関係者数を使って組み合わせ計算をし、joinで結合して出力してます。

上記では組み合わせ計算をメソッドに切り出していますが、(n - i - 1)の値で条件分岐させたinject等でも実装可能です。

・・・見通しが悪くなりますが、例えば以下の通り。

puts degree[1, n].map { |i| i >= n - 1 ? 0 : ((n - i - 3)..(n - i - 1)).inject(:*) / 6 }.join(" ")

解法のまとめ

今回の問題は、特に難しいアルゴリズム的な問題ではなく、どちらかといえば数学の問題かなと思いました。
利害関係者の数を除いた組み合わせの問題だと分かれば、発想の流れとしては割とシンプルな問題かと思います。

1. 研究者数を取得する
2. 各研究者ごとの利害関係人数を求める
3. 研究者の総数から自分を除いたメンバーを求める
   • ３人未満の場合は、組み合わせは0通り
   • 3名以上の場合は、xC3で求める
4. 結果を出力する

ただし、今回の問題では条件として利害関係について同じ値が含まないのでシンプルですが、同じ関係を表すデータが複数入っている(例として、(1, 2)と(2, 1)など)場合は、単純に数を数えるだけでなく過去にそれと同じことを表すデータがないかを判定する必要が出てくるので注意です。
例えばですが、SetやHashを使って研究者ごとに利害関係がある研究者番号を格納しておき、過去に同じ組み合わせがなかったかを判定するなどの条件分岐が必要になってくるかと思います。

また、私はRubyで実装しているので影響はないですが、C++などだと扱う値が大きくなるとオーバーフローする可能性も考慮する必要が出てきます。
組み合わせの問題だと、nCrのnが大きくなればなるほど組み合わせ数は爆発的に増えるの注意が必要です。

まとめ

今回は、AtCoderの練習として解いた過去問ABC442のC問題を解いたので、考え方や解法をまとめました。
今回の問題は、割と短めの時間で解決方法を見つけることができ、正解することができました。
AtCoder Problemsのサイト上のDifficultyは低めでした。
今後は、このくらいの問題を重点的に解いていきながら練習していこうと思います。

合わせて、個人的にはプログラミングよりも日本語の問題文を読んで理解するのに一番時間がかかっていた印象です。
利害関係のデータを見て、何を表しているのかを問題文を読んでもいまいちピンとこず、以下の箇所を読んだ時に「研究者1に対してA1とB1が利害関係者なのか？」とか勘違いしてました。

i=1,2,…,M に対して研究者 Ai​ と研究者 Bi​ は互いに利害関係にあります。

一度理解してしまえば何故そんなふうに考えたのか謎ですが、内容を素早く理解し実装に移れるように練習あるのみかなと思いました。

今回は、ここまで。

おわり