DやE問題が難しくてCまでの3完速解き回だった。解法を思いつくのに無限時間かかって敗北…。
C - Reversible
https://atcoder.jp/contests/abc310/submissions/43617976
この問題の肝はダブルカウントしないよう処理できるかどうか。考えなければならない単語は、回文、逆順が存在する、どちらでもない、の3種類あって無限時間悩んでしまった。逆順と正順をsetに入れたデータ構造を用意し「正順setの単語が逆順setに存在するか」を調べて判定した。最後に逆順の存在する単語は1/2倍の個数、それ以外は1倍の個数として計算すれば良い。コンテスト中は「逆順と正順を同一視したデータ構造に変換できたらなあ」と悩んだが、よくよく考えると正順と逆順のうち辞書順最小のほうを選択した新たなデータ構造を用意すればシンプルに解ける。具体的には正順の単語Aと逆順の単語Bを用意して if(A<B) else if(A>B) で辞書順最小だけ選んだ場合のデータ構造を新たに構築できる。発想力のある人は良い成績を取っているようなので、どうも自分は発想力と言うかプログラミング的思考力の才能が平均値より低いらしい。
