E - Self-contained

原題はE - Self-containedですが、問題の本質は以下のとおりです。

問題

0以上未満の整数からなる集合が与えられる。この中の相異なる3要素で、となるものはあるか。

知識

今回は要素の大きさに制限がありますが、制限がない場合、のアルゴリズムが限界だと思われているようです。2018年度の東京大学情報理工学系研究科コンピュータ科学専攻の院試に似たような話がありました。

解法

まず、話をわかりやすくするために配列を定義します。は整数が集合に含まれるとき1, そうでないとき0とします。

さて、集合の中の相異なる2要素を考えたときに、これらの和は999999未満となりますね。

では、和がとなるようなの組み合わせを考えてみましょう。

そのような組み合わせが存在するとしたら、はのいずれかとなっているはずです。

そこでを考えます。

もしもの組み合わせの中で、実際に集合の要素で構築可能なものがあったとしたらは1以上になります。逆にそのようなものがなかったとしたらsumのすべての項は0となります。

すでにピンときた方は多いでしょうが、これは離散フーリエ変換そのものです。 具体的にはとを畳み込んで得られる長さの配列のうち、前個を新たにと呼ぶことにすると、のelementwise ANDがすべて0ならば、問題の条件を満たすtripletが存在しなく、1以上になるものがあれば存在します。

このアルゴリズムの計算量はです。

Codeforces Round #510 (Div. 2)

595位でした。前日に比べればかなりマシですが、AとCをHackされ、 さらにEよりCを優先したためさほど難しくないEを捨ててしまうという散々な結果でした。

追記）Eやっぱむずかったです。じゃあまあいつも通りの結果という感じですかね

C - Array Product

0の個数と負の個数に注目して場合分けするだけだと思うんですが、、、(6WA)

D - Petya and Array

セグ木を使って、配列にあるhoge以下の要素をで数えるやつを使います。これは非常に便利でライブラリ化していたので貼るだけでほぼ終了しました（1800点とれました！）。

具体的には累積和をとり、のを固定したときに、右はしまでに]未満の要素()がいくつあるかカウントすればいいですね。

Codeforces Round #509 (Div. 2)

散々な成績でした。C, 正解者数的にも絶対シンプルなアルゴリズムがあるのに思考を切り替えられなかったです。

codeforces.com

C - Coffee Break

1日目には、が最小なものから、差をより大きくして、選べるだけ選びます。選んだものはその都度、setから削除します。 2日目には、残った要素のなかから、同様に差をより大きくして選べるだけ選びます。 これを繰り返すとできるのですが、set.upper_boundがで動くことを知らなかったため、自らAVL木を実装する羽目に、、、

後日、気合のACです。

Submission #42969399 - Codeforces

冷静に、想定解なわけがなく、が小さい順に見ていったとき、追加できる日付を順に割り当ててやるとよいです。各日付にすでに割り当てられている最大のを保存しておくだけでいいですね（それが最小な日付に追加すればいいです）。

D - Glider

各上昇気流のスタートから飛び始めるときの答えをそれぞれ計算し、その最大値を取ります。

次以降に通過する各上昇気流のスタートまでにどれだけ下降するかは累積和を用いるとで求められ、さらに着地するまでにどこまで進めるかは二分探索でで求められます。

合わせてで解けました。

No.732 3PrimeCounting

問題

以下の相異なる3つの素数の組のうち、が素数になるものはいくつあるか。

No.732 3PrimeCounting - yukicoder

解法

100000以下の素数の個数は10000個ぐらいなので、で間に合う。ただしは以下の素数の個数。この問題の場合、自明な解が10分ぐらい待てば動くので、答えを埋め込むのも手ですが、ここでは正攻法を解説します。

triplet系の問題は一つ固定して考えるのがあまりに定石ですが、今回はとを固定します。このとき、より小さい素数の組で和がhogeになるものが何通りあるかを、あらゆるhogeについてすぐに答えられるといいです。

