ac-predictor.user.js Feature/next-ac

#17 を実装しました。元のIssueでは「現在開いているページの問題を正解した場合の順位」でしたが、順位表ページなどでも見れるようになりたいので、「指定した問題を正解した場合の順位」としました。

実装方針

実際に該当する問題を解いた後の(パフォーマンスを含めた)順位表を正確に取得するのは現状無理なので、現在の順位表でどこに挿入されるか(何位に相当するか)を取得することで近似しています。

変更箇所

新たに必要となる情報は以下の通りです。

全員の現在のスコア(result.TotalScore)、およびペナルティを含めた経過時間(result.Elapsed)
各問題の名前(task.assignment)、配点(task.point) (task.taskScreenNameはユーザーのTaskResultsとの兼ね合いで必要です)
ユーザーのペナルティ
ユーザーがAC済の問題

これらの情報を追加するために、Resultクラスを書き換え、Taskクラスを追加しています。

その他

$("#predictor-nextac-button")を押した際にそこそこ重くなります。今のところ考えている原因は2つあります。

fetchContestPenaltyが重い atcoder-userscript-libsの#2修正分がリリースされたら、コメントアウトされたcontestInformation.Penaltyに切り替えることでリクエストが1つ減ります。
contest.standings.StandingsData.filterが重い現在ユーザーがAC済の問題を取得するためにstandingsでループを回しています。まともに計測していないのでこれが本当に重いかはわかりません。ResultでTaskResultsを持てばいい気がしますが、それはそれで前処理が重くなる気がします。

あと、ページにアクセスするたび(initPredictor()が呼ばれるたび)に、配点の取得のために(通常コンなら)6つのリクエストが新たに飛ぶので、サーバーに負担をかけることになると思います。途中で配点が変わったり問題が消えたりすることは(某forcesではないので)ありえないと仮定すると、一度取得したらローカルで持つようにしてもいいかもしれません。

Jul 05 '19 14:07 miozune

Task関連の話

変更部分が結構大きくなりそうなのでとりあえず後回しですかね… 配点の取得の失敗についてですが、今後発生した際にPredictor全体が止まってしまうと結構困るので、失敗しても他の部分は動くようにした方がいいと思います。(順位表の取得などと比べるとoptionalな機能なので) ただ、配点の取得に失敗したことをユーザーに通知せずに握り潰すのは不親切かなーという気もしていて、UIも含めてどうすればいいんでしょうね…

ペナルティについて

すみません、もう少し詳しくお願いします…(TotalResultから取得したElapsedにはペナルティ分が含まれているということですか？)

Results関連について

確かに、OnDemandResultsおよびFixedResultsのprototypeで実装すると綺麗になりますね。書いてみます。また、その他の部分でcontest.standings.StandingsDataでループを回すのは遅くないと述べられているのですが、二分探索は本当に必要でしょうか？(早くなるのは事実ですが)

atcoder-userscript-libs

commitしました。

standingsでループ

把握しました。

results.getUserResult

commitしました。

ACした問題をドロップダウンに表示させない

僕も最初はこれを考えていたのですが、「全完した人のドロップダウンが無くなるのは不親切では？」と思ってやめました。が、今考えると全完した人はそもそもこの機能を使わないので問題ありませんね。実装してみます。

Jul 06 '19 06:07 miozune

二分探索は本当に必要でしょうか

そうですね、二分探索は大した改善にはなりません。この関数を大量に呼ぶ場面もないため普通に要らないと思います(できるのでやりたがってしまいがちです。) 追記ですが、ArrayからDictionaryにしたもののvalueを取得するのはあまり好ましくないと思います。ゴリ押し感が否めない上、オブジェクトの挿入順が維持されるのは規格ではないはずです。 Standingsのように整列していることが保証されているものを舐める、または渡されるArrayが整列していることを前提とする(またはソートをする?)ことで十分だと思います。それと、RatedRankを自前でインクリメントせずともresult.RatedRankを使えば良いと思ったのですが、不都合が発生しますか?

すみません、もう少し詳しくお願いします

{
    "TaskResults": {
        "abc132_a": {
            "Count": 2,
            "Failure": 2,
            "Penalty": 1
        },
        "abc132_b": {
            "Count": 2,
            "Failure": 2,
            "Penalty": 0
        },
        "abc132_c": {
            "Count": 3,
            "Failure": 3,
            "Penalty": 0
        }
    },
    "TotalResult": {
        "Count": 7,
        "Accepted": 1,
        "Penalty": 1
    }
}

この結果について、例えばb問題がACされた場合はペナルティが2加算され、3となります。僕が読む限りでは、それが実装では反映されていないように見えました。

Jul 06 '19 07:07 key-moon

getInsertedRatedRankについて

https://github.com/key-moon/ac-predictor.user.js/blob/617f7dd2d41e8f29e4e0806155a15f9b58822fab/src/libs/contest/contest.js#L23-L101 や https://github.com/key-moon/ac-predictor.user.js/blob/617f7dd2d41e8f29e4e0806155a15f9b58822fab/src/elements/predictor/script.js#L382-L437 で行われているいろんな処理を再利用したいという気持ちでresultsを使っていました。ここら辺は全く理解していないのですが、Standingsをそのままなめたら不都合が生じるのですよね？ここで二つ方針が生えて、

