多段階選抜 (C++20)


|多段階選抜|解答日|シリーズ:yieldの練習/ジェネレータを入れ子に/整数平方根・立方根の実装|
|:--|:--|:--|
|問題|　|http://nabetani.sakura.ne.jp/hena/ord24eliseq/<br>https://qiita.com/Nabetani/items/1c83005a854d2c6cbb69|
|Ruby|2014/8/2(当日)|https://qiita.com/cielavenir/items/9f15e29b73ecf98968a5|
|C#/Python|2014/8/4|https://qiita.com/cielavenir/items/a1156e6a4f71ddbe5dcb|
| |　|ここから上はdrop_prev_square/drop_prev_cubicをまとめる前の答案|
|Go/C#/Ruby/Python|2014/8/5|https://qiita.com/cielavenir/items/2a685d3080862f2c2c47|
|PHP/JavaScript|2014/9/9|https://qiita.com/cielavenir/items/28d613ac3823afbf8407|
|VB|2014/9/10|https://qiita.com/cielavenir/items/cb7266abd30eadd71c04|
|D|2015/12/21|https://qiita.com/cielavenir/items/47c9e50ee60bef2847ec|
|Perl|2017/3/10|https://qiita.com/cielavenir/items/6dfbff749d833c0fd423|
|Lua|2017/3/13|https://qiita.com/cielavenir/items/c60fe7e8da73487ba062|
|C++20(TS)|2017/3/15|https://qiita.com/cielavenir/items/e1129ca185008f49cbab (MSVC)<br>https://qiita.com/cielavenir/items/1cfa90d73d11bb7dc3d4 (clang)|
|F#|2017/3/17|https://qiita.com/cielavenir/items/a698d6a26824ff53de81|
|Boo/Nemerle|2017/5/13|https://qiita.com/cielavenir/items/e2a783f0fe4b0fe0ed48|
|Perl6|2017/5/15|https://qiita.com/cielavenir/items/656ea17fa96c865c4498|
|Kotlin|2017/5/25|https://qiita.com/cielavenir/items/9c46ce8d9d12e51de285|
|Crystal|2018/5/8|https://qiita.com/cielavenir/items/1815bfa6a860fd1f90db|
|MoonScript|2018/6/16|https://qiita.com/cielavenir/items/8b03cce0386f4537b5ad|
|Julia/Rust|2018/12/20|https://qiita.com/cielavenir/items/3ddf72b06d625da0c4a5|
|Nim|2018/12/26|https://qiita.com/cielavenir/items/5728944867e609fd52a7|
|Tcl|2018/12/31|https://qiita.com/cielavenir/items/76cbd9c2022b48c9a2c9|
|Pascal/Cobra|2019/1/16|https://qiita.com/cielavenir/items/81b81baf8dfc1f877903|
|Icon|2019/1/17|https://qiita.com/cielavenir/items/889622dcc721f5a4da24|
|Swift|2020/5/31|https://qiita.com/cielavenir/items/3b0b84a218e35d538f7f|
|Java/Groovy/Scala|2020/5/31|https://qiita.com/cielavenir/items/7f058203a8fd03b65870|
|V|2020/10/17|https://qiita.com/cielavenir/items/df30a6c101a97a713df5|
|Zig/Zen|2020/10/17|https://qiita.com/cielavenir/items/9cced9e4a94dcd70df0f|
|Pike|2020/11/2|https://qiita.com/cielavenir/items/3a8248f41611302b34fd|
|Vala/Smalltalk|2020/11/29|https://qiita.com/cielavenir/items/085dabe593cd916af5e8|
|Objective-C|2020/11/30|https://qiita.com/cielavenir/items/a1736e38789a3dd5cc5a|
|Ruby(Ractor)|2021/1/2|https://qiita.com/cielavenir/items/f493c6d512b63cc571cc|
|Python(_xxsubinterpreters)|2021/6/29|https://qiita.com/cielavenir/items/f1f581a055db918954f1|
|Falcon/Scheme|2021/9/5|https://qiita.com/cielavenir/items/c13d12cf44f0d17f4a94|
|Clojure/Lisp|2021/9/7|https://qiita.com/cielavenir/items/7458ba076f4e5bc0f196|
|(icbrtの実装に関する)補題|2017/5/11|整数除算であってもn/(x*y)はn/x/yに等しい(ことの証明)<br>https://qiita.com/cielavenir/items/21a6711afd6be8c18c55|

