マトリョーシカ的日常

ワクワクばらまく明日のブログ。

最低限度の回文と喫茶店のコーヒー(Topcoder SRM 528 div2 250pt)

回文は英語でpalindromeと言うらしい。

喫茶 - 無料写真検索fotoq
photo by nodoca


 TopCoder Statistics - Problem Statement

 問題:文字数が偶数である文字列sが与えられる。sを構成する文字は'o','x','?'のいずれかである。あなたのタスクは'?'を文字列sが回文になるように'o'か'x'に置き換えることである。このとき置き換える際のコスト、oCostとxCostが整数として与えられるとして、最小のコストを返せ。回文にならないときは-1を返せ。

 例:"oxo?xox?" oCost:3 xCost:5 Returns: 8
   "ooooxxxx" oCost:12 xCost:34 Returns: -1

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 class MinCostPalindrome{
	public:
	int getMinimum(string s, int oCost, int xCost)	{
        string a("i");
        string b("j");
        int mincost=0;
        printf("oCost=%d:xCost=%d\n",oCost,xCost);
        for(int i=0;i<s.size()/2;i++){
            a=s[i];b=s[s.size()-i-1];
            cout << a <<":"<< b <<":"<< i <<endl;
            if (a=="?" || b=="?"){
                if (a=="?" && b=="?") {
                    mincost+=2*min(oCost,xCost);
                }else{
                    if (a=="?") mincost+=(b =="o")? oCost:xCost;
                    if (b=="?") mincost+=(a =="o")? oCost:xCost;
                }
            }else{
                if (a!=b) {printf("not\n");return -1;}
            }
        }
        printf("mincost=%d\n",mincost);
        return mincost;
    }
};

int main(){
    MinCostPalindrome ob1;
    string string("ooooxxxx");
    int oc=3,xc=10;
    ob1.getMinimum(string,oc,xc);
    return 0;
}
  • 文字列の頭とお尻から抜き出し、一文字ずつ比較する。
  • 場合分けが面倒くさい。まずは「'?'があるか」と調べそのあとに「a,bともに'?'」「aのみ'?'」「bのみ'?'」

 と場合分けしていく。

  • min,max関数はalgorithmをインクルードしておくと使用できる。