1/29 PKU
1650 Integer Approximation
分母分子がL以下の分数で、Aに最も近いものを求めよ。
Farey数列やるだけ
3683 Priest John's Busiest Day
結婚式がいくつかある。結婚式の最初か最後のD分に特別な式を行う。特別な式は同時には行えない。全部の結婚式について条件を満足できるか。
2-SAT。復元が面倒
2125 Destroying The Graph
有向グラフがある。各頂点について、「その頂点から出る辺」もしくは「その頂点に入ってくる辺」をすべて削除できるが、それぞれコストが決まっている。コストの和を最小化せよ。その手順も示せ。
コストの和を最小化するだけなら、最大流を用いて簡単に答えを出すことができる。
問題は手順を求める作業であるが、各辺が必要な条件は「その辺が使えないとすると、コストが跳ね上がる」ということである。
そこで、最大流を求めた後のグラフにおいて、重みを無視して残余グラフを考える。具体的には、余裕がある辺のみを集めたグラフを作る。すると、明らかにこの残余グラフは非連結である。ある辺を加えるとグラフが非連結になるとき、その辺に対応する削除手順が必須であるとわかる。逆に非連結にならない場合は、その辺を加えてしまう。これをすべての辺に対して行うと答えが出る。
1434 Fill the Cisterns!
水槽をいくつかパイプでくっつけたみたいな形のものに量Vの水を入れる。高さはどれくらいになるか。
二分探索
3475 Paper-, er, Transcript-Folding Game
封筒と紙の大きさが与えられる。紙は垂直または水平に半分に折ることができる。封筒に収めるために何回折る必要があるか。
やるだけ
2007 Scrambled Polygon
原点を通る凸多角形が与えられる。原点から始めて、反時計回りに辺をたどるとき、通る頂点を順に列挙せよ。
原点の次の点に注意してやるだけ
2062 Card Game Cheater
2人のプレイヤーがN枚のカードを持っていて、１列に並べる。カードを一斉に裏返した時、対応する相手のカードより自分のカードが強ければ点数が入る。カードにマークをつけたので、相手のカードは手に取るように分かる。最大何点得られるか。
最大流つかったけどそんなの多分いらない