これを求めるのには、（に関するforループ内で）に関する2重ループを回して可能な和をすべて調べればできますが、合わせて3重ループになるのでTLEしてしまいます。しかし、数え上げに注目すると、が次のものに変わるとき、ひとつ前に数えたものはすべて重複して数えられています。が次のものに変わるとき、新しくカウントされる組み合わせはとなっているものに限られることに注目すると、オーダーが一つ落ち、間に合います。

実装

エラトステネスの篩の部分は省略しています。

bool is_prime[303030];
int cnt[303030];
vi primes;

int main() {
    init();
    int n;
    cin >> n;
    i64 ans = 0;
    for (int i = 1; i < primes.size(); i++) {
        int c = primes[i];
        if (c > n) break;
        int b = primes[i - 1];
        for (int j = 0; j < i - 1; j++) {
            int a = primes[j];
            cnt[a + b]++;
        }
        for (int j = 0; j < primes.size(); j++) {
            int sum = primes[j];
            if (sum - c >= 0) {
                ans += cnt[sum - c];
            }
        }
    }
    cout << ans << endl;
}

感想

大小関係があるtripletの数え上げは、今回のように一番大きいものを固定すると差分だけを数えられるようになってオーダーが落ちますね。典型か？

G - Sword profit

University Codesprint 5で唯一解けなかった問題。ツイッターを見る限りFよりもずいぶん簡単という評価だったのでコンテスト中に解けるようになりたい www.hackerrank.com

番目の店で本の剣を買う費用は円で、それを番目の店ですべて売ると、円の利益がでます。同じ種類の剣は複数の店で分割して売る必要がないことはちょっと考察すればわかると思います。

それぞれのに関してとを変化させて利益を最大化するという問題です。

利益を最大化するには

1. 1本あたりの売上を最大化し
2. それを利益が最大になる本数分買う

という戦略をとればいいです。1はが最小となるを見つければよく、これにはConvexHullTrickというアルゴリズムを使います。 これはを最小化するをで求めるアルゴリズムです。詳細は以下のブログで解説されています。

satanic0258.hatenablog.com

ここまでわかっても実装上のひっかけが多く、doubleでやろうとすると精度的に足りなく、i64もオーバーフローするためi128を使う必要があります。また、二次関数の最大値を求めるのに、三分探索を使ってしまうと（使う人はほとんどいないと思いますが）TLEします。i128ですし100倍近くの定数倍がかかってそうですね、、

using i128 = __int128_t;
i64 n, qs[303030], as[303030], bs[303030], rs[303030], ds[303030];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> qs[i] >> as[i] >> bs[i] >> rs[i] >> ds[i];
    }
    
    ConvexHullTrickDynamic cht;
    vi mins(n); // min_j{jx + rs[j]}, evaled at x
    for (i64 i = n - 1; i >= 0; i--) {
        cht.add(i, rs[i]);
        mins[i] = cht.get(ds[i]);
    }
    
    i64 ans = 0;
    for (i64 i = 0; i < n; i++) {
        i64 sales = max(0ll, qs[i] + i * ds[i] - mins[i]);
        auto prof = [&](i64 m) {
            return i128(sales) * m - (i128(as[i]) * m + i128(bs[i]) * m * (m + 1) / 2);
        };
        ans += prof(max(0ll, (sales - as[i]) / bs[i])) % MOD;
        ans %= MOD;
    }
    cout << ans << endl;
}

ライブラリとしてsatanic0258さんのコード、デバッグ時にUniversity CodeSprint 5 - ei1333の日記を参考にしました。

Educational Codeforces Round 50

A - Function Height

入力が大きい整数のときはdoubleの精度が足りなくなるので、整数のまま処理をしましょうという問題

B - Diagonal Walking v.2

まずゴールまで最短で行ってから、(1,1), (-1,-1)のムーブを繰り返すという戦略が最適なのであとはやるだけ

C - Classy Numbers

0からnまでのclassy numbersの数をcnt(n)とおくとcnt(R) - cnt(L - 1)で求まる。 桁dpを書くだけなんですが、本番中にすごく手間取ってしまった。

ポイントは、非ゼロの桁の数は0,1,2,3の4通りだということ。自分は1,2,3の3通りだと考えたせいで初期化が複雑になりすぎて撃沈しました。

