AGC032 B - Balanced Neighbors

atcoder.jp

グラフで考えた

隣接するグラフの頂点の番号の和が、同じになるように辺を引きましょう。という問題。前半は実際にグラフを書いていた。う〜ん難しい。

隣接行列で考える

途中で隣接行列で考えるようにすると、とても考えやすくなりました。例えばN=6のとき。それぞれの行がそれぞれの頂点と繋がってるかどうか？を考えていきます。

それぞれの合計を取ると、

こうなります。実は、逆向きに斜め線を引くと合計が同じになります。

ここまでくるとあとはこれを実装すればいいんですが、今回の制約を見ると、Nが100以下なので

• boolのN×Nの隣接行列を作って、
• 左上から右下にfalse false…とする
• 右上から左下にfalse false…とする
• 辺の数を数えて、出力する
• 辺を出力する

という風に実装していけばいいです。

Nが偶数か奇数か？で場合分けをしないと、斜め線がクロスする辺りでWAが発生します。気をつけましょう。