Codeforces Marathon Round1 Online Exam

問題文 http://codeforces.com/contest/684/problem/A2

タイトルのマラソンで考えたことが書いてあります。過程を書いたので長いです。
暫定スコアは７７２６１点、暫定順位は３位でした！がんばった！

６９０００点

２つのアイデアが必要でした。

１．ビット区間を反転してスコアが下がったら戻す

テキトーなビット列をクエリに投げてスコアを確認します。
１．そのビット列の一部を反転したものをクエリに投げます。
２．その結果、スコアが上がればビット列は反転したまま、スコアが下がればビット列を元に戻します。
１．２．をくりかえせばスコアは上がり続けます。

ではどんな一部を反転すればよいでしょうか。

１回のクエリで反転するビットの数は際限なく多いほうがよいです。
１つのビットを反転させたときのスコアの改善は高々１
２つのビット～は高々２
３つのビット～は高々３
．．．と反転するビットの数が多いほどスコアの改善が大きいことが期待できます。

また、スコア番目以降のビットを反転してもスコアは変わりません。つまり情報がとれない。そして初期スコアはＫ＊２の４０００前後で、クエリごとに上がるので４０００ちょっとのビットから情報がとれます。

また、最初のクエリは初期ビット列のスコアの確認に使いますし、最後のクエリの結果を元にさらにクエリを投げることもできません。なので使えるクエリの数は９８で、めいっぱい使います。

また、同じビットを何度も調べるのは意味がない（一度調べて改善したビットを反転しても半分以上の確率でスコアが下がるため）のでクエリごとに反転するビットは重複しないほうがよさそうです。

以上より４０００ちょっとのビット列を等しく９８分割してクエリごとに順番に反転するという方針が立ちます。 4000 / 98 = 40.8... なので長さ４１のビット区間×９８あたりのスコアが一番よくなります。

２．クエリの結果－１番目のビットは確実に誤答

左端から順番に採点して誤答の数がＫになったら即座に終了ですから当然直前のビットは必ず誤答です。

この誤答はクエリを投げた直後に正し、以降このビットは不変としたほうがよいです。というのも正さずに放っておくと以降のクエリでこのビットが間違ってるやで～とまた言われてしまうので（間違っていることはすでにわかっているのでもったいない）。

１つのビットを正したときのスコアの上昇期待値は＋２ です。１つのビットを正しているので確実に＋１され、次のビットも正しければ＋２、その次のビットも正しければ＋３と続きます。次以降のビットが正しい確率は半分なので 1 * 0.5 + 2 * 0.25 + 3 * 0.125 + 4 * 0.0625 ... = 2 になります。＋２点×９９クエリ×１００ケースで１９８００点くらい上がります。

上述のビット区間の反転と組み合わせるときにずれるので補正します。
１．あるビット列のクエリを投げて古いスコアをゲット
２．確実な誤答を正す
３．ビット区間を反転してクエリを投げて新しいスコアをゲット。新しいスコアと古いスコアを比較
このとき古いスコアは確実な誤答を正す前のスコアなのでその分ずれます。じゃあ期待値分＋２すればよいかというと＋１．３３３くらいがよいようです。たいていは＋１か＋２のどちらかだからだと思います。

また、上述のビット区間の反転とこれが重なってしまうのももったいないです。上述のビット区間の反転の全体の範囲が４０００ちょっとが最適なのは（もっと広くてもよさげなのに）これが効いてるやも。んで、できるだけ重ならないようにするには速やかにビット列のスコアを４２００くらいまで上げればよい、これはビット列をクエリごとに改善してれば十分か。あるクエリであるビット区間を反転したほうがスコアが上がることがわかったときに、あえて反転せずにためてためて最後のクエリでどばっと反転させてどばっとスコアを上げるテク（後述）を使ったときにやりすぎて（１～９９クエリ目でほとんどスコアを上げなかったときに）死んだ。

---

この２つをやると６９３００点くらい出ました。

７４０００点

６９０００点の時点で７５０００点の人がいたのでその差を考えると１ケース６０ビットの差があり、これは１クエリや２クエリの差ではないことがわかります。毎クエリやっていることが違う、毎クエリもっとたくさんの情報が得られると考えました。

そこでクエリを観察するとスコアが大きく変わるときと小さく変わるときがあります。この大きく変わるときとは正誤が偏っている（めっちゃ当たってるかめっちゃ外れてる）ということです。そして小さく変わるときは正誤が半分ずつに近いということです。