i64 cnt(i64 n) {
    string b = to_string(n);
    vvvi dp(b.size() + 1, vvi(2, vi(4)));
    // dp[i][j][k]: 上からi桁見たときに、n未満確定で、0でない桁の数がk個のような数の個数
    dp[0][0][0] = 1;
    for (int i = 0; i < b.size(); i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 4; k++) {
                if (k < 3) {
                    for (int d = 1; d < (j ? 10 : b[i] - '0' + 1); d++) {
                        dp[i + 1][j || d < b[i] - '0'][k + 1] += dp[i][j][k];
                    }
                }
                dp[i + 1][j || 0 < b[i] - '0'][k] += dp[i][j][k];
            }
        }
    }
    i64 ret = 0;
    for (int i = 0; i < 4; i++) {
        ret += dp[b.size()][0][i] + dp[b.size()][1][i];
    }
    return ret;
}

D - Vasya and Arrays

まず、答えが存在する条件はAのsumとBのsumが等しいこと。 のとき、となるが存在するので、左端から貪欲にを決めてあげるとよい。

University Codesprint 5

AからFの6完で144位でした。

AからBの難易度の跳ね方がすごすぎて焦りました。 D問題は既出のようですね。

SPOJ.com - Problem SUBXOR

B - Array Triplets

全探索をうまくやります。最初これでTLEすると思っていて別解法を模索してたのですが、１時間経っても思いつかず、 部分点狙いで全探索書いたら通りました、、、

ちなみに最大の答えは、入力がすべて0のときで128746950通りあります。これ通るんだ、、、

それぞれの部分集合の部分和を予め全列挙しておき、１つ目の部分集合を全探索します。 部分和がsum/3になるものが見つかったら、その部分集合の補集合の部分集合で、和がsum/3になるものを全探索します。

この際、ビットによる部分集合の列挙 - SRM diary(Sigmar) - TopCoder部で解説されているように

for (int i = subset; i >= 0; i = (i - 1) & subset) {
  // subsetの部分集合iを列挙
}

で、効率よく部分集合を列挙できます。

i64 sub_sum[1 << 17];
i64 as[17];
i64 sum = 0;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> as[i];
        sum += as[i];
    }
    
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1) {
                sub_sum[i] += as[j];
            }
        }
    }
    
    if (sum % 3) {
        cout << 0 << endl;
        return 0;
    }
    
    i64 ans = 0;
    for (int i = 1; i < (1 << n); i++) {
        for (int j = i ^ ((1 << 17) - 1); j > 0; j = (j - 1) & (i ^ ((1 << 17) - 1)))  {
            if ((i | j) == (1 << 17) - 1) continue;
            if ((i & j) == 0 && sub_sum[i] == sum / 3 && sub_sum[j] == sum / 3) {
                ans++;
            }
        }
    }
    cout << ans << endl;
}

C - a,b Special Points

テクニックを知らなくても解ける問題なのでBよりも簡単だと思います。

連結成分内はもちろん行き来することができるので、uとして連結成分内で次数最小の頂点、u'として連結成分内で次数最大の頂点をとって、連結成分内で全探索すればいいです。

D - Limit XOR

調べたら既出でした。ちゃんと理解したら解説を書こうと思います。

E - Cube-loving Numbers

素数の3乗の個数だけカウントすればいいのでは？

→(2 * 3)の3乗とか重複して数えてしまうなー

→(2 * 3)の3乗はカウントから引いて、(2 * 3 * 5)の3乗とかは足せばよさそう

→各素数をたかだか1回まで使った積で表される数を列挙し、奇数回使ったものはカウントに足して、偶数回使ったものを引くと良さそう（包除原理！）

以下のコードでは最初にエラトステネスの篩を実装しており、その後似たようなアルゴリズムで、各整数が"各素数をたかだか1回まで使った積で表される数"かどうかを判定し、そうだった場合は何種類の素数の積か、そうではない場合は-1をcntという配列に記録しています。

これもかなりTLEすれすれだと思うのですが、投げたら通りました、、、

