9/7 PKU
1214 "Accordian" Patience
「Accordian」というトランプゲームで遊ぶらしい。
ルールは、「カードの山（最初は各山１枚ずつ）が横に並んでいて、山の一番上のカードが、その左もしくは３つ左の山の一番上のカードとマッチするとき移動できる。２枚のカードは数かスートが一致するときマッチする。山が空になったら、右の山を詰めてくる。」というもの。
このゲームを、「動かせるときは動かせる一番左のものを動かす。１つでも３つでもどちらでも動かせるときは、３つ動かす。」という規則でプレイする。
最終的に残った山のカードの枚数を求めよ、という問題。
やるだけ。問題文盛大に読み違えていて（山の一番上以外は無意味になると思ってた）萎える。
1838 Banana
バナナの木がたくさんある。座標は1<=x,y<=10000。一箇所に複数はない。隣接している木は同じ地域に入る。できるだけバナナの木がたくさんあるように地域を選べという問題。
DFS×二分探索で一発。普通に2次元配列でやろうとするとTLEするはず。
1723 SOLDIERS
兵士がN人いて、それぞれは1回の動きで上下左右に1マス動くことができる。
今兵士をある水平線上に並べたい。すなわち、兵士の位置があるX,Yを用いて(X,Y),(X+1,Y),…,(X+N-1,Y)と表せるようにしたい。兵士の順番はどうでもいい。また、同じマスに同時に2人以上の兵士がいてはならない。
兵士の移動回数の和を最小にするとき、その値を求めよ、という問題。
まず、「同じマスに〜」というルールは、目標の水平線がどのようであっても、無視していいことがわかる。そして、兵士の順番を無視できることから、兵士のX,Y座標の関連付けを撤廃していいことがわかる。ここで、X,Y座標でソートする。
今、Y座標がyになるような水平線上に移動したいとする。すると、各兵士からその水平線上までの距離は|Y0-y|+…+|YN-1-y|である。ここで、これのグラフを考えると、yが[-∞,Y0]に含まれるときは傾き-N、yが[Y0,Y1]に含まれるときは傾き-N+2、…であることがわかる。よって、和が最小値をとるのはy=Y[N/2]のときである。
X座標についても同様に考える。X'i = Xi - i (0 <= i < N)とすると、X座標の最小値がxとなる水平線上に移動するときの距離は|X'0-x|+…+|X'N-1-x|となることがわかる。これも同様にして、xがX'の中央値のとき最小になる（Xはソートされているが、X'の順序は乱れているかもしれないことに注意）。
以上より最適な水平線がわかるので、普通に距離を計算すればよい。
