はまやんはまやんはまやん

hamayanhamayan's blog

MostFrequentLastDigit [SRM747 Div1 Easy]

N要素の以下のルールを満たす配列を構築せよ

  • 全ての要素が異なる
  • 0~10^9の数から成る
  • 10で割り切れる数はダメ
  • 全ての2つの要素を取ってきて和をとったときの最下位の桁を集計したときに、dが最も多くなる(タイはダメ)

n≦200, d≦9

解説

d=5のときを考えてみると、最下位が2と3の数があればいい。
最も2+3となる組み合わせが多いのは、n要素をちょうど2つに分けて、片方を2、もう片方を3とすればいい。
これを10で割り切れないよう、全ての要素が異なるように気をつけて実装する。
以下の実装は丁寧にやりすぎた例かもしれない。
floor(d/2)とceil(d/2)を使うが、d≦1のときは0が出てくるので、そこだけ場合分けする。

struct MostFrequentLastDigit {
    vector <int> generate(int n, int d) {
        vector<int> res;
        
        if (2 <= d) {
            rep(i, 0, n / 2) res.push_back(10 * (i+1) + d / 2);
            rep(i, 0, n - n / 2) res.push_back(10000 * (i+1) + d - d / 2);
            return res;
        }

        if (d == 1) {
            rep(i, 0, n / 2) res.push_back(100 * (i + 1) + 6);
            rep(i, 0, n - n / 2) res.push_back(100000 * (i + 1) + 5);
            return res;
        }

        rep(i, 0, n / 2) res.push_back(100 * (i + 1) + 6);
        rep(i, 0, n - n / 2) res.push_back(100000 * (i + 1) + 4);

        return res;
    }
};