2022-09-07 ARC147 の B を解いた
ARC147 : AtCoder Regular Contest 147 の B を解いた。
- B - Swap to Sort
https://atcoder.jp/contests/arc147/tasks/arc147_b
- 提出: https://atcoder.jp/contests/arc147/submissions/34672276
- 解説 AC
- 操作 A は
iとP_iの偶奇の一致・不一致が変わる - 操作 B は何度繰り返しても
iとP_iの偶奇の一致・不一致は変わらない iとP_iの偶奇が一致しないものを操作 A の対象に 1 回はしないといけないiとP_iの偶奇が一致しないものの数はP_iの偶数側と奇数側で同数あるiとP_iの偶奇が一致しないもの同士を操作 A の対象とすると最小の操作 A の回数になる- つまり操作 A の回数は
iとP_iの偶奇が一致しないものの数の半分になる N <= 400で選択ソートをそれぞれ半分ずつに対してすると2 * (N/2)^2 <= 80000で 10^5 には収まる- このあたりまで考察してサンプルは通るものの WA を消せず解説を見た
- 解説によるとまず偶奇が一致しないものを先頭 or 末尾に寄せて操作 A をまとめて実行したあと操作 B だけでソートする
- たぶんぼくの解法だと操作 A を偶奇の一致しないもの同士を対象に実行できていなかったのだと思う
- ARC は解かせてくれないのでぼくは参加しない
今日のコミット。