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;
}
Author And Source
この問題について(ESM オフラインリアルタイムどう書くの問題を解いた（３日ぐらいかけて）), 我々は、より多くの情報をここで見つけました https://qiita.com/emattsan/items/c5be573586df510eb5b7著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .