naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Regular Contest 085

土曜の夜9時から
1完でレートちょい下げ

C - HSI (300点)

https://beta.atcoder.jp/contests/arc085/tasks/arc085_a
m回に1回起こる事象が初めて起こるのは何回目か、の期待値ってmだよね
と思って愚直に掛け算してAC

期待値Eがmになる確認

mになるのは幾何分布の期待値+1(=ファーストサクセス分布という名前があるらしい)ということで
等比級数のΣを取るとわかる

(同じgeometricを[幾何]と言ったり[等比]と言ったりするの気持ち悪いよね;等比級数(geometric series)は直訳して幾何級数とも言うけど等比級数の方が馴染み深いのでここでは等比級数で。それに対し等差級数の方はarithmetic seriesで、直訳して算術級数とも言うのだけれど、幾何分布(geometric distribution)に対して算術分布(arithmetic distribution)って何?って調べたら一定間隔ごとに離散的に分布する何かが出てきた)

p=\frac1m とおくと

  • 1回目に出る確率:p
  • 2回目に出る確率:(1-p)p
  • 3回目に出る確率:(1-p)^2p

...

  • k回目に出る確率:(1-p)^{k-1}p

期待値\displaystyle E
\displaystyle=\sum_{k=1}^\infty{k\cdot(1-p)^{k-1}p}
\displaystyle=p + 2(1-p)p + 3(1-p)^2p+\cdots
\displaystyle=(p + (1-p)p + (1-p)^2p+\cdots) + ((1-p)p + (1-p)^2p + (1-p)^3p+\cdots)+\cdots
\displaystyle=(1 + (1-p) + (1-p)^2+\cdots)\cdot (1 + (1-p) + (1-p)^2+\cdots)p
\displaystyle=(\frac1p)^2p = \frac1p = m

D - ABS (500点)

https://beta.atcoder.jp/contests/arc085/tasks/arc085_b
問題文意味わからん
と思ったら既にclar2本投げられてた
(X、Y交互に真逆の意図を持って操作していく)&(
自分の操作が相手の選択肢に及ぼす影響まですべて織り込んだ上で自分に利する(相手を害する)選択をしていくってこと、でいいのかな(こういう問題って何度読んでもそこが確信できない)
とりあえず、Xがi番目(あるいは元の手札)Yがj番目(あるいは元の手札)のときの差の絶対値を表にしてみて(2001x2001)、これでDP組んだら多分いけるんだよね、と思って
でも確信できない何かが、結局のところ、自分が何をやったらいいのか何をしているのかあやふやにしていて
時間だけが過ぎるから
パス

追記

Xが全部取る or Yに1枚残す の二択らしい。(がまだ腑に落ちてない)

E - MUL (700点)

https://beta.atcoder.jp/contests/arc085/tasks/arc085_c
読んだ

最初素因数分解してみたけど…違うんだよね。4,8,12,16,...みたいな(2,6,10,14,...に触れない)系列があるわけだし。
包除原理的な何かで計算する?いやそういう事するにしても組み合わせ数多すぎる

大きい順に見て行って、51以上の数は倍数がないから「非負なら維持、負なら捨てる」
もうちょい小さい数(2倍が存在する)を見ていって、「非負なら維持、負なら…倍数系列から借り入れてそれでも負なら系列ごと捨てる、借り入れでなんとかなるなら維持&系列の一番大きな数に系列の残高を全部移す」
みたいなことを1に至るまでしてみて
この解法だと前半38ケースぐらいがAC、残りのケースがWAだった

N=10で、3に負があって6で埋め合わせ可能な場合、3系列最大の9に残高をシフトしちゃうと、その後2に負があっても6の値が埋め合わせに使えないよね

ああ
なんかこの計算もっと賢くできない?

と考えてるうちに時間切れ

追記

最小カットで解けるらしい。→最小カットを使って「燃やす埋める問題」を解く