このことよりスコアの変化量から正誤の偏りが推定できます。正誤の偏りはずばりそのビット区間の改善の余地を意味します。偏りが小さいほど改善の余地が大きいです。たとえば長さ１００のビット区間のうち９０が当たっているときはあと１０しか改善できませんし、９０が外れているときは反転すれば９０が当たっているときと同じですし、長さ１００のビット区間のうち５０が当たっているときは５０も改善の余地があります。

そこで改善の余地が大きい偏りが小さいビット区間に優先的にクエリを投げるとよさそうということがわかります。あるビット区間にクエリを投げるべきかどうかはある区間を含むより広い区間の偏りがわかっていないといけない、つまりそのより広い区間にクエリが投げられていないといけないです。

そこでこのようなクエリが考えられます。

誤答率というのは正誤の偏りの言い換えです、同じことを言っています。んでこのクエリの投げ方は以下のクエリの投げ方と同じクエリ数で同じ情報量が得られます。つまりその情報群から最適な戦略をとったきにまったく同じスコアになります（誤差を無視すれば）。

この２つのクエリの投げ方からは同じ情報量が得られ、相互に入れ替えが可能です。ここで６９０００点解法を思い出してみます。４０００ビットを９８分割して等間隔にクエリを投げていましたね。

これを

こうして

こうして

こうじゃ！

なんか Binary Indexed Tree っぽいな？ BIT 違いですあんまり関係ないです。これはまだ等価な置き換えをしただけなのでスコアは変わりません。ここで改善の余地が大きい偏りが小さいビット区間に優先的にクエリを投げるように変えます。

投げているクエリの数（赤線の数）が変わっていないこと、ビット区間を仕切る黒縦線がばらついているのに注目してください。これで同じクエリの数で改善の余地が少ないビットへのクエリを節約して、改善の余地の大きいビットにたくさんクエリを投げれています。

これを実装すれば７４０００点が・・・出ません。誤差が大きくなりすぎます。このマラソンは誤差との壮絶な戦いでした。この誤差マラソン中にやってよかったことは誤差を無視したらどうなるのかを常に意識するとです。それは正解ビット列をカンニングしながら推定値を使うところをすべて真値を使うプログラムを書くことです。これをすると実装がバグってるのか誤差が大きすぎるかの切り分けができる、誤差０のときのスコアつまり誤差に対する上界がわかる、上界を元に１位に届くか判断できる、誤差でどのぐらいスコアが下がっているのかがわかるです。

でまあ以上のようなことをやって上界が７８０００点（１位オーバー）ですが誤差ありでは７１０００点くらいしかでず誤差が大きいことがわかりました。そこで誤差を小さくできれば１位に届くと思い、誤差が大きい箇所を調べました。誤差が大きい箇所は３つでした。

１．広いビット区間の反転は誤差が大きい
さっき述べましたがたくさんビットを反転するとスコアの変化量が大きいのでそれにともない誤差も大きくなります。広いビット区間のクエリは控えたいですね。

２．区間ＡＣの誤答率と区間ＡＢの誤答率から区間ＢＣの誤答率を算出推定するときに誤差が累積する。
クエリ値からの推定は１次ソースなので誤差は常に一定値以下ですが区間と区間から区間の誤答率を求めるたびに誤差が累積します。ビット区間が狭くなるほど深くなるほど誤差が大きくなります。あまり深くしなければよさそうですね。

３．区間ＢＣの誤答率がわかった時点で区間ＢＣを反転した方がスコアが上がるかどうかがわかりますがこれを即時反転してしまうと誤差る
少し前に後述って言ってたやつです。わかった時点で反転してスコアを改善してしまうとスコアの上昇量を推定しないといけなくなり誤差がでます。反転したほうがスコアが上がるという情報を覚えておいて最後のクエリの直前にまとめて反転すると誤差を０にできます。

１．２．より長さ８８の区間４６個を初期ビット区間集合として深さを３に制限する。３．をやる。パラメーター調整をする。これで７４０００点がでました。上界が７８０００点なので軽減したとはいえ結構誤差がのこってます。

７７０００点

誤差は限界まで小さくしたので他に何か問題がないか考えてます。反転するビット区間が広すぎると誤差が大きすぎてよくないことがわかりました。逆に狭すぎるとスコアの変化量が小さすぎるのでよくないこともわかっています。

