48. 競プロでも文字列の扱いは少し慎重になった方が良い話

今日は「競プロ典型90問」を解いていました。

第4問で $H \times W$ 行列の出力を求められるのですが、初めは（計算量的に自信があったので）かなり適当に考えて、このような処理を書いていました。

for(var i = 0; i < input.H; i++)
{
    for(var j = 0; j < input.W; j++)
    {
        var ans = sumH[i] + sumW[j] - input.A[i, j];
        if (j == input.W - 1) Console.WriteLine(ans);
        else Console.Write($"{ans} ");
    }
}

これで 5534ms 要したテストケースがあり、TLE となりました。

f:id:ibako_piyo:20220122221414p:plain

意外だったので驚いたのですが、アルゴリズム的には合っているはず…と思い、とりあえず出力周りを最適化してみました。

var sb = new StringBuilder();
for (var i = 0; i < input.H; i++)
{
    for (var j = 0; j < input.W; j++)
    {
        var ans = sumH[i] + sumW[j] - input.A[i, j];
        if (j == input.W - 1) sb.AppendLine($"{ans}");
        else sb.Append($"{ans} ");
    }
}
 
Console.Write(sb.ToString());

これだけでなんと 1286ms まで速くなりました。

f:id:ibako_piyo:20220122221709p:plain