AGC032 参加メモ
https://atcoder.jp/contests/agc032
A, Bの2完でパフォーマンスは1797でした。 青パフォ出たのは嬉しかったですが、もう少し早くA, Bを解きたかったという気持ちもあります。
A
逆順に考えて解きました。 つまり、最終状態からj番目の要素を削除する操作を繰り返して、全消しできるかを検証しました。 削除する過程で削除候補が複数ある場合、最も後ろの要素を削除しました(ここ、直観的ですが)。
逆順に考える、という発想が難産で解くのに23分かかりました。 ABC120-Dのように逆から操作を考えると簡単な問題は多いように思えるので、逆を試す習慣はつけておきたいところです。
B
結論は、Nが偶数のとき(1, N), (2, N - 1), (3, N-2), ... を除く辺をすべて使ったグラフ、Nが奇数のとき(1, N-1), (2, N-2), (3, N-3), ... を除く辺をすべて使ったグラフが解です。
ポイントは、
- Nが偶数のとき、1+2+...+Nは(N+1)の倍数なので、頂点の和がN+1になるようにグループを分けられる
- Nが奇数のとき、1+2+...+NはNの倍数なので、頂点の和がNになるようにグループを分けられる
グループ分けしてしまえば、他グループのすべての頂点との間に辺を張るだけです。
最初、2部グラフにするだけじゃんと思ったのですが、和が奇数の場合にどうするんだ?となって、そもそもN=5の解を見つけるのに苦労しました。 とはいえ、K部グラフにするという方針は合っていたので、もう少し落ち着いて問題に向き合っていればなあと感じました。
C
オイラー閉路の存在条件から、すべての頂点の次数が偶数であることが必要なのは分かりました。 さらに3つのサーキットを作るには、次数が6の頂点が存在する、または、次数が4の頂点が2つ以上存在するのどちらかを満たせばよいと考えたのですが、後者が不十分でした。
公式の解説の通りで、次数4の頂点が2つの場合が罠ですね。 ていねいに場合分けして考察すれば十分解ける余地のある問題だと思います(つまり、精進不足!)。
起きたら自分でもコードを書いて通したいですね。とくに、次数4の頂点が2つ存在するときに、それらの頂点間のパスが2つのみ存在するかの判定処理くらいはサクッと書けるようにしておきたいです。