391.1
書き忘れてた...。
250
小文字の英字からなる文字列が複数個与えられて、ある文字列から別の文字列へのマッピングが存在するペアの数を答えよという問題。マッピングが存在するのは、ある文字列の特定の文字と、別の文字列の特定の文字が、必ず同じ場所に存在することである。
すべてのペアを書いてあるように比較して、一致するかどうかを判定するだけ。登場した最初の文字から順に新しい文字に割り当てるという、名前の付け替えをやった結果が一致するかどうかを判定しても良さそう。(汎用性は上がるかも知れないけれど、実装コストは増えるし、この問題としては違いがない。)
500
N個の箱の中に、いずれか一つの箱を開けられる鍵が一つずつ入っている。M個の箱を壊してよい時、すべての鍵を手に入れられる確率を分数で答えよ、という問題。
箱の中に自分の鍵が入っている確率は1/Nで、このときは、N-1個の箱をM-1個壊してよいという問題になる。一方(N-1)/Nの確率で、どれか別の箱が開く。次に開けられる箱は均等に発生するので、N-1個の箱をM個壊してよい問題になる。(厳密には既に開いた箱の鍵を持っている箱が残るが、その箱を開くことが自分の鍵を持つ箱を開くことと同じ条件になり、自分と同じ鍵を持つ箱を開くことはなくなるため一致している。)
後はDPでNとMの値からテーブルを埋めていくだけ。途中経過でちゃんと約分しないと終わらないので注意が必要。longでやるとオーバーフローの危険がある。
