AGC024 A B

A Fairness

問題概要

高橋君、中橋君、低橋くんがそれぞれ数A,B,Cを持っている。「3人が同時に他の2人が持っている整数の和を求め、それを自分の持っている数に置き換える」という操作をK回行った時、高橋君の持っている数-中橋君の持っている数を求めよ。

取った方針

三人の数の総和が1回操作するごとに倍になることはすぐにわかるので、文字のま何回か操作をシミュレートしてみる。すると、Kが偶数の時は答えがA-B、奇数の時はB-Aとなることがわかるので、それを出力して終了。

正しい方針

同上

得られた知見

・複雑な操作は文字のまま考える

解くのに必要な要素

・特になし(強いて言えば数学)

周辺調査によって得られた知見

特になし

B Fairness

Backfront

任意の要素を列の先頭または末尾に移動する、という操作だけを用いてソートをする。この時の最短手数を求めよ。

取った方針

中央値に近い数から貪欲に前または後ろに飛ばしていけば最長N回でできることはすぐにわかるが、どういうときに手数が減るのかまったくわからず終了。
最小値だからできるできないで二分探索、とか操作が定義されているから最短経路、とか色々考えたけど空振りで厳しかった。

正しい方針

まず操作によって移動されない数字を考える。操作によって移動されない数字は、操作によって移動されないので、その数字のみを含む部分列を取り出した場合1ずつ増えるソート済みの数列である必要がある。
よって、1ずつ増える最長の部分列を考えて、それに含まれないものを中央値から近い順に貪欲に先頭/末尾に送れば最適であることがわかる。
以上より、1ずつ増える最長の部分列の長さを求めてそれをNから引けばそれが最短手数となる。
1ずつ増える最長の部分列の長さは、Q[P[i]] = i(Pは入力される数列)なるQを考えて、それが単調増加である最長の区間の長さを求めることでわかる。
なぜなら、上記のように定義すると、Qは、i番目にあるべきものがQ[i]番目にあることを示しており、Q[i]がx<=i<=yで単調増加であるとは、Pの部分列として1ずつ増えるxからyまでの数列を持つということだからである。

得られた知見

・入力に対する操作が与えられたとき、「操作されない要素」に注目することで解ける問題がある。
・1ずつ増加する部分列は、Q[i] = jなるQが、iがj番目に存在することを表すQを考え、それにおいて単調増加である最大長さを求めることで求められる。

解くのに必要な要素

・「操作されない要素」に注目する。
・要素が1ずつ増える部分列ならO(N)で求めることができる。

周辺調査によって得られた知見

特になし