2018-01-25

ABC056/D - No Need

Atcoder

https://beta.atcoder.jp/contests/abc056/tasks/arc070_b

考察

要素の順番は関係無いので、考えやすくするためにとりあえずa_iは昇順ソートされているものだとします。

まず、「カードiが必要であること」とはどういうことかと考えてみると、条件の否定を考えて「カードiを含むある集合が存在して、その集合からiを抜くと総和がK未満になってしまう」ということになります。

このことから「カードiを除いた全ての数で[K - a_i, K)に含まれる数が作れるか」ということと同値だと分かります。もし作れるのなら、そこにカードiを加えた集合は良い集合になるのでカードiは必要だと分かるし、逆に[K - a_i, K)に含まれる数が作れないのならiを加えたところで良い集合になるものは存在しないと分かるからです。

なので、各iについて「カードiを除いた全ての数で[K - a_i, K)に含まれる数が作れるか」を調べていけばいいことになってこれを愚直に総当たり＋部分和DPでやるとO(N^2 * K)になってしまいます。これでもN = K = 400までの部分点は取れそうですが、N = K = 5000の満点は無理そうなのでもう少し計算量を落とす必要があります。

まず考えられるのは「愚直に全部見ていく必要はあるのか？」ということです。もし「iが必要である⇒i+1も必要である」というような単調性が成り立っていれば、真面目に全探索する必要はなく二分探索を使えばいいのでそうなっていないかと考えたくなります。a_iが昇順ソートされているものだと思うと、区間[K - a_i, K)はiが増えるごとに広がっていくので何となくそのような単調性がありそうだなと思います。

少し考えると実際に、このような単調性を示すことができます。

もし、iが必要であるとすると、iを除いた集合で[K - a_i, K)に含まれる整数が作れます。もしそれがi+1を含まないもので作れているとすると、i+1を除いた集合でも明らかに作れて、それは[K - a_{i+1}, K)にも明らかに含まれるので良いです。
問題はi+1を使って作っている場合ですが、このとき、i+1をiに置き換えて作った整数はいくらか小さくはなりますが[K - a_{i+1}, K)に含まれていることは分かります。小さくなった分だけ区間が広がっているからです。

こうやって二分探索が使えることが分かると、計算量はO(N * K * log(N))に落とすことができます。それでも、最大ケースでは3 * 10^8程度になるっぽいのでこれは想定解じゃないのかな……と思いましたが、１つの想定解であったそうです。
実際これをやってみるとそんなに無理なく通すことができました。

そしてO(N*K)の想定解もあったようで、こちらは前の方から部分和DPをやって後ろの方から部分和DPをやると、{0, ..., i-1}で作れる整数と{i + 1, ..., N - 1}で作れる整数が分かるので、これらの結果をtwo-pointersでいい感じにやるとO(N*K)で出来るみたいな感じでした。（本当は解説にはtwo-pointersじゃなくて「累積和を使う」と書いてあるのですが、よく分かりませんでした）

ソースコード

ソースコードはテンプレートとか適当に省略しています。

二分探索

void main() {
    int n, k;
    int[] a;

    scan(n, k);
    a = readln.split.to!(int[]);

    a.sort();

    bool check(int mid) {
        if (a[mid] >= k) {
            return true;
        }
        
        auto dp = new bool[](k + 1);
        dp[0] = 1;

        foreach (i ; 0 .. n) {
            if (i == mid) continue;
            foreach_reverse (j ; a[i] .. k + 1) {
                dp[j] |= dp[j - a[i]];
            }
        }

        foreach (i ; max(0, k - a[mid]) .. k) {
            if (dp[i]) {
                return true;
            }
        }

        return false;
    }


    int btm = -1, top = n;

    while (top - btm > 1) {
        int mid = (top + btm) / 2;

        if (check(mid)) {
            top = mid;
        }
        else {
            btm = mid;
        }
    }

    writeln(btm + 1);
}

前/後ろDP + two-pointers

