A - C-Filter

実行時間制限: 2 sec / メモリ制限: 64 MiB

問題文

セキュリティに興味がある高橋君は、デジタルアーツ株式会社に就職したい青年です。
彼は、面接で自分をアピールするために、得意なプログラミングでフィルタリングソフト「C-Filter」を作ろうと考えています。
「C-Filter」は、与えられた文字列 s に、あらかじめ登録しておいた「NGワード」と一致する文字列が存在する場合、その文字列の長さと等しい数の *に置き換えて出力するソフトウェアです。この文字列を置き換える処理をフィルタリングと呼びます。
「NGワード」とは、半角英小文字と*から構成されます。*はすべての半角英小文字 1 文字と一致します。
例えば myonmyon は、NGワードmyo*myonと一致します。
ただし、NGワードは単語ごとに適用されるため、myo myon はNGワード myo*myonとは一致しません。
また、NGワードはある単語に対して完全に一致する必要があります。
例えば、abcdeは、NGワードabcやbcd、cdeに一致しません。

文字列 s と、NGワードが与えられるので、C-Filterの出力する文字列を答えてください。

入力

入力は以下の形式で標準入力から与えられる。 
s
N
t_{1}
:
:
t_{N}
  1. 入力は N+2 行からなる。
  2. 1 行目には 1 文字以上 1,000 文字以下の文字列 s が与えられる。
    • s はフィルタリングする対象の文字列を半角スペースで区切って繋げた文字列である。
  3. 2 行目にはNGワードの個数を表す整数 N(0≦N≦50) が与えられる。
  4. 3 行目から N+2 行目までNGワードを表す文字列 t_{i}(1≦i≦N)が与えられる。
    • 文字列 t_{i} は半角英小文字と * から構成される。
    • 文字列 t_{i} の長さは 1 文字以上、 20 文字以下である。
    • 文字列 t_{i} に含まれる * は、半角スペースを除くすべての半角英小文字 1 文字をフィルタリングの対象とします。

出力

入力された文字列 s をC-Filterでフィルタリングした結果を 1 行で出力せよ。
なお、最後には改行を出力せよ。

入力例 1

abc aaa ababa abcba abc
2
abc
**a**

出力例 1

*** aaa ***** abcba ***
  • NGワードにはabcと**a**の 2 つの文字列が登録されています。
  • 1 番目と 5 番目に入力されるabcはNGワードabcに一致するので、***と出力されます。
  • 3 番目に入力されるababaはNGワード**a**に一致するので、*****と出力されます。

入力例 2

aaaa aaa aaaaaa aaaa
3
a
aa
aaa

出力例 2

aaaa *** aaaaaa aaaa
  • 完全一致のパターンだけを考慮すれば良いため、aaaa や aaaaa は変える必要がありません。

入力例 3

i have a pen
1
*

出力例 3

* have * pen
  • １文字の単語だけNGワードとして認識されます。

入力例 4

digital arts
1
digital*arts

出力例 4

digital arts
  • 半角スペースは*にマッチしません。

出典

DigitalArts 2012
B - Password

実行時間制限: 2 sec / メモリ制限: 64 MiB

問題文

セキュリティに興味がある高橋君は、デジタルアーツ株式会社に就職したい青年です。
そこで、高橋君は自分が運営するサービスであるAtCoderのセキュリティについて見なおしてみることにしました。

現在AtCoderのシステムでは、パスワードは 1 文字以上 20 文字以下の英小文字のみとしています。
そして、文字列 s に対してハッシュ値( hash(s) )を求める以下の式があり、パスワードと入力した文字列に対して、それぞれこの式で算出したハッシュ値が一致すると、入力した文字列は正しいとみなします。

hash(s) = Num(c_1) + Num(c_2) + ... + Num(c_{N})　(c_i は文字列 s の i 番目の文字を意味する)

なお、上記の式の関数 Num() とは英小文字を数字に変換する関数で、Num(a) = 1, Num(b) = 2, ...., Num(z) = 26 というように、a から z に対して順に 1 から 26 までの数字を返します。

高橋君は、このシステムではパスワードと違う文字列でも簡単にハッシュ値が一致してしまうことに気づきました。
例えば、文字列 abc のハッシュ値は、1+2+3=6 となりますが、文字列 bbb のハッシュ値も 2+2+2=6 ですし、f も 6 になってしまいます。

