実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 180

問題概要

$N$ 個の、英小文字からなる文字列 []tex: S_1, S_2, \cdots, S_N] が与えらえる。これらの文字列の長さの最大値を $M$ とする。以下の条件を満たす $M$ 個の文字列 $T_1, T_2, \cdots, T_M$ を出力せよ。

条件 :
- 各 $T_i$ は英小文字か*からなる。
- 各 $T_i$ の末尾は*ではない。
- 各について、
  - 各 $j = 1, 2, \cdots, |S_i|$ について、 $T_j$ の $N-i+1$ 文字目を $j$ の昇順に連結したものは $S_i$ と一致する。
  - 各 $j = |S_i| + 1, |S_i| + 2, \cdots, M$ について、 $T_j$ の $N-i+1$ 文字目は存在しないか*である。

制約

$N$ は整数で、 $1 \leq N \leq 100$ を満たす。
$1 \leq M \leq 100$

考察

やりたいこととしては、「横書きの文字列を縦書きにして出力する」ということで、つらつらと書かれた条件はそのためのものである。

基本的には条件の通りに2重ループを用いてそのまま実装していけばよいのだが、少し詰まるのは条件2「各 $T_i$ の末尾は*ではない」というところ。どう実装しようか少し迷ったが、文字列に対してもpop_back()が使えることを利用して、「 $T_i$ が空文字列でないかつ末尾が*である限り末尾を削除する」という方針で書くことにした。

C++ の stringに関する扱いはこの記事が詳しいので参照のこと。

zenn.dev

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
#define rrep(i, start, end) for (auto i = (start); (i) >= (end); (i)--)

template <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<string> S(N);
    rep(i, 0, N) cin >> S[i];

    int M = 0;
    rep(i, 0, N) chmax(M, (int)S[i].length());

    rep(i, 0, M)
    {
        string t;
        for (int j = N - 1; j >= 0; --j)
        {
            if (i < S[j].length())
                t += S[j][i];
            else
                t += '*';
        }

        while (!t.empty() && t.back() == '*')
        {
            t.pop_back();
        }

        cout << t << endl;
    }
}