void main() {
    int n, k;
    int[] a;

    scan(n, k);
    a = readln.split.to!(int[]);

    auto dp1 = new bool[][](n + 1, k);
    dp1[0][0] = 1;

    foreach (i ; 1 .. n + 1) {
        foreach (j ; 0 .. k) {
            dp1[i][j] = dp1[i-1][j];
            if (j - a[i-1] >= 0) dp1[i][j] |= dp1[i-1][j-a[i-1]];
        }
    }

    auto dp2 = new bool[][](n + 1, k);
    dp2[n][0] = 1;

    foreach_reverse (i ; 0 .. n) {
        foreach (j ; 0 .. k) {
            dp2[i][j] = dp2[i+1][j];
            if (j - a[i] >= 0) dp2[i][j] |= dp2[i+1][j-a[i]];
        }
    }

    int ans;

    foreach (i ; 0 .. n) {
        int mv;

        for (int l = 0, r = k-1; l < k; l++) {
            if (!dp1[i][l]) continue;
            for (; r >= 0; r--) {
                if (dp2[i+1][r] && l + r < k) {
                    mv = max(mv, l + r);
                    break;
                }
            }
        }

        if (mv < k - a[i]) ans++;
    }

    writeln(ans);
}

2017-12-20

競技プログラミング初めて１年経ちました

その他

競技プログラミング（競プロ）を初めて１年くらい経ったので、１つの区切りとして競プロについて得られた知見や感想を書いておきます。
強くなる方法とか競プロお役立ちテクニックとかそういう話は一切書いてません。

パソコンのプロじゃなくても出来る

何かいきなり馬鹿みたいな話ですが、競プロはパソコンのプロじゃなくても簡単に参加できます。
競技プログラミングやってる人っていうと、日常的にLinuxとか使っててコマンドプロンプトとかめっちゃ使いこなしているスーパーハッカーみたいなイメージでしたが、私みたいにWindowsしか使えない、マウスが無いとまともに操作できない、プログラミングは大学で習った程度のことしかできずアプリとかも作れない……みたいな人でも何とかできます。サンプルコピペするときにカチッペタッカチッペタッてやるのは何かアホっぽいですがそれでもコンテストに参加していくつかの問題を解くことができます。

pythonで競プロ続けていくのはなかなか厳しい

最初半年ぐらいはpythonでやってたんですが、それからはだいたいD言語でやるようになってしまいました。ひねくれ者だったので「pythonで競プロは厳しい」みたいな風潮を見てもいけるとこまでいってやろうとか思ってましたが……散々言われてたことですが、「やっぱりpythonは遅い」です。経験的に、pythonって反復処理が10^6超えるとTLEするかも？って感じなんですよね。10^7だったら絶対TLEします(pypyで出せるならもうちょっとマシになりますが10^7になると相当不安です)。でも競プロの問題って想定解が10^7とか普通にあって、何なら10^8ってこともありました。Atcoderの簡単な問題やyukicoderでやる分にはpypyで提出したりすることで割といけるのですが、こどふぉとかJOIの過去問とかはどうしてもpythonじゃきついなあっていう場面が結構ありました。あと再帰深さの制限を上げても再帰深さのせいで（？）REしたりしたこともありました。いろいろあって辛くなるのでpythonで競プロをやるのは止めました。

こどふぉに参加すると生活リズムが狂う

日本で流行ってる競プロサイトといえば、一番はAtcoder、二番はCodeforces、三番Topcoderって感じっぽいです。私が初めて「競技プログラミング」という存在を知ったころはTopcoderというサイトしか知らなかったので今もそんな感じでTopcoderが一番栄えてるんだろうな～と思っていたんですが、どうやらそうではないらしいです。

それは置いといてCodeforces、通称こどふぉですがこれはロシアの競プロサイトです。「なんでロシア？」と思いますが、ロシアは競プロが一番強い国らしいです。ここのコンテストにも結構日本人が参加しています。問題文はロシア語ではなく、英語なので何とか読めます。コンテストの質（？）は正直あまりよろしくないというのが競プロ界隈での定評です。サイトが重い・つながらない、ジャッジキューが詰まりすぎ、問題の質も悪い（こどふぉはストーリー付きの問題文であるのでそれが邪魔みたいなのとか、考察が軽く実装が重いみたいな問題は嫌われる傾向にあるからかもしれません。あと想定解が誤解法だったとか）などなど。デメリットは多いですが、それでも世界規模で見ると一番栄えている競プロサイトです。こどふぉはSNS的な側面もあって、コンテストが終わるとフォーラムが賑わうので見ていると面白いです。そういう意味ではAtcoderよりお祭り感があって楽しいです。あとはAtcoderにない特徴的なシステムとして、他人のコードを撃墜できるHackというシステムがあってそれも面白いかもしれません。

