Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2418-788dbcec
この記事にトラックバックする(FC2ブログユーザー)

Round #208 DIV2 B問題 - Dima and Text Messages (この記事を編集する[管理者用])

Source

Codeforces Round #208 DIV2 B問題 (1000pt)
Problem description

問題概要

$n$ 個のアルファベット小文字からなる単語 $w_1, w_2, \ldots, w_n$ が与えられる.
単語を順番につなげて,各単語の間と最初と最後に "<3" を挿入した後,更に何らかの文字をいくらか挿入した.
その結果が文字列 $S$ になったという.
矛盾していないか調べる問題.
$|w_1| + |w_2| + \cdots + |w_n| \leq 10^5$
$|S| \leq 10^5$

解法

"<3"を挿入した文字列を実際に作って,$S$ の部分列になっているかどうか調べる.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i, j, k, n;
  static char a[1000000], b[1000000];
  int as, bs;

  as = 0;
  scanf("%d", &n);
  rep(i,n){
    a[as++] = '<';
    a[as++] = '3';
    scanf("%s", a+as);
    as += strlen(a+as);
  }
  a[as++] = '<';
  a[as++] = '3';

  scanf("%s",b);
  bs = strlen(b);

  i = j = 0;
  for(;;){
    if(i==as){ puts("yes"); break; }
    if(j==bs){ puts("no"); break; }
    if(a[i]==b[j]){i++; j++; continue;}
    j++;
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2418-788dbcec
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。