タイトルの通り、生産スケジューラFLEXSCHEで競技プログラミングの問題を解いてみたいと思います。わざわざFLEXSCHEを使う意味は全くありませんが、思いついてしまったのでやってみます。

• 答えを計算して出力する

だけではなく、

• 問題を視覚化する

ということもやってみたいと思います。

生産スケジューラとは？という方はこちらもご覧ください。
競技プログラミングとは以下のようなものです。日本ではAtCoderが競技プログラミングコンテストを行うサービスとして有名です。

競技プログラミングでは、参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。
https://ja.wikipedia.org/wiki/競技プログラミング

また、PG BATTLEという年に1回開催されている学校・企業対抗の競技プログラミングイベントがあり、弊社でも協賛・参加しています。今回はこのPG BATTLEの過去問にチャレンジしてみます。

スケジューラとしての便利さは直接伝わらないかもしれませんが、もしかしたらFLEXSCHEってすごいのかも、と思っていただけるようやっていきたいと思います。

問題

こちらの問題にチャレンジしてみます。
PG BATTLE 2019 ましゅまろ スライドボウリング(Sliding Bowling)

• 各レーンに1本ずつピンがあり、そのピンが1秒ごとに隣のレーンに移動する
• (aj+bj)秒後に倒れていないピンがレーンjにあればそのピンを倒す
• 合計で何本のピンが倒されるかを出力する

といった内容になります。

FLEXSCHEで解いてみる

FLEXSCHEにはtakt式というものがあります。
takt式はFLEXSCHE独自の言語です。FLEXSCHE内部の様々なオブジェクトにアクセスしてそのプロパティを取得したり、様々な演算を行ったりすることができ、FLEXSCHEの様々な振る舞いをきめ細かく指定することができます。過去のブログでも紹介しているのでより詳しく知りたい方はそちらもご覧ください。(takt式マニアクス① ②)
このtakt式を使って問題を計算してみます。

入力は文字列の引数で受け取ることにし、以下のような処理を行わせます。

• 各ピンに対応するフラグを用意
• (aj+bj)秒後に、レーンjにピンがあればそれに対応するフラグを立てる
• 立っているフラグの数を答えとする

以下のようなtakt式になりました。入力は変数$inputに受け取っています。

// 入力をメッセージパネルに表示
UI.MessagePanel.Write('---入力---' + String.LF),
UI.MessagePanel.Write($input + String.LF),

// 入力からn, mを取得
$line1 := $input.Separate(String.CR).First, // 入力の1行目を取得
$n := $line1.Separate(' ').First,
$m := $line1.Separate(' ').Last,

// フラグを用意
$flags := BoolList.Empty,
LongList.Make(0, $n+1).ForEach([
	$flags.Append_(false)
]),

// 入力の2行目以降を対象に計算していく
$input_ab := $input.Separate(String.CR),
LongList.Make(1, $n).ForEach([
	$aj := $input_ab.At($_object).Separate(' ').First,
	$bj := $input_ab.At($_object).Separate(' ').Last,
	$j := $_object,
	$i := $j - $aj - $bj,
	$flags.Set_($i, (1 <= $i and $i <= $m) ? true : $flags.At($i)),
]),

// 立っているフラグの数が答え
$ans := 0,
$flags.ForEach([
	$ans :=  $_object ? $ans + 1 : $ans
]),

// 答えをメッセージパネルに表示
UI.MessagePanel.Write('---出力---' + String.LF),
UI.MessagePanel.Write($ans + String.LF)

詳細な説明は割愛しますが、公式の解答例と同じことをしています。

出力はメッセージパネルと呼ばれるパネルに出力します。
問題の例1，例2の入力を与えるとそれぞれ以下のような出力が得られます。無事、両方とも合っていました。

視覚化してみる

計算することはできました。次はこの問題を視覚化してみます。例1でやってみます。

FLEXSCHEのガントチャートで表示するために、

• レーン→資源
• ボール→作業
• ピン→作業

で表現します。tの変化に応じてボール(作業)の日時を変化させることでボールが動くさまを表現します。さらに、ボールの色を位置に応じて白→オレンジ→グレーと変化させてみます。同様にピンの色も紫→グレーと倒される前後で変化させます。ピンの作業には倒されたかどうかのフラグを持たせています。問題ではレーンは縦方向でピンは横に流れていきますが、FLEXSCHE上では90度回転させたかたちになります。

t=0のときはこんな感じになります。ボールとピンの四角さには目を瞑りましょう。04/01(土)にいるボールが04/09(日)にいるピンに向かって動いていきます。ピンは下のレーンへ動いていきます。(N=4なのでピン5以降は省略します。)

t=2のときに、ピン1がレーン3上で倒されます。ボールは投げられた瞬間からオレンジに変わり、先に着くとグレーになります。ピンは倒されるとグレーになります。

t=0から5まで変えていくとこうなります。（右上にtを変化させる特別なボタンを配置しています）

おわりに

いかがでしたか。

takt式とガントチャートで、競技プログラミングにチャレンジしてみました。何やらFLEXSCHEすごそう、と少しでも思っていただけたら幸いです。

今回はあまり複雑な問題ではありませんでしたが、takt式では連想配列なども使うことができるので頑張ればもう少し複雑な問題でも解くことができそうです。
*今回の問題では、入力の制約の最大値(10^5)を与えてみても大丈夫でしたが、問題によっては大きな入力だと実行制限時間に間に合わないかもしれません。

なお、今回は無理やりFLEXSCHEを使ってみましたが、競技プログラミングは普通のプログラミング言語で解いていただき、FLEXSCHEは計画を立てるのにご使用ください。

弊社ではFLEXSCHEを紹介・または簡単に体験いただける無料のセミナーを毎月開催しています。FLEXSCHEの正しい使い方を知りたい、という方のご参加をお待ちしています。