397.1

プログラマ失格。500解くまで他の問題に手を出しちゃダメだろうと思う。明後日までにちゃんと解け。

250

整数配列を連続するk個の要素を反転させるという操作でソートを行う時に必要なステップ数を答えよという問題。

要素数が8までなので、どうやっても大丈夫っぽい。Hashtableをなるべく使わないようにしているのだけれど、こういうときはちゃんと使った方がいいのかも知れない。

純粋に配列を使おうとすると、short配列にしないとメモリ制限に引っかかる気がした。2^24=16Mエントリなので、4バイト使うとそれだけで他にメモリが使えないはず。

500

1^k+2^k+...+n^kを求めよ、という問題。

出題場所としては間違っていると思うけれど、プログラマなら絶対に解けないといけない問題。modulo演算になるのを利用して効率良く解く方法があればいいのだけれど、数式を色々いじらないといけないのかも知れない。どうしたものか。

追記

解いた。1^k+2^k+...+n^kはnのk+1次の多項式になるので、n=1~(k+1)まで代入した結果から、各係数を求めれば良いとのこと。連立一次方程式の解を求めれば良くて、ちゃんと精度を考慮しつつやれば問題なく動く。modulo演算の結果を返す四則演算をちゃんと実装すれば間違えないだろう。

いずれにせよ人間の手で解くような問題ではなさそうだ。

1000

見てる暇すらない。二部グラフマッチングの問題らしい。