まとめ

pretest 100 ケース 98,027,620 (順位 : 27 位)

systemtest 1000 ケース 982,098,992 (順位：29 位)

99 M に乗る方法が全くわからね〜

1 日目

問題文を読む。シミュレーションを書かないと始まらないので書いた。将来的に焼きなましとかをするなら、2 点swap したときの差分計算を高速にしたいと思ったが、これが全くわからない。

初めは、11111...22...3333..... みたいな感じで置いてみたが、ものすごくスコアが低い。

2日目

仙台旅行にいっていたので、あまり進捗はなかったのだが、大阪から仙台にいくまでの期間で色々試していた。

よくわからなかったので、適当に shuffle して投げてみたところ、 89826736 がでた。

次に、123...m123...m... のような感じで周期的においてみると、 93527792 が出た。周期的にやるのがいいと思い込み、 123...m の部分を焼きなましをして、最短時間となる並び方にすると 96489831 がでた。このとき、順位が 8 位とかでこの方針がいいと思い込んでいた。。( がここからが失敗。。。。)

仙台のいろいろな地酒を飲んで、疲れたので特に改善はなし。

3 日目

仙台の水族館に行っていた。

とてもかわいいぬいぐるみをゲット。

f:id:jupiro:20210815132010j:plain

牛タンも食べて、かなり仙台に満足したのもあり？帰りの電車はぐっすり寝てしまったので、改善はなし。

4 日目

全くと言うレベルでアイデアがでず、特に改善はなし。

5 日目

5 日目にして、問題文の重要な情報に気づく。

正の実数 $w _ i$ を定める。 $w _ i$ は車種 $i$ の生産比率と呼ばれる。 $\sum _ {j} t _ {ij}$ が大きいiほど $w _ {i}$ は小さくなる傾向がある。

数が多いやつは作業時間が短く、数が少ないやつは作業時間が多い傾向にあるらしい。ここで、周期を 123..m に加えて、数が多いのをいくつか追加していれてみた。→ 96893776

数が多いのと少ないのとでペアを組んでそれを周期的にしてみると言うのもやってみた。→ 96945882

もしかして、周期的にやるのがよくないのではと原点回帰する。単純に貪欲していきたいが、シミュレーションに時間がそこそこかかるので、直前と今入れるやつを 2 つのときのみの停止時間が最小となるやつをとってみる -> だいたい 95 - 96M ぐらい

となり、こっちのほうで伸ばす方針にした。

6 日目

シミュレーションの際、毎回全てのレーンをみていたのだが、車の数が少ない場合実際に作業しているレーンは少ないことに今頃気づく。( ほんとに黄色コーダか？) 数が少ない場合のシミュレーション関数を作り、 $m = 20$ なら前 6 つと、 $m = 40$ なら前 3 つとのシミュレーションをした停止時間が最小となる貪欲をする -> 97380333