東京大学プログラミングコンテスト2012

B - 残像に口紅を


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題

ハチモジ国の文豪達は,奇妙な方法で小説を書くのを好むという.第1章は,AからHまでの8種類の文字を自由に使って書く.第2章では,使ってはいけない字を1文字決めて,残りの7種の文字だけで書く.第3章は,さらに1文字禁止文字を増やし,6種類の文字で書く.以下,章が終わるたびに禁止文字が増えていき,1種類の文字だけを使って書いた最終章の第8章が終わり,最後の1文字が禁止されることで小説が完成する.すなわち,ハチモジ国の小説は以下の手順に従って作られる文字列である.

  1. A,B,C,D,E,F,G,H を適当な順番に並び替えて,c_1, c_2, ..., c_8 とする.これが文字を禁じる順番である.
  2. 長さ1以上の文字列を8個作り,s_1, s_2, ..., s_8 とする.ただし k 番目の文字列 s_k に使ってよい文字は,c_k, c_{k+1}, ..., c_8(9-k) 種類のみである(必ず全種類の文字を使う必要はないし,同じ文字を複数回使ってもよい).
  3. s_1, s_2, ..., s_8 をこの順で連結する.

書かれた小説だけを見て,どの順番で文字を禁じたか推測できるだろうか?上記の手順で作られた文字列 s だけが与えられた時に,文字を禁じた順番 c_1, c_2, ..., c_8 を逆算するプログラムを作成して欲しい.複数の可能性がある場合,どれを出力してもよい.


入力

入力は A,B,C,D,E,F,G,H の8種類の文字からなる長さ N の文字列である.

出力

A,B,C,D,E,F,G,H の8文字を,禁止された順番に並び替えて出力せよ. 複数の可能性がある場合,どれを出力してもよい.

制約

部分点

この問題の判定には,50点分のテストケースのグループが設定されている. このグループに含まれるテストケースの入力は以下の条件を満たす.


入力例 1

DCBAHGFE

入力例 1 に対する出力例

DCBAHGFE

8文字しかないので,第1章がD,第2章がC,…,第8章がEと決まる.禁止された順番の可能性は DCBAHGFE のみである.


入力例 2

EEEEAAAA

入力例 2 に対する出力例

BCDEFGHA

最初の3文字にEが入らず,最後がAのパターンはすべて可能性がある.どれを出力してもよい.BCDEFGHA は一例である.


入力例 3

DEADBEEFCAFEBABEHAHAHA

入力例 3 に対する出力例

GDCFBEHA

章の切れ目がどこかはわからないが,一番最後まで残った文字はAであることなど,いくつかの条件は確定する.GDCFBEHA は一例である.


Submit提出する