A. Gennady and a Card Game

解答例

各トランプが2文字で与えられるので1,2文字目を比較．

B. Petr and a Combination Lock

解答例

$N<=15$に注目．時計回り／半時計回りの組み合わせを全列挙すればよい．すなわち各回転に対して+1倍か-1倍かを選んで足し合わせ，合計が360の倍数であればよい．$2^{15}=32768$であるから間に合う．

この合計は負数となり得るが，これに対してmod演算をしてしまったことに後から気付いて冷や汗をかいた．実際は負数であっても余りが$0$かを見るだけなら結果は変わらない．

C. Yuhao and a Parenthesis

解答例

括弧列は次のように分類可能：

• 左側に'('が欲しい
• 右側に')'が欲しい
• 両側とも必要
• 両側とも必要ない

これらを対応するものごとに組み合わせればよい．最初は括弧の深さ（'('のとき+1, ')'のとき-1）だけを見て，これが正であれば')'，負であれば'('が必要，0であれば両側とも不要としていた．しかしこれでは両側に括弧の補充が必要な場合を見逃してしまう（例えば本文中にある"(()))("は深さの合計は0になるが，左に'('，右に')'がなければ揃わない）．1WA．

ここでAtCoderに類題があったことを思い出した．まず左から見て'('の不足を数える：これは-1*(深さの最小値)となる（この数だけ'('を補充すれば負の深さがすべて0以上となる）．これを$p$個とする．これらを左側に補充した上で')'の不足を数える：これは開始深さを$p$としたときの右端での深さであるから，もう一度ループを回すか，あるいは先の右端での深さ+$p$とすればよい^[1]．以上より文字列が先の分類のどれにあたるかが判別可能．ここで両側に必要とするパターンは本問では組を作れないが，残る3パターンは可能：左側に$n \ge 0$個必要な括弧列に対して右側に$n$個必要なものを組み合わせればよい．

本番ではSystem Testに通らず残念な結果に．これは括弧列の文字数が$\le 5 \times 10^5$という制約の読み落としによるRE，および'('の補充を何も考えずそのまま文字列結合で行ってしまったことによるTLEの合わせ技だった．

D. Makoto and a Blackboard

(2019/03/06): こちらの記事に追加．

---

1. 掲載したコードでは後者を採用．さらに深さが$-1$になるとき，代わりにもう一つの変数$pre$にその分だけ加算している．すると深さが「左側に括弧を補った際の深さ(>=0)」という意味になるため，右端でのこの値が右側の必要個数となる．左側の必要個数は$pre$． ↩︎