Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

Codeforces Round #489 (Div2)

一昨日と同様、深夜25:35から2時間に渡って行われたDiv2コンテスト。 前回の反省を活かして眠気ほぼなしの状態で挑みましたが、何か大切なものを犠牲にしているような気がしています。

今回まともに手を付けられたのはC問題まで。というわけで、さっそくA~Cの3問を振り返っていきましょう。

(例によって数式が丸々使えないので、HackMD版のリンクを貼っておきます。なんとかならんかね。)

目次

A. Nastya and an Array (ナーシャと数列)

問題リンク

概要

任意の整数を選び、数列の0でない要素全てにその整数を加える。

与えられた数列に対して、上の操作を繰り返して数列の全要素を0にする。 この最小手数を求めよ。

解説

一例としてはこんな感じ。この場合はあと4回で全部0にできるので、答えは6回となる。

f:id:misteer:20180619152554p:plain:w500

上を見ての通り、一度の操作では数列中の同じ値の要素を全部0に出来る。

操作する様子を色々考えれば、答えが数列の異なる要素の数であることが分かるだろう。 これはカウント配列やsetを使えば容易に実装できる。

ただし0を要素としてカウントしないように注意。サンプルに含まれていたのが良心的。

回答例

int main() {
    int N;
    cin >> N;

    set<int> used;
    // 出てきた要素を突っ込む
    // 重複は取り除かれるので要素数=答え
    
    REP(_, N) {
        int a;
        cin >> a;
        if (a != 0) {
            used.insert(a);
        }
    }

    cout << SIZE(used) << endl;
    return 0;
}

上の9行目では、for文の内部でループ変数を使わないことをREP(_, N)とすることで明示的にし、さらに変数名を節約している。 以前AtCoderで見かけて以来、愛用している記法だったりする。

B. Nastya Studies Informatics (ナーシャ、情報科学を学ぶ)

問題リンク

概要

整数l, r, x, yが与えられるので、

  • l ≦ a, b ≦ r
  • GCD(a, b) = x, LCM(a, b) = y

を満たす(a, b)の数を求めよ。

ただし、a ≠ bならば(a, b)と(b, a)は別としてカウントする。

(1 ≦ l ≦ r ≦ 109, 1 ≦ x ≦ y ≦ 109)

補足
GCD 最大公約数 (Greatest Common Divisor)
LCM 最小公倍数 (Least Commom Multiple)

解説

(数学Aの整数の知識を存分に使います。お覚悟を。)

まず、上の条件下でa = a'x, b = b'xとおくとa',b'は互いに素となる。

GCDとLCMの性質から、ab = xy。

ここでy' = y / xとおけばy' = a' b'と表せるので、このa'を全探索すればいい。

ただし、愚直に1 ≦ a' ≦ y'を全探索すると上の制約から余裕でTLEとなる。 じゃあどうすればいいかというと、a' ≦ b'と仮定して1 ≦ a' ≦ √y'の範囲に絞ればいい。素数判定で定番のやつである。

さらに気をつけるべきこととして、a' = b'の場合が挙げられる。この場合はa = bなので2つではなく1つとしてカウントしなくてはならない。

さらにさらに危険なのが、そもそもyがxの倍数でないケース(y % x > 0)。この場合は条件を満たす(a, b)がそもそも存在しないので答えは0となる。 実装方法によってはこれで落ちる可能性もあるので、最初に弾いておくのが吉。

回答例

ll gcd(ll a, ll b) {
    // Euclidの互除法で、aとbの最大公約数を求める
    
    if (a > b) return gcd(b, a);
    // 常にa<=bが保たれるようにする

    return a == 0 ? b : gcd(b % a, a);
}

