---
tags: IOI
---
# IOI2008 Day1-1 活字印刷機 (Type Printer)

なんでIOIに難易度6があるんだ :thinking_face:

## 問題

https://www.ioi-jp.org/ioi/2008/problems/Day1_jpn/type_printer_j.pdf
https://oj.uz/problem/view/IOI08_printer

あなたは $N$ 個の単語を好きな順番で印刷したいです。
あなたは活字印刷機に対して以下の操作ができます。

- 印刷機の現在の単語の最後に 1 文字を追加する
- 印刷機の現在の単語の最後の 1 文字を削除する
- 印刷機の現在の単語を印刷する

最小の操作回数と、そのときの操作を答えてください。

## 考察

最後に印刷機の単語を空にするとして考えると、 prefix が同じものをできるだけ隣あわせにするとよく、これはソートすると最適になりそう。
そこから、最後の印刷機の単語の分操作回数が減るので、最後が最長になるように文字を入れ替えてからソートすると良い。

## 実装

https://oj.uz/submission/217174

#include <bits/stdc++.h>
using namespace std;
#define name3(a,b,c,d,...) d
#define rep1(a) for(int i = 0; i < a; i++)
#define rep2(i,a) for(int i = 0; i < a; i++)
#define rep3(i,a,b) for(int i = a; i < b; i++)
#define rep(...) name3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<string> a(n);
    string t;
    each(i, a){
        cin >> i;
        if(t.size() < i.size()) t = i;
    }
    each(i, a) rep(j, i.size()) i[j] ^= t[j] ^ -1;
    sort(all(a));
    each(i, a) rep(j, i.size()) i[j] ^= t[j] ^ -1;
    string ans;
    ans += a[0];
    ans += 'P';
    rep(n - 1){
        int at = 0;
        while(at < a[i].size() && at < a[i + 1].size() && a[i][at] == a[i + 1][at]) at++;
        rep(j, at, a[i].size()) ans += '-';
        rep(j, at, a[i + 1].size()) ans += a[i + 1][j];
        ans += 'P';
    }
    cout << ans.size() << '\n';
    each(i, ans) cout << i << '\n';
}