TopCoder Marathon Match 105

思い通りにはいかないね
provisional score: 678065.56
provisional rank: 15th / 57
Problem: MessageChecksum

概要

メッセージを復元しなさ～い
以下殴り書きメモ

一文字ずつチェックサムして編集距離 0 の文字列を得る自明を投げる
スコアは 5*n で上から押さえられる

submission 1: 894596.65 (2)

しばらく考えるも自明以外が思い付かない



インターバル k ごとに substr(i*k, k) を拾ってきてチェックサムが合えば ans に文字列追加
合わなければ一文字ずつチェックして厳密解を得る方針を試す
→ 編集距離が 0 にならずスコアが 1E8 とかになるので無理

スコア計算の方式からして編集距離は 0 のほうが良さそうだが…



L = 100
d = editDistance(getMessage(0, L), substr(s, L)) として
pseudo_error = d / L / 2 とする

* pseudo_error > 0.03 のケースは submission 1 で投げた自明をやる
* pseudo_error <= 0.03 のとき
    ans = "";
    REP(i, n) {
        map<char, int> mp;
        // 3 回 i 文字目を引く
        REP(j, 3){
            char c = getMessage(i, 1)[0];
            mp[c]++;
        }
        // 票がばらけたら submission 1 と同様に厳密な正解を求める
        if (mp.size() >= 2) {
            int cs = Sender::getChecksum(i, 1);
            ans.push_back(cs + 'A');
        }
        // 全会一致ならそれを採用
        else {
            ans.push_back(mp.begin()->first);
        }
    }
    return ans;

error_rate の低いケースなら 3 回の投票がほとんどのケースで全一致するので checkSum より安上がりに済む
100 テストケース試すとトータルで 104% くらいの得点向上が見込めそうだったので投げてみる

submission 2: 781615.95(4) → 787749.88 (3)

0.007% しか上がっとらん

順位の上では 1 つしか変わってないけど団子ゾーンを抜けたので rating delta はかなり上向きになった
よかった



最初 L 文字を 1 文字ずつ getChecksum で厳密に求めて s.substr(0, L) との編集距離 d を計算
pseudo_error = d / 100.0
とすると getMessage(0, L) なして上述した方法と同じ効果が得られる

submission 3: 594515.34 (17) → 612351.63 (12)




最初に receiveMessage(n, s1) の引数として与えられる文字列 s1 を有効活用できればうれしい
削除を含まない(位置ズレのない)文字列 s2 を得るためには
    for (int i = start; i < end; i++) {
        while (true) {
            string ch = Sender::getMessage(i, 1);
            if (!ch.empty()) {
                s2 += ch;
                break;
            }
        }
    }
のように empty 以外が出るまで一文字ずつ取得していけば良い
これは error_rate = 0.5 でもせいぜい n + 数百程度のコストで済む

s2 が得られたら s1 の適切な位置に空白を挿入して s1 の位置ズレを修正していく
    sim[i] = (s1[i] == s2[i]) ? 1 : -1
とした後に累積和を取ってみる

s1: YMJWDKPTZBASZTUFSJDMJWBIKLFOEJHOJXEMYGDNKADGRHFABZYTHAJXEJDUAOHXSZHQYZIGNVJJXWSHGRBQKCRHQXYESEVRNHQWNPBTYQQDTHVPDOPKDDQHVZXOHPWAFPERTYUUNAPKUWSNJOAOANYQIDEXROCSAIYFPNJLIEBIQBGKZIMTZVXDLBDPHSLTHGXTJAPW
s2: YMJWMMPTZBARZTEFSJKMJEBIKLFOEJHCBXEMYGDNKADGRHFABZYTHBJDXEHDUAOHXSZHQYZIGNVJEXWSHGRBQKCEHQXLESEVRNHQWKJOTYQVDTHVKVYPNXDUHQPXOHPPAFPERTYTASZPAYOSNQOVBASYOJZEJROTXAIYAPNJPIDBISBGKLIMTUZXQWIVPHSOUTIVTJOP
sim: {1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, -1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
cumulate: {1, 2, 3, 4, 3, 2, 3, 4, 5, 6, 7, 6, 7, 8, 7, 8, 9, 10, 9, 10, 11, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 18, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 36, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10, -11, -12, -11, -12, -13, -14, -15, -16, -17, -18, -19, -20, -21, -22, -23, -24, -25, -26, -27, -28, -29, -30, -31, -32, -33, -34, -35, -36, -37, -38, -39, -40, -41, -42, -43, -44, -45, -46, -47, -48, -49, -50, -51, -52, -53, -54, -55, -56, -57, -58, -59, -60, -61, -62, -63, -64, -65, -66, -67, -68, -69, -70, -71, -72, -73, -74, -75, -76, -77, -78, -79, -80, -81, -82, -83, -84, -85, -86, -87, -88, -89, -90, -91, -92, -93, -94, -95, -96, -97, -98, -99, -100, -101, -102, -103, -104}

位置ズレが生じると sim の累積和が明確に増加から減少に転じているのが分かる
これを検出して，そのへんの位置で s1 に空白を挿入すれば良い
実装はしゃくとり法で → しゃくとりはバグる　Sender のやり取りに比べれば軽いのでナイーブに実装

s1 の位置ズレが直ると getMessage(0, n) 1 回分と同じ効果が得られるのでだいぶうれしい

pseudo_error < 0.03 なら getMessage を追加で 1 回
pseudo_error < 0.20 なら 2 回行う


submission 8: 606378.27 (18) → 647697.48 (15)
人権



位置ズレ修正，pseudo_error が大きいとあんま上手くいかない
なんか焼いたりビーム飛ばしたりするべきな予感がする



テスターの出力をつぶさに見てみると編集距離 1 になって死んでるケースが 3 くらいあった
これはもったいない

そういえば checksum 使ってなかった
checksum が等しくなる悲しい事態が発生しなければ，誤り一つにつき O(log N) 程度クエリを投げると位置を特定できるはず

BinaryIndexedTree と再帰で誤り訂正の関数をつくった

数個程度のエラーであれば訂正可能なことがわかった
それっぽくパラメータをいじるとスコアが大幅に上昇

submission 9: 647780.59 (15) → 714634.13 (12)

なんとなく目標にしてた 700k に届いてよかった



位置ズレ修正に LCS を使ってみる

sa を引数で受け取った文字列
sb を 1 文字ずつ getMessage で取得した長さ n の文字列とする

c = LCS(sa, sb) と対応する添字 ({a[i]}, {b[i]}) を求める
つまり c[i] == sa[a[i]] == sb[b[i]]

手前から見ていって，
a[i] == b[i] なら一致
a[i] < b[i] なら sa の i 文字目の手前に (b[i] - a[i]) 文字だけ空白挿入
a[i] > b[i] なら無視

で位置合わせをしていく


頭が悪いのか筋が悪かったのか素直にピーク検出した方がいいスコアだった　無念



checkSum をメモ化したらスコア上がるんじゃないかとか実は厳密解を出すのに checkSum は n/2 回しか必要ないんじゃないかとか無駄な勘繰りをしたけど無駄だった


pseudo_error < 0.05 かつ s.size() == n のやつは s に対して O(logn) の checkSum を
適用するだけでほぼ編集距離を 0 にできる
1 文字ずつ checkSum して厳密解を求めるより 10 倍以上良いスコアが出ることも


あとはいつも通りゴミみたいなパラメータチューニングをして終わり

submission 12: 679042.16 (15) → 686682.97 (14)
f:id:my316g:20181222110348p:plain