このことから誤差が大きすぎず（長さが広すぎず）、スコアの変化量が小さすぎない（長さが小さすぎない）最適なビット区間の長さがあるのではと考えました。７４０００点解法は広い区間から徐々に狭い区間に狭めていくという解法でこの考察が正しいとするとよくないですね。なんとかしたい。

そこで広い区間を狭い２つの区間に分割した後にもう一度統合すれば最適な区間の長さを保持できるのではと考えました。ここで統合という概念がでてきたのでここからは区間（連続している）という表現は正しくなくなったので以降ビット部分列という表現に変わります。

問題はどのビット部分列と部分列を統合するかです。これは誤答率ができるだけ近しい部分列と部分列を統合するのがよいです。理由は情報量の減少が小さいから。たとえば誤答率が１０％の部分列と９０％の部分列を統合してしまうと誤答率が５０％になり情報がうすまってしまいます。

以上のことから偏りが小さく、かつ誤答率が近しい部分列を２つ選んで統合、分割して片方のビットを反転してクエリを投げるというのを繰り返すと改善の余地が大きいところを集中的に最適な長さのビット部分列で殴り続けられるので７６０００点がでました。

あとパラメーター調整とかヒューリティスとか誤差を小さくしたりあやしげな工夫をいろいろして７７０００点がでました。

リファクタしまくってたら１００行くらいになった。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int N = 5000, K = 2000, X = 100;
bool a[N + 1];
bool b[N + 1];

void invert(const vector<int>& v) {
    for (int i : v) {
        if (!b[i])
            a[i] = !a[i];
    }
}

int query(double prev, const vector<int>& v) {
    invert(v);

    for (int i = 0; i < N; ++i)
        cout << (int)a[i];
    cout << endl;
    cout.flush();
    int p;
    cin >> p;

    a[p - 1] = !a[p - 1];
    b[p - 1] = true;
    if (p < prev)
        invert(v);
    return p;
}

struct S {
    vector<int> v;
    double w;
    double score(const S& s, int t) const {
        return s.w - w + abs(s.w + w - v.size()) *
            (t < 3 ? 0.74 : t < 9 ? 0.5 : 0.3);
    }
    bool operator < (const S& s) const {
        return w < s.w;
    }
};

int main() {
    const int NUM = 42;
    const int LEN = 98;
    const int LEN2 = LEN / 2;
    const int Q = 3954;
    const double P = 1.34;
    const double DIFF = 4.8;

    vector<int> v;
    for (int i = 0; i < N; ++i)
        v.emplace_back(i);
    int p = query(K * 2, v);
    double prev = (p < Q ? query(0, vector<int>()) : max(p, K * 4 - p)) + P;
    S q[NUM];

    for (int i = 0; i < NUM; ++i) {
        for (int j = i * LEN; j < (i + 1) * LEN; ++j)
            q[i].v.emplace_back(j);
        int p = query(prev, q[i].v);
        q[i].w = LEN2 - abs(p - prev) / DIFF;
        prev = min<double>(max(prev + P, p + P), N);
    }

    for (int t = X - (p < Q) - NUM - 3; t; --t) {
        sort(q, q + NUM);
        S* s = q;
        for (int i = 2; i < NUM; ++i) {
            if (s[0].score(s[1], t) > q[i - 1].score(q[i], t))
                s = q + i - 1;
        }
        S ns[2];
        for (int i = 0; i < LEN * 2; ++i)
            ns[i < LEN].v.emplace_back(s[i % 2].v[i / 2]);
        int p = query(prev, ns[0].v);
        double diff = p - prev;
        for (int i = min(p, (int)prev); i < max(p - 1.0, prev); ++i)
            diff += b[i] && (p > prev ? -1 : 1);
        ns[0].w = LEN2 - abs(diff) / DIFF;
        ns[1].w = s[0].w + s[1].w - LEN2 - diff / DIFF;
        s[0] = ns[0];
        s[1] = ns[1];
        prev = min<double>(max(prev + P, p + P), N);
    }

    auto& s = *min_element(q, q + NUM, [LEN2](const S& a, const S& b) {
        return abs(a.w - LEN2) < abs(b.w - LEN2);
    });
    p = query(prev, vector<int>(s.v.begin(), s.v.begin() + LEN2));
    if (s.w - (p - prev) / DIFF > LEN2)
        invert(vector<int>(s.v.begin() + LEN2, s.v.end()));
    s.w = 0;

    for (auto& s : q) {
        if (s.w > LEN2)
            invert(s.v);
    }
    query(0, vector<int>());
    return 0;
}