読者です 読者をやめる 読者になる 読者になる

SRM561:div1 medium CirclesGame

先輩にgrundy数を教えてもらったりしたので少し前に解いた。

↓参考 もとい問題概要も書いてある


Nimber(グランディー数, grundy数) メモ - antaの競技プログラミング練習日記

 

問題概要

  • 二次元の平面上に円がたくさん与えられます。
  • 任意の点を選ぶとその点を包含する円を全て消せます。
  • AliceとBobが互いに円を消し合って最後に消した方の勝ち。どっちが勝つ?
  • かならず円を消さなければない。
  • 円は交差することはない(包含はある)

解法

  • 円aに包含される円bに対し b->a のエッジを貼る。
  • するとDAGがいくつか出来ます。
  • 各々のDAGにgrundy数を求めxorを取ったものが0なら後攻、1なら先行の勝利
  • DAGの処理が結構複雑
ソースコード

感想

grundy数使う問題の解き方は割りと理解できた。

ただ、今回みたいなのはグラフの処理が複雑ですごい手間取った。

グラフマスターへの道は遠い。