高橋君は、現在使っているパスワードに対してどのような文字列が正しいパスワードとして認識されてしまうか知りたいです。
正しいパスワード以外で条件を満たすものを 1 つ出力しなさい。
条件を満たすものが複数ある場合は、どの文字列を出力しても構いません。
もし条件を満たすパスワードが存在しない場合は NO と出力しなさい。
なお、AtCoderのシステムで入力できるパスワードは 1 文字以上 20 文字以下の英小文字のみなので、 答えとして出力する文字列もその条件をみたします。

入力

入力は以下の形式で標準入力から与えられる。 
c_1c_2‥‥c_N
  • 入力には正しいパスワードを表す長さ N(1≦N≦20) の文字列が 1 行で与えられる。
    • 正しいパスワードの i 番目の文字を表す c_i は英小文字 (a-z) である。

出力

与えられた正しいパスワードを表す文字列と等しいハッシュ値になる英小文字 1 文字以上 20 文字以下の文字列を、正しいパスワード以外のいずれか 1 つ出力せよ。
また、そのような文字列が存在しない場合は NO と出力せよ。
なお、出力は 1 行のみとし、最後には改行を出力せよ。

入力例 1

abc

出力例 1

bbb
  • 問題文内に示しているように、ハッシュ値が 6 になります。
  • 他にも f 、aaaaaa 、 cc でも構いません。

入力例 2

zzzzzzzzzzzzzzzzzzzz

出力例 2

NO
  • 条件を満たす文字列は正しいパスワードしか存在しません。

入力例 3

abcdef

出力例 3

fedcba
  • ハッシュ値は 21 になります。

入力例 4

k

出力例 4

bbbbba

入力例 5

aa

出力例 5

b
  • ハッシュ値が 2 になる文字列は正しいパスワード以外に、b しかありません。

出典

DigitalArts 2012
C - Chokutter

実行時間制限: 2 sec / メモリ制限: 256 MiB

問題文

セキュリティに興味がある高橋君は、デジタルアーツ株式会社に就職したい青年です。
彼はいま、自分で運営している「つぶやき型」SNSのログを調べています。
このSNSは「Chokutter」と呼ばれており、一部の競技プログラマの間で大流行しています。
以下で「Chokutter」の仕様を説明します。
  1. 短文を「つぶやく」ことができます。
    • あなたのつぶやきは自分のタイムラインに表示されます。
  2. 自分以外のユーザを「フォロー」することができます。
    • あなたがあるユーザAをフォローすると、以降にユーザAがつぶやいたつぶやきはあなたのタイムラインに表示されるようになります。フォローする前のつぶやきは表示されません。
    • Chokutterでは、あなたがユーザAをフォローすると、システムによって強制的に同時にユーザAもあなたをフォローします。
    • 上記より、あなたとユーザAのタイムラインのそれぞれに、フォロー後のあなたのつぶやきが表示されることに注意してください。
    • 既にフォローをしている人や、自分自身をフォローすることは出来ません。
  3. 自分以外のユーザを「アンフォロー」することができます。
    • あなたがあるユーザAをアンフォローするとフォロー状態が解除され、アンフォロー後のユーザAのつぶやきはあなたのタイムラインに表示されなくなります。もともと見えていたつぶやきは、そのまま表示されています。
    • Chokutterでは、あなたがユーザAをアンフォローすると、システムによって強制的に同時にユーザAもあなたをアンフォローします。
    • 上記より、あなたがアンフォローしたユーザAのタイムラインには、アンフォロー後のあなたのつぶやきが表示されなくなります。
    • フォローをしていない人や、自分自身をアンフォローすることは出来ません。
類似サービスといくつか仕様が異なることにお気をつけ下さい。

高橋君はChokutterログをもとにして、ユーザ自身のタイムラインに表示されているつぶやきの数が多いユーザランキングを作ろうと思いました。
整数 K が与えられるので、そのランキングの上から K 番目にあたるユーザのタイムラインに表示されているつぶやきの数を出力してください。
なお、初期状態では、各ユーザは誰もフォローしていないものとします。

入力

