bouzuya.hatenablog.com

ぼうずやのにっき

第八回 アルゴリズム実技検定 (PAST) M - バランス を解いた

第八回 アルゴリズム実技検定 (PAST) M - バランス を解いた。

問題: https://atcoder.jp/contests/past202109-open/tasks/past202109_m

考察の大筋は簡単なのだけど思ったよりも難しくて 7WA になってしまった。

考えたことを書く。

頂点 i に書かれた整数を X_i とすると辺 i の条件は X_{A_i} + X_{B_i} = C_i になる。これを入力例 1 で考える。

3 2
1 2 2
2 3 1
  • X_1 + X_2 = 2
  • X_2 + X_3 = 1

これを整理すると次のようになる。

  • X_2 = 2 - X_1
  • X_3 = 1 - X_2 = 1 - (2 - X_1) = -1 + X_1

X_1 を使った P_i + X_1 または Q_i - X_1 の形に整理できる。つまり X_1 を決めればすべての頂点が決まる。

次に各頂点に書かれた整数は >= 0 なので

  • X_2 = 2 - X_1 (Q_i - X_1) から 2 >= X_1 (X_1 <= Q_i)
  • X_3 = -1 + X_1 (P_i + X_1) から X_1 >= 1 (X_1 >= -P_i)

それぞれ上限と下限になる。

X_1 = 0 と置いて頂点 1 からすべての辺をたどって各頂点の P_i or Q_i or その両方を設定する。設定した値から上限・下限を求める。上限・下限を満たせる値があれば、その値を実際に X_1 に埋めて辺をたどって頂点を埋めれば良い。

おおまかにはこんな感じ。辺や頂点をたどるだけなので O(M) ないし O(N) 程度で速度的な悩みはない。

……で実装してみると WA が消せない。諦めて解説を読む。

解説: https://atcoder.jp/contests/past202109-open/editorial/2659

解説の考察もほとんど同じ。足りていない点は P_i + X_1 かつ Q_i - X_1 の場合で整理すると P_i + X_1 = Q_i - X_1 なので X_1 = (Q_i - P_i) / 2 と決まってしまう。

実装のコーナーケースがいくつかあった。

まず X_1 を 0 にするのだけどこれを P_i + X_1 と Q_i - X_1 のどちらにどう割り当てておくか迷う。辺の走査でたどりつくこともあるので例外的に扱うのも面倒くさい。ぼくは P_i = Q_i = 0 としておいた。

閉路がありえるので P_i + X_1 が複数回くることがある。 P_i が不一致になる場合は -1 で終了する。 Q_i 側も同様。

上限・下限を求める段階。また X_1 のものが邪魔する。間違えて X_1 を含めて処理しようとするとおかしなことになる。このときの初期値も意外と面倒で 1 から伸びる辺をたどってその最小値を上限に 0 を下限にした。

解説で把握した答えが一意に決まる条件。一意に決まった答えが上限・下限に含まれていないこともある。忘れずに検査しないといけない。

こんなところかな……。大筋は簡単なのだけど意外と落とし穴の多い問題だった。

提出: https://atcoder.jp/contests/past202109-open/submissions/28820045

今日のコミット。