上に挙げた二つの処理を関数で括って使用する
ObjectではなくMapを使う(Mapは挿入順が保証されています。→参考)

個人的には後者の方が変更量が少ないのでいいと思うのですが、どうでしょうか？

result.RatedRank、完全に忘れていました。そちらを使うようにします。

ペナルティ

なるほど、理解しました。今からACする問題のFailureをTotalResult.Penaltyと足し合わせればいいのですね。

Jul 06 '19 07:07 miozune

result.RatedRankについてですが、FixedResultsには-1が渡されているのでダメでした。

https://github.com/key-moon/ac-predictor.user.js/blob/617f7dd2d41e8f29e4e0806155a15f9b58822fab/src/elements/predictor/script.js#L424

OnDemandResultsは大丈夫なようなので、こちらはresult.RatedRankを使うようにします。

Jul 06 '19 07:07 miozune

それと、$("#predictor-nextac-button")を押すと重くなる現象についてですが、少なくとも自分の環境では解消しました。おそらくfetchContestPenaltyのリクエスト分だったのでしょう。

Jul 06 '19 07:07 miozune

(Closedはミスクリックです、ごめんなさい。)

Standingsを舐めた後にresults.getUserResult(userScreenName)をして該当ユーザーのResultを取得すれば良いかなと思っていましたが、上述のようにFixedResultでRatedRankが持てていない以上Mapでやるのが良いと思いました。

Jul 06 '19 08:07 key-moon

https://github.com/key-moon/ac-predictor.user.js/blob/617f7dd2d41e8f29e4e0806155a15f9b58822fab/src/elements/predictor/script.js#L104 はresults.getUserResult(userScreenName)にしても大丈夫ですか？

Jul 06 '19 08:07 miozune

Failureって結果に関わらず提出しただけで値が増えるんですね、見たところCountと同じようですが… なので、コンテストの途中でリジャッジが行われた場合、ペナルティ数を多く見積もってしまい、予測に誤差が出ます。例：ABC132で1位のアカウントは、abc132_dのFailureは4ですが、Penaltyは0です。これは、該当の問題を実際にACすることで誤差はTotalResultに吸収され、無くなります。

Jul 06 '19 09:07 miozune

流石にリジャッジの部分までは考慮しなくても良いと思います。Failureはざっと見たところ、Count-CEになりそうですね。例えACした後でも、提出をすればFailureやCountは増えるようです。(ショートコーダーの提出履歴を参照しました。) ただ、今回のそれについてはその対処で十分だと思います。ありがとうございます。

Jul 07 '19 05:07 key-moon

atcoder-userscript-libs/src/libs/contestInformation.jsでgetTasksを実装したら実質staticになってしまいました。data.js内で実装する形の方がよいと思うのですが、どうでしょうか？ https://gist.github.com/miozune/ac71a8007dfbaaf80fe36fddf16e91b7#file-contestinformation-js-L20

Jul 11 '19 12:07 miozune

トップページへのアクセスはfetchContestInformationでも行っているので、パース処理をそっちに持ってくることはできませんか…?

Jul 13 '19 03:07 key-moon

最初のreviewで遅延評価的にやるとよさそうとのことだったので、fetchContestInformationに入れるのはあまり良くないと考えました。例えば、Unratedだったりコンテストが始まっていないならPredictorを動かさないので、配点の取得は不要です。また、配点の取得にはstandings/json→(fetchContestInformation内で行わない場合)トップページ→(トップに配点が載っていない場合)各問題ページと多数のリクエストを投げることになるので、配点が不要な場合にgetTasksを実行しないことによるパフォーマンスの改善幅も大きいと思われます。

Jul 13 '19 15:07 miozune

fetchContestInformationでトップページのパースのみをした後、getTasks呼び出し時に取得に失敗していた場合は各問題ページへリクエストを飛ばすという挙動を想定していました、それならば特に問題はないと思います…?

Jul 14 '19 05:07 key-moon

https://github.com/key-moon/ac-predictor.user.js/pull/40#issuecomment-511082827 のコメントを「getTasksの処理を全てfetchContestInformationに移す」という意味だと勘違いしていました。トップページをキャッシュしておくことでリクエストを減らすということだったんですね。それなら良さそうです。

また、提案していたdata.jsへの切り出しですが、インターフェース的にContestInformationに含めた方がよさそうだと感じたので、このままでいきます。

Jul 26 '19 14:07 miozune

libsの方にプルリクを投げたので、そちらが解消次第こちらの処理に反映させます。

Jul 27 '19 05:07 miozune

ac-predictor.user.js ac-predictor.user.js copied to clipboard

Feature/next-ac

実装方針

変更箇所

その他

ac-predictor.user.js
ac-predictor.user.js copied to clipboard