入力は以下の形式で標準入力から与えられる。 
N M K
s_{1}
s_{2}
:
:
s_{M}
  1. 1 行目にはユーザ数を表す整数 N(2≦N≦100,000) 、ログの行数を表す整数 M(0≦M≦100,000) 、整数 K(1≦K≦N) が半角スペース区切りで与えられる。
  2. 2 行目から M+1 行目までの M 行にわたってログ s_{i}(1≦i≦M) が与えられる。
  3. ログ s_{i} は 3 種類の形式に分類することができる。以下の 整数 j と 整数 k はそれぞれユーザを表す番号で、 (1≦j, k≦N, j ≠ k)が保証されている。
    • s_{i} の先頭文字が t のとき
        • t j
        ユーザ j が「つぶやいた」ことを表す。
    • s_{i} の先頭文字が f のとき
        • f j k
        ユーザ j が ユーザ k を「フォロー」したことを表す。
    • s_{i} の先頭文字が u のとき
        • u j k
        ユーザ j が ユーザ k を「アンフォロー」したことを表す。

出力

ユーザ自身のタイムラインに表示されているつぶやきの数が多い順に上から K 番目にあたるユーザのタイムラインに表示されているつぶやきの数を出力せよ。
なお、最後には改行を出力せよ。

入力例 1

5 9 1
t 1
f 1 3
f 2 1
t 2
t 1
u 3 1
t 1
t 5
t 5

出力例 1

4
  • 図a参照
    1. まず、ユーザ1がつぶやきます。ユーザ1をフォローしている人はこの時点で存在しないため、ユーザ1のみがこのつぶやきを閲覧することが出来ます。
  • 図b参照
    1. 次に、ユーザ1が、ユーザ2およびユーザ3をフォローします。
    2. ユーザ2がつぶやきます。ユーザ2をフォローしているのはユーザ1だけなので、ユーザ1とユーザ2のタイムラインにこのつぶやきが表示されます。
    3. ユーザ1がつぶやきます。ユーザ1をフォローしているのはユーザ2とユーザ3なので、ユーザ1、ユーザ2、ユーザ3の3人のタイムラインにこのつぶやきを表示されます。
  • 図c参照
    1. ユーザ3がユーザ1をアンフォローした後、ユーザ1がつぶやきます。このつぶやきはアンフォローが行われたので、ユーザ1とユーザ2の2人のタイムラインにのみ表示されます。
    2. その後、ユーザ5が2回つぶやきます。このつぶやきが表示されるのはユーザ5のタイムラインだけです。
    3. 最終的に各ユーザのタイムラインに表示されたつぶやきの数は、ユーザ1が 4 つ、ユーザ2が 3 つ、ユーザ3が 1 つ、ユーザ4が 0 つ、ユーザ5が 2 つです。
    4. よって、一番自分自身のタイムラインに表示されているつぶやきの数が多いユーザはユーザ1であり、その表示されているつぶやきの数の 4 が答えとなります。

入力例 2

5 9 2
t 1
f 1 3
f 2 1
t 2
t 1
u 3 1
t 1
t 5
t 5

出力例 2

3
  • K の値以外は入力例1と同じ入力なので、自分自身のタイムラインに表示されているつぶやきの数が 2 番目に多いユーザはユーザ2で、表示されているつぶやきの数は 3 です。

入力例 3

5 9 3
t 1
f 1 3
f 2 1
t 2
t 1
u 3 1
t 1
t 5
t 5

出力例 3

2
  • K の値以外は入力例1と同じ入力なので、自分自身のタイムラインに表示されているつぶやきの数が 3 番目に多いユーザはユーザ5で、表示されているつぶやきの数は 2 です。

入力例 4

5 9 4
t 1
f 1 3
f 2 1
t 2
t 1
u 3 1
t 1
t 5
t 5

出力例 4

1
  • K の値以外は入力例1と同じ入力なので、自分自身のタイムラインに表示されているつぶやきの数が 4 番目に多いユーザはユーザ3で、表示されているつぶやきの数は 1 です。

入力例 5

5 9 5
t 1
f 1 3
f 2 1
t 2
t 1
u 3 1
t 1
t 5
t 5

出力例 5

0
  • K の値以外は入力例1と同じ入力なので、自分自身のタイムラインに表示されているつぶやきの数が 5 番目に多いユーザはユーザ2で、表示されているつぶやきはありません。

入力例 6

4 4 3
t 1
t 2
t 3
t 4

出力例 6

1
  • 4 人のユーザのタイムラインに表示されているつぶやきの数は全て 1 なので、K の値が 1 から 4 のいずれの値でも、出力すべき答えは 1 となります。

出典

DigitalArts 2012