int main() {
    ll l, r, x, y;
    cin >> l >> r >> x >> y;

    if (y % x > 0) {
        cout << 0 << endl;
        return 0;
    }

    ll y' = y / x;

    ll ans = 0;
    for (ll a' = 1; a' * a' <= y'; i++) {

        if (y' % a' > 0) continue;
        // 条件: a'はy'の約数
        
        ll a = x * a', b = x * y' / a';
        
        if (gcd(a, b) > x) continue;
        // 条件: a'とb'は互いに素
        // ここでは既にxをかけてしまっているので上の通り
        // (gcd > 1で1WA)

        if (l <= a && a <= r && l <= b && b <= r) {
            // 条件: l <= a, b <= r
            if (a != b) {
                ans += 2;
            } else {
                // a=bのケースに注意
                ans++;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

見た目の通り完全に整数の問題。Xor Sumとどことなく似た空気を感じるが、無論こっちの方が全然簡単。

AtCoderなら内容的には300点レベル、さらに実装で+50点くらいか。

しかし絶妙にバグが発生しやすい構造をした問題である。 事実、コンテスト終了時点でB,Cの正解者はそれぞれ1,324人、1,341人となり、なんとCの方が正答者数が多いという異例の事態に。

Bとしては難問の部類に入るだろう。TLでも哀しみの声が観測された。

C. Nastya and a Wardrobe(ナーシャとタンス)

問題リンク

概要

服を入れると1ヶ月後に服が2倍になるという不思議なタンスがある。 しかしそのタンスは服を2倍にした後、50%の確率で中の服を1着だけ食べてしまう。 ただし1年の最後の月だけは、服が食べられることはない。1

例えばタンスに3着の服が入っていたとする。 この1ヶ月後にはタンスの中の服は2倍の6着になっているのだが、50%の確率でそのうちの1着が食べられてしまう。 つまり1ヶ月後の服の数は50%の確率で5着、50%で6着ということになる。

ナーシャは新年にこのタンスを貰い、x着の服をその中に入れた。ナーシャの国では1年がk + 1ヶ月であるという。

このとき、年末時点でタンスの中にある服の数の期待値を109 + 7で割った余りを求めよ。

(0 ≦ x, k ≦ 1018)

解説

先に言ってしまうが、この問題も完全に数学である。

計算過程リンク

解説にも数式を大量に使うわけで、いかんせんここに書くのは不可能なレベルとなってしまった。 というわけで、計算過程を書いたHackMD版のリンクをここに貼っておきます。考察ノートとかも載せてあります(要るか?)

f:id:misteer:20180619145444p:plain:w300

結論だけ先に言ってしまうと、上の計算式を109 + 7で割ったものを出力すればACとなる。

値の累乗は「ダブリング」というテクニックを使うことで対数オーダーで計算することができるので、バカみたいにデカいkの制約にも余裕で対応できる。詳しくは回答例にて。

コーナーケース

ただし、これをそのまま実装すると落ちてしまう(pretestが通るかは分からない)。 色々試せば分かるのだが、実はx = 0がコーナーケースなのだ。

x = 0のときは明らかに答えは0だが、上の式に代入してもそうならない。 これは式を立てる時点で、「そもそも食べられる服がない」という状況を考慮していないために起こる。 存在しない服を食べ続けてしまうことになるため、期待値が負に発散してしまうわけだ。

というわけで、ちゃんと最初に弾いておこう。

回答例

const ll MOD = 1e9 + 7;

ll calc_pow(ll n, ll k) {
    // ダブリングでn^kを求める
    
    if (k == 0) return 1;
    if (k == 1) return n;
    // 終端条件

    if (k % 2 > 0) {
        // kが奇数 -> n^k = n*n^(k-1)
        // 下の偶数の場合に帰着させる
        return calc_pow(n, k - 1) * n % MOD;
        
    } else {
        // kが偶数 -> n^k = (n^2)^(k/2)
        // これで指数を半分にすることで、計算量がlogkとなる
        return calc_pow(n * n % MOD, k / 2);
    }
}

int main() {
    ll x, k;
    cin >> x >> k;

    if (x == 0) {
        // さっき述べたコーナーケース
        cout << 0 << endl;
        return 0;
    }

    ll X = (x * 2 - 1 + MOD) % MOD;
    // X = 2x - 1
    // 少しまどろっこしいが、x<0の状態を防いでいる

    ll ans = (X * calc_pow(2, k) + 1 + MOD) % MOD;
    // ans = x_{k+1} = (2x - 1) 2^k + 1

    cout << ans << endl;
    return 0;
}

実装は軽い方だが、現実世界での前計算が慣れてないと大変。

ダブリングは毎回実装するのは少し面倒な上、modの逆元2を求めるのにも使うので私はライブラリ化している。

感想

記事を読んでいただければ分かる通り、数学色の強いコンテストだった。 D問題も連続部分列の積と和とかいう話だったので、全体としてもそういう傾向だったのだろう。

しかし私も伊達に東大に受かってないので、この手の問題は得意な方。前回の雪辱を果たし、無事3完を達成できた。でもDは残念ながら歯が立たず。

次のコンテストは実質4日後の6/24深夜。次こそはキッチリ決めて紫に上がりたいところ。


  1. なんで最後の月だけ例外扱いかというと、単に答えが小数になってしまうためだと思われる。

  2. na ≡ 1 (mod M)が成立するとき、aをnの逆元と呼び、a = n-1と書いたりする。「nで割る」という演算はmod系ではそのまま出来ないのだが、これを「n-1を掛ける」という演算で代用することができる。(一般にはもっと条件は緩いが)Mが素数の場合、Fermatの小定理から「n-1 ≡ nM - 2」で逆元が求められ、この累乗計算にダブリングを使う。