読者です 読者をやめる 読者になる 読者になる

Google Code Jam Qualification Round - B問題「Magicka」

Dashboard - Qualification Round 2011 - Google Code Jam

背景

Magicka(TM) はArrowhead Game Studiosによって開発されたアクションアドベンチャーゲームです。
Magickaであなたは魔法使いを操り、Magicksを生成するためにelementsをinvokingとcombiningすることができます。
本問題はMagickaのアイディアを参考にしていますが、Magickaのプレイ経験は不要です。

注意: "invoke"は"call on"を意味しますが、本問題では英語の正しい意味を気にする必要はありません。

問題

魔法使いは8種のelementsをinvokeすることができ、その8種はbase elementsと呼ばれます。
それぞれのbase elementはアルファベット1文字で表され、それらは「Q, W, E, R, A, S, D, F」のいずれかです。
あなたがelementをinvokeすると、そのelementはあなたのelement listの末尾に追加されます。
例えば、WをinvokeしたあとにAをinvokeすると(これを簡単のために"WAをinvokeした"と言うことにします)、
element listは[W, A]となります。

base elementsのとあるペアがcombineして
non-base elements(他の18文字のアルファベットのいずれか)を形成(form)することができる、と定義します。
例えば、QとFがcombineしてTを形成するとします。
すると、element listの末尾にQとFが現れた瞬間にその2文字は消え去り、Tに置き換わります。
もしelement listが[A, Q, F]あるいは[A, F, Q]となった場合、すぐに[A, T]になるということです。

opposedなbase elementのペアというものも定義します。
elementをinvokeした後、もしそのelementがcombinedされなかった場合、
そのelementとopposedなelementがelement listに存在すれば、element listは空っぽになります。

例えば、QとFがcombineしてTになり、RとFがopposedである場合を考えます。
下記のそれぞれのelementsをinvokeしたときの結果を記します。
(invokeは左の文字から右の文字へと順番に行います。)

QF → [T] (Q and F combine to form T)
QEF → [Q, E, F] (Q and F can't combine because they were never at the end of the element list together)
RFE → [E] (F and R are opposed, so the list is cleared; then E is invoked)
REF → [] (F and R are opposed, so the list is cleared)
RQF → [R, T] (QF combine to make T, so the list is not cleared)
RFQ → [Q] (F and R are opposed, so the list is cleared)

さて、invokeすべきelementsが与えられたとき、最終的にelement listはどのようになるでしょうか?

入力

最初の1行はテストケース数Tを表し、T個のテストケースが後に続きます。
それぞれのテストケースは1行で表され、半角スペースで区切られて以下のような値が記されています。

まず整数Cがあり、続けてC個の文字列があります。
このC個の文字列はそれぞれ3文字のアルファベットから成り、最初の2文字はbase elementsで最後の1文字はnon-base elementです。
これが意味するのは、2文字のbase elementsがcombineしてnon-base elementを形成するということです。
続けて整数Dがあり、D個の文字列が続きます。
このD個の文字列はそれぞれアルファベット2文字から成り、この2文字はopposedです。
最後に整数Nと、N文字からなる文字列が1つあります。
この文字列はあなたがinvokeするbase elementsです。
あなたはそれぞれの文字を出現した順(左から順)に1文字ずつinvokeします。

出力

それぞれのテストケースにおいて、"Case #x: y"の形式で1行ずつ出力します。
xはテストケース番号(1から始まる)で、yは最終的に残るelement listです。
後述の出力例を見てください。

制限

1 ≦ T ≦ 100.
base elementのとあるペアは1つのcombinationにつき1度しか現れません。
ただし、combinationとopposedの両方に現れることはできます。
base elementはそれ自身とopposedになることはありません。
実際のMagickaのゲームとは異なり、element listのサイズに制限はありません。

Small dataset

0 ≦ C ≦ 1.
0 ≦ D ≦ 1.
1 ≦ N ≦ 10.

Large dataset

0 ≦ C ≦ 36.
0 ≦ D ≦ 28.
1 ≦ N ≦ 100.

サンプル

入力

5
0 0 2 EA
1 QRI 0 4 RRQR
1 QFT 1 QF 7 FAQFDFQ
1 EEZ 1 QE 7 QEEEERA
0 1 QW 2 QW

出力 	
 
Case #1: [E, A]
Case #2: [R, I, R]
Case #3: [F, D, T]
Case #4: [Z, E, R, A]
Case #5: []

注意事項

Magicka(TM) is a trademark of Paradox Interactive AB. Paradox Interactive AB does not endorse and has no involvement with Google Code Jam.

所感
これは今回唯一間違えてしまった問題です(smallでincorrectを喰らってしまった、という意味です)。問題自体はシンプルというか超絶簡単なのですが、英語の読解力が一番必要な問題だったと思います。他に強いて注意点をあげるとすれば、Small datasetとLarge datasetの差が顕著ということでしょうか。計算オーダーが大きく変わるというよりは、性質が大きく変わってしまうような、そんな差があります。


プログラマのための論理パズル 難題を突破する論理思考トレーニング

プログラマのための論理パズル 難題を突破する論理思考トレーニング