7K12 blog

猫でも分かるアルゴリズム解説

ABC165 E - Rotation Matching

f:id:tkr987:20210627022716p:plain
https://atcoder.jp/contests/abc165/submissions/22916768

  • 回転するので生徒を円状に配置して考察する
  • 向かい合った頂点に辺を貼ると距離が異なるので被りづらくなる
  • 偶奇で場合分け

f:id:tkr987:20210529162420p:plain

サンプル2がヒントであり、生徒を並べたとき距離の異なる数字同士でペアにすると重複しない組み合わせが最大になりそうという気持ちになる。つまり、頂点iと頂点N-1+iで辺を貼るのが理想になる。

ただし、Nの偶奇で場合分けする必要があり(こういうところセンスが問われるが常に偶奇チェックをすると良いかと思う)偶数のときは途中から距離が同じになる。これは円状に生徒を配置してシミュレーションすると気づける(かもしれない)。したがって、偶数のときはN/2(辺数としてはN/4)から1ずらして辺を貼ると組み合わせ最大になる。

 

感想: 奇数のときしか自力ACできなかった