[C#] AtCoder Beginner Contest 147 に参加した振り返り記録と解説

AtCoder Beginner Contest 147 に参加した振り返り記録と解説

AtCoder Beginner Contest 147 – AtCoder

AtCoder Beginner Contest 147 に参加した記録をしておきます。使用した言語はC#、結果はABCDの4完、パフォーマンスは1400くらいでした。過去最高のパフォーマンス、二度目の水色パフォがでました。

E問題がDPで解けるのはわかったんですが、実装ミスして諦めました。考え方はわかったので悔しかったです。

ということで振り返っていきます。

A – Blackjack

A – Blackjack

3 個の整数 A1, A2, A3 が与えられます。

A1+A2+A3 が 22 以上なら bust、21 以下なら win を出力してください。

問題文の通りにif文書くだけです。

B – Palindrome-philia

B – Palindrome-philia

高八士君は回文が大好きで、回文でない文字列が許せません。高八士君は文字列を 1 回ハグするごとに、文字列から 1 文字を選んで任意の文に変えることができます。文字列 S が与えられます。

S を回文にするために必要なハグの最小回数を答えてください。

「与えられた文字列の前半半分を走査して、後半の対応する文字と比較して異なっているときにカウントする」みたいな実装を行いました。

var ans = 0;
for (int i = 0; i < N / 2; i++)
{
    var j = N - i - 1;
    if (S[i] != S[j]) ans++;
}

C – HonestOrUnkind2

C – HonestOrUnkind2

1 から N までの番号がついた N 人の人がいます。彼らはみな、必ず正しい証言を行う「正直者」か、真偽不明の証言を行う「不親切な人」のいずれかです。

人 i は Ai 個の証言を行っています。人 i の j 個目の証言は 2 つの整数 xij , yij で表され、yij=1 のときは「人 xij は正直者である」という証言であり、yij=0 のときは「人 xij は不親切な人である」という証言です。

この N 人の中には最大で何人の正直者が存在し得るでしょうか？

制約:1≤N≤15

考え方

一瞬問題文が理解できずに悩みましたが、C問題なので冷静に全探索すればいいという考えに至りました。基本的にC問題までは全探索で解けると思うのがいいですね。

N人について「正直者」「不親切な人」のすべての組み合わせを考えます。つまり2^Nパターンを全探索します。ビット演算で全探索するか、再帰関数を使って全探索するかの方法がありますが、私は再帰関数を使いました。

制約が 1≤N≤15 なので最大でもパターン数が 2^15 = 32,768‬ 程度です。余裕で間に合う計算です。

仮定のパターンが得られたら、その仮定と「正直者」と仮定された人の発言が矛盾しないかを判定し、すべての「正直者」の発言が正しいパターンにおける、「正直者」の数の最大を求めればよいです。

static int N;
static Tuple<int, int>[][] Data;
static int Ans = 0;
static void Rec(int n, int[] katei)
{
    if (n == N)
    {
      　// N人の組み合わせが出そろったとき
        // その仮定の時、矛盾するかどうかチェックする
        Check(katei);
    }
    else
    {
        // n番目の人が正直者のパターン
        katei[n] = 1;
        Rec(n + 1, katei);

        // n番目の人が不親切のパターン
        katei[n] = 0;
        Rec(n + 1, katei);
    }
}

static void Check(int[] katei)
{
    for (int i = 0; i < N; i++)
    {
        // 不誠実な人の発言は無視する(整合性が取れていようが関係ないため)
        if (katei[i] == 0) continue;

        for (int j = 0; j < Data[i].Length; j++)
        {
            var x = Data[i][j].Item1;
            var y = Data[i][j].Item2;

          　// 正直者の人の発言が仮定と一致しないときは矛盾
            if (katei[x] != y) return;
        }
    }
    // すべての正直者の発言に矛盾がないとき、正直者の数を数える
    Ans = Math.Max(Ans, katei.Count(k => k == 1));
}

こんな感じですね。

Tuple<int int>[][] Data はn番目の人の発言を格納しています。

ビット列を使って書いたほうがスマートだと思うので、後で書き直してみようと思いました。

D – Xor Sum 4

D – Xor Sum 4

N 個の整数があり、i 番目の整数は Ai です。∑N−1i=1∑Nj=i+1(Ai XOR Aj) を 10^9+7 で割った余りを求めてください。

制約: 2≤N≤3×10^5, 0≤Ai<2^60

非常にシンプルな問題文です。Σ(シグマ)が登場する問題文に初めて出会いました。が、「N個の数の中から2個選んで xor をした値の合計を求めてください。」という内容です。

入力例1を参考にすると、

3
1 2 3

上のような入力が与えられたとき、

(1 XOR 2)+(1 XOR 3)+(2 XOR 3)=3+2+1=6 と

なります。3個の中から2個選んでXORをとり、その合計を求めています。

N個の中から2個選ぶとき、単純に全探索すると O(N^2) になり 10^10 で TLE します。つまり次のような2重ループは使えません。

long ans = 0;
for (int i = 0; i < N; i++)
{
    for (int j = i + 1; j < N; j++)
    {
        ans += A[i] ^ A[j];        
    }
}

XOR の性質

D問題以降は基本的に予習しなければ解けません。とくに XOR が出てくる問題は難しい印象があります。XOR の性質を理解してなければ解けないためです。

XORの性質には以下のようなものがあります。

• A XOR A = 0

同じ数を XOR とると 0 になります。

• A XOR B = B XOR A
• A XOR (B XOR C) = (A XOR B) XOR C

XOR は計算順序を入れ替えてもOKです。交換法則も結合法則も成り立ちます。

考え方

AtCoder の問題で XOR を使う問題では、上の性質以外にも解くときに使える考え方があります。「bitごとに独立して考える」ということです。

bitごとに独立して計算することができれば、O(N) でなく O(logN) で計算できるようになります。

今回の制約を見るとご丁寧に 0≤Ai<2^60 となっています。つまりたかだか O(10^5 * 60) くらいで計算できるようになります。

計算量的にはいけそうなのでbitごとに考えると、どのような結果になるか考えます。

例えば (1 XOR 2)+(1 XOR 3)+(2 XOR 3) はビット列で考えると以下のようになります。

(001 XOR 010)+(001 XOR 011)+(010 XOR 011)

各 XOR の計算でk桁目が1になるのは、ビット列k桁目が 1 と 0 の組み合わせでなければなりません。つまり全組み合わせで(1, 0) の組み合わせになるような数を数えます。

例えば0桁目(一番右の数字)に注目すると、

(1 XOR 0)+(1 XOR 1)+(0 XOR 1)

になります。

k桁目が1になる組み合わせの数がx個あれば、x * 2^k がk桁目の合計値です。各桁の合計値を合算すると、それが今回求める答えになります。

上記例の0桁目には2個(1, 0) の組み合わせがあるので、2*2^0=2 で0桁目の和は2になります。これを全60桁分計算します。

実装

実装は以下のような感じです。

long ans = 0;
int mod = (int)1e9 + 7;

// bit列60桁分をすべて走査する
for (int k = 0; k < 60; k++)
{
    long x0 = 0;
    long x1 = 0;
    for (int i = 0; i < N; i++)
    {
        // k桁目をビット演算で取り出す
        var x = (A[i] >> k) & 1;
        // k桁目が 0, 1 のどちらかを数えておく
        if (x == 0) x0 += 1;
        else x1 += 1;
    }

    long p = 1;
    for (int i = 0; i < k; i++)
    {
        p *= 2;
        p %= mod;
    }
    // x0 * x1 が 0, 1 の組み合わせ数
    var count = (x0 * x1) % mod;
    ans += count * p;
    ans %= mod;
}

mod をとるのを忘れて WA しないように気を付けなければいけません。

また、どんな数字に対しても制約の最大に合わせて60桁分ループすればよいです。小さい数でも 0 XOR 0 が何度も計算されるだけで合計には影響しません。

感想

AtCoder Problems を見ると C問題でも Difficulty が緑なのに驚きました。問題文が少し難しかったからですかね。個人的には茶色前半くらいの難易度かと思いました。この問題より二分探索とかのほうが実装も難しいと思うのですが。

例えば今回の問題より(AtCoder Problems の Difficultyによると)簡単とされるこれとかこれとかこれのほうが個人的には難しと感じています。相性の問題ですかね。

いずれにせよ自分のレート帯だとこの手の問題ならどんどん来てほしいなと思いました。

D問題は類題というか、XOR を使う問題を何問か解いたことがあったのでうまく対応できたと思います。というかこの XOR Sum X という問題はシリーズなんですかね。過去問で1~3までもあるので解いておこうと思いました。

結果、パフォーマンスも過去1でうれしいです。この調子で水色レートまで行きたいですが、今回はたまたま解けただけなのでまだまだこれからですね。頑張ります。

欲を言えば E問題も解ける問題だったので解きたかったですね。もう少しCDを早く解けていれば何とかなったかもしれません。

次も頑張ります。