久々にPKU記をつけることにしました

PKU

JOI予選で満点がとれなかったのでPKUを年内に100問解く決意をしたのですが、解法の復習はやはり勉強になるということで記録をつけます。

12月13日

1. PKU 1406

先に和を全部列挙しておいて二分探索とかで探す。二分探索じゃなくても間に合いそうだけど。

2. PKU 1505

二分探索で最小の和を求めて、後ろからgreedyに分割していく。

3. PKU 1598

文字列処理。やるだけ。

4. PKU 1591

配列処理。やるだけ。

5. PKU 1707

Wolfram Alphaの力を借りて解埋め込みました本当にごめんなさい。

12月14日

6. PKU 1037

DP+探索。

まず、 dp[d][n][i][j] を、「板の数があとn枚あって、次に来るべき板が最後の板より高いときd == 0、そうでないときd == 1で、最後の板より高い板があとi枚、低い板があとj枚残っているときに、あと何とおりの冊ができるか」を表すものとしてDP。


で計算できる。

後はそれを使って普通に探索してC番目の冊を求める。

7. PKU 1715

探索するだけ。

8. PKU 1717

DP。

dp[n][s]を、「1〜nまでのドミノを使って、上の列の和 - 下の列の和 = s とすることができるなら、そうするために必要な回転の最小数、できないなら∞」としてDP。

9. PKU 2018

二分探索。

10. PKU 2139

Floyd

11. PKU 2138

文字列を長さ別にまとめて、最初のやつから到達できるかどうか長さ順に判定していく。

12. PKU 2137

DP。

1番目の牛の場所をs番目に固定して、dp[i][j]を、「i番目の牛の場所がj番目のとき、最初の牛からそこに到達するまでの最短距離」としてDP。これを全てのsについて行う。

13. PKU 2136

やるだけ。

14. PKU 1320

を満たす整数 x, y (1 < x < y) を求める問題になる。

15. PKU 1264

凸包 + 点の内外判定 + 多角形の面積