Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-05-01

[][] Codeforces Beta Round #71 22:50 はてなブックマーク -  Codeforces Beta Round #71 - 練習帳

問題一覧:Dashboard - Codeforces Beta Round #71 - Codeforces

結果:Standings - Codeforces Beta Round #71 - Codeforces

=.ABCDE
--0:050:30---
490+0/-0490WA---

部屋内17位(Room 59),全体612位

Rating: 1614→ 1531 (-83)

 ちょっとショックでした.作業のみの問題は人並みの速さで解けるようになってきたので,そうでない問題を時間内に解けるようになる練習が必要なのだと思います.

A. Bus Game

要約

 100円玉がx枚,10円玉がy枚ある,2人がそこから220円を交互に取っていき,先に取れなくなった方が負けのゲームを行う.取り方が複数通りある場合には,先手は100円玉ができるだけ多くなるように取り,後手は10円玉ができるだけ多くなるように取る.先手後手どちらが勝つかを答えよ.x, y は0以上10^6以上.

方針

 220円の取り方は3通りしかないので,for文で書くよりも愚直に書いた方が速いと思います.

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

using namespace std;

int main(){
  int x,y;
  while(cin >> x >> y){
    for(;;){
      if(x >= 2 && y >= 2){
	x-=2;y-=2;
      }else if(x >=1 && y >= 12){
	x-=1;y-=12;
      }else if(y >=22){
	y-=22;
      }else{
	cout << "Hanako" << endl;
	goto next;
      }
      if(y >= 22){
	y-=22;
      }else if(x >=1 && y >= 12){
	x-=1;y-=12;
      }else if(x>= 2 && y >=2){
	x-=2;y-=2;
      }else{
	cout << "Ciel" << endl;
	goto next;
      }
    }
  next:;
  }
}

B. Colorful Field

要約

 n*mに区分された長方形の畑があり.一つの区画に人参,キウイ,ブドウのいずれかを栽培できる.しかしいくつかの区画は不毛な土地でそこには栽培できない.どの植物を栽培するかは次のように決める.左上から右方向に区画を数えていき,右端まで達したら次の行の左端に移動し再び右方向に進む事を繰り返し右下まで走査する.その時不毛な土地はスキップしながら順番に人参,キウイ,ブドウ,人参,キウイ,ブドウ・・・の順番に栽培する.

i j

の形をした t 個のクエリが与えられるので,i行j列が不毛な土地か,栽培されている植物の種類を答えよ.

 n,mは1以上4 * 10^4以下,不毛な土地の数は1以上10^3以下,クエリの数は1以上10^3以下.

方針

 n, mが大きいので,区画が不毛かをint [n][m]で保存する事は出来ない.そこでmap<pair<int, int > , int >で不毛な区画のみを記録する.さらに,それぞれの行にある不毛な区画の数はクエリによらないので前計算しておく,実際には上k行の不毛な区画の合計を計算して用いている.

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

using namespace std;

typedef long long ll;

int main(){
  ll n,m,k,t;
  while(cin >> n >> m >> k >> t){
    map<pair<int, int > , int> table;
    vector<int > wastes(n);

    for(int i = 0; i < k; i++){
      int a,b;cin >> a >> b;a--;b--;
      table[make_pair(a,b)] = 1;
      wastes[a]++;
    }
    vector<ll> sums(n);
    ll temp = 0;
    for(int i = 0; i < n; i++){
      sums[i] = temp;
      temp += (m-wastes[i]);
    }

    for(int k = 0; k < t; k++){
      int i, j;cin >> i >> j;i--;j--;
      if(table.count(make_pair(i,j)) > 0){
	cout << "Waste" <<endl;
	continue;
      }

      ll sum = sums[i];
      for(int m = 0;m <= j;m++){
	if(table.count(make_pair(i, m)) == 0){
	  sum ++;
	}
      }

      if(sum % 3  == 1){
	cout << "Carrots" <<endl;
      }else if(sum % 3 == 2){
	cout << "Kiwis" <<endl;
      }else{
	cout << "Grapes" <<endl;
      }

    }
  }
  return 0;
}

