考えたこと

予測がスコアに全く影響しない状態になっている

優先度は後継タスクが多いやつ、割り当ては一番早く終わるやつ

2021/11/12

結果は変わらず

LOOP を増やしても結果がよくならなかった

スキルの予測の精度はランダムでは上がらないし、精度がちょっと上がっても結果に影響を与えない

mean 1826.971000

mean 1825.967000

mean 1813.458000

タスク選択を単に番号順+後継タスクが0のものは後回し

mean 1825.242000

タスク選択は後継タスク多いやつ順

2021/11/11

タスクの実行順序を色々かえてもだめだった

後継タスクが多いやつから順に実行しても、待ち時時間が発生してしまう

タスクの割り当て方法を修正する必要がある

→ 今は単に予測スキルを使ってコストが最も短くなる人に割り当てている

タスクの実行順序を変えた

タスクの優先順を考えてグラフにした

code:test-all

count 1000.000000

mean 1799.092000

std 210.211909

min 1076.000000

25% 1656.000000

50% 1811.000000

75% 1948.000000

max 2323.000000

悪くなった。改善してみる

改善するともっと悪くなった

2021/11/10

最初はスキルの予測精度が悪いので、とにかく簡単 or 後継タスクの多いもの

スキルの予測がそこそこできてきた時に難しいタスクをやる

後半に難しいタスクをすると、一人だけそのタスクを長々とやって、全体が遅れてしまう可能性がある

スキルをランダム生成するときは、完了タスクのレベルよりも大きくならないようにした

code:test-all

count 1000.000000

mean 1825.555000

std 200.534653

min 1118.000000

25% 1684.750000

50% 1834.000000

75% 1971.000000

max 2306.000000

スコアは上がっていない

タスク割り当てをいじった方が良さそう

タスクの割り当てが悪いと、スキルの予測の精度をあげても結がよくならなそう

めちゃくちゃ詰める場合の話

タスクの予約とかを考えると、この話が出てきそう。

自分がタスクをやると100かかるが、別のワーカーは10+10+10=30で終わるなら自分がやらなくて良い

2021/11/9

予測スキルを使って、タスクの予測完了日数を求める

次のタスクを決めておく

予測スキルが十分正しいとするなら

二分探索で終了時刻を決めておいて、各ワーカーが自分がやったら一番早く終わるタスク（か、ほどほど早いタスク）をどんどん割り当てていって、設定した時間以内に終わるか確かめる

スキルが(1, 10) のワーカーにレベル(10, 0)を割り当てるのはもったいない

9 日分、スキル 10 浮く

可能な限りスキルを全部使えた方が良い

コスト = スキルを使えなかった分、と考えられる

スキル(5, 8) のとき

タスク(6,1)、コスト1

タスク(0, 10), コスト2

なら、後者の方がやって欲しい気がする。

タスクを割り当てる際のパラメータは今のところ以下

レベル合計

後継タスクの数

ワーカーがそのタスクをやったときの予測完了日数

ワーカーがそのタスクをやったときの有効スキル合計

無駄を出さないようにするのを重視してテストを実行した

code:test-all

count 1000.000000

mean 1738.324000

std 212.090951

min 917.000000

25% 1606.000000

50% 1754.000000

75% 1886.250000

max 2247.000000

平均 100 日ぐらい悪くなった

それぞれで順位を出して、両方ほどほどよかったら選択をする、という戦略だとスコアが下がった

同じタイミングでワーカーの手が開くことはない

→ 手が空いたワーカーに順次タスクを割り当てていくことになる

予測完了日数の行列を作成する

予測スキル活用数の行列を作成する

タスクごとに優先度が着く

優先度が高いタスクをみる

予測完了日数と予測スキル活用数を使って、ワーカーにタスクを割り当てる

タスクはワーカーに n 個割り当てる

先行タスクがあって手をつけられないタスクも割り当てる

タスクをやるとき、そのタスクが完了するまでの日数を全ワーカー調べて、自分の順位が低いときはそのタスクを選ばない

