2017-10-27

■ [MM] Marathon Match 95 CirclesMix 16:10 はてなブックマーク - Marathon Match 95 CirclesMix - TopCoderの学習のお時間

https://community.topcoder.com/longcontest/?module=ViewStandings&rd=16959

1日目（木曜）


問題を読んだ

2日目（金曜）


テスターをカスタマイズ（いつもの）

  • マルチスレッドでのバッチテスト
  • 結果の出力を良い感じに
  • 問題パラメタを自分で指定できるようにする

3日目（土曜）


テスト画像をwikimediaからクロール

（イラストとか本のページとかの画像は弾くのだけど、基準に主観が入るので迷うのが多かった）

1000枚取ってきたけどそんなに要らなかったかな…

greedyに円を一つずつ置いていくのを実装

  • ランダムな位置・半径で円をたくさん作る
    • すでに生成したものと近すぎる円は生成されないようにする
    • 半径は徐々に小さくする
  • それぞれの円に対して、最適な色にしたときにペナルティがどれだけ減るかを評価
  • ペナルティ減少が一番大きい円を選ぶ
    • 選ばれたやつと重なるもの以外の円は保持しておいて再利用する

また、選んだ円に対して、位置と半径を動かす山登りを実装

4日目（日曜）


高速化色々、SSEも使う

円の最適な色を決めるために、円の内部のピクセルに対して中央値を取る処理が重いので、かわりに円の中心にある7*7の正方形範囲の中央値を使う、という大胆な近似を取り入れたり

最終的に、greedyフェーズでは各ターンで 10000/sqrt(N) 個の円を生成し、選ばれた円に 10000/sqrt(N) イテレーションの山登りを行った。所要時間は6,7秒くらい？

5日目（月曜）


まだまだ高速化

円を置いてしまった後に、時間いっぱい使って繰り返し山登りで改善するのを実装（高速化を頑張っていたのは、これをやる時間を作るため）

山登り対象になる円をランダムに選ぶと、評価のためにその円の上に重なっている円をすべて再描画しないといけなくなって受け入れられないほど遅そうで、そうならないよう1つめの円から順番にひとつずつ山登りした。

各ピクセルごとに、未来側に円が何枚重なっているかと色の和を覚えておけば、再描画無しで評価できる。

  • まずN枚目〜2枚目までの情報を計算して、それを使って1枚目の円を山登りする
  • 未来側の情報から2枚目の円の寄与分を取り除いて、2枚目の円を山登りする
  • 以下同様

この問題は、とにかくいかに逐次改善可能な形に持って行くかが勝負だと思ったので、ここが一番の重要ポイントだった

6日目（火曜）


調整色々

前日実装したものが山登りになっていなかった（良い解になっても状態を更新しておらず、初期状態の近傍しか調べてなかった）という致命的なバグを修正

7日目（水曜）


パラメタ調整やる、が、ほとんど変わらず

AWSで36coreマシン借りて35スレッドでテストを実行したら、めちゃくちゃ遅くなってまともにテストできなかった。16スレッドに減らすと普通だったので、コア数もったいないがそれで。

原因は追ってないけど、テスターで画像を読んでるからだろうか？

やらなかったこと


  • はじめは画像を縮小して処理することで高速化
    • やったけど良くならなかった
  • 画像から円をパターン検出
    • seed=1を見るとそういうことを考えてしまいたくなるが、実装も実行もコスト高過ぎそうでやめた

結果


1位とだいぶ差があった。

最終日にしか提出しなかったのは、戦略のつもりではなくて、単に何度も提出するのがめんどいからです

2017-07-02

■ [TCO][MM] TCO17 Marathon Round2 20:55 はてなブックマーク - TCO17 Marathon Round2 - TopCoderの学習のお時間

https://community.topcoder.com/longcontest/?&sc=5&sd=desc&module=ViewStandings&rd=16928

準備フェーズ


とりあえず、感覚をつかむために次の2つの自明解を作った。

  • 毎ターン一番近い敵に攻撃
  • 990人まで貯まったら一番近い敵に攻撃

これだけでもそこそこ勝てている。前者が強い場合と後者が強い場合がだいぶはっきり分かれていて、勝ちやすいケースは前者が強くて、最終的に負けてしまうケースでは後者の方が強い。

これらをうまく組み合わせていく感じかなー、と考える。

スコアが順位ベースで決まるので、何もしない解に負けてしまうと大ダメージだからそれだけは無いようにしないといけない。

