243.1

これのログアウトのタイミングがかなり謎。

250

素数Pが与えられた時に、A^K=1(modP)なる最小の正整数KがP-1であるAをすべて求めよ、という問題。

Pが高々1000なので、全部試せばおしまい。(問題文を簡潔に書こうとしたら用語を知らないことに気付いたので、必要以上な記述になっているのかも。)

500

3問の問題のスコアと正解している確率のデータがN人分与えられる。自分のスコアが確定している状況で、自分以上のスコアを得る人間が4人以下である確率を求めよ、という問題。

自分以上のスコアの人間が今までにN人いる確率をDPしながら求めていくだけ。

1000

クイーン1つでキング2つのうちどちらかを捕まえるのに必要な最小手数を答えよ、という問題。キングはクイーンを取ることはできない。盤面の大きさは100x100とする。

可能な盤面を全探索＋多少の最適化という問題。まず片方のx座標を合わせると、それとx座標が一つずれた状態になり、次にもう一方のy座標を合わせるともう一方とのy座標が一つずれた状態になる。後は斜めに移動すれば両王手になるので、高々4手で詰むことは分かっている。なので、最初の2手分だけ全探索すれば問題ない。

どちらにも王手をかけない状況が最適になるケースもあるらしいので、全探索するほかないのかも。