TCO Round 1

432位だったのでRound 2には進めるようです．

250

価格priceの商品Aを買う際に他の商品も一緒に買うとpriceが定められた割合だけ控除されるときに最適な買い方をしたときの合計金額を求めよという問題．ただし割引率は1,2,3の三通りしかない．また他の商品の個数Nは高々50個しかない．
たとえばprice=100で他の商品が{(価格,割引率(%))}={("1 1", "1 2", "1 3")}のとき割引率が2%の商品と3%の商品を一緒に買って1+1+100*0.99*0.98=97.06払うのが最適となる．
割引率が3通りしかないので割引率ごとに分類してそれぞれの割引率の商品をどれだけ買うかをN^3で全探索して個数を固定したところでは貪欲に安いものから取っていけばいい．

500

N*3(N<=100)の長方形が与えられる．いまプレイヤーはその中から1点を選んでその点より右上の部分を全て取り除く．

* *     *
* * - > *
* *     * *

上の例は(2,2)の点を選んだ場合である．
このとき二人のプレイヤーが最適な手順でゲームを行った場合の最短終了ターン数を求めよ．ただし，勝つほうのプレイヤーはできるだけゲームを早く終わらせようとし，負けるほうのプレイヤーはできるだけゲームを引き伸ばそうとするとする．
このとき盤面の状態は各行の残りの点の数で表現でき，それは高々N^3個しかないのでメモ化再帰で解ける．

追記
250点問題は値段の一番下がるものをとるという貪欲だとうまくいかない，反例は

discounts = {"2950 3" , "1951 2" , "1951 2"}
price = 100000

で，1個目は貪欲だと"2950 3"を取って50得して，次のものをとっても良くはならないので99950を返すけど，実は最適なとり方は"1951 2"を2個とるものでこのとき解は99942なので貪欲は間違い．

最初貪欲でもいけるのかなと思ってたけど正当性が見えなかったので考えてたら割引率ごとに層別すればいいということに気づいた．challenge phaseでみたら割と貪欲が多くてしかもだれもchallengeしてなかったので通るのかなと思ってたら全部System testで落ちてた．