2021/11/8

削減度

レベルの総和分時間がかかるところ、スキル量でかかる時間を減らせるため

予測完了日数を使って計算した場合は、予測削減度

誰がやるかにもよるけど

優秀なワーカーは 0.01 ~ 0.4 ぐらいの値を取っている

ざっと見ると、0.1 以下はかなり小さい、0.5~ が上限

削減度を元に、予測スキルをタスクのレベルに近づける

基本的には下限しか決まらない

レベルの低いタスクをやると削減度が高くなるが、スキルはレベルより高いかもしれない

レベルに近づけるとスキルが低くなりすぎる可能性がある

予測削減度 = r

$ (1 - r)^2

r が低いほど↑の式の値が大きくなる

r が 0.5 なやつはほとんど影響を与えないようにしたいので、2 乗して大小をより大きくしている。

ここ実はパラメーター化かも。

この式の値を元に、そのタスクにスキルをどれだけ近づければ良いかを考える

やってみたけどあまり変わらなかった。

ビジュアライザ見てみると、スキルの予測はほどほどにできている。

削減度が高いなら、スキルがレベルと遠いことを表す

2021/11/7

バグとり中

ルーレット選択するときにすべての値が 0 の配列が渡される

すべての値が 0 -> 差分がない -> 完了日数が 0 -> continue されるはず

差分や予測完了日数をまとめてアップデートするように変更中

想定完了日数が多いとき、予測スキルが高いものほど下げたくなる

ただし、レベルよりもスキルが高いものに関しては、当確率で下げる必要がある。

レベルよりもスキルが高いとコスト 0 になるので、区別ができない

例）

予測スキル(5, 10), レベル(5,5), 予測完了日数 1, 完了日数 2

このとき、実際のスキルは(4, 4) や (3, 10), (5, 8) が考えられる

予測スキルには 2 倍の差があるが、実際のスキルがどれになるかはわからない

レベルよりも高い予測スキルを持つ場合は、どれを変更するかは当確率になる。

スキルの予測を実装したけど精度低い

スキルが高くなった部分ほど diff が大きくなって、完了までの日数が長いタスクを割り当てられたときに、下げられやすい気がする。

手元では 2s かかるのに提出したら 0.3 ms しかかからなかった。

同じような形のタスクが割り振られやすくなるので、予測スキルの変化がわかりやすくなるかも

code: test-all

count 1000.000000

mean 1637.691000

std 250.954577

min 910.000000

25% 1467.250000

50% 1659.000000

75% 1826.250000

max 2271.000000

予測精度が悪すぎて、ランダムとほぼ変わらない結果になった。

一旦、予測スキルを update するだけのプログラムを投げたら AC した

タスク割り当ての実装が間違っている

理由はわからないが AC した

提出頻度制限があるので、試したいことがあったらさっさと投げないと困りそう

完了日数が 1 より大きい = レベルにスキルが足りていない

予測スキルを変化させたときに、予測完了日数と完了日数の差の合計がどうなるか見た

→ まったく小さくなっていっていない

上がったり下がったりしていて、意味がない感じがする

予測完了日数と完了日数の差によって、どのくらい予測スキルとタスクレベルが近いかわかる

タスクレベルが +2 したのにコストが +2 ではなかった場合、スキルがどこにあるか推測できる

まずランダムを試す、というのを考えていたはずなのに、スキルに関してはランダムを考えれていなかった

code:test-all

count 1000.000000

mean 1744.065000

std 219.346547

min 1015.000000

25% 1604.500000

50% 1758.000000

75% 1902.000000

max 2292.000000

ちょっとスコアが上がった

ランダムで探すとき、前回の予測スキルを初期値に設定するようにした

code: test-all

count 1000.000000

mean 1769.059000

std 219.243429

min 999.000000

25% 1618.750000

50% 1783.500000

75% 1936.000000

max 2300.000000

微妙。上がったようなそうでないような。

探索回数が十分に多いなら、あってもなくても良さそう

完了時間が短いタスクのレベルを、スキルを探索するときのスキルの各値の下限とする