敵の方がPowerが高いことから、基本的には不利なんだけど、この不利を緩和したい。端数がたくさん切り捨てられるような攻撃をするといい、とかそういうのがありそう

…と考えていたら、6人以下で攻撃すると1:1でロスなし対消滅できて最もおトクであることに気づいた。速攻で連打するとそこそこ勝てるのは最初実装したやつで分かっているので、簡単に勝てるケースはこれをどこまで最適化できるかのゲームになるんだと理解する。

…で、そこではそんなに差がつかなさそうだからやっぱり難しいケースをどう賢くするかだなあ、という雰囲気になる。

モンテカルロシミュレーションやったりするのかなあと思いつつ、何やるにしても敵のパラメータ（power・attackT・locality）やTroopの行き先推定は必要なのでそいつらを実装していく。

実装フェーズ


そして実装していたら1週間経ってしまったので絶望する https://twitter.com/tomerun/status/864889052826288128

ついで、速攻ケースのシミュレーション+倒すbaseの順番での山登りを書き上げて、ある程度の高速化・パラメタ調整をやる。

この時点でまだ本丸（勝ちにくいケース）に手がついていないのに、もう2回目の週末が終わっていて絶望する https://twitter.com/tomerun/status/866298649680027648

とにかく、速攻で勝てないケースの戦略を作っていく。

とりあえず、全滅させられてしまう直前の逃避戦略を実装する。これはまあやるだけ

最序盤ですぐ倒せるところだけは速攻で倒しておくとして、基本は980まで貯めてから攻撃する。攻撃先をどこにするのかが考えるところ。

単純に一番近いところを攻撃するのは、すでに倒せるのが確定しているところに集まりすぎで損、というのはこれまでの結果から分かっている。

すでに倒せることが確定したbaseへは攻撃せず、他を狙うようにするとそれなりに良くなった。

あと、980貯まっていても、敵の攻撃が向かってきていて、攻撃で人数が半分になった状態では全滅させられてしまう場合は、攻撃せず待つようにしたり。

ここまででもう終了前日になってしまったので、全然細かい調整できてないんだけど観念して提出したら93万点とか出てびっくりした。

最後に、他の敵から攻撃されづらい位置にあるbaseを優先的に攻撃する、というのを入れようとしてみるが、良くならなくて終了

ビジュアライザ

f:id:tomerun:20170702204626p:image

カスタマイズした点は以下の通り。

  • 早送り・巻き戻し可能に
  • growRateに応じてbaseの形を変える
  • baseのindexも表示できるように（デバッグ用、普段はoff）
  • playerごとの合計人数を表示

そのほか


  • 今回は実装が難しそうで、そこまで高速化勝負にはならなさそうだったのでJavaを使った。結果的に、やっぱり実装がボトルネックだったのでこれは正解だった
  • 仲間同士で人数を1箇所に集中させて成長速度を増やすのはちょっとやってみようとしたが、あまり効果が感じられなくてやめた
  • 敵のlocalityも推定した（離散化してベイズ推定）けど結局使わなかった

結果

2017-06-17

■ [CodeChef] June Challenge 2017 20:49 はてなブックマーク - June Challenge 2017 - TopCoderの学習のお時間


https://www.codechef.com/JUNE17/

A Good Set (GOODSET)


500,499,498,... を出力する

https://www.codechef.com/viewsolution/14009670

Xenny and Coin Rankings (XENRANK)


やる

https://www.codechef.com/viewsolution/14009805

Chef and the Feast (NEO01)


大きい値のものから順に、まとめた方が得する限りまとめる。それ以外は1つずつ使う

https://www.codechef.com/viewsolution/14213083

Pairwise union of sets (UNIONSET)


K/2より大きい集合はBitSetで、小さい集合は配列で持つ

len1 + len2 + .. + lenN ≤ 10000 の制約があるのでこれで速くなる

https://www.codechef.com/viewsolution/14013196

Triplets (SUMQ)


ソートしてしゃくとりっぽく

https://www.codechef.com/viewsolution/14012356

Chef and Prime Queries (PRMQ)


永続segtreeで殴った

https://www.codechef.com/viewsolution/14213423

Cloning (CLONEME)


まともにやったら判定できる気がしないのでハッシュ的な方法を使う。

累積和・累積二乗和、kビット目だけの累積和・いろんな素数でmodの累積和 を持っておく。

二つの範囲で、すべての値が一致していたら完全一致と判定する。

