cplusplusonly's memo

Atcoder: https://atcoder.jp/users/cplusplusonly

AtCoder M-SOLUTIONS プロコンオープン 参戦記

AtCoder の M-SOLUTIONS プロコンオープン に参戦しました。

atcoder.jp

結果は ABCE (1 WA) を取って 144 位。パフォーマンスも調子よく 2210 となりました。レーティングは爆上げで 1616 となり青色になりました。今年中に青色になれればいいなぐらいに思っていたのですが、想定外の伸び方です。
確かに始める前に前回のパフォーマンス (2332) 付近を取れば青色に手が届くというのはちらっと頭に思いうかんではいたのですが、まさか本当に取れてしまうとは...

f:id:y_r:20190601235316p:plain

今回取れた C, E はいずれも剰余の中での割り算が絡むので、

yrdev.hatenablog.com

で、 「mod の計算にちょっと強くなった気がする」といったのが実証できました。

感想

A 問題 B 問題

瞬殺

C 問題
  • 引き分けは決着を引き延ばす効果しかないのでまずは引き分けを除いて考えてよい
    • 引き分けの確率を  p とすると、最後に  1/(1 - p) を掛ければよい
    • 引き分けを考えない状態で A が勝つ確率を  q とする
  • A が最終勝利するには n 回勝つまでに B が  n - 1 回しか勝たなければよい
    • B が勝つ回数を  m (< n) とすると、この状態で決着する確率は  _{(n + m - 1)}C_mq^n(q-1)^m となる
    • 上記を  0 <= m < n ですべて足す。
  •  _{(n + m)}C_m をその都度求めていたら TLE するはずなので、  _{n-1}C_0 = 1,  _{(k+1)}C_l = _kC_{ l - 1} を利用して  (n - 1) <= k < 2n まであらかじめ計算しておく
  • B が最終勝利する確率も同じように求めれれる

でこれを愚直に実装すればよい。

D 問題

最初

  • 値をソートして辺の数が少ない頂点から割り付ける

を実装して WA をくらったので後回しにした。 C, E を解いてから

  • 木構造の中央から高い値を割り付ける

という方針に変えて (とはいえこの考察があっているかは未検証) 実装しようとしたがバグが取り切れなかった。

E 問題

Wikipedia 先生 等差数列 - Wikipedia に答えが書いてある。
 (x/d)^{\overline{n}} の計算は一見難しそうだが剰余上での演算なので、  x/d から n 個掛けた数を求めればよい。 x/d s とすると、 factorial(s + n - 1) / factorial(s - 1) で求まる。
ただし以下のコーナーケースに気を付けること。

  •  s + n - 1 が大きすぎると答えは 0 になる
    • 1000000007 の倍数になる (= 剰余が 0)
    • 閾値 1000000007 <=(s + n - 1)
  •  d = 0 のときは答えは  x^n
F 問題

見てもいない