2017-06-14 - HIR180's diary

競プロ再開します。(今回はマジです。) 最近やった問題のまとめ的なことをします。

Rabbit Party (500pts)

クリークを全て調べて終わりです。(575)

引っ越し (550pts)

つながれた風船 (550pts)

高さで二分探索することを考えると、結局N個の円があった時すべての円が含む点が存在するか否かを判定すれば良くなる。

2円の交点と各円の中心を考えれば十分。

夕食 (550pts)

良問。そのままDiv1Medに使えそう。解法は食堂に使うべき順番(Ci+i*pの大きい順)が決まるので、食堂を0個、1個、2個...使う場合の幸福度を順に計算してmaxをとればOK.

Reverse Sort (600pts)

解の上限は9なので、8以下にできるかを考える。区間を選び反転する操作は可逆なことに気づけば半分全列挙のノリですり合わせるだけ。(カンニングしました。)

ほぼ周期文字列 (600pts)

sa+lcpを貼って、Tだけずらした文字列同士に対してグチャグチャやると通る。ハッシュを使った解法の方が綺麗に書けます。

最強の呪文 (700pts)

良問。解法は後ろから見て(dp[v] = (vからゴールに至る辞書順最小の文字列)とする)ベルマンフォードをする。存在しない場合を弾くのが難しくて結局良く分からないまま通してしまった(反省)。

800pts以上はなかなか手がつかなさそうですが国内予選まで頑張りたい。