そうでない場合、食い違いが1個だと仮定すると、累積和と累積二乗和の差から、ひとつめの範囲にのみ含まれる値 x とふたつめの範囲にのみ含まれる値 y がわかるので、これが他の累積和たちと矛盾しないかを確認する。

矛盾しない場合、両方の範囲の中にxとyの間の値が存在しないことが必要なので、それを永続segtreeを使って確認する。

https://www.codechef.com/viewsolution/14212683

Euler Sum (ES)


eを有理数で近似する。

A * e = B + ε (0 <= ε << 1) のとき、e = B / A と思うと1〜Aまでの floor(i * e) の和は、算数をするとO(1)で求まる。

AとしてN以下でできるだけ大きいものを取る。i > A については、 i = A + j と分解すると、N -A についての問題に帰着されるので再帰的に解く。

そのようなAはどうやって見つけるかというと、まず100くらいまで探索して、整数よりちょっと大きくなる係数Pと、整数よりちょっと小さくなる係数Sを（そこまでの範囲で）決める。

  • P * e = Q + ε (0 <= ε << 1)
  • S * e = T - δ (0 <= δ << 1)

このとき、 (P + S) * e = Q + T + (ε - δ) で、整数とのズレの部分 ε - δ は絶対値が ε, δ どちらよりも小さくなるので、ε - δの符号に応じてPとSのどちらかをP+Sに更新する。

これを繰り返せば、端数部分をどんどん小さくできる。

通してる人がみんなPythonだったのでRubyで書いてみたら、10^4000はTLEになってしまった。定数倍の範囲だとは思うのだけど…。

https://www.codechef.com/viewsolution/14231349

Persistent oak (OAK)


13点分は、永続化の実装の練習なので実装をする。

https://www.codechef.com/viewsolution/14218335

Saboteur (SBTR;タイブレーク)


残す頂点の集合を決める。

始点の頂点を1つ決めて、連結している頂点の中からコストが大きなものを使っていく、というgreedyを始点を変えつつ時間いっぱい試す

https://www.codechef.com/viewsolution/14223678

89.8点

結果


  • 852.817pts/1000pts
  • 43位/9386人
  • レーティング 2448->2422

ESの満点は取れないといけなかった感

2017-05-11

■ [TCO][MM] TCO17 Marathon Round1 01:11 はてなブックマーク - TCO17 Marathon Round1 - TopCoderの学習のお時間

https://community.topcoder.com/longcontest/?&sc=5&sd=desc&module=ViewStandings&rd=16903

やったこと


3段階で焼きなましをした。

  1. 35*35のグリッド上で、ランダムな頂点をランダムな位置に動かす遷移。評価値は、各辺について目的の長さと実際の長さの差の絶対値
    • 点の位置の重複は許す
    • 終わったら、各頂点をグリッド内の20*20のどこかにばらまいて700*700にする
  2. ランダムな頂点をランダムな近傍に動かす遷移。現在の辺の比の最大/最小の少し内側を目標にして、そこから外れた辺にペナルティがつく評価値
    • ペナルティは、(外れ量+0.5)^8 とか外れ具合に応じて大きく傾斜をつける
    • 頂点の移動距離は時間に伴って徐々に小さくしていく
  3. 比が最大/最小の辺に属した頂点をランダムな近傍に動かす遷移。真のスコアが評価値
    • 頂点の移動距離は時間に伴って徐々に小さくしていく
    • どの辺の比が最大/最小かを管理するのに、辺を比の値でバケットに入れて扱った
      • 各辺が自分のバケット内で何番目かを覚えておくと更新がO(1)でできる

最後の仕上げとして山登りをした。遷移は、比が最大/最小の辺に属した頂点を微少に動かして、他の辺が最大/最小を超えたら再帰的にその辺の頂点を動かす、というのを一定深さまでやる。

一応無意味ではないかな…くらいの効果はあった（結果のBestsが多かったのはこれのおかげだと思っている）

焼きなましの3フェーズの時間配分は 0.39:0.16:0.45 だった。これと別に最後の山登りに50ms使う。

焼きなましのイテレーション回数は合計6000万回くらい。SSEも使った（高速化の恩恵は1割程度）

時系列で


とりあえず真っ先に思いつくのは比が最大/最小の辺をいじることだけど、最大/最小だけ見てたら評価がハードすぎて一瞬で局所最適にハマりそう。もっとソフトな感じに評価したい。

