cafelier@SRM

SRM465

SRM | 00:24 |

SRM465 の成績・ソース (要ログイン) : AC/AC/- : スピード勝負はなかなか厳しいなあ

250開く

• Lv2が600だったので恐れを成して250を先に開きました。
• 問題文よみにくい…
• 『xy平面上のn個の点から2点を選んで、それぞれの点が中心になるように、変の長さが自然数の正方形を置きます。回転させても構わないので、重ならないように置きます。置き方は何通り？』
  • n≦50
  • 座標は±10000の範囲

• テストケース作成
  • (0,0)と(0,1)に点があるやつが最小
    • これは…置けるか。両方にサイズ1の正方形で。
  • 最大も適当に追加。

• とりあえず二点の選び方全通り(50*49/2≦1250通り)を全部試す
• それぞれで置き方を数えて足し算
• これで十分だろう。

• それぞれの置き方は？
• 回転してもいいというのは…あー、二つ平行に置くのがベストか。一番重なりにくい。
• 点どうしの距離が d として、辺の長さAとBとすると、
  • (A+B)/2≦d なら重ならない
  • ≦でいいんだっけ。ピッタリくっつく場合は…（問題文再読）…OK。これも重ならないにカウント。

• 式変形して
  • A+B≦2d なら重ならない
  • AとBは整数だから、A+B≦(int)2d なら重ならない
  • n=(int)2d とすると…
    • A=1 なら、B=n-1,n-2,...,1 のn-1通り
    • A=2 なら、Bはn-2通り
    • …
  • つまり全部で、n-1 + n-2 + ... + 1 通り
  • 等差数列の和の公式。(n-1)*n/2 通り

• できた
• サンプル通った。submit！

600開く

• また問題文が読みにくいぞ…
• 『xy平面上にc個の砲台があります。b個の敵の基地もあります。p個の敵のエネルギー供給基地もあります。砲台から距離dのところに一発ビーム撃つのはd^2の燃料が要ります。同じ砲台から何発ビーム撃ってもいいです。b個の基地全部を、最小の燃料で機能不全にしてください。』
  • 機能不全にするには、ビームを直接打ち込むか、
  • その基地から距離r以内にあるエネルギー供給基地全部にビーム打ち込むか
  • どっちか。
  • たしかc,b,p≦50

• 色々ややこしいけど整理しよう

• どの砲台から何発うってもいいので、ビーム撃つなら常に一番近い砲台から撃てばいい
  • つまり、それぞれの基地/エネルギー供給ごとに「燃料いくつで壊せるか」は前もって計算できる
  • O(c(b+p))
  • 計算した

• あと、距離r以内にあるかどうかも前もって計算して
• エネルギー供給してたら辺を繋ぐ、というグラフを作れる
  • O(bp)
  • これ二部グラフになるなー。

●　●　●　　基地
｜×｜／
☆　☆　　　　エネルギー供給

• こんなの。

• で、これを計算してしまえばもうrとcは忘れていい。
  • 上のようにつくったグラフのそれぞれのノードに破壊に必要なコストが計算済みだから、
  • 「以下を満たし、コストが最小になるようなノードの集合を求めよ」
    • 各 ● について、●自身が含まれているか、またはその●から繋がってる☆全部が含まれるかのどっちか

• これを求めればいい。
• なんか典型問題っぽくないかな。
• 要は、「全ての辺●－☆についてどっちかの端点は入っているような集合でコスト最小の物」だ。
  • どっちも入ってないような辺があったらその●基地は機能不全になってないし
  • 逆に全部入ってたら全部死んでる。

• これは…最小コスト点カバー…？はNP完全と思いきや二部グラフならなんとかなりそうだけど…
• えーっと
• うーんと
• なんか最大流か最小費用流だと思うんだけど、
• そのためには、「基地などを壊すコスト」を点ではなくて辺に乗せてやらないとフローの問題にならない。
• というわけで無理矢理●と☆を引き延ばして辺にする。

　　src
　／｜＼（容量∞）
●　●　●
｜　｜　｜　　基地（辺の容量は壊すのに必要な燃料の量）
●　●　●
｜×｜／（容量∞）
☆　☆
｜　｜エネルギー供給（辺の容量は壊すのに必要な燃料の量）
☆　☆
　＼｜（容量∞）
　　dest

• 上から下が繋がらなくなるように切るにはどうすればいいか
• このグラフの最小カットだ！

• 書いた
• サンプル通った
• submit

1000開く

• 『1～nまでのマスが１直線にある双六を対戦してます。サイコロはd面ダイスです。（マスxにいるときにyの目が出たらx+y＜nならx+yに進み、x+y=nならゴール、x+y＞nならn-(x+y-n)に跳ね返ってすすみます）。今自分の番ですがaのマスにいて、相手はbのマスにいます。自分が勝つ確率は？』
• a,b,d＜n≦5000

• 素直に確率の式を立てると
  • p[n][_] = 1.0
  • p[a][b] = Σ_{i=1..d} p[b][next(a,i)]/d

• うーむこれでは5000×5000変数の連立方程式…
• 端から順に決まっていったりしないか

• p[][] の関係式がループしているのは、最後nを越えて跳ね返ってくる場合だけのはずで…

• あと一回でゴールできる位置にいる a+d≧n 場合、
  • 確率 1/d でゴール
  • それ以外の場合、また「あと一回でゴールできる位置」に必ず行く
• ので、どの位置でも確率は等しい

• 特にbもあと一回でゴールの場合、p[a][b]=p[b][a]=Pとすると
  • P = 1/d + (d-1)/d P
  • となるから、P 求まる

• あとはループしてない。端から埋まる。
• p の式をそのまま埋めていくと O(n^2d) で…
• これはちょっとタイムアウトしそう…？
• まあ書いてみよう。
• 書いた。
• あれ？答えあわない
• あれれ？
• タイムアウト

感想

• 250点は下手にやるとint溢れるという撃墜ポイントを見落としてしまった。情けない
• 600点は、●や☆を伸ばして辺にしなくても、仮想src/destからの辺に容量を乗せればいいだけだった。余計なことをしてしまった。

• そんなに速くは解けなかったせいで特別良い順位ではないのだけど、
• このくらいの順位(40位台)を常にキープできれば悪くないかなーと思っているところです。
• あと撃墜ポイントを上乗せして時々10位台に乗り込めれば。
• まあ悪くない。