/ 最近 .rdf 追記 編集 設定 本棚

脳log[20220511]



2022年05月11日 (水) [AtCoder] 精進。UTPC 2021-A「Make UTPC」。「A 問題は運営の想定でセット内で最も易しい問題です」。すっごく難しかったよ。■最初は長さ4の文字列をすべて切り出して「UTPC」との不一致を数えればいいと思った>提出 #31608295 (WA×13)。これはスワップによる交換回数の節約が考慮できていない。■そこで交換が1組ある場合と2組ある場合を列挙した。提出 #31608534 (WA×6)。これはスワップしていない部分が「UTPC」と一致していることを(勝手に)条件にしていて列挙に漏れがあった。■提出 #31608677 (WA×3)。一致不一致とスワップを独立して数えるようにしたら WA が3つ減った。だけどこれは3つ組4つ組が位置をローテートしている場合の交換回数の節約が考慮できていない。■提出 #31608753 (WA×3 / 列挙漏れ)。提出 #31608788 (WA×3 / 列挙漏れ)。■提出 #31609353 (WA×1)。ようやくローテートしているものを考慮することで WA が2つ減ったけど、唯一残る WA は「UTPC」との一致がゼロでスワップもゼロで「UTPC」のアナグラムでもないケース。つまり考え得る最悪のケース。全列挙して数えたけど、実は交換回数の最大は4回ではなく3回だった。■提出 #31609535 (AC)。すっごく難しかったよ。