Algoogle

Algorithm for Programming Contest

JOI 春合宿 2009 Stamps

Category: JOI Tag: greedy

Stamps

問題概要


元となる判子をいじることで新しい判子をつくりたい(判子に使われる文字はIとOのみ).
元となる判子はIOIOIOIOIみたいにIとOが交互にきて, 両端はIでなければならない(それを満たすなら長さは自由).
この元となる判子に対して, 以下の操作をそれぞれ1秒でできる.

  • 判子の文字をIからO(OからI)に変更する
  • 判子に文字を1つ挿入する
  • 判子から文字を1つ削除する

最短で何秒で新しい判子を作れるか, またそのとき元となる判子の長さの最小はいくらになるか.

解法


新しい判子から元の判子をつくると考える.
連続した文字をみる.
もし奇数個連なっているならその間を交互に反転させるのが一番いい.
もし偶数個連なっているならそのその端を一つ取り除いてあとは奇数個と同じ.

文字の端の処理が複雑になるので両端にIO, OIをつけて回避する.

コード


(Stamps.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

int n, len, cst;
string s;

void solve()
{
        cst = 0; len = n;
        int cnt = 0;
        char pv = 'O';
        s = "IO"+s+"OI";
        for(auto &c: s) {
                if(pv != c) {
                        if(cnt%2) cst += cnt/2;
                        else if(cnt){
                                cst += (cnt-1)/2+1;
                                len--;
                        }
                        pv = c;
                        cnt = 1;
                }
                else cnt++;
        }
}

void output()
{
        cout << cst << endl;
        cout << len << endl;
}

void input()
{
        cin >> n >> s;
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        solve();
        output();
        return 0;
}

Comments