AtCoder Regular Contest 154 A～D 自分が考えたやり方

# A - Swap Digit

問題：[A - Swap Digit](https://atcoder.jp/contests/arc154/tasks/arc154_a)

十進数で同じ桁数の数値が2個与えられるので、対応する桁を好きな個数入れ替えて、積を最小にしたい。

2個の数値の積を、ある桁の値 `a, b`、その桁に対応する係数 `k`、残りの部分 `X, Y` を用いて、
`(X + k * a) * (Y + k * b)` と表す。
(たとえば、`a = 2, b = 5, X = 103, Y = 406, k = 10` として、
`123 * 456 = (103 + 10 * 2) * (406 + 10 * 5)` と表せる)
これを展開すると `X * Y + X * k * b + Y * k * a + k * k * a * b` となり、
`a` と `b` の入れ替えはこのうち `X * k * b + Y * k * a` の部分のみに影響する。
この部分は、`k` でくくって `k * (X * b + Y * a)` と表せる。

このように2個の値の積の足し算を行う場合、なるべく小さい値と小さい値、大きい値と大きい値を組み合わせたほうが和が大きくなることが知られている。
(たとえば、`1 * 1 + 2 * 2 = 5 > 4 = 1 * 2 + 2 * 1`)
よって、和を最小にするには、その逆をやればよい。
`X` と `Y` の大小関係は、異なる最上位の桁で決まる。
よって、たとえば `X > Y` とする場合、`b <= a` にしたい。
`X > Y` とするには、異なる最上位の桁について `X` の方が大きくしたく、これも `b <= a` にするというのと同じことである。

よって、それぞれの桁について、小さくないほうの数字をどちらかの数値に集めてやればよい。

提出コード：[提出 #38253746 - AtCoder Regular Contest 154](https://atcoder.jp/contests/arc154/submissions/38253746)

# B - New Place

問題：[B - New Place](https://atcoder.jp/contests/arc154/tasks/arc154_b)

文字列の先頭の文字を好きな場所に移動させる操作を繰り返すことで、目標の文字列に一致させるための最小の操作回数を求めたい。

操作をk回行うとすると、最初の文字列のうち最初のk文字を除いた部分の好きな場所に、最初のk文字を挿入することができる。
(kは0以上文字列の長さ以下とする)
よって、この「最初のk文字を除いた部分」が目標の文字列に同じ順番で出てくるような最小のkを求めたい。
(目標の文字列に同じ順番で出てくる部分をなるべく長くしたい)

これは、以下のアルゴリズムで実現できる。

1. 注目する文字を、最初の文字列の一番最後の文字とする。
2. 目標の文字列の文字を後ろから見ていく。
   1. 見ている文字と注目する文字が一致したら、注目する文字を1個前の文字にする。
3. 最終的な注目する文字の次から最後の文字までが、目標の文字列に同じ順番で出てくる部分である。

提出コード：[提出 #38254758 - AtCoder Regular Contest 154](https://atcoder.jp/contests/arc154/submissions/38254758)

# C - Roller

問題：[C - Roller](https://atcoder.jp/contests/arc154/tasks/arc154_c)

数列の好きな要素を次の要素(最後の要素の「次の要素」は最初の要素)の値に書き換える操作を好きな回数繰り返すことで、数列を目標の数列に一致させることができるかを求めたい。

まず、操作を行った後の数列には必ず同じ値の隣り合った要素の組ができるので、目標の数列の隣り合う要素で同じ値の組が存在しない場合、操作によって一致させることはできない。
すなわち、一致させることができるのは最初から目標の数列に一致している場合のみである。

次に、数列に同じ値の隣り合った要素の組があるとき、操作を繰り返すことで数列のローテート (数列をある場所で2個に分割し、前の部分と後ろの部分を入れ替える) が可能である。
たとえば、操作を行う要素を`[a]` のように表すとすると

```
a[a]b c
a b[b]c
a b c[c]
a b c a
```

のように1要素ずらすことができ、これを繰り返すことで任意の要素数ずらすことができる。

さらに、操作は「ある要素から前に向かってその要素の値を塗っていく」と考えることができる。
「塗り重ねる」こともでき、例えば

```
1 2 3 4 5 6 7 8 
1 5 5 5 5 6 7 8 (5を塗った)
1 5 5 6 6 6 7 8 (6を塗った)
```

のようにできる。
このとき、適当に始点(この例1)と終点(この例では8)を決めると、終点の値は必ず塗られずに残る。
また、前の値に後ろの値を塗り重ねることはできるが、逆はできない。
よって、

1. 操作前の数列の最初の要素を、注目する要素とする。
2. 目標の数列のそれぞれの要素について、前から順に以下を行う。
   1. 注目する要素が目標の数列の対象の要素と同じ値になるか、最後の要素になるまで、注目する要素を1個後ろの要素にする。
   2. 注目する要素が目標の数列の対象の要素と同じ値にならなかった場合、目標の数列にはできないと判定し、終わる。
3. 最後まで目標の数列にはできないと判定されなかったら、目標の数列にできると判定する。

これを、操作前の数列をローテートしながら行い、1回でも目標の数列にできると判定されたらできると判定する。
ただし、最初に考えた「目標の数列に隣り合う要素で同じ値の組が無く、最初から目標の数列に一致していない」ケースはできないと判定する。

提出コード：[提出 #38265256 - AtCoder Regular Contest 154](https://atcoder.jp/contests/arc154/submissions/38265256)

# D - A + B > C ?

問題：[D - A + B > C ?](https://atcoder.jp/contests/arc154/tasks/arc154_d)

1～N の整数の順列 (1～Nの整数が1個ずつ含まれる長さNの列) が決まり、その長さだけが与えられるので、
位置i, j, k を指定した「i番目の値 + j番目の値 > k番目の値 か？」という質問を繰り返すことで、順列を特定したい。

まず、「1」の位置を特定する。
k≧2のとき「1 + 1 > k」は偽なので、i以外の全ての位置jについて「i番目の値 + i番目の値 > j番目の値」が偽であるような位置iがわかれば、それが「1」の位置である。
仮の「1」の位置をxとし、残りの位置kについて「k番目の値 + k番目の値 > x番目の値」かを質問していく。
答えが真である場合は、そのままにする。
答えが偽である場合は、仮の「1」の位置をkに更新する。
このとき、「k番目の値 + k番目の値 ≦ x番目の値」が成り立ち、k番目の値は1以上なので、「k番目の値 < x番目の値」が成り立つ。
すなわち、普通に配列の最小値を求める時の

```c
int minPos = 0;
for (int i = 1; i < length; i++) {
    if (array[i] < array[minPos]) minPos = i;
}
```

のような処理がこの質問を用いて実現できる。
i番目の値が「1」のとき、i以外の全ての位置jについてi番目の値 + i番目の値 > j番目の値」は偽、「j番目の値 + j番目の値 > i番目の値」は真になるので、この方法で、(順列の長さ - 1) 回の質問で「1」の位置を特定できる。

次に、対応する値の昇順で、「位置」のソートを行う。
今回扱う値は1刻みなので、異なる値a, b について「a > b」と「a + 1 > b」は同値である。
よって、これを比較操作としてソートを行うことができる。
マージソートを用いると、順列の長さを$N$ としたとき、$\lceil \log_2 N \rceil$ ラウンドでそれそれ高々 $N$ 回の比較をすることでソートできる。
よって、1回の比較は1回の質問でできるので、質問の回数は高々 $N \times \lceil \log_2 N \rceil$ である。

前半の「1」の位置を求める処理と合わせると、質問の回数は高々$N + N \times \lceil \log_2 N \rceil$ である。
$N = 2000$ のとき、この値は $2000 + 2000 \times 11 = 24000$ なので、制約の「25000回以下」を満たせる。

提出コード：[提出 #38260007 - AtCoder Regular Contest 154](https://atcoder.jp/contests/arc154/submissions/38260007)