C. Beaver

要約

 文字列sと禁止ワードb[0], .., b[n-1]が与えられている.sに含まれる部分列で,いずれの禁止ワードも含んでいないもののうち,長さが最大のものを求めよ.最大のものが複数ある場合はいずれを答えても良い.s の長さは1以上10^5以下,禁止ワードの長さはそれぞれ1以上10以下,禁止ワードの数nは1以上10以下.

方針

 まず,禁止ワードが出現する位置をすべて見つける(それを禁止区間と呼ぶ事にし,半開区間で[fstart[i], fstop[i]) と表す).それを順番にソートし(1ミス),答えの候補を次の要領で更新していく,どのように更新をすれば良いかを考えるため,出現する禁止区間の一つに注目して考える.

・・・・・・・・FFFFF・・・・・ 

文字列の中でFの部分が考えている禁止区間だとする.この禁止区間を含まないような部分列は次のように取れる.


ーーーーーーーーーーーー        (1)
         ーーーー       (2)
・・・・・・・・FFFFF・・・・・ 
         ーーーーーーーーー  (3)

禁止区間の出現位置を終端の位置でソートすれば,(3)の方はこれより後ろに出現する禁止区間で考慮の対象に入る,そこで,禁止区間の出現区間を終端位置の早い順でソートする(終端位置が同じ場合の順序付けの方法は後々考える).(1)の方は上の「ーーー」で表した部分をすべて取る事は出来ない.別の禁止区間で,


ーーーーーーーーーーーー        
・FFF・・・・FFFFF・・・・・ 

のようになっているかもしれないからである.そこで,解となる部分列の候補の先頭を記憶しておく,変数topは「これ以上左に延ばしたら,今考えている禁止区間より前に扱った禁止区間を含んでしまう」という位置を示す.

 (top)
  ーーーーーーーーーー       
・FFF・・・・FFFFF・・・・・ 

そこで,len, posの他にこのtopを更新しながら答えを求めていく,上記の(1)(2)のどちらになるかはtopと禁止区間の先頭の位置関係による.

・top < (Fの先頭位置の場合)
   (top)
    ーーーーーーーー        (1)
・・・・・・・・FFFFF・・・・・ 
topを更新し,len = max ( len,  fstop[i] - top - 1)

・top >= (Fの先頭位置の場合)
        (top)
・・・・・・・EEEE・・・・・・・
     ーーーーーーーー       (2)
・・・FFFFFFFFFF・・・・・ 
topを更新せず,len = max ( len,  fstop[i] - top - 1)

ここで,EはF以前に現れた禁止区間で,2文字目部分をtopが指しているようなもの.

 次に終端は同じで先端が異なる2つの禁止区間を考える.例えば禁止区間が2つで下図のようになっていたとする.

EEEEEEEE
・・・FFFFF 

Eを先に考えるとその時点でlenの値が7(Eの長さ - 1)となり,lenは値が大きくなるように更新されているので,不適切な答えを返してしまう.逆にFを先に扱えば,これは上の「top >= (Fの先頭位置の場合)」に帰着されるので,問題なく更新が行える.従って,考える順番はF->E,すなわちより開始位置が遅い禁止区間を先に扱わなければならない.

 これだけだと,2つの場合が考慮されていない,

  • 禁止区間が全くない場合
  • 最も右端にある禁止区間よりさらに右にある文字列

これらは[-1, s.size())という禁止区間を便宜的に考えれば同時に解決できる

(これを考えた当初はなぜこれでうまく行くのかがよくわからなかった.というのも,この半開区間を入れるのは「部分列全体が禁止区間です」と言っているようなものだからである.しかし,これまで考えてきたアルゴリズムでの禁止区間の終端は実際には「解となる部分列の終端部分の候補」として本当は扱うべきもので,それならば,右端にs.size()を持ってくる事にも納得が理屈がつく).

コード例(C++, コンテスト外)
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>

using namespace std;

vector<int> fstart;
vector<int> fstop;

bool comp(int i, int j){
  return (fstop[i] != fstop[j]) ? fstop[i] < fstop[j] : fstart[i] > fstart[j];
}