そんなわけでこどふぉのコンテストに参加するのはなかなか刺激的で楽しいんですが、大きな欠点としてだいたい日本時間で深夜に行われるというのがあります。通常24:00~26:00くらいでそっからシステムテストが終わるのを待ったり、寝ようと思ってもコンテスト後は目が冴えてしまっているのでうだうだやっていると27時とか28時くらいになってしまいます。なので結構な頻度でこどふぉに参加してしまうと完全に昼夜逆転生活になってしまいます。

全探索すればいい

私が競プロ始めた頃によくあったこととして、問題を解こうとしたときに「賢く解こう」としてしまうということがあったなあと思いました。賢く解こうというか数学的に解こうとか、貪欲で解こうとか、そういう感じです。

例えば、yukicoderの「No.90 品物の並び替え」という問題があります。
https://yukicoder.me/problems/no/90

これはある程度慣れた人なら「N <= 9と制約が小さいから、全ての並び順を全探索するO(N! * N^2)の解法でも十分間に合うな」とぱっと分かる問題です。しかし１年前の私のコードを見ると、「各アイテムをどの位置に挿入したら最も点数が高くなるか？」という怪しい貪欲で解こうとしてWAを食らってます。

このエピソードから得られる教訓として「証明できない貪欲は出来るだけ避けよう」という話もありますが、それ以前の問題として「全ての並び順を調べればいい」という全探索の思考が全く無かったからこのようなコードになってしまったのだと思います。

全探索っていうと何となく「頭の悪い解法、非効率的で競プロには向かない」みたいな先入観があったのですが、全然そんなことは無くて基本中の基本でとっても大事なので全探索の心は常に持っておきたいなと思いました。

まとめ

結構飽き症なので競プロ始めた頃はすぐ飽きるかな～と思ってましたが、意外と１年くらい続きました。（２ヶ月くらい飽きてやってない時期ありますが）
競プロって見た目は地味ですが、多種多様な問題が出されるので「またこの問題か……」みたいなのがあんまり無くて毎回凄く考えさせられます。面白いです。パズルとか考えるゲームが好きな人にはおすすめです。

2017-08-08

Educational Codeforces Round 26

codeforces

久しぶりにブログを書きます。
４完でした。D問題のDPを通せたのは個人的になかなか成長したのではないかと思える回でした。

A. Text Volume

問題概要

いくつかの単語で構成される文が与えられる。
各単語の音量はその単語に含まれる大文字の数で決まり、その文の音量はそれらの単語の音量の最大値で決まる。
与えられた文の音量を求めよ。

感想

これはそのままやるだけですね。強いて言うなら、最初大文字判定を'A' <= chみたいに書いててバグらせたのがアレでした。
asciiコードでは大文字が先に割り振られてるので'A' <= chだと小文字も全部カウントしちゃうんですね。
なので書くとしたらch <= 'Z'じゃないとダメでした。そもそも横着せずにちゃんと'A' <= ch && ch <= 'Z'と書いておけばよいですね。

D言語パワーを使ってスマートに書くとこんな感じ。

void main() {
    readln;
    readln.split.map!(w => w.count!(isUpper)).reduce!(max).writeln;
}

そもそもisUpperっていう大文字判定関数みたいなのがありました。

B. Flag of Berland

問題概要

R, G, Bのみで構成される旗が与えられる。
それがロシアとかイタリアみたいな国旗になっているか判定せよ。

感想

場合分けでゴリ押しました。結構めんどくさくて、めんどくさかったです。
丁寧に場合分けしないとコーナーケースとかで落とされて、割とHackで落とされた人が多かったみたいです。
長いだけなのでコードは省略します。

C. Two Seals

問題概要

a * bの土台となる長方形がある。n枚のシールを持ってて、シールiはx[i] * y[i]の長方形である。
この土台に２枚のシールを貼りたい。シールははみ出しちゃダメで、各辺は土台の辺と並行になるように貼らなければならず、２枚のシールが重なってもいけない。
このとき貼れる２枚のシールの面積の総和の最大値を求めよ。貼れる２枚が無いときは0とせよ。

制約

1 <= n, a, b <= 100
1 <= x[i], y[i] <= 100

感想

nが小さいので２つのシールの全ての組合せを試すO(n^2)解で十分間に合うのでそれをやりました。
１つのシールを左上隅に固定して貼ったとすると、２つの長方形を重ねたような多角形が残るので
そのどちらかの長方形に収まるようにもう一方のシールを貼れるか、みたいな判定をするみたいな。

int n, a, b;
int[] x, y;

void main() {
    scan(n, a, b);

    x = new int[](n);
    y = new int[](n);

    foreach (i ; 0 .. n) {
        scan(x[i], y[i]);
    }

    bool check(int U, int V, int u, int v) {
        return (u <= U && v <= V) || (u <= V && v <= U);
    }

    int ans;

    foreach (i ; 0 .. n) {
        foreach (j ; 0 .. n) {
            if (i == j) continue;
            
            if (x[i] <= a && y[i] <= b) {
                if (check(a - x[i], b, x[j], y[j]) || check(a, b - y[i], x[j], y[j])) {
                    ans = max(ans, x[i]*y[i] + x[j]*y[j]);
                }
            }

            if (x[i] <= b && y[i] <= a) {
                if (check(a - y[i], b, x[j], y[j]) || check(a, b - x[i], x[j], y[j])) {
                    ans = max(ans, x[i]*y[i] + x[j]*y[j]);
                }
            }
        }
    }

    writeln(ans);
}

D. Round Subset

問題概要

n個の整数 a_1, ..., a_n が与えられる。
この中からk個選んで全ての積を取ったときの末尾の連続する0の個数を最大化したい。
その最大値を求めよ。

制約

1 <= k <= n <= 200
1 <= a_i <= 10^18

感想

まず、k個選んだときの末尾の0の個数がどうやって決まるかって話ですがこれは10で何回割れるかっていうことなので
各整数が2を何回含むか、5を何回含むかを前処理で求めておいて、選んだk個のそれらの値をそれぞれ足して、最後にminを取ることで求まります。
それで最大値問題ってことで最初は二分探索かなーとか思って考えてました。何か平均最大化問題みたいな感じで基準を定めてうんたらかんたらみたいな。
あれも「n個からk個とるとき」って感じだったのでそういうパターンかなって思ったのですがどうにも上手くいきそうにありませんでした。
それで次に考えたのがDPでした。「n個からk個とるとき」みたいな問題をDPで解いたことあったなあーとか思い出したので。
なんかちょっとぱっと出てこないんですがありますよね。dp[ここまで見た数][ここまでで選んだ数]みたいなDP問題。
ただこのまま
dp[ここまで見た数][ここまでで選んだ数] = (2の数, 5の数)
として、min(2の数, 5の数)が上回るとき更新、みたいにするとちょっとまずそうだなって思います。
例えば
3 2
4 10 25
みたいなケースで上手くいかなくなるはずです。
だからこのままではまずいけど、
dp[ここまで見た数][ここまで選んだ数][ここまでで取った5の数] = (2の数)
にして、2の数が大きくなるとき更新、にすると上手くいきそうっていうのは何となく分かるかなと思います。
別にこうじゃなくて
dp[ここまで見た数][ここまで選んだ数][ここまでで取った2の数] = (5の数)
としてもいいんですけど、状態数はなるべく少なくしたほうが計算量も少なくなるのでこれより上の奴のほうがいいと思います。
それで実際計算量は大丈夫なのでしょうか？
ここまで見た数 = 200,
選んだ数 = 200,
ここまで取った5の数 = 200 * 25
が最大ケースっぽいのでこれを掛け合わせると2 * 10^8くらいになるっぽいです。
Pythonだとまず間違いなくTLEしますが、Dの力を信じてサブミットするとあっさり300msぐらいで通っちゃいました。凄い速い。
実際DPテーブルを2 * 10^8作るとMLEしそうなので、１個目の変数は１個前しか参照しないから2個でいいっていう奴をやってます。

