DouKaku?beta

[topic] 情報オリンピック2007年度国内本選問題2

中高生向けの情報オリンピック国内本選2007年度問題2です。

問題文（下記PDFの4ページ目）
http://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf
コンテスト概要
http://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/index.html
サンプルデータ（出題時に公開）
http://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/joi2008.zip
採点データ（出題時に非公開）
http://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/data.zip

「問題ごとに、プログラムの実行時間（や使用メモリ量）に制限が設定されています。」にご注意ください。本問では、制限時間1秒、メモリ制限64MBとなっています。

出題時はサンプルデータのみが公開され、採点は、採点データによる、自動採点にて行われます。

実際のコンテストでは、予選通過者48名が対象となっていて、100点満点中38点以上とった、16名が本選通過です。

post comment

Posted feedbacks - Flatten

Nested Hidden 
ブログのほうでリクエストがありましたので書き込ませていただきます。
公式ジャッジデータで時間内に正答することは一応確認しています。
少しでも参考になれば幸いです。

see: JOI2007-2008 Honsen 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<vector>

#define DEBUG(c) cerr<<"> "<<#c<<" = "<<c<<endl;

using namespace std;

int main()
{
    string s,t; cin>>s>>t;
    vector<vector<int> > dp(s.size(),vector<int>(t.size(),0));
    
    int res=0;
    for(int i=0;i<s.size();i++)
    {
        for(int j=0;j<t.size();j++)
        {
            if(i==0 || j==0)
            {
                if(s[i]==t[j])
                    dp[i][j]=1;
            }
            else if(s[i]==t[j])
                res=max(res,dp[i][j]=dp[i-1][j-1]+1);
        }
    }
    
    cout<<res<<endl;
    
    return 0;
}

いくつかのデータで1秒制限を満たしてないと思いますが、とりあえず接尾辞配列で。

see: 接尾辞配列 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct char_at
{
    const char* s;

    static size_t i;

    explicit char_at(const char* s_) : s(s_) {}

    operator bool() const { return s[i]; }

    friend bool operator==(const char_at& lhs, const char_at& rhs)
    {
        return lhs.s[i] == rhs.s[i];
    }

    friend bool operator<(const char_at& lhs, const char_at& rhs)
    {
        return lhs.s[i] < rhs.s[i];
    }

    friend ostream& operator<<(ostream& out, const char_at& at) // debug
    {
        return out << (at.s + i);
    }
};

size_t char_at::i;

bool compare_s(const char_at& lhs, const char_at& rhs)
{
    return strcmp(lhs.s, rhs.s) < 0;
}

int main()
{
    string s1; getline(cin, s1);

    string s2; getline(cin, s2);

    vector<char_at> v;

    for (const char* p = s1.c_str(); *p; ++p)
    {
        v.push_back(char_at(p));
    }

    sort(v.begin(), v.end(), compare_s);

    size_t result = 0;

    for (const char* p = s2.c_str(); *p; ++p)
    {
        char_at at(p);

        pair<vector<char_at>::iterator, vector<char_at>::iterator>
            r = make_pair(v.begin(), v.end());

        for (char_at::i = 0; ; ++char_at::i)
        {
            r = equal_range(r.first, r.second, at);

            while (r.first != r.second && !*r.first)
            {
                ++r.first;
            }

            if (r.first == r.second || !at)
            {
                break;
            }
        }

        result = max(result, char_at::i);
    }

    cout << result << endl;
}

うーん、このコードをJavaに移植すると30倍速いんだけど…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
object P2 extends Application {
  val s1 = readLine.toArray
  val s2 = readLine.toArray
  val len = new Array[Array[int]](s1.length, s2.length)
  
  var max = 0
  for(i <- 0 until s1.length) {
    val c1 = s1(i)
    for(j <- 0 until s2.length) {
      val prev = if(i > 0 && j > 0) len(i-1)(j-1) else 0
      len(i)(j) = if(c1 == s2(j)) prev + 1 else 0
      max = Math.max(max, len(i)(j))
    }
  }
  println(max)
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class P2 {
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String s1 = in.readLine();
        String s2 = in.readLine();
        int[][] len = new int[s1.length()][s2.length()];

        int max = 0;
        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i);
            for (int j = 0; j < s2.length(); j++) {
                if (c1 == s2.charAt(j)) {
                    int prev;
                    if (i > 0 && j > 0)
                        prev = len[i - 1][j - 1];
                    else
                        prev = 0;
                    len[i][j] = prev + 1;
                    max = Math.max(max, len[i][j]);
                }
            }
        }
        System.out.println(max);
    }
}

2次元配列をやめてみたけど、実行時間は変わらず…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class P2 {
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String s1 = in.readLine();
        String s2 = in.readLine();
        int[] prev = new int[s2.length()];

        int max = 0;
        for (int i = 0; i < s1.length(); i++) {
            char c1 = s1.charAt(i);
            int[] next = new int[s2.length()];
            for (int j = 0; j < s2.length(); j++) {
                if (c1 == s2.charAt(j)) {
                    if (j > 0)
                        next[j] = prev[j - 1] + 1;
                    else
                        next[j] = 1;
                    max = Math.max(max, next[j]);
                }
            }
            prev = next;
        }
        System.out.println(max);
    }
}

関数型言語の良さを生かしたコードになりました。ちょっと感動！参照透過性を使っています。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
object P2_2 extends Application {
  val s1 = readLine.toList
  val s2 = readLine.toList
  def lcs(s1:List[char], prev:List[int], max:int):int = {
    if (s1.isEmpty) return max
    val c1 = s1.head
    val next = List.map2(s2, 0 :: prev)((c2, p) => if (c1 == c2) p + 1 else 0)
    lcs(s1.tail, next, next.foldLeft(max)(Math.max(_, _)))
  }
  println(lcs(s1, List.make(s2.length, 0), 0))
}