clang-5以降でコルーチン使えるようになっていたことを最近知ったので修正しました。Windows以外でコンパイルできると安心感がありますね。

```cpp:tyama_hena24_enum.cpp
//usr/bin/true; tmpfile=$(mktemp); clang++ -fcoroutines-ts -stdlib=libc++ -std=c++17 -o $tmpfile "$0" && $tmpfile; rm -f $tmpfile; exit

// http://qiita.com/Nabetani/items/1c83005a854d2c6cbb69
// http://nabetani.sakura.ne.jp/hena/ord24eliseq/

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <numeric>
#include <cstdio>
#include <cmath>
using namespace std;

#if defined(_MSC_VER)
#include <experimental/generator>
#else
//based on https://github.com/Microsoft/Range-V3-VS2015/issues/12#issuecomment-291325027
//modified by cielavenir
//(according to http://releases.llvm.org/5.0.0/tools/clang/docs/ReleaseNotes.html#major-new-features and https://wandbox.org/permlink/Dth1IO5q8Oe31ew2)

/***
*generator
*
*       Copyright (c) Microsoft Corporation. All rights reserved.
*
*       Purpose: Library support of coroutines. generator class
*       http://open-std.org/JTC1/SC22/WG21/docs/papers/2015/p0057r0.pdf
*
*       [Public]
*
****/
#pragma push_macro("new")
#undef new

#include <experimental/coroutine>

namespace std {

namespace experimental {

	template <typename _Ty, typename _Alloc = allocator<char>>
	struct generator
	{
		struct promise_type
		{
			_Ty const *_CurrentValue;
			auto get_return_object() { return generator{coroutine_handle<promise_type>::from_promise(*this)}; }
			auto initial_suspend() { return suspend_always{}; }
			auto final_suspend() { return suspend_always{}; }
			void unhandled_exception() { std::terminate(); }
			void return_void() {}

			auto yield_value(_Ty const &_Value)
			{
				_CurrentValue = addressof(_Value);
				return suspend_always{};
			}

			using _Alloc_traits = allocator_traits<_Alloc>;
			using _Alloc_of_char_type = typename _Alloc_traits::template rebind_alloc<char>;

			void *operator new(size_t _Size)
			{
				_Alloc_of_char_type _Al;
				return _Al.allocate(_Size);
			}

			void operator delete(void *_Ptr, size_t _Size) _NOEXCEPT
			{
				_Alloc_of_char_type _Al;
				return _Al.deallocate(static_cast<char *>(_Ptr), _Size);
			}
		};

		struct iterator
		{
			using iterator_category = input_iterator_tag;
			using difference_type = ptrdiff_t;
			using value_type = _Ty;
			using reference = _Ty const &;
			using pointer = _Ty const *;

			coroutine_handle<promise_type> _Coro = nullptr;

			iterator() = default;
			iterator(nullptr_t) : _Coro(nullptr) {}
			iterator(coroutine_handle<promise_type> _CoroArg) : _Coro(_CoroArg) {}

			iterator &operator++()
			{
				_Coro.resume();
				if (_Coro.done())
					_Coro = nullptr;
				return *this;
			}

			void operator++(int)
			{
				// This postincrement operator meets the requirements of the Ranges TS
				// InputIterator concept, but not those of Standard C++ InputIterator.
				++*this;
			}

			bool operator==(iterator const &_Right) const { return _Coro == _Right._Coro; }
			bool operator!=(iterator const &_Right) const { return !(*this == _Right); }
			reference operator*() const { return *_Coro.promise()._CurrentValue; }
			pointer operator->() const { return _Coro.promise()._CurrentValue; }
		};

		iterator begin()
		{
			if (_Coro) {
				_Coro.resume();
				if (_Coro.done())
					return {nullptr};
			}

			return {_Coro};
		}

		iterator end() { return {nullptr}; }
		explicit generator(coroutine_handle<promise_type> x) : _Coro(x) {}
		generator() = default;
		generator(generator const &) = delete;
		generator &operator=(generator const &) = delete;
		generator(generator &&_Right) : _Coro(_Right._Coro) { _Right._Coro = nullptr; }

		generator &operator=(generator &&_Right)
		{
			if (this != addressof(_Right)) {
				_Coro = _Right._Coro;
				_Right._Coro = nullptr;
			}
			return *this;
		}

		~generator()
		{
			if (_Coro) {
				_Coro.destroy();
			}
		}

	private:
		coroutine_handle<promise_type> _Coro = nullptr;
	};

} // namespace experimental

}

#pragma pop_macro("new")
#endif
using namespace std::experimental;

int isqrt(int n){
	if(n<=0)return 0;
	if(n<4)return 1;
	int x=0,y=n;
	for(;x!=y&&x+1!=y;)x=y,y=(n/y+y)/2;
	return x;
}
int icbrt(int n){
	if(n<0)return -icbrt(-n);
	if(n==0)return 0;
	if(n<8)return 1;
	int x=0,y=n;
	for(;x!=y&&x+1!=y;)x=y,y=(n/y/y+y*2)/3;
	return x;
}

generator<int> mygenerate(){
	int i=1;
	for(;;){
		co_yield i;
		i+=1;
	}
}
generator<int> drop_prev(bool(*check)(int),generator<int> _prev){
	auto prev=_prev.begin();
	int a=*prev;
	++prev;
	int b=*prev;
	for(;;){
		if(!check(b))co_yield a;
		a=b;
		++prev;
		b=*prev;
	}
}
generator<int> drop_next(bool(*check)(int),generator<int> _prev){
	auto prev=_prev.begin();
	int a=*prev;
	++prev;
	int b=*prev;
	co_yield a;
	for(;;){
		if(!check(a))co_yield b;
		a=b;
		++prev;
		b=*prev;
	}
}
generator<int> drop_n(bool(*check)(int,int),int n,generator<int> _prev){
	auto prev=_prev.begin();
	int i=0;
	for(;;){
		i++;
		int a=*prev;
		if(!check(i,n))co_yield a;
		++prev;
	}
}
bool is_sq(int n){
	int x=isqrt(n);
	return x*x==n;
}
bool is_cb(int n){
	int x=icbrt(n);
	return x*x*x==n;
}
bool is_multiple(int i,int n){return i%n==0;}
bool is_le(int i,int n){return i<=n;}

int main(){
	map<char,function<generator<int>(generator<int>)>> f={
		{'S',[&](auto e){return drop_next(&is_sq,move(e));}},
		{'s',[&](auto e){return drop_prev(&is_sq,move(e));}},
		{'C',[&](auto e){return drop_next(&is_cb,move(e));}},
		{'c',[&](auto e){return drop_prev(&is_cb,move(e));}},
		{'h',[&](auto e){return drop_n(&is_le,100,move(e));}},
	};
	vector<int>v(8);
	iota(v.begin(),v.end(),2);
	for(auto &e:v)f[(char)('0'+e)] = [&](int &j){
		return [&](auto e){return drop_n(&is_multiple,j,move(e));};
	}(e);

	string line;
	for(;getline(cin,line);){
		bool first=true;
		//cS => f['S'](f['c'](generate()))
		//auto z=reduce!((s,e)=>f[e](s))(generate(),line);

		auto z=mygenerate();
		for(char e:line)z=f[e](move(z));
		auto it=z.begin();
		for(int i=0;i<10;i++){
			int n=*it;
			++it;
			if(!first)putchar(',');
			first=false;
			printf("%d",n);
		}
		puts("");
		fflush(stdout);
	}
}
```