Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #33 B問題 - String Problem (この記事を編集する[管理者用])

Source

Codeforces Beta Round #33 B問題
Problem description
Beta Round #33の自分の参加記録

問題概要

長さ100000以下の文字列AとBが与えられる.
変換規則として
 文字aを文字bに変えるためにはコストcかかる (cは100以下)
という形のものが100個以下与えられる.
変換規則を何回使っても良いので,AとBを一致させるための最小コストと,その時,一致した文字列を出力する問題.
不可能ならそれを指摘する.

解法

長さが違うと不可能.
各文字から各文字に変更するのはワーシャルフロイドして求めておく.
文字ごとに,26種類どの文字にどれに変換したら良いのか別々に求める.

C言語のスパゲッティなコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define INF 1000000000000000LL

int main(){
  int i,j,k,l,m,n;
  ll cnv[300][300];
  ll res=0, tmp, g;
  char a[110000], b[110000], c[110000];
  char tmp1[10], tmp2[10];
  int len;

  rep(i,300) rep(j,300) cnv[i][j]=INF;
  rep(i,300) cnv[i][i]=0;

  scanf("%s%s%d",a,b,&n);
  rep(i,n){
    scanf("%s%s%d",tmp1,tmp2,&k);
    if(cnv[tmp1[0]][tmp2[0]] > k) cnv[tmp1[0]][tmp2[0]] = k;
  }

  REP(k,'a','z'+1) REP(i,'a','z'+1) REP(j,'a','z'+1) if(cnv[i][j]>cnv[i][k]+cnv[k][j]) cnv[i][j]=cnv[i][k]+cnv[k][j];

  for(i=0;;i++) if(a[i]<' ') break; len=i;
  for(i=0;;i++) if(b[i]<' ') break;
  if(i!=len){puts("-1"); return 0;}

  rep(k,len){
    tmp = INF;
    REP(i,'a','z'+1){
      g = cnv[a[k]][i] + cnv[b[k]][i];
      if(g < tmp) tmp = g, j=i;
    }
    if(tmp==INF) break;
    res += tmp; c[k] = j;
  }

  if(k!=len) puts("-1");
  else{
    c[len]='\0';
    printf("%I64lld\n%s\n",res,c);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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