第8回 Asprova プログラミングコンテスト参加記

f:id:eijirou_kyopro:20220318104338p:plain

第8回 Asprova プログラミングコンテストお疲れ様でした。

暫定テストでは得点率99.2536%で2位、システムテストでは得点率99.2106%で4位でした。

問題概要

円環状に繋がったコンベアの生産スケジュールを組む問題です。

何種類かの製品があり、作る製品を変える間は別の製品を作ることができません。また、同じ形状の製品は同時に一定数までしか作ることがきません。

スケジュールの長さと作業員の手間の両方を最小化します。2つの指標の優先度はテストケースごとに異なります。

円環状というのが特徴的で、周期をフックの数に合わせることで作業員の手間が減るようになっています。

方針

1色ずつ順番に処理しました。

周期性が生まれるように周回数を決めました。

条件を変えて貪欲法を何度か試しました。焼きなまし法もビームサーチも使っていません。

形状と色の順番

形状は同じ順番で何周も計画され、色は1周します。どちらもTSP（巡回セールスマン問題）を解くことで（ほぼ）最適な順番を得ることができます。

TSPは、現在いる頂点と訪問済みの頂点集合を考えることで $O(N^{2} 2^{N})$ で解くことができ、十分高速です。

周期性の揃え方

input0001 の color = 2 のケースを例に説明します。

形状の順番は 2,4,3,5,1,6 で、1周あたりの形状を変えるコストは39です。

1周あたり 250 - 39 = 211 個の製品を作って、形状6で終わっているようなスケジュールが理想的です。

N22	N42	N32	N52	N12	N62
88	49	39	91	19	48

K_2	K_4	K_3	K_5	K_1	K_6
76	53	47	78	23	48

数量をハンガーの数で割ることで、最低何周する必要があるかを求めることができます。

この例の場合だと、形状2から順に 2,1,1,2,1,1 周する必要があるため、最低でも形状2から5までは2周、形状1と形状6は1周する必要があります。（形状を 2,4,3,5,1,6,2,4,3,5 の順に変えるということです。）

N22 / 2	N42 / 2	N32 / 2	N52 / 2	N12 / 1	N62 / 1	sum
44	24.5	19.5	45.5	19	48	200.5

周期が 200.5 < 211 で、理想的なものよりも少しだけ短くなっています。

周期が長い場合は、周回数を増やすことで周期を短くすることができます。この例の場合、形状1や形状6も2周するようにすれば周期を短くできます。

周期がフックの数に近い場合は、最初と最後の個数を調整することで周期を微調整できます。

この例の場合では、最初に作る形状2の製品の個数を35個程度にすると上手くいきます。

	N22	N42	N32	N52	N12	N62	N22	sum
1周目	35	24	20	45	19	48	20	211
2周目	33	25	19	46	none	none	none	123

1周目と2周目で個数がほぼ揃っていることがわかると思います。

「最初と最後の個数を調整する」と述べましたが、前後の色の影響もあり、具体的にいくら増やす（減らす）と上手くいくのかはよくわからなかったため、いくつか試して得点が高いものを採用しました。

-1か-2か

ハンガーを回収するときは-1、ハンガーを吊るしたままにするときは-2を出力します。

作業員の手間も最小化する必要があるため、可能な限りハンガーを吊るしたままにしておくとよいです。

ところが、ハンガーを回収するべきか否かをその時点で判断するのは難しいです。

そこで、とりあえずハンガーを吊るしたままに設定しておき、ハンガーが足りなくなったら吊るしたままの空ハンガーを後からゲットするというようにしました。すなわち、必要に応じて後から-2を-1に書き換えました。

ひたすら試す

形状や色の順番を変えて何度も試すことで得点が上がりました。

逆順を試したり、最初のものを変えたりしました。

高速化

何度も試すには高速化が必要になります。

私の実装だと、シミュレータのコピーが重くなっており、シミュレータに含まれる解答部分を削除してからコピーすることで高速化できました。解答の長さは数千になるため、コピーに時間がかかっていたようです。

ハイブリッド

解の評価には、作業員の手間と計画の長さという2つの指標が用いられており、テストケースによって優先度が大きく異なります。

f:id:eijirou_kyopro:20220318104459p:plain

今までの方針だと、a（作業員の手間にかかるペナルティ）が非常に大きいレアケースに対応できなさそうだと考え、ハンガーの位置を固定した解法を追加しました。

f:id:eijirou_kyopro:20220318105915p:plain

早く切り上げる処理を適切に入れることで、ある程度は計画を短くできるようにしました。例えば上図の長方形で囲んだ部分では、黄色の正方形を連続で置くことができるにもかかわらず、早く切り上げて黄色の五角形を優先しています。

こちらの解法に約50ms、元の解法に残りの時間を費やして、得点が高いほうを採用しました。

実装について

シミュレータと制御側でクラスを分けました。

同じ製品が連続で並ぶため、まとめて処理することもできそうですが、うまく実装できませんでした。1つずつ製品を並べる形式になっています。

上位陣との比較

f:id:eijirou_kyopro:20220318104600p:plain

wleiteさんが作った統計データによると、私の解法は、aが中途半端で製品数が多いときに強く、aが極端な値で製品数が少ないときに弱かったらしいです。別の言い方をすると、得点を得にくいケースでは上位で、得点を得やすいケースでは比較的下位になっていました。ハイブリッドにしたつもりでしたが、あまり上手く動作しなかったようです。

私が調べた限りだと、上位にはハンガー固定方針と焼きなまし法を組み合わせている人が多かったように感じます。その方針だと、aが大きいときにかなり上手くいきそうな感じがします。

aの値や製品数などで場合分けをして、適切に焼きなまし法を用いると高得点が出そうです。