一瞬バネ物理シミュレーションが浮かんだのだけど、その手の問題は以前ぼろ負けした（TCO13R3）のでひとまず考えないことにする。

というわけでまず焼きなましPhase2だけを作った。これが初日の48万点。

で、いろいろなケースの結果を出力して眺めていたら、長い辺がボトルネックになりがちなことが分かる。

長い辺は後から微調整が効きづらいので、最初の方でだいたい良い感じにしておかないといけない、と考える。

そこで焼きなましPhase1を作った。比で評価すると短い辺の重みが強くなってしまうので、差で評価。これで70万点超え。

ちょこちょこ調整した結果が3submit目の76万点。

ここで満を持してPhase3を追加すると4submit目の78.5万点。

（https://twitter.com/tomerun/status/855468636860891136 ここで言っていた「伸びしろ」はこれのこと）

このあとはほとんど焼きなましの調整と高速化だけだったと言ってよい。

最終日の1日前の段階でアルゴリズム的な改善は打ち止めにして、ここで有給休暇を取って細かい高速化をまとめてやり、最終日に会社行っている間にクラウド使ってパラメタ調整、というのが最近の試合運びのトレンドになっている。

EC2のc4.8xlargeを24時間ほど動かして$17くらい使った。35スレッドだと1000ケースのテストが3分で終わるので良い。

もうちょっと探っておくべきだったかなーというところは、

  • 多スタート
    • 難しいケースでスコアが0.1くらいぶれることがあるので、その安定性のため
  • 辺の目標長を最初から短めに設定しておく
    • ちょっとやってみたら良くならなかったので捨てたのだけど、実際最終状態が短い方に寄るケースが多いし、Psyhoさんはこれ入れるとめっちゃ伸びる（余裕で1位超えるくらい）らしいし、もっと時間をかけて見ておくべきだったかも
  • 頂点の移動先はランダムじゃなくて辺の向きを考えて選ぶ
    • 1位2位はそれをやっているみたいなので

結果

2017-01-22

■ [CodeChef]January Challenge 2017 18:13 はてなブックマーク - January Challenge 2017 - TopCoderの学習のお時間


https://www.codechef.com/JAN17

Cats and Dogs(CATSDOGS)


やる

https://www.codechef.com/viewsolution/12432868

Reservior(RESERVOI)


やるだけだけど問題文で網羅されていない仕様があって1WAした

https://www.codechef.com/viewsolution/12534258

Capital Movement(CAPIMOVE)


首都の隣かどうかで場合分け

https://www.codechef.com/viewsolution/12452430

Tourists in Mancunia(TOURISTS)


DFSして閉路を作る→グラフの残っている部分について閉路を作って最初の閉路に挿入する　を繰り返す

https://www.codechef.com/viewsolution/12456303

Digits Cannot Separate(DIGITSEP)


普通に桁DPするだけ、にしては正解者数少ない

https://www.codechef.com/viewsolution/12457791

Chef and Circle(CHEFCIRC)


N点中3点を通る円を全列挙したい。

まず2点A,Bを決める。残り1点Cを決めたときに外接円の中心がABの垂直二等分線上のどこに来るかが分かる。

この垂直二等分線上で外接円の中心となる点の位置をソートしてスイープすると、A,Bを通って点がK個以上含まれるような円の中心となる範囲が分かる

これがO(N^3 logN)だけど、遅くてダメだった。

制限時間が来たらその時点での最善の解を出力するようにしたら通ってしまった

https://www.codechef.com/viewsolution/12562803

想定解は、半径Rについての二分探索。

円が通る点Aをまず1つ決めて、Aを中心とする半径Rの円周上を円の中心の候補として、ほかの各点について円に含まれるような円の中心の存在範囲を求めて偏角ソートしてスイープ

Fantastic Four(FOURSQ)


前半パートの積を求めるところはごく普通のsegtree（ただしオーバーフローに気をつける必要あり）。

後半パートの、4つの平方数に分解するところがわからず、定数倍高速化を頑張って通してしまった

https://www.codechef.com/viewsolution/12491784

想定解は、積を求めてしまってから平方数に分解するのではなくて、各要素を平方数に分解してから掛けていく方法だった

https://discuss.codechef.com/questions/90269/foursq-editorial

参照 : オイラーの四平方恒等式

Sereja and BOX(SEABOX)


最小化は木DP、最大化はGreedy

スコアは必ず 7*N+1 の形になるので、これを利用して状態を1/7に圧縮すると考えやすい。

