Zenn
⏹️

Siv3D | 「二次元いもす法」を可視化する

2022/03/03に公開
#
競技プログラミング
siv3d
tech

二次元いもす法

競技プログラミングにおけるテクニック「いもす法」を二次元に拡張した、「二次元いもす法」を可視化する Siv3D プログラムです。

いもす法については下記の記事を参照してください。

動画

https://twitter.com/Reputeless/status/1499360860632141824

Siv3D による可視化プログラム

# include <Siv3D.hpp> // OpenSiv3D v0.6.3

void Main()
{
	// Web 版の場合コメントをはずす
	// Scene::SetResizeMode(ResizeMode::Keep);
	// Scene::Resize(1280, 720);

	Window::Resize(1280, 720);

	Scene::SetBackground(ColorF{ 0.8, 0.9, 1.0 });

	// フォント
	const Font font{ FontMethod::MSDF, 48, Typeface::Bold };

	// セルの大きさ
	constexpr int32 CellSize = 40;

	// マス目の数
	constexpr Size GridSize{ 1080 / CellSize, 720 / CellSize };

	Grid<int32> grid(GridSize);

	// 選択開始したセル
	Optional<Point> grabbed;

	// 長方形領域
	Array<Rect> rects;

	// 累積和計算位置
	int32 iX = GridSize.x;
	int32 iY = GridSize.y;

	// 累積和アニメーションのストップウォッチ
	Stopwatch stopwatch;

	// アニメーションの速さ
	double speed = 0.4;

	while (System::Update())
	{
		// すべてのマスを描画
		for (auto p : step(GridSize))
		{
			const Rect rect = Rect{ (p * CellSize), CellSize };

			if (auto value = grid[p])
			{
				const ColorF color = (value < 0)
					? ColorF{ 0.0, 0.4, 0.8 } : Colormap01F(value / 6.0, ColormapType::Viridis);

				rect.stretched(1).draw(color);
			}
			else
			{
				rect.stretched(-1).draw(ColorF{ 1.0 });
			}
		}

		// セルの数値を描画
		for (auto p : step(GridSize))
		{
			const Rect rect = Rect{ (p * CellSize), CellSize }.stretched(-1);

			font(grid[p]).drawAt(24, rect.center(), ColorF{ grid[p] ? 1.0 : 0.8 });
		}

		// 長方形の領域を描画
		for (const auto& rect : rects)
		{
			Rect{ rect.pos * CellSize, rect.size * CellSize }
			.drawFrame(3, 1, ColorF{ 0.7 });
		}

		// 領域の選択を開始
		if (MouseL.down())
		{
			const Point pos = (Cursor::Pos() / CellSize);

			if (InRange(pos.x, 0, (GridSize.x - 1))
				&& InRange(pos.y, 0, (GridSize.y - 1)))
			{
				grabbed = pos;
			}
		}

		// 領域選択中
		if (grabbed)
		{
			Point pos = (Cursor::Pos() / CellSize);
			pos.x = Clamp(pos.x, 0, (GridSize.x - 1));
			pos.y = Clamp(pos.y, 0, (GridSize.y - 1));

			const Size size = (pos - *grabbed);

			Rect rect{ *grabbed, size };

			if (rect.w < 0)
			{
				rect.x += rect.w;
				rect.w *= -1;
			}

			if (rect.h < 0)
			{
				rect.y += rect.h;
				rect.h *= -1;
			}

			rect.size += Size::One();

			Rect{ rect.pos * CellSize, rect.size * CellSize }
				.draw(ColorF{ 0.1, 0.4, 0.7, 0.4 })
				.drawFrame(3, 1, ColorF{ 0.7 });

			if (MouseL.up())
			{
				rects << rect;

				const Point tl = rect.tl();
				const Point br = rect.br();

				++grid[tl];

				if ((br.x < GridSize.x) && (br.y < GridSize.y))
				{
					++grid[br];
				}

				if (br.x < GridSize.x)
				{
					--grid[{ br.x, tl.y }];
				}

				if (br.y < GridSize.y)
				{
					--grid[{ tl.x, br.y }];
				}

				grabbed.reset();
			}
		}

		if (SimpleGUI::Button(U"X →", Vec2{ 1100, 20 }, 140))
		{
			iX = 1;
			stopwatch.restart();
		}

		if (SimpleGUI::Button(U"Y ↓", Vec2{ 1100, 80 }, 140))
		{
			iY = 1;
			stopwatch.restart();
		}

		if (SimpleGUI::Button(U"Reset", Vec2{ 1100, 140 }, 140))
		{
			rects.clear();
			grid.fill(0);
			iX = GridSize.x;
			iY = GridSize.y;
		}

		SimpleGUI::Slider(U">>", speed, 0.0, 0.5, Vec2{ 1100, 200 }, 30, 110);

		// X 方向累積和（アニメーション）
		if (iX < GridSize.x)
		{
			Line{ (iX * CellSize), 0, (iX * CellSize), 720 }.draw(4, Palette::Red);

			if (SecondsF{ 0.5 - speed } <= stopwatch)
			{
				for (int32 y = 0; y < GridSize.y; ++y)
				{
					grid[y][iX] += grid[y][iX - 1];
				}

				++iX;
				stopwatch.restart();
			}
		}

		// Y 方向累積和（アニメーション）
		if (iY < GridSize.y)
		{
			Line{ 0, (iY * CellSize), 1080, (iY * CellSize) }.draw(4, Palette::Red);

			if (SecondsF{ 0.5 - speed } <= stopwatch)
			{
				for (int32 x = 0; x < GridSize.x; ++x)
				{
					grid[iY][x] += grid[iY - 1][x];
				}

				++iY;
				stopwatch.restart();
			}
		}
	}
}

Discussion