DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦: C - 01文字列

問題概要

空文字列Sに対して以下の3種類の操作を好きな順番で好きな回数行い、与えられた文字列Tに一致させたい。そのための最小コストを求めよ。 1. Sの先頭に0を挿入する(コストA)。 2. Sの末尾に1を挿入する(コストB)。 3. Sの01をすべてflipする(コストC)

|T| <= 2×10⁵

解法

操作1の回数をa回と決め打つと、操作bの回数は|T|-b回に定まる（Sの長さは操作1, 操作2によってしか増えないため）。さらに操作の特性上、先頭a文字が操作1由来、後ろのb文字が操作2由来であることも確定する。この時点でコストAはa回, コストBはb回支払うことが確定し、問題は操作3の回数をどれだけ少なくできるかという点に移る。操作3が反転であることを考えると明らかに0と1の切れ目では反転を行う必要があり、そうでないところでは必要がない。またaとbの切断箇所で隣り合う文字が同一の場合、どちらかが1回待たなければならない。とかの面倒なケースを処理しつつ計算する。これはO(1)でできるので操作1の決め打ち回数を全探索してO(N).

感想

なんかごちゃごちゃしてしまってつらかった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

void main() {
    auto s = readln.split.map!(to!long);
    auto A = s[0];
    auto B = s[1];
    auto C = s[2];
    auto S = readln.chomp.map!(c => (c - '0').to!int).array;
    auto N = S.length.to!int;
    long ans = 1L << 59;

    auto seg1 = new int[](N);
    auto seg2 = new int[](N);
    seg1[0] = 1;
    seg2[N-1] = 1;
    foreach (i; 1..N) seg1[i] = S[i] == S[i-1] ? seg1[i-1] : seg1[i-1] + 1;
    foreach_reverse (i; 0..N-1) seg2[i] = S[i] == S[i+1] ? seg2[i+1] : seg2[i+1] + 1; 
    
    foreach (a; 0..N+1) { // 先頭に追加する回数
        int b = N - a; // 末尾に追加する回数
        int s1 = a == 0 ? 0 : seg1[a-1];
        int s2 = a == N ? 0 : seg2[a];
        int flip = max(s1, s2) - 1;
        if (a > 0 && a < N && s1 == s2 && S[a] == S[a-1]) flip += 1;
        if (s1 >= s2 && S[0] == 1) flip += 1;
        if (s1 < s2 && S[N-1] == 0) flip += 1;
        ans = min(ans, a * A + b * B + flip * C);
    }

    ans.writeln;
}