ABC 401-500/ABC403B - Four Hidden - 競技プログラミング用 知識集積所

---

問題

ABC403B
元ネタは、RFC9110で規定されるHTTPコードの403 Forbiddenとのダジャレか。

必要知識

A問題レベルのものは省略

• 必要十分条件（未作成）
• 全探索（未作成）
• 二重ループ（未作成）

考え方

Uが当てはまる可能性がある場所を全探索する。（外側のループ）

その場所が部分列になりうる必要十分条件は、Uのすべての文字について、

• Tでの対応する場所がUと一致する
• Tでの対応する場所が?である

を満たすこと。
これをループで確認する（内側のループ）

if分岐の複雑な条件を処理する方法も参照。

解答例

解答例

注意点

全探索の範囲に注意

例えばTが10文字、Uが3文字の場合、全探索するべき位置は8か所ある。
うっかり10-3=7か所で終わらないように注意。

別解

?を全パターンごり押し全探索

4つの?にaからzを全パターンあてはめて、contains()か何かでUが部分列になっているかを探索。
全探索対象が26^4で約45万通り、1つの探索は多くとも5*6=30回以内に終わるので、よほど下手なコードでない限りTLEの心配はない。
解答例