253.1

250

文字の出現頻度から、暗号を解読せよ、という問題。同じ頻度の場合はアルファベット順。

やや面倒な実装系。

500

2次元盤面上をアルファベット順に縦横斜のいずれかに移動する。Aから始まってN文字移動できるパスは何通りあるか答えよ、という問題。

各文字について、隣接するひとつ前の文字へのパス数の合計を計算して回る。早々に整数が溢れるので、溢れたときに計算を打ち切らないように注意する必要がある。この問題程度の計算量なら、BigIntegerとかでも問題ないかも知れない。実際にはそこそこに大きいINF値を用意しておいて、それ以上になったらそれで抑える、という処理を入れるのが妥当。

1000

野球の現在のカウントが与えられるので、ピッチャーが勝利する確率を求めよ、という問題。球種は二種類で、お互いが自分に有利になるような予想を行うとし、予想に応じた結果の確率が与えられる。

お互いの予想は鞍点があるので、三分探索を双方について行えば良さそう。後は単純なDPになる。