adventar.org
もうちょっといいネーミングは無かったのでしょうか。
おことわり
今回の記事にデータ源として登場する人は、新AtCoderのコンテストに20回以上参加した人のうち、だいたいレートが2700以上とかの人だけです。
赤にいかないうちは、典型も解けていないという証拠なのでどんな問題がでても文句を言わずに解きましょう
— rng_58 (@rng_58) 2017年10月12日
APIとかの使い方がわからないので、手作業で集められる範囲で許してください。
はじめに
ある程度プログラミングコンテストに出ていると、限界を感じます。具体的には典型を全部把握していて過去に見たことがあるような問題ならゼロ時間で解けるのに、ある程度典型から外れた瞬間全く解けなくなるというやつです。AGCやCode JamのRound 3以降で顕著です*1。
だいたいそこからできることというのは、爆速でコーディングを上げる能力と、ズルです。ただしAGCにおいてはコーディング量が元から少ないので、爆速でコーディングして変わる時間がほぼありません。困りました。残された道はズルです。
ズルと言ってもやってはいけないズルとそうでないズル、あとグレーゾーンなズルがあります。グレーゾーンなズルは白黒はっきりさせたくないのでここでは割愛します。やってはいけないズルというのは、他の人と解法を共有する・サブ垢を作ってACしたものだけを送ることでペナルティを解消する・ジャッジキューをつまらせて他の人を妨害して順位を上げる、などです。やってもいいズルというのは、戦略の中に収まるものから順に、証明しないで正しいと思う・順位表を見て解いている人の集合から問題ジャンルを予想する・定数倍改善・input解析(この二つは最近結構難しいです)・嘘だとわかっているがどうせ落とすデータはないだろうと思って提出する・OEISを見る・問題名やキーワードを検索し、同じ(部分)問題を探す、とかでしょうか。
嘘解法対策などは、昔に比べたらどこでもある程度対策されていると思われます。しかしながら未だに変なオーダーで解いたり、TLEした1ケースはどうせ○○だからあらかじめこのケースだけ埋め込んで置けばOKとか、変な解き方をすることは十分可能です。現に僕はAtCoderでよくtesterをしているのですが(これは言ってもいいよね)、tester中に思いついた変な解法を出すことで、「じゃあこういうケースを足してこれを落とそう」とか「問題設定をちょっと変えてOEISに出てこないようにしよう」といった改善がされることも多いです。
OEISについてだけは少し触れておきましょう。OEISは、使い方に慣れてないと見落としが多いかもしれません。たとえば、そのまま実験した結果だと検索しても出てこないけど2^nで割ったら出てくるとか、(2^n)(n!)で割ったら出てくるとかはよくあります。2変数の数列(さすがに(i≤j)となる(i,j)のペアにしか定義されないものがほとんどです)も実はOEISに相当数入っています。いろいろ割ったり足したり引いたり掛けたり差分を取ったり2変数のものを1次元に押しつぶしたりして、いろいろ検索を掛けてみることはとても大事です。
それでは本題に入りましょう。
本題
過去の「Aさんが問題Bを解けたかどうか」データから、特徴を見つけていきましょう。統計に弱いので*2、変な方法でもお許しください。生データは欲しい人がいたらあげます。
使ったもの
結果の鑑賞
とりあえず鑑賞してください。
データシートの様子
PCA 1軸/2軸
さすがにわかると思いますが1軸はだいたい問題の難度に対応していて、これを見ることは今回の趣旨ではない上、問題についた配点をみればいいだけの話なので、この軸は無視しましょう。
PCA 2軸/3軸
よくわからん... 一部やたらと遠くに位置していることがわかると思いますが、なぜだかわかりません(antaさんはわかる気がする)。不思議ですねえ。
不安定感というか、独特の解き方になっている人が外側にいるのかもしれません。この人たちが解いているかどうかはあまり参考にできないということでしょうかね。
PCA 3軸/4軸
何か特徴があるのかないのか、よくわかりません。問題のほうの外れ値も調べてみればわかると思いますが、別に変な問題とは思えないものばかりでした。
クラスタリング 人
PCAで出てきたうち2~6軸でWard法を使いました。こういうことって統計的に正しい操作なのかなあ
わりかしこれは、僕が順位表を眺めるときに使う戦略(この人が解いてたから自分も解けるはず)に近い気がします。真ん中の僕がいるあたりが低配点・典型系の安定性が高い人で、右側の人が高配点か非典型に強い感じですかねえ。左側の人たちはそれぞれの距離がかなりありますが、それもなんとなく納得いきます。
クラスタリング 問題
同様のことを問題についてしました。
ここで注目して欲しいのは、複数回writerをやった人の回が、別に近い場所にいるわけではないということです。若干DEGwer回とsemiexp回がそれぞれの中でまとまっているようにも見えるのですが、気のせいの範囲だと思います。
参考 AGCを2回以上開いた人 sugim48: 2, 4, 6, 8, 16 DEGwer: 3, 9, 15 yutaka1999: 10, 14 semiexp: 11, 17 maroonrk: 13, 18
まとめ
仮説1. 「誰が」解いているのかを見る価値はあるだろう
僕のフィーリングでしかなく根拠は特にありませんがなんか変なことしたらきちんとした数値として出てくるかもしれません。上の結果だけでも、例えばクラスタリングの木で遠く離れた人が解いていても特に気にしない、とかには使えそうです。
現に個々人の「知識量」とか「実装の速度」とかを知ってると、この人が解いたから変な知識ゲーではない、とか、この人が一瞬で解いたから実装が少ない、とかはありそうです。なんどもコンテストに出ることで世界中の多くの人の問題の解き方データベースを貯めることにより、競プロ力も上がるかもしれません。これ以上書くと順位表非公開コンテストとか増えそうだからこれくらいにしておこう。
仮説2. writerと参加者の相性というのは、思っているほど大きくはない？ writerによりけりという可能性もある
writer によりけりという説を推していきます。少なくとも僕はDEGwerセットが苦手だと感じているし、semiexpセットとかsnukeセットとかは得意だと思います。
それに、明確にwriterが偏った問題ジャンルを出すこともあります。AGCでない例を挙げますが、tozangezanというwriterが難問枠で数え上げ以外を出したことがあったでしょうか。あったら教えてください。
おわりに
いかにも即席感溢れるAdvent Calendar記事なのは、3日後に控えた 今年読んだ一番好きな論文2017 Advent Calendar 2017 - Adventar にも参加予定でこっちばっかり真面目にやってるからです。許してください。3日後に各記事はこれよりずっと中身がある記事だと思うので是非とも読んでくれたらと思います。投票とかあったら投票協力してね！(クズ)
データ
やっぱデータ置いとこ→ advent calendar - Google スプレッドシート
このレート帯でAGC皆勤賞が居ないのは、面白いかもしれません。
