Web備忘録 プログラミングを中心に技術的な事柄を忘れないように書き残します。

AtCoder Beginner Contest 156 に参加した記録

AtCoder Beginner Contest 156 に参加した記録
目次

AtCoder Beginner Contest 156 に参加した記録

AtCoder Beginner Contest 156 – AtCoder

ABC156 に参加しました。

結果はABCDの4問ACでした。今回はやらかしていません。無事Dまで解けました。全体的に数学チックな問題が多かった印象です。

E問題は30-50分くらいこねくり回しましたが。難しかったです。

パフォーマンスは水色でした。最近D問題30-50分くらいが安定してきたような気がします。

ということで問題を振り返ります。

A – Beginner

A – Beginner

高橋君はプログラミングコンテストサイト「ButCoder」の会員です。

ButCoder の会員には 2 つのレーティング 内部レーティング と 表示レーティング が割り当てられています。

表示レーティングは、その会員のコンテスト参加回数が 10 以上のときは内部レーティングに等しく、そうでないときは、会員のコンテスト参加回数を K として、内部レーティングから 100×(10−K) を引いたものになります。

高橋君のコンテスト参加回数が N で表示レーティングが R であるとき、高橋君の内部レーティングを求めてください。

AtCoder のレーティングをテーマにした問題です。普段のA問題に比べて問題文が長いですが、条件分岐して計算式をそのまま実行すればよいです。

Rが表示レーティング、Nが参加回数です。求めるのは内部レーティングです。

参加回数が10未満の時は 100×(10−K) が引かれたレーティングが表示されているので、これを足せば内部レーティングが求まります。

var ans = R;
if (N < 10)
{
    ans += 100 * (10 - N);
}
Console.WriteLine(ans);

B – Digits

B – Digits

整数 N を K 進数で表したとき、何桁になるかを求めてください。

制約

入力は全て整数である。

  • 1≤N≤109
  • 2≤K≤10

シンプルな問題です。10進数をK進数に変換するのは情報処理の試験問題でもよく見かけます。

C#だと標準ライブラリにK進数に変換する関数が用意されてますが、普通に割り算をループして実装できます。

var ans = 0;
while (N > 0)
{
    ans++;
    N /= K;
}
Console.WriteLine(ans);

これは以下の計算方法をコードに落とし込んだものになります。

125 を 8 進数にする方法
125 ÷ 8 = 15 余り 5
 15 ÷ 8 =  1 余り 7
  1 ÷ 8 =  0 余り 1

余りを下から並べて 175 が答え

K進数に変換するとき、商が0になりまでKでの割り算を繰り返します。今回は桁数を求めたいので、割り算の実行できた回数が答えになります。

C – Rally

C – Rally

数直線上に N 人の人が住んでいます。

i 番目の人が住んでいるのは座標 Xi です。

あなたは N 人全員が参加する集会を開くことを考えています。

集会は数直線上の任意の 整数値の座標 で開くことができ、座標 P で集会を開くとき、i 番目の人は集会に参加するために (Xi−P)2 の体力を消費します。

N 人が消費する体力の総和としてありえる値の最小値を求めてください。

制約

  • 入力は全て整数である。
  • 1≤N≤100
  • 1≤Xi≤100

(Xi−P)2 という計算は正負を無視してPからの距離の大小だけが問題になります。つまり Xi の範囲が 1≤Xi≤100 なので Pの座標も 1≤P≤100 に収まります。

なのでPの候補の座標を単純に全探索しても O(10000) なので十分間に合います。

var ans = long.MaxValue;
// i は P の座標の候補
for (int i = 1; i <= 100; i++)
{
    var now = 0L;
    foreach (var x in X)
    {
        now += (i - x) * (i - x);
    }
    ans = Math.Min(ans, now);
}
Console.WriteLine(ans);

これは簡単なC問題でした。

D – Bouquet

D – Bouquet

あかりさんは n 種類の花を 1 本ずつ持っています。

あかりさんは、これらの花から 1 本以上を選び、花束を作ろうとしています。

ただし、あかりさんは a と b の 2 つの数を苦手としていて、いずれかと一致するような本数の花からなる花束は作ることができません。

あかりさんが作ることのできる花束は何種類あるでしょうか。

(109+7) で割った余りを求めてください。

ここで 2 つの花束は、一方では使われているが、 もう一方では使われていない種類の花があるとき、別の種類の花束であるとみなします。

制約

  • 入力は全て整数である。
  • 2≤n≤109
  • 1≤a<b≤min(n,2×105)

