5/2 PKU

「やるだけ」な問題ばっかり。

2559 Largest Rectangle in a Histogram

前回O(n log n)のコードを書いていたので解き直し。
左から見ていって、高さが常に広義単調増加になるようにスタックに積んでいく。
もし、前の高さより低くなったら、広義単調増加になるように前の高さを調整する。
その時に解を更新する。
（前回のコードのほうが速いのは秘密）

3494 Largest Submatrix of All 1’s

縦方向にDP、横方向に2559

1964 City Game

3494と全く同じ

3299 Humidex

やるだけ

3517 And Then There Was One

数学ゲーらしい。ちょっとした高速化を入れればbrute-forceでも解ける

2271 HTML

やるだけ

2631 Roads in the North

DP

1973 Software Company

二分探索＋DP

1877 Flooded!

二分探索

1308 Is It A Tree?

やるだけ

3087 Shuffle'm Up

やるだけ

1930 Dead Fraction

全探査

2349 Arctic Network

最少全域木もどき