Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-06-21

Codeforces Beta Round #75 Div. 2 00:46 はてなブックマーク - Codeforces Beta Round #75 Div. 2 - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #75 (Div. 2 Only) - Codeforces

結果:Standings - Codeforces Beta Round #75 (Div. 2 Only) - Codeforces

=.ABCDE
--0:091:07---
1164+0/-0482682---

部屋内20位(Room 20),全体387位

Rating: 1557→ 1510 (-47)

 TLEに泣いた回でした.ナイーブに書いたら間に合わないのは分かっていても,じゃあどうすれば計算量を減らすかが思いつけませんでした.Editorialがあるのが救いです.

A. Chips

 問題文:http://www.codeforces.com/contest/92/problem/A

コード(c++)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>

using namespace std;
int main(){
  int a, b;
  while(cin >> a >> b){
    for(int i = 0 ;;i++){
      int j = (i % a) + 1;
      b -= j;
      if (b <= 0){
	if(b < 0){
	  b += j;
	}
	cout<< b <<endl;
	break;
      }
    }
  }
}

B. Binary Number

 問題文:http://www.codeforces.com/contest/92/problem/B

コード(c++)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>

using namespace std;

typedef long long ll;


int main(){
  string s;
  while(cin >> s){
    ll cnt = 0;
    int odds = 0;


    bool flag = false;
    for(int i = 1;i < s.size();i++){
      if(s[i] == '1'){
	flag = true;
	break;
      }
    }

    if(s[0] == '1'  && !flag){
      cout << s.size() -1 <<endl;
    } else if( s == "1"){
      cout << 0 <<endl;
    }else{
    
      int zeros = 0;
      for(int i = s.size()-1;i >=0;i--){
	if(s[i] == '1'){
	  break;
	}
	zeros ++;
      }

      for(int i = 0;i < s.size();i++){
	if(s[i] == '1'){
	  odds ++;
	}
	if(s[i] == '0' && odds > 0){
	  cnt++;
	}
      }

      cout<< cnt + s.size() + 1 - zeros << endl;
    }
  }
}

C. Newspaper Headline

要約

 アルファベット小文字からなる文字列s, tがある,tを何回か繰り返してできる文字列から,いくつか文字を除いてtを作りたい.必要となるsの個数の最小値を求めよ.sは10**4文字以下,tは10**6文字以下.

方針

 ナイーブに実装したのが下のコードです.s, t内での位置を示すポインタを持っておき,sの方のポインタをぐるぐる回しつつ,両者で一致する文字があればtのポインタを進めています.もちろんこの方法ではO(s*t)だけかかるので,TLEを起こしてしまいます.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cstring>

using namespace std;

int main(){
  string s, t;
  while(cin >> s >> t){
    int pos= 0;
    ll cnt = 0;
    while(true){
      cnt ++;
      for(int i = 0;i < s.size();i++){
        if(s[i] == t[pos]){
          flag = true;
          if(pos == t.size() - 1){
            cout << cnt <<endl;
            goto next;
          }
          pos++;
        }
      }
      if(!flag){
        cout << -1 <<endl;
        goto next;
      }
    }
  next:;
  }
}

 tの走査の「中で」sを「1つずつ」前に進めている事なので.括弧でくくったどちらかを外す事を考えます.前者の方法は分からなかったので,後者の方法を試みます.つまり,s[pos]より後でアルファベットαが次に現れるのがいつかを全てのpos, αについて前計算します.これを用いると,1つずつ進めていたポインタをまとめて進める事が出来ます.


#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cstring>

using namespace std;

typedef long long ll;

int next[11111][26];
int tablet[26];
int tables[26];

int main(){
  string s, t;
  while(cin >> s >> t){
    memset(next, -1, sizeof(next));
    memset(tablet, 0, sizeof(tablet));
    memset(tables, 0, sizeof(tables));
    
    // Impossible case.
    for(int i = 0;i < s.size();i++){
      tables[s[i]-'a']++;
    }
    for(int i = 0;i < t.size();i++){
      tablet[t[i]-'a']++;
    }
    for(int i = 0;i < 26;i++){
      if(tablet[i] != 0 && tables[i] == 0){
	cout << -1 << endl;
	goto next;
      }
    }



    // pre-calculation
    for(int i = s.size() - 1;i >= 0;i--){
      for(int j = i;j >=0; j--){
	next[j][s[i]-'a'] = i;
      } 
    }

    int cnt = 1;
    int nextpos = 0;

    for(int i = 0;i < t.size() ;i++){
      nextpos = next[nextpos][t[i]-'a'];
      if(nextpos == -1){
	nextpos = next[0][t[i]- 'a'];
	cnt++;
      }
      nextpos++;

    }
    cout << cnt << endl;
      
  next:;
  }
}