「最長共通（連続）部分列」
i-1 とか j-1 とかのインデックスを使わずに。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
import List

solve s1 s2 = fst $ foldl f (0, 0: map (const 0) s1) s2 where
  f (m, xs) c = (m', 0:xs') where
    (m', xs') = mapAccumL g m $ zip s1 xs
    g n (d, x) = if (d == c) then (max n (x+1), x+1) else (n, 0)
{-
> solve "ABRACADABRA" "ECADADABRBCRDARA"
5
-}


「最長共通（連続）部分列」
#5978 は yukobaさんの #5969 とほとんど同じでした。
いつも書いた直後に気づく。orz

#5969 と同じ書き方にしました。

1
2
3
4
5
import List

solve s1 s2 = fst $ foldl f (0, 0: map (const 0) s1) s2 where
  f (m, xs) c = (maximum (m:xs'), 0:xs') where
    xs' = zipWith (\d x -> if (d == c) then x+1 else 0) s1 xs

遅くなる理由として次の2点があると思います。

  • 非常に繰り返し回数の多いループにおいて forを使用していること(forは無名関数 を引数に取るメソッド呼び出しの構文糖なので 遅い)
  • objectのすぐ内側で変数を定義しているため、 それらがフィールドになってしまっている (フィールドの参照はローカル変数の参照に 比べて遅い)

コードは汚くなりますが、元のコードを改造して 以下のようにすることで、自分の環境 (Athlon 64 3000+, Windows XP Professional, JDK 1.6.0)において、Javaに 移植した場合にかなり近い性能が出ることを 確認できました。ここで、

  • { }で囲むことによって、s1やs2などをローカル 変数にすることで高速化
  • 組み込みのループ構文であるwhileを使うことで 高速化

しているのがポイントです。一般的にはそれほど 気を使う必要は無いと思いますが、この問題の ようにループの回数が非常に多い場合には 有効なテクニックかと思います。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
object P2Tune extends Application {
  {
    val s1 = readLine.toArray
    val s2 = readLine.toArray
    val len = new Array[Array[int]](s1.length, s2.length)
  
    var max = 0
    var i = 0
    while(i < s1.length) {
      val c1 = s1(i)
      var j = 0
      while(j < s2.length) {
        val prev = if(i > 0 && j > 0) len(i-1)(j-1) else 0
        len(i)(j) = if(c1 == s2(j)) prev + 1 else 0
        max = Math.max(max, len(i)(j))
        j += 1
      }
      i += 1
    }
    println(max)
  }
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
reader = System.in.newReader()
s1 = reader.readLine()
s2 = reader.readLine()
prev = new int[s2.length() + 1]
max = 0
s1.eachWithIndex({ c1, i ->
    next = new int[s2.length() + 1]
    s2.eachWithIndex({ c2, j -> 
        if(c1 == c2) {
            next[j + 1] = prev[j] + 1
            max = Math.max(max, next[j + 1])
        }
    })
    prev = next
})
println(max)

両方の文字列から接尾辞配列を作って処理するようにしたら、若干高速化しました。（手元で判定データ 2-6 が 17秒 => 10秒。このマシンはPen2-266で遅いんですが、それを差し引いても大会のマシンで1秒制限を満たすか怪しいです）

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 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
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h> // strcmp()

#define REP(i, b, e) for (size_t i = b; i < e; ++i)

bool compare_str(const char* s1, const char* s2)
{
    return strcmp(s1, s2) < 0;
}

void make_suffix_array(const std::string& s, std::vector<const char*>& v)
{
    v.resize(s.size());

    REP(i, 0, s.size())
    {
        v[i] = s.c_str() + i;
    }

    std::sort(v.begin(), v.end(), compare_str);
}

typedef std::vector<const char*>::const_iterator Iter;

void skip_empty_string(Iter& beg, Iter end, size_t depth)
{
    while (beg != end && (*beg)[depth] == '\0')
    {
        ++beg;
    }
}

void find_range(Iter& beg, Iter& end, size_t depth, char c)
{
    while (beg != end && (*beg)[depth] < c)
    {
        ++beg;
    }

    Iter cur = beg;

    while (cur != end && (*cur)[depth] == c)
    {
        ++cur;
    }

    end = cur;
}

void traverse(Iter beg1, Iter end1, Iter beg2, Iter end2, size_t depth, size_t& max_depth)
{
    skip_empty_string(beg1, end1, depth);

    skip_empty_string(beg2, end2, depth);

    while (beg1 != end1 && beg2 != end2)
    {
        const char c = (*beg1)[depth];

        Iter the_beg1 = beg1, the_end1 = end1;

        find_range(the_beg1, the_end1, depth, c);

        Iter the_beg2 = beg2, the_end2 = end2;

        find_range(the_beg2, the_end2, depth, c);

        if (the_beg1 != the_end1 && the_beg2 != the_end2)
        {
            max_depth = std::max(max_depth, depth + 1);

            traverse(the_beg1, the_end1, the_beg2, the_end2, depth + 1, max_depth);
        }

        beg1 = the_end1;

        beg2 = the_end2;
    }
}

int main()
{
    std::string s1, s2;

    std::getline(std::cin, s1);

    std::getline(std::cin, s2);

    std::vector<const char*> v1, v2;

    make_suffix_array(s1, v1);

    make_suffix_array(s2, v2);

    size_t max_depth = 0;

    traverse(v1.begin(), v1.end(), v2.begin(), v2.end(), 0, max_depth);

    std::cout << max_depth << std::endl;
}

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]