Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
2
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

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

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

それはそれとして。

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

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

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;
}
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
2
Help us understand the problem. What are the problem?