int main(){
  string s;
  while(cin >> s){
    int n;cin >> n;
    vector<string> b(n);
    for(int i = 0; i < n; i++){
      cin >> b[i];
    }

    fstart.clear();
    fstop.clear();

    for(int i = 0;i<n;i++){
      string c = b[i];
      int j= 0;
      while(j< s.size()){
	size_t pos = s.find(c, j);
	if(pos != string::npos){
	  fstart.push_back(pos);
	  fstop.push_back (pos + c.size());
	  j = pos + 1;
	}else{
	  break;
	}
      }
    }
    fstart.push_back(-1);
    fstop.push_back(s.size());

    int m = nstart.size();
    vector<int > ind(m);
    for(int i = 0;i<m;i++){
      ind[i] = i;
    }
    sort(ind.begin(), ind.end(), comp);

    int len = 0;
    int pos = 0;
    int top = 0;

    for(int i = 0; i < m; i++){
      int index = ind[i];
      if(fstart[index] + 1 > top){
	if(len < fstop[index] - 1 -top ){
	  len = fstop[index] - 1 -top;
	  pos = top;
	}
      }else{
	if(len < fstop[index] - top){
	  len = fstop[index] - top;
	  pos = top;
	}
      }
      top = max(top, fstart[index] + 1);
    }

    cout << len << " " << pos << endl;
  }
  return 0;
}

 

コンテスト中

 目標3問.失敗しないようにがんばりたい.A問題,yenって他の国の人に通じるかなと余計な心配をするも,特に問題なくできる.5分.B問題・・・これもやるだけかな,不毛な土地位置をvector<vector<int> > で,1行の不毛な土地の数をvector<int> waste(m)で保存して(ここでなぜか行と列の数を逆にしてしまい,WAをだしてしまう),実装する.ローカルテスト => 間違い .

      for(int m = 0;m <= j;m++){

for文の終了条件を間違えていた,書き直して提出 => Memory limit exceeded on pretest 4.int[n][m]で保存しているのがまずかったのはすぐにわかった.vector<vector<int> > を map<pair<int, int> > に直して提出,Pretest Passed.C問題,サンプルケースの文字列に「うなぎおいしい」.うん,確かにおいしい.一番最初に書いたのは「禁止ワードとなっている文字列を全部潰し,残った中で最大の部分列を見つける」というものだった.これ自体は正しく書けたが,実際にサンプルケースに当てはめてみて,正しくない事に気づく.例えば一つ目のサンプルケースならば,

Go_***aight_a****_this_*****t

となるが,正しい最長部分列はtraight_alon.つまり,禁止ワードの一部分は残さないとならない.禁止ワードを潰すような方法は駄目だと出力してようやく気づく.少し考えて,禁止ワードの先端と終端の位置(fstart[i], fstop[i]) のペアをすべて見つけて,適当な順番で処理していけば良いだろうと考える.紙に書いて考えようとするも試行錯誤の方法がわからず混乱状態になる.D問題に移動しようとも考えたが,残り30分程度でその時点で解いている人が数人程度しかおらず,しかもC問題の提出者が着実にのびているのでこのまま解き進める事に決める.紙に書いて考えた結果,処理の順番は終端の位置が早い順で,答えの先頭(top)となる候補を記憶し,1次元DPの要領で行えば良いのだろうと考える.fstart[i]とtopの前後関係で場合分けして部分列の長さを計算し,topの更新をするというアルゴリズムを考えた結果,十分一般的なケースと思われる一つ目のサンプルケースでは正しく答えが出た.しかし,それ以外のサンプルケースが通らなかった.おそらく難しく考えすぎているのだろうと思うも,何が原因かわからずそのまま終了.なんというか,終止全然考えがまとまらないで呆然としているような感じだった.

余談

f:id:delta2323:20110501201943p:image

すみません,ダメでした.

余談2

参加者のコメントの一つにこのようなものが

「This problemset leaves no room for error, the competition for most of participant was to
 solved 3 problems cleanly and faster, only to write not to think」

やっぱ今回は3問解けるのがノルマだったんだろうな.