Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-05

[][] Yandex Open 2011 Qualification 1 09:35 はてなブックマーク -  Yandex Open 2011 Qualification 1 - 練習帳

問題一覧:Dashboard - Yandex.Algorithm Open 2011Qualification 1 - Codeforces

結果:Standings - Yandex.Algorithm Open 2011Qualification 1 - Codeforces

=.ABCDE
---0:29---
0+0/-0--1-2--

部屋内10位(Room 68),全体781位

Rating:1531 → 1452 (-79)

 Yandexなるロシアのインターネット関連会社が主催するプログラミングコンテストが,Codeforcesをホストとして開催されています(ルールは通常のCodeforcesと同様です).今回は2回あるQualificationラウンドの1回目で,上位500位までがRound1に進出します.ボーダーは1188点なので,A+Bを高速で解くか,A+Cを少ない誤答で解けばノルマを達成できたようです.

 自分については,Codeforcesで0点は初めてかもしれないです.A, B問題について掲載します.C問題までは消化したいと思っています.

A. Plug-in

要約

 1行の文字列に対し,同じ文字が隣同士にあったらそれら2つを削除するという操作を考える.文字列が与えられているので,この操作を行える限り行った結果を出力せよ(どのような順番で文字を消しても最終的な答えは同じである.).つまり,それぞれの文字を「ぷよぷよ」のぷよだと思って,2個消しでできるだけぷよを消す操作を行え.

 文字列の長さは1以上2*10^{5}以下.

方針

 文字列を走査していき,ぷよで言うところの1連鎖分をシミュレートするような実装の場合,最悪文字列の長さの2乗のアルゴリズムとなってしまい時間内に終わらない.スタックを用いるとスマートに実装できる.今回の場合最後の出力はスタックの先頭から順に取り出すので,デックを用いると便利.

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

using namespace std;

int main(){
  string s;
  while(cin >> s){
    deque<char> ss;
    for(int i = 0;i<s.size();i++){
      if(ss.empty()){
	ss.push_back(s[i]);
      }else{
	char t = ss.back();
	if(t == s[i]){
	  ss.pop_back();
	}else{
	  ss.push_back(s[i]);
	}
      }
    }
    while(!ss.empty()){
      cout << ss.front();
      ss.pop_front();
    }
    cout << endl;
  }
  return 0;
}


B. Sequence Formatting

要約

 整数(123など複数桁もありうる,長さは任意),コンマ,スペース,三連ドットからなる一列の文字列がある,これをスペースの数を調節する事で,次の条件を満たすように整形せよ.

  • コンマの後には1個のスペースがある(コンマが文字列の終端にある場合はスペースを入れない)
  • 三連ドットの前には1個スペースがある(三連どっとが文字列の先頭にあるばあいはスペースを入れない)
  • 整数と整数の間には1個のスペースがある
  • これ以外にはスペースは入らない.

例えば

□□1,2□,3,...,□□□□□10□□11□□

1,□2□,3□,□...,□10□11

と整形される(□はスペース1個分を表す)

方針

 はじめにスペースを出来る限り取り除き(正規化),その後必要な箇所にスペースを挿入するというアプローチをとる(最終的に残るスペースを一度消してしまうなど二度手間になる可能性がありますが,すっきりしてわかりやすいと思います).

 正規化では整数と整数それぞれの間にスペースを1つだけ残し,残りは全部取り除く,前述の例に当てはめれば

1,2,3,...,10□11

とする.これは,「文字列を走査していってスペースを見つけたら

(数字)□(数字)

となっていない限り取り除く」というアルゴリズムで行える.

 つぎに,必要なスペースを挿入していく,整数と整数の間のスペースは既にあるので,コンマと三連ドットに付随するスペースを挿入していく.コンマ,三連ドット個別に考えれば良いだろうと思うし,実際それで問題ないのだが,コンマ,三連ドット両方からスペースを挿入され,スペースが連続してしまう可能性がある.例えば,

,...

の場合,「すべてのコンマの後にスペース」を適用した後「すべての三連ドットの前にスペース」を適用すると

,□□...

となる.そこで,三連ドットについては自分の前がスペースでないかを確認しなければならない.

コード(c++, コンテスト外)
#include <iostream>
#include <vector>
#include <string>
#include <cctype>

using namespace std;

int main(){
  string s;
  while(getline(cin, s)){
    for(int i = s.size() -1;i>= 0;i--){
      if(s[i] == ' '){
	if( i -1 >= 0 && i + 1 < s.size() && isdigit(s[i-1] ) && isdigit(s[i+1]))
	  continue;
	s.erase(i, 1);
      }
    }
  
    for(int i = s.size();i>=0;i--){
      if(s[i] == ',' &&  i!= s.size()-1){
	s.insert(s.begin () + i + 1,1, ' ');      
      }
    }

    int cnt = 0;
    for(int i = s.size();i>=0;i--){
      if(s[i] == '.'){
	cnt ++;
	if(cnt % 3 == 0 && s[i-1] != ' ' && i != 0){
	  s.insert(s.begin () + i ,1, ' ');
	}      
      }
    }
    cout << s  <<endl;
  }
  return 0;
}

分析

 おそらく常套手段ですが,文字列の挿入,消去を行う場合,後ろから走査すると,処理済み,未処理を明確に区別でき便利です.例えば,「文字列の中にスペースがあったらそれを複製する」という操作duplicate_spaceを考えます.

abc□de□f

なら,

abc□□de□□f

です.これを次のように実装すると無限ループになります.

void duplicate_space(string & s)
for(int i = 0;i<s.size();i++){
  if(s[i] = ' '){
    s.insert(s.begin() + i , 1, ' ');
  }
}

これは新しく挿入したスペースの上も操作する事で,スペースが次々に挿入されてしまうためです.for文を逆順にすれば,スペースはiの操作済の範囲に挿入されるのでこの心配はありません.

void duplicate_space(string & s)
for(int i = s.size() -1;i>=0;i--){ // The direction in which variable i runs is reversed.
  if(s[i] = ' '){
    s.insert(s.begin() + i , 1, ' ');
  }
}
補足

 正規表現ライブラリが標準で付属している言語ならそれを用いるのが賢明だと思います._dp_さんの提出解答は上の方針をPythonのreモジュールを用いて実装しています.

Status - Yandex.Algorithm Open 2011Qualification 1 - Codeforces