SRM561:div1 medium CirclesGame

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

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

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

問題概要

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

解法

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

ソースコード

感想

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

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

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