底辺大学生の奮闘プログラミング+α

プログラミング初心者が毎日書いたコードを載せたりします。競技プログラミングにも随時参加します。

TLEの罠

前回の記事の通り、Coder-Strike 2014 - Round 1のÇ問題でTLEを食らってしまった。


その際に少し気になったことがあったため、メモ

Problem - C - Codeforces



・最初に提出したソースコード(TLEしたコード)

import java.util.Scanner;

public class C {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] s = new String[n];
        
        for(int i=0; i<n; i++){
            s[i] = sc.next();
        }
        String ans ="";
        for(int i=0; i<s[0].length(); i++){
            char c = '?';
            boolean flag = false;
            
            for(int j=0; j<n; j++){
                char c2 = s[j].charAt(i);
                if(c == c2 || c2 == '?'){
                    continue;
                }else if(c=='?'){
                    flag = true;
                    c = c2;
                }else{
                    flag = true;
                    c = '?';break;
                }
            }
            if(!flag)c='x';
            ans += ""+c;
        }
        System.out.println(ans);
        sc.close();
    }
}


・後に提出したコード(AC)

import java.util.Arrays;
import java.util.Scanner;

public class C_3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] s = new String[n];
        
        for(int i=0; i<n; i++){
            s[i] = sc.next();
        }

        char[] ans = new char[s[0].length()];
        Arrays.fill(ans, '?');
        
        for(int i=0; i<s[0].length(); i++){
            boolean flag = false;
            
            for(int j=0; j<n; j++){
                char c2 = s[j].charAt(i);
                if(ans[i] == c2 || c2 == '?'){
                    continue;
                }else if(ans[i]=='?'){
                    flag = true;
                    ans[i] = c2;
                }else{
                    flag = true;
                    ans[i] = '?';break;
                }
            }
            if(!flag)ans[i]='x';
        }
        System.out.println(ans);
        sc.close();
    }
}

1つ目のソースだと大きな入力になると実行時間が1000msを超えTLEとなってしまう

2つ目のソースだと最高でも実行時間は155msと、1つ目のプログラムに比べて断然速い。




しかし、この2つのコード。

違っているのは、答えを格納する"ans"のデータ構造の部分だけ。
その他のアルゴリズムだったりは全て同じである。


一つ目のプログラムでは、初めに

ans = "";

として、適宜ansに文字を付け足していく方針であるのに対し、



2つ目のプログラムでは、

char[] ans;

というようにchar配列で初めに宣言し、それを書き換えていく方針である。




このことから、

ある文字列に後ろから新たな文字を連結させるという動作は処理に時間がかかることが分かる。

一回だけその動作を行うのなら実行時間に影響は無いであろうが、

繰り返しが多くなるときにはそのようなことでも、実行時間に大きく影響してくる。


前々回の記事
http://tkslimee-beginner-procon.hatenablog.com/

でもSystem.out.println()を使うことでTLEが起きてしまっていたが、今回と全く同じである。


今回はfor文の中で、

String ans += c

という処理を入れていたために、TLEが起こってしまった。




実行時間はオーダーだけで決まるわけではない、という教訓でした。