Codeforces Beta Round #62

Codeforces

久しぶりに参加記を書いてみたり。

  • -

A. Irrational problem

問題：p1, p2, p3, p4, a, bが与えられたとき、[a,b]の区間の整数xのうち、x mod min(p1, p2, p3, p4) = x になるものの個数を答える

  • 問題文が長かったのでテキトーに読んでこう理解した。
  • 単に、x > min(p1, p2, p3, p4)になる物の個数を数えておしまい。
  • 後で問題文をしっかり読んだらpermutationとか確率とか言ってて焦ったのは内緒。

B. Energy exchange

問題：バッテリーn個があって、全バッテリーの電気量が同じになるようにバッテリーからバッテリーに電気を移す。移すときにkパーセントのロスが発生するとき、最終状態の電気量は最大でどれくらい？

  • 目標電気量をxと決め打ちしてやって、需要量と供給量を比較する。
    • 需要：xに足りないバッテリーの不足分の和
    • 供給：xを越えるバッテリーの超過分の和 - 移動時のロス
    • 供給が需要より多ければ電気量xにする事は可能
  • 電気量をxにできるなら適当に浪費してx未満にもできるので、2分探索した。

C. Synchrophasotron

問題：流量下限・上限付きの枝を通じてノード1からノードnにフローを流す。可能な流量の最小値と、その流量で可能なコストの最大値を求める。

  • n≦6, 流量下限・上限はどっちも0以上5以下。
  • 制約条件が「全探索じゃね？」という甘い囁きをしてくる。
  • が、不安だったので後まわし。
  • 結局他に思いつかなかったので、思いつく限りの枝刈りを入れて探索。
  • 探索は、枝ごとに下限→上限まで1ずつ流量を増やしていく深さ優先。
  • 暫定解より悪くなったり、ノードの流出量が流入量を超えたりしたら枝刈り。
  • 結局、実行時間30msで通りました。

D. Half-decay tree

問題：完全2分木に対し、add v e(ノードvにeの電荷を追加する)、decay（ランダムに1つの葉を選んでルートから葉までのパスを除く操作を考える。このときに作られる各連結成分の総電荷の最大値の期待値を求める）の2種類のクエリを処理する。

  • ワカンネと思って適当に式を組んでたらサンプル通ってしまった。
  • 調子に乗って提出してみたらpretestも通ってしまった。
  • まぁ、普通に反例があったわけで。あとで考えよう…。
  • -

結果：0:04(492, +0) / 0:13(948, +0) / 1:52(828, +0) / Failed System Test / -- ，69位
レーティング：1856 -> 1990


自己最高レートを更新できて、ついに赤が見えてきました。
Dみたいな問題も解ければと思いますが、久々のCodeforcesとしては満足な出来でした。