Google Code Jam 2019予選B問題 問題訳及び回答例

まえがき

昨日に引き続き、問題B「You Can Go Your Own Way」の考え方と実装例を記録します。

問題訳

問題

ここに世界で最も簡単な迷路がある。迷路はN×Nのマスから成り立っていて、迷路から出ない限り自由に動くことができる。スタートは北西、ゴールは南東だ。君はこの迷路を初めて抜けた人になるべく、迷路に入った。
しかし君が見たのは君のライバルである、「迷路のリンディ」の足跡だった。彼女は君より先に迷路を解いたようだ。

君はリンディと全く違う軌跡を通ってゴールに向かいたい。リンディがマスAから隣のマスBへ移動していたのなら、君はAからBにそのまま向かってはいけない。(別の経路を使ってAからBまでたどり着くのは適正だ)
リンディの使わなかった道を探そう。

例えば、リンディの足跡が青だとすると、オレンジのような解き方は適正だ。(リンディと同じマスを何度か踏んでいるが、同じ足跡はつけていないことになる。)

入力

1行目はテストケースの数(T)が入力されている。
それぞれのケースには2行の入力がある。最初の行は迷路の1辺のサイズNが入っている。
2行目は文字列P(長さ 2 N - 2文字)が入っている。これはリンディの足跡を示していて、それぞれの文字がEであれば東に進んだことを示していて、Sであれば南に進んだことを示している。上記の図であればEESESESSとなる。

出力

各テストケースごとに、Case #x: yの形で1行出力する。xは1から始まるケースの通し番号、yはSとEから成り立つ足跡だ。
例えば上の画像であればSEESESSEだ。

制限

1 \leq T \leq 100

時間制限：各テストセットごとに15秒
Pは2 N - 2個の文字になっていて、SとEをそれぞれN-1文字含む。

テストセット1

2 \leq N \leq 10

テストセット2

2 \leq N \leq 1000

テストセット3

最大10件は$ 2 \leq N \leq 50000 $
残りは$ 2 \leq N \leq 10000 $となる

考え方及び回答例

今回は解答とコードが短くなったためまとめて折りたたみ

A問題に続いて、「任意の解答を一つ答えれば良い」タイプ。
なるべく短い実装方法で、歩き方がリンディと絶対一致しないものを考える。

……リンディと全く逆の歩き方でいいよね？と気がついたので素直に実装。
(リンディが南に歩くタイミングで東に歩き、東に歩くタイミングで南に歩く。)

T = int(input())

for i in range(T):
    _ = input()
    rival = input()
    newans = ""
    for c in rival:
        if c == "S":
            newans += "E"
        else:
            newans += "S"
    print("Case #{}: {}".format(i + 1,newans))

これで解決。Nなんていらなかった。

C問題は正答できるようにならないといけないので時間がかかります。多分ラウンド1より遅くなる。