Codeforces Beta Round 62

スポンサーリンク

A. Irrational problem

剰余で一度も減らないということなので,$\min(p)$ 未満という条件です.順序を入れ替えても判定は変わりません.

B. Energy exchange

送らなくてはいけない量に減衰率をかけた値が,受けとらなければいけない量以上でなければいけません.この条件で二分探索します.その値は各頂点が受け取るか送るの一方だけになるようにすれば実現可能です.

C. Synchrophasotron

全探索可能です.単純には $6^{15}$ 通り程度ありそうですが,頂点での流量の釣り合いで決まるものをがあるので,全部で $6^10$ 通り程度の状態しかありません.

D. Half-decay tree

加算クエリでは,単に部分木の和が計算できるようにしておきます.

求値を考えます.まず根の左右のどちらで崩壊が起こるかで場合分けをします.部分木和が小さい方で崩壊が起こる場合は,potential が確定するというのがポイントです.残りの興味がある方について子に進んで再帰的に解きます.

再帰の各段階では,根からそこまでの和,他の成分で確定している最大の和などを持てばよいです.常に片方の子にしか進まないのでクエリあたり $O(h)$ 時間です.

E. Contact

たいへん.

場合分けが網羅できていることを確信するのが難しいですが,$k$ 個の点から作った三角形 $4$ つを入力としたときに $k$ 以下の答を出力するかどうかでストレステストできるので,それに気づいてかなり気楽になりました.

  • $4$ つの三角形からそれぞれ 1 辺を選んで長さ 4 のサイクルを作る
  • 長さ 3 のサイクルを作る(三角形 $3$ つの位置関係が決まる,三角形をつける向きで何通りかある)→ 残り 1 個の三角形との位置関係を調べる
  • 辺で貼り合わせる.というのを $2$ 組作ってそれらの点集合を重ねる.
  • 辺で貼り合わせたあといい感じに三角形をつけることを $2$ 回やる.

などを実装しました.

適切な eps の大きさなどは検証していません.この辺出題側も解答者もどのくらいちゃんと証明しようとしているのか謎(特にかなり古い時代のコンテストだしなあ).

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました