ABC106解説

公式の解説が充実しているので正直書くことはないのですが、記憶を定着させることと日本語の勉強のために書きました。
まず、公式の解説を読もうね。
https://img.atcoder.jp/abc106/editorial.pdf

A,B,Dが一発ACでCが7WAでした。（全完）
下がり続けていたレートを回復できたので良かったと思いました。

A問題

道のある農場の面積を求める問題です。
結論から言うと縦:B, 横Aに対して をすればよいです。
公式は、右下に持っていくことで に移動させてました。

解法

上図のように を定めます。その時、入力A, Bに対して、が成り立ちます。
農道を除いた面積 Sは

で表すことができます。
ここで、

であることから、答えは

と求まります。

int main()
{
    int a,b;
    cin>>a>>b;
    cout<<(a-1)*(b-1)<<endl;
    return 0;
}

コメント

コンテスト中は、そんなやり方が思いつかず、

でACしました。（因数分解すれば結果は同じ）

所感

A問題にしては難しいと思った。

B問題

N以下の数で約数が8個ある数を数え上げる問題。数学的な解説は公式の方にあるのでそちらを参照ください。

解法

すべてのNに対して、1~Nの数で割っていって割り切れる数を数え、それが8だった個数を出力すればよいです。
とかだと、この方法が通らないので、エラトステネスのふるいとかを使って素数リストを作って…ってやつと思うんですが、Nがなので、高々で終わるのでOKです。

int main()
{
    int n;
    cin >> n;
    int count = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i % 2 == 0)
            continue;
        int num = 0;
        for (int j = 1; j <= i; j++)
        {
            if (i % j == 0)
                num++;
        }
        if (num == 8)
        {
            count++;
            if (DEBUG)
                cout << i << endl;
        }
    }
    cout << count << endl;
    return 0;
}

そんな人はいないと思いますが、奇数を数える問題なので、i%2==0を忘れないように。

所感

B問題にふさわしそうな問題だった。この時は、このセット、高速で全完あるのでは…？と思ってました。

C問題

今回の魔境（ほんとか？）。7WAをたたき出した問題。
増えていく数列を追っかけていく。数字列がどんどん伸びていく。2は2倍, 3は三倍…と5000兆回繰り返す。
もちろんシミュレーションはできないので、エスパーして解きます。

解法

まず、5000兆日後に文字がどれくらいになるか考えます。一番増加の速度が小さい2について考え、スタートの数字列が"2"だったとします。
5000兆日後の桁数は

桁になります。
参考 : 常用対数を用いた桁数と最高位の数の計算 | 高校数学の美しい物語

15桁ではなく、100 000 000 000 000桁です。なのでシミュレーションは不可能です。
前述の数字が最低値になるので、どんなKをもってきても、先頭の数字の範囲に収まります。
しかし、"1"は例外なので、最初に1がK個以上続いたときは1を出力する必要があります。
なので、問題は
先頭から数えて、1がK個以上続いたときは1を、それ以外は先頭の1以外の数を出力してやればいいです。
Kが32bit intに収まらないので気を付けましょう(1敗)。

int main()
{
    string s;
    cin >> s;
    long long int k;
    cin >> k;
    rep(i,k){
        if(s[i]=='1') continue;
        else{
            cout<<s[i]<<endl;
            return 0;
        }
    }
    cout<<'1'<<endl;
    return  0;

最初、「1111111」のような1のみのケースを考えていなかったため、3敗ぐらいしました。

所感

最初2*5000兆だとおもってたので、ビビりました。
解けたときの気持ちよさはいい感じだったと思います。

D問題

2次元平面に累積和とっていくやつ。多分より良い解法があるのと思うので、それを探していただいた方がいいと思います。
数直線のある区間に内包されている線分の数を数え上げる問題です。
線の数がm, クエリがq個あるので、愚直に解くとなので2secで終わらせるのは厳しいです。
また、計算量から逆算してか、ぐらいで何とかしたいなという感じになります。

解法

クエリの時の各始点に対して、任意の終点をとったとき、何本内包しているかを累積和で撮ってあげます。
クエリの始点と終点をそれぞれ、l,rとしたときにa[l][r~n]++;という風な配列を作ります。
ケース3の時に、二次元配列は下のようになります。囲ってある点は、1,5,10番目のクエリです。

これを作れば、lから始まる区間が任意のrの時の内包する数がわかります。
クエリ実行時には、lをrまで変化させることで、クエリで指定された区間内で始まるすべての始点から、rの地点で内包している線分の数を求めることができます。

1クエリを処理するのにかかるので、全体として、
で解けます。

int main()
{
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> a;
    rep(i, n)
    {
        vector<int> hoge(n, 0);
        a.push_back(hoge);
    }
    rep(i, m)
    {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        for (int j = r; j < n; j++)
        {
            a[l][j]++;
        }
    }
    rep(i, q)
    {
        int p, q;
        cin >> p >> q;
        p--;
        q--;
        int ans = 0;
        for (int j = p; j <= q; j++)
        {
            ans += a[j][q];
        }
        cout << ans << endl;
    }
    return 0;
}

所感

最初、いもす法でやるのかなと思っていたのですが、いい感じの組み合わせがあると検知できないことに気づき、2次元に広げました。クエリ実行前に、もう1回累積和を求めることでになるそうです。
累積和とらなくても先に全部計算してもなので、そっちでもよいかもです。

総括

テクニック的に難しいセットではなかったという印象なので、全完できてよかったと思った。
C問題の境界で事故ったのが精進不足の所作だと感じたので、お盆で圧倒的成長を見せたい。

コンテスト中に解法について触れるのは規約違反なので、僕もやってしまうことがありますが、気を付けましょう。
「難しい」、「簡単」というワードもヒントになりうるので、”コンテスト中はTweetしない！”、これが良いと思います。
BANされると、楽しくなくなっちゃうと思うし、ネタバレ見たらつらい気持ちになっちゃうので、お互い楽しいAtCoder lifeを送るためにもご協力ください。