Codeforces Beta Round #24

Codeforces

久々にCodeforcesに参加。
しばらくレーティングが水平線でしたが、今回は良い感じの順位を取ることができました。

  • -

A. Ring road

問題：n個のノードが有方向の枝でリング状につながっている。各ノードに方向を反転させるコストが定められてて、ノードを全部回れるようにするために必要な最小コストを求める問題。

  • ノード数が100くらい
  • 適当に反時計まわりと時計まわりでコストを出して小さい方を返した。

B. F1 Champions

問題：F1のレース結果が与えられて、2通りの方法それぞれでシーズンのチャンピョンを求める問題。

  • 方法1：獲得スコア -> 1位とった回数 -> 2位とった回数 -> …
  • 方法2：1位とった回数 -> 獲得スコア -> 2位とった回数 -> …
  • というわけで、ベクタに突っ込んでソートした。

C. Sequence of points

問題：平面上の点M0と，点A0, A1, ..., A(n-1)が与えられる。M0がi回目の移動では点A(i-1)%nに対して対称移動するときに，j回目の移動でMがどこに移動するかを求める。

  • 点の数nは奇数で10万以下で、移動回数jは10^18以下。
  • とりあえずx方向とy方向は独立に考えて良い。
  • なんか周期性あるんだろうなぁ…と点の数3で試してたら2周したら戻ってきた。
    • なるほど、点数が奇数だと2周目が1周目の分を打ち消していくのか。
  • という事で、2*n回の移動分を求めてから周期性を使って答えを返した。

D. Broken robot

問題：ロボットがグリッド上を[右に進む、左に進む、下に進む、待機]から外にでないものからランダムに選んで行動する。現在地から一番下の行のマスに移動するまでのステップ数の期待値は？

  • 行ったり来たりするから期待値で連立方程式を立てるのかな…？
  • とりあえず、上の行に戻る事はないから行ごとに独立に解けば良さそう。
  • だけど、行数・列数が最大1000なので連立方程式を解くのにO(n^3)は絶望的。
  • 無理かなぁ…と思ったところで、行列がすごく疎なことに気づく。
  • 三重対角行列ならO(n)で連立方程式が解けるとえらい人(※)が言ってた気がする。
    • ※研究室の同期です
  • 1行あたりO(n)の求解なら全体でO(n^2)だし間に合いそう。
  • ということで、頑張って実装して提出した。
  • -

結果：0:10(+1) / 0:21(+0) / 0:40(+0) / 1:49(+0) / -- ，26位
レーティング：1852 -> 1959


いつも50位前後だったので、喜んで良い結果ではないでしょうか。
でも、Aにて配列外アクセスで1REを出してるあたりが、いつもの自分。