Codeforces Round #609 (Div. 2)（Bまで）

Div2A. Equation

差が $n$ であるような2数を答える。差が $n$ のもので順番に素因数分解していこうかと一瞬思いましたが，よく考えるとギャグでした。$9n$ と $8n$ を答えてやれば差が $n$ でいずれも合成数になってくれます。

python

n = int(input())
print(9*n,8*n)

C++

# include<bits/stdc++.h>
int main(){
    int n;
    std::cin >> n;
    std::cout << 9*n << " " << 8*n << std::endl;
}

Div2B. Modulo Equality

まず問題文が分かりづらいです。置換 $p_n$ を用いてどうこう……と書いてありますが，要するに

数列 ${a_i}$ と ${b_i}$ が与えられる。数列 ${a_i + x\ (\mathrm{mod}\ m)}$ が ${b_i}$ を 適当に並び替えたもの と一致するような最小の $x$ を答えよ。

という問題です。

さて，まず脳死で思いつくこととして $x$ を全探索したいという気持ちになるでしょう。$\mathrm{mod}\ m$を考えるので $x$ として $m$ を越える分は同一視できます。しかしながらそれでも $m$ の範囲が$1\leq m \leq 10^9$なので，この範囲内をすべて探索するのは時間的に不可能です。

他の制約として，$1\leq n\leq 2000$ すなわち数列 $a$ と $b$ のサイズが2000までというものがあります。じつはこれが大切で，$x$ をすべて探索するという方針はそのままに調べる範囲を少なくすることができます。a に x 加算したものと b を適当に並び替えたものが一致するためには，a[i]+x の要素の少なくとも1つはb[0]と一致しなければいけません。

そこで，aのどれがb[0]と対応するかを全探索して，そのうち条件を満たす最小のものを出力してあげましょう。具体的には下のコードを参考にしてください。

Python

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    b.sort()
    answer = []
    for i in range(n):
        x = (b[0] - a[i]) % m  # b[0]とa[i]が一致するようにxを決める
        tmp = list(map(lambda num: (num + x) % m, a))
        tmp.sort()
        if tmp == b:
            answer.append(x)
    print(min(answer))
    return

if __name__ == '__main__':
    main()

C++

# include <bits/stdc++.h>
using i64 = int_fast64_t;
# define repeat(i, a, b) for(int i = (a); (i) < (b); ++(i))
# define rep(i, n) repeat(i, 0, n)

void solve() {
    int n, m;
    scanf("%d %d", &n, &m);
    std::vector<int> a(n), b(n);
    rep(i, n) scanf("%d", &a[i]);
    rep(i, n) scanf("%d", &b[i]);
    std::sort(begin(b), end(b));
    std::vector<int> ans;
    rep(i, n) {
        int x = (b[0] - a[i] + m) % m;
        std::vector<int> tmp(n);
        std::transform(begin(a), end(a), begin(tmp), [&](int num) { return (num + x) % m; });
        std::sort(begin(tmp), end(tmp));
        if(tmp == b) {
            ans.emplace_back(x);
        }
    }
    std::sort(begin(ans), end(ans));
    printf("%d\n", ans[0]);
}

int main() {
    solve();
    return 0;
}