252.1

問題をちゃんと読みましょう。

250

整数Nの各桁を並び替えてできる整数の総和を、重複するものを2度数えないようにして求めよ、という問題。

まさにC++のnext_permutationを使いましょうという問題。普通に実装してもすぐ終わるようにNは100000以下になっている。(テーブル用意して重複検査できる。)

500

ある点を中心に回転する扇型の領域に入らないように、目的地に到達するまでの最小ステップ数を求めよ、という問題。各ステップでは上下左右のいずれかに移動しなくてはならない。

シミュレーション問題。ステップ数の上限を適当に決めてやれば良い。盤面の大きさが50x50で、扇型の領域は100ステップでループするので、250000ステップ計算しないと本当はいけないのかも知れないけれど、実際にはもっと状態は少ない。(次に扇型の位置が同じ場所にくるときに、同じ場所にいる必要はない、というのでループ判定して、すべての状態でループしたら到達不可能、という判定を本当はしたい。)計算量的には50000ステップくらいまでならできるけれど、1000ステップもいらなさそう。

1000

4x4の文字がある。任意の文字から上下左右に文字を一度ずつ選択していって、辞書にある単語を作成できた場合、文字数の二乗のスコアを得ることができる。16個の立方体ブロックがあり、その各面に文字が書かれているとき、それを4x4に任意に配置した盤面のスコアの期待値を答えよ、という問題。

各辞書の文字について、4x4の盤面において何通りの位置で作成できるかを考える。すべての位置について、そこにその通り文字が並ぶ確率は等しく、文字数分ブロックを選んで、正しい文字が正面を向く確率をかければ良い。この確率をDPで適当に求めて、最終的に合計すればおしまい。