差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0323_agc032 [2019/04/19] – ikatakos | programming_algorithm:contest_history:atcoder:2019:0323_agc032 [2019/04/19] – ikatakos | ||
|---|---|---|---|
| 行 14: | 行 14: | ||
| * 数列 b1,b2,...,bNb1,b2,...,bN がある | * 数列 b1,b2,...,bNb1,b2,...,bN がある | ||
| - | * 空の配列 aa に以下の操作を NN 回繰り返して bb と同じにできるか判定し、可能なら操作手順を示せ | + | * 空の数列 aa に以下の操作を NN 回繰り返して数列 |
| * ii 番目の操作では、1≤j≤i1≤j≤i なる jj を1つ選び、aa の jj 番目に整数 jj を挿入する | * ii 番目の操作では、1≤j≤i1≤j≤i なる jj を1つ選び、aa の jj 番目に整数 jj を挿入する | ||
| * 1≤N≤1001≤N≤100 | * 1≤N≤1001≤N≤100 | ||
| 行 28: | 行 28: | ||
| 最後に挿入した数字は、ai=iai=i となっているはずである。 | 最後に挿入した数字は、ai=iai=i となっているはずである。 | ||
| - | そのような箇所が複数ある場合は、1つ前の状態を考えると、一番右を最後に操作しないと困ったことになる。 | + | そのような箇所が複数ある場合は、1つ前の状態を考えると、一番右を最後に操作したことにしないと矛盾が発生する。 |
| i | i | ||
| - | a | + | a |
| | | ||
| i=3を最後に操作したことにすると、1つ前の状態は | i=3を最後に操作したことにすると、1つ前の状態は | ||
| 行 87: | 行 87: | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| - | なんかこういうのは、サイコロの対面が必ず7になるように、和が同じになるペアに着目するとうまくいきそう。 | + | 自身の頂点の和を調整するために、ある辺を無くすと、その相手の和にも影響してしまうため、考え出すとこんがらがる。 |
| + | |||
| + | こういうのは、サイコロの対面が必ず7になるように、和が同じになるペアに着目するとうまくいきそう。 | ||
| １ ２ ３ | １ ２ ３ | ||
| 行 99: | 行 101: | ||
| ある頂点から、他の全ての頂点に辺を張った完全グラフを考える。 | ある頂点から、他の全ての頂点に辺を張った完全グラフを考える。 | ||
| - | 自身に対する辺のみが無いので、頂点 vv に隣接する頂点の和は S−vS−v となる。 | + | 自身に対する辺のみが無いので、このままでは頂点 vv に隣接する頂点の和は S−vS−v となる。 |
| ここで、ペアへの辺を1本だけ無くすと、S−TS−T となり、これは全ての頂点で同じとなる。 | ここで、ペアへの辺を1本だけ無くすと、S−TS−T となり、これは全ての頂点で同じとなる。 | ||
| 行 105: | 行 107: | ||
| ==NN が奇数の場合== | ==NN が奇数の場合== | ||
| - | T=NT=N （頂点 NN だけぼっち）となるので、上記と同様に構築すると、完全グラフの時点で頂点 NN は $S-v=S-T$ となり、他の頂点と等しくなっている。 | + | T=NT=N とする。頂点 NN だけぼっちとなる。上記と同様に構築すると、完全グラフの時点で頂点 NN に隣接する頂点の和は S−TS−T となり、他の頂点と等しくなっている。 |
| <sxh python> | <sxh python> | ||
| 行 232: | 行 234: | ||
| 【こういう風に、毎回indexを定義しなおさなくてもよい】 | 【こういう風に、毎回indexを定義しなおさなくてもよい】 | ||
| i 1 2 3 4 5 6 7 8 9 | i 1 2 3 4 5 6 7 8 9 | ||
| + | | ||
| p 5 3 4 7 6 1 2 9 8 | p 5 3 4 7 6 1 2 9 8 | ||
| , | , | ||
| 行 355: | 行 358: | ||
| グラフを作って最短経路で解く。 | グラフを作って最短経路で解く。 | ||
| - | 通過する頂点は、位置を変化させない数字。通過しない頂点は、位置を変化させる。 | + | 通過する頂点は、位置を変化させない数字。通過しない頂点の位置を変化させる。 |
| 通過する頂点の位置を変化させないために、その間で前や後ろに持っていく必要のある数字の移動コストが、辺のコストになる。 | 通過する頂点の位置を変化させないために、その間で前や後ろに持っていく必要のある数字の移動コストが、辺のコストになる。 | ||
| 行 448: | 行 451: | ||
| * b+db+d で MM 以上なのだから、c+dc+d は MM 以上 | * b+db+d で MM 以上なのだから、c+dc+d は MM 以上 | ||
| - | よって、組み替えた後も MM未満/ | + | よって、組み替えた後も MM未満/ |
| また、a+c≥a+ba+c≥a+b、b+d≥c+db+d≥c+d が成り立つので、最終的な XX の値も X左≥X右 となり、常に改善される。 | また、a+c≥a+b、b+d≥c+d が成り立つので、最終的な X の値も X左≥X右 となり、常に改善される。 | ||
