Round1

午前3時開始で、部屋の再割り当てがあった後チャレンジフェーズ。最近事故が多過ぎやしませんか？ついでにいうとマシン再起動とか途中で入ったりもう...。(これの影響は皆無でしたが。)

250

欲しい靴の値段が与えられて、他の靴を買うとそれにつけられた値引率を欲しい靴に適用できる。値引きは重ねがけできるので、一番安くなるのはいくらか、という問題。

値引率は3種類しかないので、それぞれについて、安い順にいくつ買うかを全探索する。ループでかけるのに再起しようとしたり、高速化のためにメモしようとしたり、色々しているうちに時間ばかりが過ぎて...。再サブミットを除いたら250では過去最低点かも。

500

長方形のマス目を、好きな場所から右上すべてを取り除くという操作を二人で交互に行う。一番左下のマスを取り除いた方が負けのとき、何手で終了するか答えよという問題。勝つ方は早く終わらせようとするけれど、負ける方はできるだけ長引かせようとする。初期盤面の大きさは3xNで、Nは100以下である。

現在の盤面から何手で終了するかをDPする問題。ただし、到達可能な全ての盤面について、勝てるならば最短になるものを、負けるならば最長になるものを選ぶ必要がある。

1000

問題開くくらいしかできませんでした。保留。