一見変な問題かと思いきや普通だった。の割に正解者数少ない

https://www.codechef.com/viewsolution/12535146

Coprime 6-tuples(TUPLES)


包除原理やって部分点だけ

https://www.codechef.com/viewsolution/12563810

想定解はFFTを巧妙に使う方法 https://discuss.codechef.com/questions/90271/tuples-editorial

Sereja and Circles(SEACIR:タイブレーク)


候補の半径をある程度保守的に選んで、互いの距離が遠くなるように焼きなましで候補円の位置を調整

入力の円それぞれについて、半径が自分以上の候補円のうち最も半径が小さいものを選んでそこに置く

https://www.codechef.com/viewsolution/12587441

75.063点

type=2の結果が不安定すぎて まだ改善の余地はあった

結果


  • 922.063pts/1000pts
  • 17位/6866人

2016-12-18

■ [CodeChef]December Challenge 2016 13:40 はてなブックマーク - December Challenge 2016 - TopCoderの学習のお時間


https://www.codechef.com/DEC16

週末1つが他の用事で埋まっていたのでつらかった

Train Partner(ANKTRAIN)


問題文が難しいので適当に推測

https://www.codechef.com/viewsolution/12173217

Kirito in labyrinth(KIRLAB)


dp[i][j] := i個目の部屋まで来たとき、直近でj番目の素数を持つシーケンスの最大長さ

でDPする（実際にはiは明示的に持たず、配列を使い回す）。

素数の個数は10^6個くらいあるのでDP配列の長さはそれだけになるけど、1つの部屋でupdateしないといけない位置は少数なので問題ない。

https://www.codechef.com/viewsolution/12173383

Our Base is Under Attack(BASE)


二分探索する

オーバーフローに悩まされた

https://www.codechef.com/viewsolution/12175362

Kth Max Subarray(KTHMAX)


最初誤読して2周りくらい難しい問題を解こうとしていた。

説明のために値はdistinctに 1〜N として、n以上の数を含まないsubarrayの個数を C_n とする。

C_N, C_N-1, ･･･を順に求める。

C_K は、Kの直近で左にあるK以上の値の位置と、Kの直近で右にあるK以上の値の位置が分かれば、C_K+1からO(1)で計算できる。また、そのような左右の位置は、SortedSet使えばO(logN)でわかる。

あとはクエリごとに二分探索すればよい。

https://www.codechef.com/viewsolution/12255980

Roses for Alexey(ALEXROSE)


まず、長さごとに何個あるかを持っておく。K以上の場合はmod Kする。

個数が大きいものから貪欲に使えるかを試す。使ったときに、どの長さのものを使うかは具体的に決めずに、「長さn以上のものをK個使った」ことだけ記録する。

長さnをそれ以上の長さのものと組み合わせてK個にできることの必要条件は、以下の通り

  • n以上の長さのものがK個以上残っている
  • n以下の長さmで過去に使ったものについて、「m以上の長さのものがK個以上残っている」の条件が崩れない

これらを満たすように、貪欲に使う。

https://www.codechef.com/viewsolution/12236989

Bear and Three Colours(THREECOL)


非常に面白かった。

まず定式化する。

3つの色を0,1,2で表す。以下の式はすべてmod 3で考える。

色Xのセルと色Yのセルを合併したとき、合併後の両者の値は 2X+2Y になる。

また、すべてのセル上でのXの値の合計は、どのように操作した後でも X(=1*X) であり、これが不変量になる。

各セルの初期色をC_1,C_2,･･･C_N^2とすると、最終目的は、すべてのセルの値を C_1+C_2+…+C_N^2 にすること。

2(C_1+C_2+…) や 0 にならないのは、すべてのセル上でのC_iの値の合計が不変量であって C_iであることと、N % 3 != 0 より N^2 % 3 == 1 であることからわかる。

（これが、N % 3 == 0 のときに不可能であることの証明にもなっている）

例としてN=4の場合の戦略を挙げる。

次のようにセルを順序づける。

 1  2  3  4
 8  7  6  5
 9 10 11 12
16 15 14 13

4つのセル1,2,3,4に対して、次の順でマージしたら、4つのセルがどれも同じ色 C_1 + C_2 + C_3 + C_4 になる。

  • 1-2
  • 3-4
  • 2-3
  • 3-4
  • 2-3
  • 1-2
  • 3-4

次に、4,5,6,7について同様のことをすると、それら4つのセルの色は C_1 + C_2 + … + C_7 になる。