int p[1000001];
int cnt[1000001];

int main() {
    for (i64 i = 2; i < 1000001; i++) {
        p[i] = 1;
    }
    for (i64 i = 2; i < 1000001; i++) {
        if (p[i] == 0) continue;
        for (int j = 2; i * j < 1000001; j++) {
            p[i * j] = 0;
        }
    }
    for (i64 i = 2; i < 1000001; i++) {
        if (p[i]) {
            for (i64 j = 1; i * j < 1000001; j++) {
                if (cnt[i * j] != -1) {
                    cnt[i * j]++;
                }
            }
            cnt[i] = 1;
            for (i64 j = 1; i * i * j < 1000001; j++) {
                cnt[i * i * j] = -1;
            }
        }
    }
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        i64 n, ans = 0;
        cin >> n;
        
        for (i64 a = 2; a * a * a <= n; a++) {
            if (cnt[a] == -1) continue;
            if (cnt[a] % 2) {
                ans += n / (a * a * a);
            } else {
                ans -= n / (a * a * a);
            }
        }
        cout << ans << endl;
    }
}

F - Interesting Trip

各頂点に英小文字1文字のラベルが付いた非巡回な有向グラフが与えられる。スタートからゴールへ向かうパスに対して、通過した頂点のラベルを順につないでできる文字列のうち辞書順最小のものは何か、という問題。

スタートから各頂点に対して辞書順最小の文字列を記録するのは空間的に不可能なので、スタートから貪欲にできるだけ小さいラベルを辿ってゴールまで行くことを考えます。

グラフが非巡回であることからスタートからゴールに到達できる場合、解の存在が保証されます。答えとなる文字列の長さはたかだか頂点数ですが、幅優先時にqueueに入る頂点の数は、同じ頂点が複数回入ることもありえるので非常に大きくなってしまいます。

しかし、ある頂点がqueueに入っているとき、その頂点から次に進みうる頂点というのは「ゴールに到達可能なもののうち、ラベルが最小のもの」であり、これを事前計算することによってかなりの高速化ができます。

めちゃくちゃ試行錯誤した結果、以下のコードでACしました。

char name[202020];
vi adj[202020];
vi invadj[202020];
int can_finish[202020];
char min_reachable_name[202020];
vi min_reachable_adj[202020];

void dfs(int v) {
    if (can_finish[v]) return;
    can_finish[v] = 1;
    for (int i: invadj[v]) {
        dfs(i);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> name[i];
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        adj[a].push_back(b);
    }
    
    for (int i = 0; i < n; i++) {
        sort(adj[i].begin(), adj[i].end());
        adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
    }
    
    for (int i = 0; i < n; i++) {
        for (int a: adj[i]) {
            invadj[a].push_back(i);
        }
    }
    
    int s, f;
    cin >> s >> f;
    s--;
    f--;
    
    dfs(f);
    
    if (!can_finish[s]) {
        cout << "No way" << endl;
        return 0;
    }
    
    for (int i = 0; i < n; i++) {
        min_reachable_name[i] = '{';
        for (int a: adj[i]) {
            if (can_finish[a]) {
                min_reachable_name[i] = min(min_reachable_name[i], name[a]);
            }
        }
        for (int a: adj[i]) {
            if (can_finish[a] && name[a] == min_reachable_name[i]) {
                min_reachable_adj[i].push_back(a);
            }
        }
    }
    
    string ans = "";
    ans.reserve(202020);
    set<int> q1;
    q1.insert(s);
    ans += name[s];
    while (1) {
        char nxtch = '{';
        for (auto t: q1) {
            nxtch = min(nxtch, min_reachable_name[t]);
        }
        assert(nxtch != '{');
        ans += nxtch;
        set<int> q2;
        for (auto t: q1) {
            if (min_reachable_name[t] == nxtch) {
                for (int a: min_reachable_adj[t]) {
                    q2.insert(a);
                    if (a == f) {
                        cout << ans << endl;
                        return 0;
                    }
                }
            }
        }
        swap(q1, q2);
    }
}