Codeforces Beta Round #19

Codeforces

研究室の後輩たちがだいぶ頑張ってるっぽいのでプレッシャーを感じつつ。

  • -

A. World Football Cup

問題：W杯の予選リーグをnチームでやった結果が与えられるので、上位n/2チームを出力する。

  • 順位は「勝ち点⇒得失点差⇒総得点」で決める。
    • これで同着になるチームが出る試合結果は与えられないものとして良い。
  • nも最大50と小さいので素直に勝ち点計算をするだけ。
  • と言いつつ、結構時間がかかってしまったので反省。

B. Checkout Assistant

問題：n個の品物を買うんだけど、品物iを買う隙に、そのうちti個は盗む事ができる。購入順は任意に決められるとき，n個の品物を手に入れるための最小コストは？

  • nは最大2000。各品物についてtも最大2000，値段は10^9以下。
  • 「i番目の品物を購入する = ciのコストで(ti+1)個の品物を買った」と解釈できる。
  • こう置き換えて、n個以上の品物を購入するための最小コストをDPで求める。
    • 計算量はO(n^2)なので時間は余裕。

C. Deletion of Repeats

問題：文字列から長さ最小のスクエアのうち最左のものを選び、その左半分およびそれ以前のすべての文字を削除する処理を繰り返す。最終的に選られる文字列は？

  • 文字列長が最大10万，1つの文字は高々10回しか現れない。
    • 2乗時間かけてナイーブにスクエア列挙しちゃうとアウト。
  • というわけで、1つの文字が高々10回しか現れない制約を使って頑張る
    • v[i] : i文字先に同じ文字が存在する場所を格納する配列
    • 各文字ごとにv[i]に入る要素を調べていく。
      • Σv[i].size() は高々(10*10*文字列長)で済む。
    • v[i]に連続した数字がi個並べばスクエアがあると分かる
  • スクエアを見つけたらその左の文字が全部消えちゃうので，新たなスクエアは出現しない。
  • なので、小さいスクエアから順にしらべてどんどん文字列をカットすれば良い。
  • 適当に実装したら2REを喰らったので、適当に実装し直したら通った。何だこれ。
  • -

結果：0:15(+0) / 0:40(+0) / 1:42(+2) / -- / -- ，53位
レーティング：1820 -> 1852


序盤で時間かけ過ぎた上にCで2RE喰らってもうダメかと思いましたが、
終わってみれば何とかそれなりの順位を取る事ができました。
DもEも謎すぎるので後で良く考えてみます…。