引き続き、7,8,9,10、 10,11,12,13、 13,14,15,16について順に同じことを行うと、 セル13,14,15,16の色は C_1 + … + C_16 になる。

次いで逆順に 10,11,12,13、7,8,9,10、 4,5,6,7、1,2,3,4 と戻りながら同じ操作をすると、すべてのセルの色が同じになる。

O(N^2)

https://www.codechef.com/viewsolution/12223130

Chef and Finding Direction(CHEFAFD)


セルを市松模様で左右に分けて完全二部マッチングが存在するかどうか。

…をやったらTLEしたので高速化を頑張った（もっと速い方法あるんだろうか）

https://www.codechef.com/viewsolution/12238069

Sereja and Increasing subsequence(SEAINCR)


制約がちょっと珍しい。

平方分割っぽくやればいけそうな気がしていたけど、わからず

Advanced Cooking Machine(BOUNCE)


手つかず

Edit Distance Revisited(EDIT:タイブレーク)


SWAP使ってない自明解のみ。

普通の編集距離DPを、SとTの長さが同じくらいになるような範囲の周辺だけ保持する。

https://www.codechef.com/viewsolution/12172536

60.283点

結果


  • 760.283pts/1000pts
  • 51位/5041人?

2016-12-01

■ [部活] AtCoderの昔の問題を難易度推定する 00:09 はてなブックマーク - AtCoderの昔の問題を難易度推定する - TopCoderの学習のお時間


これは Competitive Programming （その2） Advent Calender 2016 1日目の記事です。

先日、Twitterでこのような発言を見かけました。

AtCoderの過去問が今の基準だと何点になるのか知りたいhttps://twitter.com/hogeover30/status/785894012716654593


やってみました。

一応、背景を書いておきます。

以前のAtCoder Regular Contest（以下ARC）・AtCoder Beginner Contest（以下ABC）では、基本的にそれぞれの問題は100点満点でした。

2016年7月にAtCoderがリニューアルされた際、難しい問題は高い点数となるよう、難易度に応じた配点がされるように変わりました。

そこで、以前の問題が最近の基準では何点くらいになるのかを、ユーザーの回答状況を元に推定しました。

AtCoderリニューアル後のコンテストの問題に対する、各ユーザーの正解/不正解の結果と配点を教師データとして機械学習し、過去の問題に対する正解/不正解の結果をテストデータとしています。

結果はこちらにあります。

https://tomerun.github.io/atcoder_statistics/estimated_scores.html

  • どうしても古いコンテストほどデータが少なくて推定しづらい様子。ABCのA問題が250点くらいといった高すぎる数値が出ている
    • 逆に、新しめのものはそこそこよさげに見える
    • こういった状況は他の機械学習案件でもありそうなんだけれど、うまく扱う方法あるんだろうか
  • ABCのD問題にもけっこう難しいのが紛れている
    • あまり出てないので知らなかった
  • 難易度順が逆転してしまっているところはあんまりない
  • これくらいの推定なら正解者数や正解率だけの分析でも出せるんではないかという気もしますが…
  • 解ける人が数人しかいない最高難易度帯の問題は、そのコンテストに誰が参加していたかによって結果がかなり影響されてしまうので、信頼性低そう
    • おおまかには、強い人がコンテストに出ていて解けなかった場合に推定スコアが高くなるという仕組みなので、あまり強い人が出ていなかった場合、推定スコアが高くなりようがない


実装に関しては、だいたいはscikit-learnのSVMに放り込んだだけですが、細々とした話としては次のようなことがあります。

  • 全ユーザー使ってしまうとデータがすごくスパースになって精度下がってしまうので、過去のコンテストに100問以上参加しているユーザーのみを計算に使いました
    • 対象ユーザーは236人でした
  • 過去に一部、満点が101点という問題がありましたが、100点以上を正解として扱っています
  • 「後ろのほうの問題だけ解いて他は無視」という参加をする人もいるので、コンテストの後半の問題は提出しているのに前半の問題は未提出の場合、前半の問題は不正解ではなく不参加という扱いにしています
    • 逆に前半だけ提出していて後半は未提出の場合、後半の問題は手が出なかったとみなして不正解扱い


せっかく今回いろいろデータを集めてきたので、他にもなにか面白い分析をやりたいですね。アイディアがある人はぜひ教えてください。

Advent Calendar2日目は、tubo28さんの「未定」と、snuke_さんの「IOIへの出題について」です。お楽しみに！