517.1

解けなかったのにレートが上がるとみじめな気分になる。

250

ある数が与えられる。数Aに対してある操作を行うと、2以上の値にBとCに分割され、A=B*Cが成り立つ。このとき、BとCとして可能なペアが複数ある場合、そのうちのどれか一つにランダムに決定される。初期値が与えられたとき、目的の値をこの操作を繰り返すことで得ることができるかどうか判定せよ、という問題。

要は、約数を全部列挙してみて、再帰的に判定を行う。すべてのペアでどちらかの約数が条件を満たせば良い。メモ等も不要。

600

N個の整数をN-1箇所のswapで目的の並び順にしたい。swapの適用順序として可能なものは何通りあるか答えよ、という問題。

隣接する二つのswapの間にはどちらが先かの順序が決定でき、かつこの順序さえ決定すれば二つ以上離れたswapについて考慮する必要がないので、もし、目的状態に到達できるのであれば、左から順に順番を決めていって、K番目のswapが何番目になっているかが分かれば、それより前に挿入するか後ろに挿入するかのどちらかであるから決定できる。

目的の状態に到達できるかどうかは、各swap位置から見て、大小関係の入れ替わっている(元々左にいたものが右にいっていて、右にいたものが左にいっている)ものが一個ずつ左右に存在することがすべてのswap位置で成り立つこと。(自分のswapでしか上下関係が入れ替わることはあり得ない。)

900

見てない。