2022-01-27 第八回 アルゴリズム実技検定 (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
今日のコミット。
- rust-sandbox 2 commits
- rust-atcoder 1 commit