SRM 629 Div2

地表に長方形の穴が開いた。長方形の板があるから、その板で穴を完全に防げるか。板を回転させても構わない。

解けた。

Med

N人の生徒が持ってる容器の大きさとほしいキャンディの重さが与えられる。キャンディは均一の密度のものしか作れない。各生徒のほしいキャンディと実際のキャンディの重さの最小値を求めよ。

差の絶対値を足してく。最初、ほしいキャンディ以上のものは作れないと思ってた。解けた。解説読んでも凸関数とか意味のわからない話が出てきた。

Z日間、Xドルもらって、Yドルのキャンディを買っていく。最後に残るのはいくらか。キャンディがいっこも持ってないなら持ってるかねで買えるだけ買う。持ってるなら買わない。

最初は愚直にシュミレーションして48秒ぐらいかかったのでむり。O(N*Z)なので当然。DPとかもムリだろうと思った。解法を見る。

通った。

ビット列bが与えられる。b+1とbを比較し何ビット違うビットがあるか

通った。最初bit演算使おうとおもったらN <= 100だったのであきらめてstringを使った

メールボックスをすべて既読にするまでの最小ステップ

通った。

アルファベットの最初からP個の文字列のみを使った文字列が与えられる。辞書順でその文字列の次に回文を含まない文字列を探す。

P = 26の時にTLE、順番に探していたのでN²⁶かかった。末尾の方をどうしても意味ないような場合にはごっそりと飛ばす。この処理がかけなかった

8点がxyz座標のどれがどれかわからない状態で与えられる。立方体が作れるかどうか。

一点を決めといて残りの7点に対してxyzを当てていく。6⁷。あとはそれぞれ立方体ができるか判定する。xyz軸に並行でないときを忘れていてWAを出した。

数字のみからなる文字列が与えられるN個のクエリA->B、AをBに変換するってのをすべて終えたあとの結果

写経しました。

これを初めてから2日目。休みなのに終わらない。平日とか死にそう。