int n, k;
long[] a;

void main() {
    scan(n, k);
    a = readln.split.to!(long[]);

    auto two = new int[](n);
    auto five = new int[](n);

    foreach (i ; 0 .. n) {
        while (a[i] % 2 == 0) {
            a[i] /= 2;
            two[i]++;
        }

        while (a[i] % 5 == 0) {
            a[i] /= 5;
            five[i]++;
        }
    }

    int lim = n * 25;

    auto dp = new int[][][](2, k + 1, lim + 1);
    fillAll(dp, -1);
    dp[0][0][0] = 0;

    foreach (i ; 0 .. n) {
        foreach (j ; 0 .. k + 1) {
            foreach (f ; 0 .. lim + 1) {
                if (dp[i & 1][j][f] == -1) continue;
                dp[(i & 1) ^ 1][j][f] = max(dp[(i & 1) ^ 1][j][f], dp[i & 1][j][f]);

                if (j + 1 <= k) {
                    dp[(i & 1) ^ 1][j + 1][f + five[i]] = max(dp[(i & 1) ^ 1][j + 1][f + five[i]], dp[i & 1][j][f] + two[i]);
                }
            }
        }
    }

    int ans;

    foreach (f ; 0 .. lim + 1) {
        ans = max(ans, min(f, dp[n & 1][k][f]));
    }

    writeln(ans);
}

AOJ/Atcoder-JOI
何かここの難易度5 ~ 6ぐらいに良い感じのDP問題がたくさんあるのでオススメです。
これで少しDPに慣れていたおかげでこの問題が解けたかなと思ってます。

E. Vasya's Function

問題概要

f(a, 0) = 0
f(a, b) = f(a, b - gcd(a,b)) + 1 (b > 0)
という関数がある。f(x, y)の値を求めよ。

制約

1 <= x, y <= 10^12

感想

少し言い換えると「(a, b) -> (a, b - gcd(a, b))という操作がbが0になるまで何回出来るか？」という問題になることが分かります。
最悪実際にシミュレーションするって解がありますがx, yがめちゃくちゃでかくなるので明らかにTLEしそうでやりたくないですよね。
x = 1だったらy回シミュレーションしなきゃいけないわけだし……
それでaが素数のときはf(a, b) = a / b + a % bで～とか考えましたが結局全然分からなかったので答えを見ました。
操作で変化するのはbだけで、古いgcd(a, b)は新しいgcd(a, b)に必ず含まれているってのがポイントらしかったです。
まずaに含まれる互いに異なる素因数を列挙しておいて、
次にg = gcd(a, b)を求めて、このgcdが変化するときっていうのはaに含まれる素因数を新たに巻き込むときってことなので
そこまでにかかるステップ数を求めて、最後にそれらの最小値を取って、答えに加算して、また最初に戻って……
ってのを繰り返すみたいです。難しいですね。
計算量的には上の一回のループがaに含まれる異なる素因数分かかって、ループする回数はgcdが倍倍倍で増えていくからlogぐらいでみたいな感じであんまりかからなさそうです（雑計算）
結局最初にaの素因数分解にかかる時間が一番大きいような気がします。

import std.stdio, std.string, std.conv, std.algorithm;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;
import std.numeric;

immutable long inf = 10L^^13;
long x, y;

void main() {
    scan(x, y);

    auto xf = factrize(x);

    debug {
        writeln("xf:", xf);
    }

    long ans;

    while (y > 0) {
        long g = gcd(x, y);

        if (g == x) {
            ans += y / g;
            break;
        }
        
        long m = inf;

        foreach (p ; xf) {
            long mp = (y - (y / (p * g)) * p * g) / g;
            if (0 < mp && mp < m) {
                m = mp;
            }
        }

        ans += m;
        y = y - m * g;
    }

    writeln(ans);
}

auto factrize(long x) {
    auto res = new long[](0);

    for (long p = 2; p*p <= x; p++) {
        if (x % p == 0) {
            res ~= p;
            while (x % p == 0) {
                x /= p;
            }
        }
    }

    if (x > 1) {
        res ~= x;
    }

    return res;
}