ESM オフラインリアルタイムどう書くの問題を解いた（３日ぐらいかけて）

鍋谷さんの投稿を拝見して問題と開催レポートが公開されていることに今日になって気がつきました。今回は開催者側、出題者側にいたはずなのに…。

それはそれとして。

参加されたみなさんの解答を見て、基本的なアイディアはそれほど変わらなくてもその実現方法は結構違うなぁ、というのが感想でした。
それらの実装を頭のすみでぼんやりと反芻していて３日ほどが経ち、ほぼビット演算だけで解く方法を思いつきました。かつての投稿同様にこの問題特化のコードです。

解説は…そのうちブログで書く予定。…たぶん。

Rubyで解いた

def solve(input)
  seats = 0
  input.split('').map(&:to_i).each do |visitors|
    begin
      seats = (seats >> 1) & 0x77777777
    end until (index = ('%016x' % (seats * 0x100000001)).index('0' * visitors))
    seats |= (((((1 << (visitors * 4)) - 1) * 0x100000001) << ((8 - visitors) * 4) >> (index * 4)) & 0x44444444)
  end
  '%08x' % ((seats | (seats >> 1) | (seats >> 2)) & 0x11111111)
end

def test(input, expected)
  actual = solve(input)
  if expected == actual
    puts "PASSED"
  else
    puts "FAILED input #{input}, expected #{expected}, actual #{actual}"
  end
end

test("3316", "11111110")
# 以下テストケース略

同じものをC++で書いた

#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>

static std::string to_hex(unsigned long int n, int digits)
{
    std::ostringstream oss;
    oss.fill('0');
    oss << std::hex << std::setw(digits) << n;
    return oss.str();
}

static std::string solve(const std::string& input)
{
    unsigned long int seats = 0;
    for(std::string::const_iterator i = input.begin(); i != input.end(); ++i)
    {
        const int              visitors   = *i - '0';
        const std::string      visitors_s = std::string(visitors, '0');
        std::string::size_type index      = std::string::npos;
        do
        {
            seats = (seats >> 1) & 0x77777777lu;
        } while((index = to_hex(seats * 0x100000001lu, 16).find(visitors_s)) == std::string::npos);
        seats |= (((((1lu << (visitors * 4)) - 1) * 0x100000001lu) << ((8 - visitors) * 4) >> (index * 4)) & 0x44444444lu);
    }
    return to_hex((seats | (seats >> 1) | (seats >> 2)) & 0x11111111u, 8);
}

static void test(const std::string& input, const std::string& expected)
{
    const std::string actual = solve(input);
    if(expected == actual)
    {
        std::cout << "PASSED" << std::endl;
    }
    else
    {
        std::cout << "FAILED input " << input << ", expected " << expected << ", actual " << actual << std::endl;
    }
}

int main(int, char* [])
{
    test("3316", "11111110");
    // 以下テストケース略

    return 0;
}