n種類の花を使って1本以上からなる花束を作ります。1種類1本しかもっていないことに注意しましょう。a, b が苦手な数という条件は今、ひとまず無視すると、n=4のとき、花束の作り方は以下のような計算式であらわせます。

Σ(4Cr) = 4C1 + 4C2 + 4C3 + 4C4

4種類の花をから2本の花を使って花束を作るには、4種類から2本を選ぶので 4C2 になります。1-4本のすべてのパターンで作ることのできる花束の数を求めるので、上のような式になります。

今回は a, b が苦手なのでこの本数の花束は作ることができないという条件があります。つまり上の式から 4Ca と 4Cb を引けば答えになります。

制約がでかい

この問題はここまで考察すればあと一歩です。一番の障害はNの制約が 109 と大きい点にあります。

Nがでかいので Σ(nCr) を愚直に計算すると O(n) くらいはかかることになります。これをうまく一発で計算して求められればよさそうです。ということで探しました。

二項係数の和，二乗和，三乗和 | 高校数学の美しい物語

ありました。二項係数の和の公式です。

Σ(nCr) = 22

素晴らしい。これを使えば計算量の問題が解決できます。最後に nCa を効率よく計算できれば良いです。

nCr = n! / (r! * (n-r)!) = {n(n-1)..(n-r+1)} / (1*2..*r)

分子がnから数え下げながらr個かけた値、分母が1から数え上げながらr個かけた値です。今回 1≤a<b≤min(n,2×105) という制約なので、ループしながら計算しても O(n) でそれぞれ求まります。

ということで解ける算段がつきました。

実装

static void Main(string[] args)
{
    var N = sc.ReadInt();
    var A = sc.ReadInt();
    var B = sc.ReadInt();
    // -1しているのは nC0 の分
    var ans = ModInt.Pow(2, N) - 1 - nCr(N, A) - nCr(N, B);
    Console.WriteLine(ans);
}

static ModInt nCr(int n, int r)
{
    ModInt ans = 1;
    // 分子
    for (int i = 0; i < r; i++)
    {
        ans *= n - i;
    }
    // 分母
    for (int i = 1; i <= r; i++)
    {
        ans /= i;
    }
    return ans;
}

public struct ModInt
{
    public const long Mod = (int)1e9 + 7;
    public long num;
    public ModInt(long n) { num = n; }
    public override string ToString() { return num.ToString(); }
    public static ModInt operator +(ModInt l, ModInt r) { l.num += r.num; if (l.num >= Mod) l.num -= Mod; return l; }
    public static ModInt operator -(ModInt l, ModInt r) { l.num -= r.num; if (l.num < 0) l.num += Mod; return l; }
    public static ModInt operator *(ModInt l, ModInt r) { return new ModInt(l.num * r.num % Mod); }
    public static ModInt operator /(ModInt l, ModInt r) { return l * Inverse(r); }
    public static implicit operator ModInt(long n) { n %= Mod; if (n < 0) n += Mod; return new ModInt(n); }
    public static ModInt Pow(ModInt v, long k) { return Pow(v.num, k); }
    public static ModInt Pow(long v, long k)
    {
        long ret = 1;
        for (k %= Mod - 1; k > 0; k >>= 1, v = v * v % Mod)
            if ((k & 1) == 1) ret = ret * v % Mod;
        return new ModInt(ret);
    }
    public static ModInt Inverse(ModInt v) { return Pow(v, Mod - 2); }
    private static List<ModInt> Facs = new List<ModInt> { 1 };
    public static ModInt Fac(int n)
    {
        for (int i = Facs.Count; i <= n; i++)
        {
            Facs.Add(i * Facs[i - 1]);
        }
        return Facs[n];
    }
    public static ModInt nCr(int n, int r)
    {
        if (n < r) return 0;
        if (n == r) return 1;
        return Fac(n) / (Fac(r) * Fac(n - r));
    }
}

ModInt は余りをとるのを簡単にするための構造体です。

四則演算、べき乗、階乗、逆元、組み合わせ(nCr)の計算をそれぞれ用意しています。

「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 – Qiita

あまり理屈は理解してないです。上の記事を見て取り合えず実装しています。ただしここで実装している nCr nの階乗を先計算する実装なので、O(N) 以上計算量がかかるので別に実装した関数で計算するようにします。

最後に0本の組み合わせ分の1を引くのを忘れず実装終了です。

E – Roaming

E – Roaming

最近はこの水色Difficultyの問題が壁になっている気がしますね。このレベルが解けるようになればもう1つレベルアップできそうな気がしてます。

解説見なきゃわかりません。

以上。

競技プログラミングカテゴリの最新記事