code:test-all

count 1000.000000

mean 1776.954000

std 217.953035

min 989.000000

25% 1630.500000

50% 1789.000000

75% 1930.000000

max 2305.000000

かわんね〜〜〜

簡単なタスクほど先にやりたいが、依存関係が解消できないと待ち時間がたくさん発生してしまう

簡単なタスクを先にやりつつも依存関係が解消できていればとても良い。

code: test-all

count 1000.000000

mean 1821.269000

std 200.419901

min 1117.000000

25% 1682.750000

50% 1830.500000

75% 1968.500000

max 2315.000000

上がった

予測スキルを探索するとき、ある個別スキルをランダムに増減させて、結果がよくなるか調べる実装を加えた

code:test-all

count 1000.000000

mean 1835.163000

std 198.393892

min 1136.000000

25% 1692.750000

50% 1840.500000

75% 1985.250000

max 2323.000000

ほんのちょっと上がった

ここまでくるとGAでいいんじゃないか。

タスクが少ないうちは初期人口（予測スキル）をランダムに生成する

タスクが多くなると何度も探索されているので実際のスキルに近くなる

→ ランダムに生成する意味が薄くなる

2021/11/6

完了したタスクの分、得点が加算

すべてのタスクを完了すると、残りの日数分得点が増える

1000 タスク、20 人で分担 -> 50 / 1 （タスク/人）

すべてのタスクが 1 日で終わる -> 50 日

最大で 1000 + 2000 - 50 = 2950 点

50 個のケースがあるなら 147,500

100,000 点取ると、100,000 / 50 = 2000 点とっている事になる

1000 + 2000 - 1000 = 2000 なので、1000 日ですべてのタスクを終わらせると、AtCoder 上では 100,000 点取れる

code: 0000.txt

count 1000.000000

mean 1864.193000

std 16.281795

min 1815.000000

25% 1852.000000

50% 1864.000000

75% 1876.000000

max 1917.000000

ランダム解法なので点数に極端な差はない

1200 日ぐらいでタスクを終わらせている

ちなみに、テストケースが異なる場合

code: test-all

count 1000.000000

mean 1641.493000

std 272.388266

min 902.000000

25% 1458.750000

50% 1672.500000

75% 1849.000000

max 2273.000000

入力値によって点数の取りやすさが異なるので、異なるテストケース間で得点を比較する意味はない

同じテストケース集合を実行したときの結果の集合を比較するのは意味がありそう

ランダム解法で 1650 点ぐらい取れる

何を可視化すれば良いのか案が出たら。

スキルの予測ができたら次は適切に割り当てられるのかの話になる

今は割り当てを考えない

待ち時間が発生したら考える

レベルの低いタスクを優先したら待ち時間が発生してスコアが下がった

→ 依存関係が解消できなくて、手をつけられるタスクがなくなってしまった

ランダム割り当てなので、

依存関係の解消を優先すると、最初からレベル合計の高いタスクが割り当てられてしまい、時間がかかってしまった

→ 最初はスキルの予測のしようがないので、レベル合計の高いタスクは割り当てたくない

依存関係が最初から 0 のタスクは 60 程度しかない

レベルの高さか依存関係かをどちらか選ぶのではなくて、両方を考慮して優先度を決めれば良さそう

2021/11/5

タスクの優先度を考える

後継タスクが多い

タスクが簡単

→能力が明らかになったときに、適切なワーカーに難しいタスクを渡した方が良い

手法

タスクを与えて完了までの日数を得る

そのワーカーの予測スキルを元に完了までの日数を計算する

実際の日数と予測日数の差が小さくなるまで予測スキルを変化させる

実際の日数の方が小さい場合は、予測スキルが低すぎる（ズレが大きい）

与えられたタスクの難易度が高いものほど高い確率で、予測スキルを増やす

予測日数が小さくなるまで、予測スキルの増加を続ける

計算量

タスクが 1000

一人当たりに割り付けられるタスクを多めに考えると 100

