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

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

こんにちは、しきゆらです。
今回は、タイトル通りABC321のC問題を解説をみながらコードを書いてみたので、自分用にまとめていきます。

今回解いた問題

ABC321は2023/09/23に開催されたABCコンテストです。
今回解いた理由としては、AtCoder Daily Trainingという平日に開催されている練習用コンテストにて出題されたからです。
他問題は解凍できましたが、この問題には手がつかなかったので、解説を聞きつつ調べつつデコードを書いてみた、という状況です。

321-like Numberの定義

まずは、問題に出てくる「321-like Number」の定義についてまとめておきます。
「321-like Number」の定義としては以下の通りです。

• x の各桁を上から見ると狭義単調減少になっている。
• すなわち、x が d 桁の整数だとすると、 1≤i<d を満たす全ての整数 i について以下の条件を満たす。
  ( x の上から i 桁目 ) > ( x の上から i+1 桁目 )

例えば、321や953は321-like Numberであり、123や491は321-like Numberではありません。
そして、問題文にある通り「0」は321-like Numberではなく、一桁の数(1 ~ 9)は321-like Numberになります。

考え方

ここからは、基本的にAtCoderの解説を聞いた上での話になります。
取りうる方法としては、いくつかあるようです。

• 1から順番に数字を確認し「321-like Number」であればカウントしていき、カウントがKになったらその値を返す
• 321-like Numberの全パターンを作成し、その中からK番目の値を返す

今回問題では条件として0~9の数値は各桁に1回しか出てこないので、321-like Numberの上限は「9,876,543,210」であることがわかります。
そして、各桁に0~9を使うかどうかと置き換えることもできるので、各数字を使うかどうかは2パターンであり、それが0~9まであるので 2 ** 10通りとわかります。

正確には、321-like Numberの定義から0は除外され、全ての数値を使わないパターンはないので321-like Numberは1024 - 2 = 1022個になります。
では、この全1022個のパターンを網羅するにはどうすれば良いでしょうか。

その方法の一つがビット全探索です。
※ 他に、再帰的に実行する方法での全探索もあるのですが、今回は扱いません。
再帰についてもう少し勉強してまとめられるようになったらまとめます。

計算回数について

プログラムが時間内に完了するかは、計算回数を考えることが重要です。
競技プログラミングでは、2 秒などの制限時間が設定されており、この時間内に結果を返す必要があります。

では、1 秒間でどの程度計算ができるかを考えてみましょう。
CPUの処理速度を表す指標として「動作周波数」や「クロック」と呼ばれるものがあり、現在の CPU は一般的に 3〜6 GHz で動作します。
つまり、1 秒に 約 10⁹ 回（10億回）程度の計算が可能です。

この 10億 回/秒というスケールを頭に入れて、アルゴリズムの計算量を評価しましょう。

全探索とは

ビット全探索の前に、全探索について簡単にメモしておきます。
全探索とは、その名の通り考えられる全パターンを列挙・探す方法です。
全てのパターンを列挙・処理するため、パターン数が増えると実行時間が指数関数的に増加するため、パターンが少ない場合によく用いられます。

例えば、「1」「2」「3」と書かれたボールがそれぞれ1つずつ箱に入っているとして、取り出したボールに書かれた数の和は何通りか、という問題を考えてみます。
この問題の全パターンは以下の通り。
ボールのマークがあるところが、そのボールを取り出したことを表しています。

ボールの取り出し方は図の通りで、ボールを取った時の和は0 ~ 6の7通りあることがわかりました。
このように、取りうる場合を全て列挙し、その中から必要な場合を探す方法が全探索です。

なお、このボールの数を増やしていくとどうなるでしょうか。
ボールが3つの場合のボールの取り方は全パターンが8通りでしたが、ボールが10個になると1024通り、ボールが20個の場合は1,048,576通り、ボールが30個の場合は1,073,741,824通りと、ボールの数が多くなると取り出すパターンが爆発的に増えます。
先ほどの計算回数のことを思い出すと、実用的な時間内で全探索できるボールの数は30個程度、ということがわかるかと思います。

ビット全探索

全探索のうち、ビット演算を使って全パターンを探索する方法です。
この方法は、取りうる場合を各ビットに対応させて考えられるような問題で使われます。
ただし、こちらも全探索の方法の一つなので、パターンが多い場合には避けるべき方法です。

上記の3つのボールを選ぶ例を使うと、ボールを取るかどうかをビットとして考えてみます。
すると、ボールを取るか取らないかは2通りあり、ボールが3つあるので 2 ** 3 = 8通りあることがわかります。

表の「-」の部分を0、それ以外を「1」として考えてみます。
パターン⑥を例として計算してみると、(ボール1 * 1) + (ボール2 * 0) + (ボール3 * 1) = 1 + 3 = 4となるわけです。

ここで、パターンの数字(①〜⑧)とビットの関係をみてみると、パターンの数字から1引いたもののビットと同じことがわかります。
再度パターン⑥を例にしてみると、6 - 1 = 5であり、5を2進数で表現すると1 0 1となります。

つまり、問題の中で取りうる場合をビットとして捉えることができればビット演算で全パターンを網羅できるということです。

以下のサイトがわかりやすくまとめてくれているので、こちらもどうぞ。

ABC321のC問題をビット全探索で考えてみる

途中で別の例を上げてしまったので、再度ABC321のC問題で考えてみます。
今回の問題では、各数値を使うかどうかをビットに置き換えて「使う場合(1)」と「使わない場合(0)」として考えてみます。

このようにちょっと工夫すると「321-like Number」を簡単に生成できるわけです。
なお、各桁の数値について、9〜0と並んでいる方が321-like Numberの定義に合っているのでこのような並び順で置いている点にご注意ください。

