SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) に参加した。D - Base n を解きながら、いままで知らなかった Ruby の振る舞いを知りえたので書いておく。
0-9 からなる文字列を、整数 d で基数変換し、整数 n 以下かどうか調べる。これがやりたいことである。整数オーバーフローに気をつけながら変換アルゴリズムを書くのが面倒に思えて、 Ruby の String#to_i ならサクッと安全に変換できるかな？ と考えた。つまりこんな感じである。
def f(s, d, m)
s.to_i(d) <= m
end
require 'minitest/autorun'
class T < Minitest::Test
def test_f
assert_equal(true, f('22', 3, 10)) # 3進数表記: '22'.to_i(3) == 8 < 10
assert_equal(true, f('22', 4, 10)) # 4進数表記: '22'.to_i(4) == 10 < 10
assert_equal(false, f('22', 5, 10)) # 5進数表記: '22'.to_i(5) == 12 > 10
end
end
で、このメソッドを繋ぎ込んで、適当な入力のテストケースを足して実行してみると、こんなエラーメッセージを出して落ちてしまう。
~~~ ArgumentError (invalid radix 37)~~~
どうやら基数が 36 以下であるうちはよいのだが、 37 はダメらしい。まったく予期していなかった結果で、どうしてだ？ 素数だからか？ と無意味な当てずっぽうをはじめてしまいかねないほどにはパニックを起こしていた。
一呼吸おいて、インターフェースを調べてみるとちゃんと書いてあった。
Returns the result of interpreting leading characters in str as an integer base base (between 2 and 36). 1
「へええ！」と思いつつ、とはいえコンテスト中に深く考える余裕はなく、さっさと Ruby で実装する方針は諦めて自前の変換アルゴリズムを書いたのだった。
一晩あけてちゃんと考えてみると、当然の振る舞いというよりない。要するに、 [0-9a-z] の 36 要素を超えて全順序を定義することはもとよりできないというだけの話である。もちろん Integer#to_s でも同じことである。今回のケースでいえば、レシーバの文字列は 0-9 のみを含む、というのは問題文の制約にすぎない。そうでない自由な文字列を任意の値で基数変換するのは不可能であるから、結局のところ基数変換のロジックはユーザーが自前で用意するよりない。
ところで問題そのものの解法については、制限時間を10分残したところで二分探索する方針にようやく辿りついたが、実装にダラダラ手間取ってしまい、15分超過してようやく正解できた。単純に二分探索が手に馴染んでいないことが白日のもとにさらされたわけである。今回のコンテストで手痛い思いをしたので、次にあらわれたときには倒してやるからな、という気持ちでいる。
提出 #20343302 - SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)