レート最大化アルゴリズムについての議論

[monkukui]

No description provided.

[monkukui]

olphe

これについてもうちょっと考えてたんですが、かなりやばくて、参加不参加の変化によって全員のレートに影響を及ぼすので、全員のレートの情報を持っておく必要があります。これでDPをやろうとすると結局2^(コンテスト回数)見る必要があって現実的には求められません。
なのでどこかで嘘の計算量削減をする必要
があって、今2個候補を思いついていて、
①自分の参加状況における他の参加者への影響を無視する。(最上位とかだとかなり影響大きいけど……)これによって、自分のパフォーマンス列だけを基に最適解を求められる。
②最適解を求めるのをあきらめて、ビームサーチ的なことをする。他者へのレートの変動を持っておける代わりに、厳密でなくなりそう。(さらに実装もやばそう)

RatedUnratedについて思ったことなんですが、Unratedとして参加したコンテストを(最適化したい場合に)Ratedのものとして扱うのは適切かどうかという疑問があって、(本来)Unratedなので参加の仕方が違う可能性があることを考えると扱うべきではないという立場と、最適化が目的であるので、最適なものに含まれているなら扱っても問題ないだろうという立場があると思います。(どちらかというと僕は後者の立場です)

[monkukui]

olphe

書いてなかったけど僕も①がいいと思っているので①の方針で実装しようと思います。
あと、UnratedのコンテストのPerformanceはhttps://atcoder.jp/contests/arc109/results/json
こういうのを見て、自分より順位が下の人の中で一番順位が高いrated参加者のperformanceで代用できるかと思います。

[monkukui]

dp[コンテスト][参加回数][rate] := true/false
の方針で行くと、

内部レートが整数ではないことを考慮すると、そもそもこの DP ができない。
適当に整数でやるにしても、テーブルのサイズが
200 * 200 * 3000 = 1.2 * 10^8 とかでかなり重い

[olphe]

rated上限ぎりぎりにしてからジャンプする場合があって、そのぎりぎりとなるようなコンテストの選び方もわからない。

[monkukui]

そうですよね...

[monkukui]

適当な案を二つ

• そもそも、レート最大化のサービスをやめる。ユーザーは、自由に参加するコンテストを選んで、レート変化を楽しむ
• 参加時に unrated だったコンテストは、完全に除外する（これだと意味ないか）

[olphe]

除外するのも意味がないというほどではないと思っていて、ボーダー以外の人々のレートは概ね正確に出る(と思う)
除外した場合はレートを下げる意味がないので、dp[見てるコンテスト][参加回数]=最大値　のDPをすると最大値が求められる。(これは嘘で、本来ratedであったコンテストがunratedになる関係で下げる意味がある場合がある……)

[monkukui]

(これは嘘で、本来ratedであったコンテストがunratedになる関係で下げる意味がある場合がある……)

これなんですよね

[olphe]

• そもそも、レート最大化のサービスをやめる。ユーザーは、自由に参加するコンテストを選んで、レート変化を楽しむ

機能が"最大化"ではなく、"大きくする"程度である場合は実装できるけど、それは存在する意味ある？(需要が全くないとは思わないけど微妙な気もする？(需要がある時点で無意味ではなさそう？))

[monkukui]

@olphe

機能が"最大化"ではなく、"大きくする"程度である場合は実装できるけど、それは存在する意味ある？(需要が全くないとは思わないけど微妙な気もする？(需要がある時点で無意味ではなさそう？))

• レートが上昇するなら、出場する

とかなら、簡単そうですね。
意味はあると思います。

まず、最大化がまともな計算量ではできないのかを確認したいです。

僕は、ちょっと考えたんですが、わからなかったです。
（とりあえず、最大化が無理だと仮定するなら、適当な貪欲法を走らせてレートを大きくする、というのは良いと思います。サイトに、どういうルールで選択されるのかも記載できたらいいですね）