あとは、この各値を使うかどうかの全パターンを網羅することを考えてみます。
各桁の使うかどうかを0/1のビットに置き換えて全パターンを網羅します。

解法

回答となる全体を載せると以下の通りです。
今回求めるべきは、入力されたkに当たる321-like Numberなので、生成した321-like Numberをソートしています。
そして、配列は0始まりなのでk - 1とアクセスしている点に注意です。

k = gets.strip.to_i

list = [] # 321-like Numberを格納する配列
# 全てのビット列を試す
(2 ** 10).times do |bit|
  num = 0
  # 9 ~ 0 が使われるかどうかを確認するため、9から0まで繰り返す
  9.downto(0) do |i|
    # bitに対して、1が立っていればその値をnumに保持する
    num = (num * 10) + i if (1 << i).anybits?(bit) # bitのうち、i番目に1が立っている
  end
  list << num if num.nonzero?
end

puts list.sort[k - 1]

実際に動かしてみます。

K = 15  =>     32
K = 321 =>   9610
K = 777 => 983210

入力例と出力例を見比べると、正しそうです。
では、もう少し細かく見ていきます。
重要な箇所は以下の箇所です。

list = [] # 321-like Numberを格納する配列
# 全てのビット列を試す
(2 ** 10).times do |bit|
  num = 0
  # 9 ~ 0 が使われるかどうかを確認するため、9から0まで繰り返す
  9.downto(0) do |i|
    # bitに対して、1が立っていればその値をnumに保持する
    num = (num * 10) + i if (1 << i).anybits?(bit) # bitのうち、i番目に1が立っている
  end
  list << num if num.nonzero?
end

それぞれを簡単に解説してみます。

パターンを表す数字を取得する

ビット全探索は、先ほど例として挙げたパターンの数をビットに見立てることが必要です。
ここでは、前述の通り全パターンが2 ** 10通りなので、その分繰り返してます。

Integer#timesメソッドはブロックパラメータをとる時、繰り返している時の値を取得できます。
このブロックパラメータを欲しいパターン(0 ~ 1023)のビットに見立ててます。

# 全てのビット列を試す
(2 ** 10).times do |bit|

パターンを表すビットの中で1が立っている箇所を取得する

この部分が今回の核となる部分です。

  # 9 ~ 0 が使われるかどうかを確認するため、9から0まで繰り返す
  9.downto(0) do |i|
    # bitに対して、1が立っていればその値をnumに保持する
    num = (num * 10) + i if (1 << i).anybits?(bit) # bitのうち、i番目に1が立っているかを判定
  end

まずは、(1 << i).anybits?(bit)について細かくみてみます。

左シフト演算

(1 << i)は１に対してi回左にビットシフトした値を取得してます。

irb(main):001> 1 << 1
=> 2
irb(main):002> 1 << 2
=> 4
irb(main):003> 1 << 10
=> 1024

では、左シフトした値に対して実行しているanybits?(bit)とはなんでしょうか。

anybits?メソッド

Integer#anybits?はselfと引数のビット積のうち、いずれかのビットが1の時にtrueを返すメソッドです。
ビット演算で表記するとself & 引数 != 0と同等です。

irb(main):001> 5.anybits? 2
=> false
irb(main):002> 6.anybits? 2
=> true

つまり(1 << i).anybits?(bit)の部分は、取りうる場合を表すbitのうち、ビットが1になっている箇所を探しているわけです。

ここまでをまとめると、以下のような流れで処理しています。

1. 9.downto(0) |i|で 9から0まで実行
2. bit(= 対象パターン)のうち、1が立っているかを確認
3. １が立っていれば、numの値を10倍し、iを加える

最後に以下の部分です。
なお、listは撮りうる場合を格納する配列です。
ここは、今回の「321-like Number」の定義として0は321-like Numberではないので除外しています。

list << num if num.nonzero?

全ての場合で条件チェックするのが嫌であれば、全パターンを網羅したあとにlist.sort!.shiftとかでソートした先頭を取れば0を削除できるので、こっちでも良いかもしれません。

解法のまとめ

全探索、ビット全探索とは、というところからビット演算の簡単な説明とRubyのコード上のビット演算について簡単にまとめました。

正直なところ、個人的にはビット演算をしている時に、ここで考えている値はビット(2進数)なのか普通の数値(10進数)なのかがごちゃごちゃするので苦手です。
しかし、ビット演算の性質をうまくつかうことである種の問題については簡単に解くことができることがわかりました。

そして、もう少しビット演算についてはまとめる必要があるな、と感じました。
一応大学では学んでいる上に、2進数についても概要は知ってはいますが、それを使うところまでは達していない状況です。

そして、学生時代にプログラミングが強い友人が「左にシフトすると2倍になるから〜」と言っているのが理解できなかったことを思い出しました。
立ち止まって考えればそうなのですが、それを使って何かしようとすると手がつかなくなってしまうのが今の状況なんだな、と実感しました。

合わせて、この問題を解く方法がビット全探索しかないわけではありません。
前述の通り再帰的に求める方法もあるのですが、そこはまだ理解できていないのでビット全探索との比較等もできていない状況です。
もう少し知識を広げないといけないな、というところでした。

まとめ

今回は、ABC321のC問題を公式の解説を聞きながら解いたので、その時に調べたことを合わせてまとめました。

あまり得意ではないビット演算を、取りうる場合に紐づけて考えるビット全探索という方法を知り、実際にコードに落としてみることはできました。
今後は、色々な問題に取り組む中で「この問題にはこれが使えそう」という勘所を掴んでいければ、と思っています。

今回は、ここまで

おわり