AOJ 12/2

2014-12-02 | [Competitive programming]

1321

枝刈り探索．以下のことをしたら通った：

• ヒントマスとの隣接関係が同じマスたちを同一視し，同一視したグループごとにその中にある宝箱の数を定める
• 途中で，その後いくら深く探索しても周囲の宝箱の数を満たせないヒントが出てきたら，枝刈り
• また，現状どうやっても現在の最良値を超えられないことがわかったら，枝刈り

2455

問題文が読みづらいが，読みやすいページ を見ると 「多項式 f について，f(x) = f’(x) = 0 の最小の正の整数解を求めよ」であることがわかる．

ところで，この条件は「f(x) = 0 の最小の正の重解を求めよ」である．x^n で割ってやって最低次の項を 0 次にすると， a が求める解であるためには a^2 が 0 次の項の約数になってないといけないことがわかる． 適当にやると，0 次の項の平方因子が求められるので，その約数についてのみ調べればよい．

ある数が答えになっているかどうかは，適当に mod をとって 0 になるか確認してやるとよい．

2341

trie を作った後に，根を始状態かつ唯一の受理状態とする NFA を作る． すると，NFA の受理状態列のうち，対応する文字列が辞書順 K 番目になるものを求める問題になる． あとは定数倍最適化