練習メモ2-5

冷えますね。
CF 398 div2
http://codeforces.com/contest/767

A heapを使うと楽
B　題意把握できず。無念の撤退。
C　木を二回切って頂点に割り振った数字の合計が同じになるようにしろ、という問題。
DFSで切ったら0を送る実装にするとどこで切ってもいいのではい、という感じになる。
一時間くらいかかってしまった。

D　二分探索する。
具体的に、店にある商品全部をソートして、m以降全部食えるかどうか、という関数をつくってmの値を二分探索する。二分探索の中はマージソートのマージ部分みたいにやる。
こういう配列を舐める系が昔から苦手で頭がこんがらがって解けないのでなるべくデータ構造で解くようにしたほうがいいのかなあ。
二分探索はいまだに蟻本に書いてあった(lb, ub]で探索範囲が１以上の間ループっていう実装しか書けない。応用力の無さを感じる。

ARC 069
C: 最初３で割っていた。
D: ４通り試せば解けるんだけど無限に時間がかかった。
E: なんかヒープにつっこんでやってたら次の位置を見れなくて…みたいな感じで時間を浪費して死んだ。
ソートしたほうが全然簡単だった……。

Rust慣れてきたけどコンテスト中にググってしまうこともけっこう多く、時間の無駄なのでなんとかしたい。まあC++に戻ったほうが実装は早いんだろうが……。
ところでplaygroundからgist生成するの使いやすいんだけどふつうにPlayGround埋め込んだ方がよくない？という気がしてきた。