428.1

やっとこさ行列乗算で解くべき(？)問題で正解にたどりつきました。

250

ある文字列のpermutationのうち、同じ文字が隣接しないものの数を答えよ、という問題。

C++のnext_permutationなら何も考えずにうまくいきます、だそうで。(ソートしないといけないので、何も考えずに、というのは言い過ぎだけれど。)

取り敢えず出てくる文字の数をカウントして、直前に使ったのを覚えておいてDFSするルーチンを回してみた。10文字程度だとうまくいく。全部の可能性をHashSetに入れてみたら時間が足りなかった。

500

長さがN以下でK種類以内の文字からなる文字列のうち、回文になっているものの数を答えよ、という問題。

長さXの文字列を任意のY種類の文字から作る方法が分かれば、長さX+2の文字列を任意のY+1種類から作る方法が分かる。文字の種類を増やさないには、Y通りの殖やし方があって(前後に既に出てきた文字のどれかを足す)、1種類増やすには、26-Y通りの殖やし方がある。この規則は常に一定なので、行列乗算に変形できる。問題はそれだと長さNのものしか計算できないので、計算の仮定で生じる各文字数のものの合計を流し込むための行を一つ追加してやる必要がある。(状態遷移図を書けば分かりやすいかも。)

コンビネーションをうまく使ってやってもいいみたい。空白文字を足してやって、空白文字についてはちゃんと割り算するとかなんだろうか？詳細は不明。

1000

長さNの盤面にLないしOの好きな石を交互に置いて、LOLの並びを先に作った方が勝ちとするとき、結果はどうなるか答えよ、という問題。勝つ場合は最速で、負ける場合は最遅で手を選択するとして、手数を答える。

両端にEとか追加して、盤面を持っておいて、(E|L|O)\s+(E|L|O)みたいなのに盤面を分割して持つようにしてやればいいのかなぁ、という感じ。端は2文字持ってないといけないかもしれないから、結構微妙かも。