レベルの数が 10

1000 * 100 * 10 = 10^6

予測スキルを 100 回まで更新（探索）できる

かなり少なく見積もっている

2021/11/4

ランダム解法を投げた

2021/11/5

ざっと確認した。そこまで細かい分析はしていない

0000.txt を対象にする

各タスクレベルを見る

50%ile の値

table: task_level

1 2 3 4 5 6 7 8 9 10

17 148 207 203 131 134 94 48 16 2

1~4 までで約 500 タスクある

std の割合を見る

小数点以下切り捨て

4, 5 が最も大きい山になっている

8~ はかなりレア

各スキルを見る

50%ile は 2-15 の範囲

数が少ないのでかなりばらつきがある

スキル合計値はかなりばらつきが大きい

2, 3 倍の差がある

待ち時間が発生しないのであれば、能力が高い人に簡単なタスクを割り当て続けるのはありかも

タスク完了までの時間を見る

スキル合計が 64 なら平均 35 日

スキル合計が 200 なら平均 10 日

当然、スキル合計が大きくても日数が多い場合もある

スキル合計 -> ランダムにタスクが割り振られたときの平均達成日数 が計算できそう

タスクをランダムには割り振らないので、役に立つかはわからない

見ただけ

スキルやレベルは思ったよりばらつきがある

ある閾値以上に注目して、スキルを予測したり割り当てるのはあり

スキルの方が全体的に高いので、低いレベルはそこまで影響が出ない

実装を変えるたびに見る

スキルとレベルはランダム

愚直にやると、スキルの値を全探索して、完了日数が最も近くなるやつを選ぶ

新しくタスクを完了したとき、予測スキルを変化させる必要がある

前回の予測スキルを、新しい情報を考慮して変化させれば良いと思っていたがそうではないかも

情報量が少ないと、大きく間違った予測をしてしまい、その後の変化で返せなくなるかも

予測スキル - レベル をする

予測スキルが小さいほど時間がかかると予想している

完了までの日数が想定よりも少ない

予測スキルが実際のスキルよりも低い

予測スキルで計算した完了までの日数が実際の完了までの時間に近づくように下げていく

差分が小さい個別スキルほど、高確率で上昇させる

完了までの日数が想定よりも多い

予測スキルが実際のスキルよりも高い

変化させるのは同じ。こちらは上げていく

タスクの個別レベルが高いほど、高確率で個別スキルを下げる

問題の分類

適切なワーカーにタスクを割り当てられるか

ワーカーの能力を当てられるか

ワーカーの能力が既知なら、コストが最小になるように貪欲したりビームサーチしたりしそう

どんどん情報が与えられていく中、どのようにスキルを推測するか？

今の最高得点が10万、ランダム解法で8万

貪欲に割り当てると待ち時間が発生しなかった

短い時間でタスクが終わる = そのタスクのレベルとワーカーのスキルが近い

近さをどう表すか？

簡単なスキルの決定方法

今までやったタスクの中で最もコストが小さくなった場合、そのタスクのレベルを自分のスキルにする

たまたまコストが小さくなるタスクが割り振られると、それ以降はスキルがほぼ既知として扱える

タスクを割り振るとき、スキルが既知だとして、コストが最小となる人に割り振る

これはだめで、タスク自体が簡単ならコストが小さくなる

→スキルの下限が決まる

2021/11/03

問題について

要求より技能レベルが高いと 1 になる

積なので 1 の場合は無視できる

要求が高くなると、-3 ~ 3 の一様乱数で日にちがずれる

乱数なのでならすと 0 になる

完了した時間が 6 日ずれる

1 日で終わるタスクは当日の夜に終わる -> 10/1 に初めて 10/1 に終わる

依存タスクがある

タスクと人は一対一

タスクを取り上げたりできない。完了を待つ

値

タスク数 2000

人 20

能力 10~20, 依存関係 1000~3000

能力も要求も標準正規分布に従う

依存関係があるタスクの番号の差は最大で100

依存関係はどのタスクも発生する可能性がある