差分
このページの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: | ||
| * 数列 $b_1, | * 数列 $b_1, | ||
| - | * 空の配列 $a$ に以下の操作を $N$ 回繰り返して $b$ と同じにできるか判定し、可能なら操作手順を示せ | + | * 空の数列 $a$ に以下の操作を $N$ 回繰り返して数列 |
| * $i$ 番目の操作では、$1 \le j \le i$ なる $j$ を1つ選び、$a$ の $j$ 番目に整数 $j$ を挿入する | * $i$ 番目の操作では、$1 \le j \le i$ なる $j$ を1つ選び、$a$ の $j$ 番目に整数 $j$ を挿入する | ||
| * $1 \le N \le 100$ | * $1 \le N \le 100$ | ||
| 行 28: | 行 28: | ||
| 最後に挿入した数字は、$a_i=i$ となっているはずである。 | 最後に挿入した数字は、$a_i=i$ となっているはずである。 | ||
| - | そのような箇所が複数ある場合は、1つ前の状態を考えると、一番右を最後に操作しないと困ったことになる。 | + | そのような箇所が複数ある場合は、1つ前の状態を考えると、一番右を最後に操作したことにしないと矛盾が発生する。 |
| i | i | ||
| - | a | + | a |
| | | ||
| i=3を最後に操作したことにすると、1つ前の状態は | i=3を最後に操作したことにすると、1つ前の状態は | ||
| 行 87: | 行 87: | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| - | なんかこういうのは、サイコロの対面が必ず7になるように、和が同じになるペアに着目するとうまくいきそう。 | + | 自身の頂点の和を調整するために、ある辺を無くすと、その相手の和にも影響してしまうため、考え出すとこんがらがる。 |
| + | |||
| + | こういうのは、サイコロの対面が必ず7になるように、和が同じになるペアに着目するとうまくいきそう。 | ||
| １ ２ ３ | １ ２ ３ | ||
| 行 99: | 行 101: | ||
| ある頂点から、他の全ての頂点に辺を張った完全グラフを考える。 | ある頂点から、他の全ての頂点に辺を張った完全グラフを考える。 | ||
| - | 自身に対する辺のみが無いので、頂点 $v$ に隣接する頂点の和は $S-v$ となる。 | + | 自身に対する辺のみが無いので、このままでは頂点 $v$ に隣接する頂点の和は $S-v$ となる。 |
| ここで、ペアへの辺を1本だけ無くすと、$S-T$ となり、これは全ての頂点で同じとなる。 | ここで、ペアへの辺を1本だけ無くすと、$S-T$ となり、これは全ての頂点で同じとなる。 | ||
| 行 105: | 行 107: | ||
| ==$N$ が奇数の場合== | ==$N$ が奇数の場合== | ||
| - | $T=N$ （頂点 $N$ だけぼっち）となるので、上記と同様に構築すると、完全グラフの時点で頂点 $N$ は $S-v=S-T$ となり、他の頂点と等しくなっている。 | + | $T=N$ とする。頂点 $N$ だけぼっちとなる。上記と同様に構築すると、完全グラフの時点で頂点 $N$ に隣接する頂点の和は $S-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+d$ で $M$ 以上なのだから、$c+d$ は $M$ 以上 | * $b+d$ で $M$ 以上なのだから、$c+d$ は $M$ 以上 | ||
| - | よって、組み替えた後も $M$未満/ | + | よって、組み替えた後も $M$未満/ |
| また、$a+c \ge a+b$、$b+d \ge c+d$ が成り立つので、最終的な $X$ の値も $X_左 \ge X_右$ となり、常に改善される。 | また、$a+c \ge a+b$、$b+d \ge c+d$ が成り立つので、最終的な $X$ の値も $X_左 \ge X_右$ となり、常に改善される。 | ||
