Mister雑記

競プロやります。

1日目 CFR536(Div2)

32分4完。E以降通してる人多くない1

codeforces.com

目次


A. Cross Counting [800]

Problem - A - Codeforces

概要

X.からなる N \times Nのグリッドが与えられる。このとき、 (x, y), (x \pm 1, y \pm 1) (複号任意)の5マス全てがXであるような (x, y)の数を求めよ。

制約

  •  1 \leq N \leq 500

解説

実際に全ての 1 \leq x, y \leq N - 1について調べればいい。

実装例

今回から実装例は折りたたむことにした。

C++

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s[n];
    for (int i = 0; i < n; ++i) cin >> s[i];

    int ans = 0;
    for (int x = 1; x < n - 1; ++x) {
        for (int y = 1; y < n - 1; ++y) {
            if (s[x][y] != 'X') continue;

            bool judge = true;  // 周囲4マスが全てXか判定
            for (int dx = -1; dx <= 1; dx += 2) {
                for (int dy = -1; dy <= 1; dy += 2) {
                    if (s[x + dx][y + dy] != 'X') judge = false;
                }
            }

            if (judge) ++ans;
        }
    }

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


B. Food Ordering [1500]

Problem - B - Codeforces

概要

あるレストランには n種類の料理がある。料理 iの値段は c_iで、最初 a_i皿用意されている。

これから m人の客が来る。 j人目の客は料理 t_j d_j皿頼む。レストランは、残った皿の数に応じて以下のように1皿ずつ料理を出す。

  1.  t_jが残っているとき。 t_jを1皿出す。
  2.  t_jが残っていないとき。他に残っている料理で最も安いものを選び、それを1皿出す。
  3. 1つも料理が残っていないとき。客は怒って帰る。

客は出した料理の分だけお金を払うが、怒って帰る場合は何も支払わない。なお客が怒って帰る場合でも、出せるだけ料理は出さねばならない。

このときそれぞれ客について、その客が払う金額を求めよ。

制約

  •  1 \leq n, m \leq 10^5
  •  1 \leq a_i \leq 10^7,  1 \leq c_i \leq 10^6
  •  1 \leq t_j \leq n,  1 \leq d_j \leq 10^7

解説

普通にシミュレーションをしようとすると、最も安い料理を求める部分がボトルネックとなる。

そこで安い順に料理を並べた配列 orderを作り、どの料理まで使い切ったかを記録しておく。こうすることで毎回全部探索しなくてもよくなり、十分高速に解ける。

ちなみにTutorial解法はpriority_queueに料理を安い順に突っ込んでいる。そっちの方が実装が楽そうな気がする。

実装

比較関数でconst参照渡ししてないけど、コピーは大したコストでもないのでまぁ。

C++

#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;
using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;

    ll a[n], c[n];
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> c[i];

    int order[n];
    iota(order, order + n, 0);
    sort(order, order + n, [&](int i, int j) { return c[i] < c[j]; });
    // 値段が安い順にソート

    int itr = 0;
    for (int i = 0; i < m; ++i) {
        int t;
        ll d;
        cin >> t >> d;
        --t;
        ll ans = 0;

        while (d > 0 && itr < n) {
            ll g = min(d, a[t]);  // tを出せる最大枚数
            ans += c[t] * g;
            d -= g, a[t] -= g;

            if (t != order[itr]) {
                t = order[itr];  // 最初だけ例外処理
            } else if (a[t] == 0) {
                t = order[++itr];  // 次に安い料理へ
            }
        }

        // d > 0なら客は怒って帰ったので0
        cout << (d == 0 ? ans : 0) << endl;
    }
    return 0;
}


C. Number Division [1000]

Problem - C - Codeforces

概要

 n個の整数 \{a_i\}が与えられる。これをそれぞれ大きさ2以上のいくつかの集合に分割する。

 m個の集合に分割したとする。 j個目の集合の総和が s_jのとき、スコアは \displaystyle \sum_{j=1}^{m} (s_j)^2で与えられる。このスコアの最小値を求めよ。

制約

  •  2 \leq n \leq 3 \cdot 10^5
  •  n偶数
  •  1 \leq a_i \leq 10^4

解説

まず、各集合の大きさはできるだけ小さい方がよい。これはなぜかというと、

 \displaystyle \left( \sum_{i=1}^{k} a_i \right)^2 = \sum_{i=1}^{k} (a_i)^2 + \sum_{i=1}^{k} \sum_{j=i+1}^{k} 2 a_i a_j

の第2項が最小になるからだ。よって2個ずつに \{a_i\}を分割すればよい(制約から nは偶数であることに注意)。


ではどうやってペアを組んでいけばいいだろうか?これは、一番小さいものと大きいもの同士を順に組んでいくのがよい。

これも証明しておく。 a \leq b \leq c \leq dとしたとき、

\begin{align} \left( (a + c)^2 + (b + d)^2 \right) - \left( (a + d)^2 + (b + c)^2 \right) &= (2ac + 2bd) - (2ad + 2bc) \\ &= (a - b)(c - d) \geq 0 \end{align} \begin{align} \left( (a + b)^2 + (c + d)^2 \right) - \left( (a + d)^2 + (b + c)^2 \right) &= (2ab + 2cd) - (2ad + 2bc) \\ &= (a - c)(b - d) \geq 0 \end{align}

 \{a, d\}, \{b, c\}にてスコアが最小になるからだ。

実装例

C++

#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

inline ll sq(ll a) { return a * a; }

int main() {
    int n;
    cin >> n;
    ll a[n];
    for (int i = 0; i < n; ++i) cin >> a[i];

    sort(a, a + n);
    ll ans = 0;
    for (int i = 0; i < n / 2; ++i) ans += sq(a[i] + a[n - i - 1]);
    cout << ans << endl;
    return 0;
}


D. Wander [1500]

Problem - D - Codeforces

概要

 n頂点 m辺の無向連結グラフがある。辺 iは頂点 u_i v_iを結んでいる。

あなたは最初頂点 1にいる。また、あなたはノートを持っていて、最初ノートには 1だけ書かれている。

あなたは辺を通って他の頂点に移動できる。もしも移動した頂点が初めて訪れたものだった場合、ノートにその頂点を書き加える。なお書き加えずにスルーすることはできない。

全ての頂点を訪れた後にノートに書かれうる数列で、辞書順最小のものを求めよ。

制約

  •  1 \leq n, m \leq 10^5
  •  1 \leq u_i, v_i \leq n
  • グラフは連結だが単純とは限らない。

解説

「辞書順は貪欲」という言葉がある通り、この問題も貪欲が解法となる。具体的には「行ける頂点の中で最も小さい頂点に移動」を繰り返せば良い。

ここで「行ける頂点」とは何かといえば、「過去に訪れた頂点と隣接している頂点」である。これは過去に訪れた頂点の集合は連結であることから従う。

よって「隣接した頂点を全て昇順priority_queueに突っ込む↔先頭を取り出す」を繰り返せば良い。感覚としてはPrim法に近い。

実装例

C++

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> path[n];
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        path[u].push_back(v);
        path[v].push_back(u);
    }

    priority_queue<int, vector<int>, greater<int>> que;
    que.push(0);

    bool visited[n];
    fill(visited, visited + n, false);
    visited[0] = true;

    while (!que.empty()) {
        int v = que.top();
        que.pop();
        cout << v + 1 << " ";

        for (int sv : path[v]) {
            if (!visited[sv]) {
                que.push(sv);
                visited[sv] = true;
            }
        }
    }

    cout << endl;
    return 0;
}

E以降について

バチャ中に通したのはこの4問だが、E以降は正直疲れてまともに考えてなかった。

EはDPというのは分かるが、遷移を高速に前計算する方法が遅延セグ木しか思いつかなかった。というわけで明日は遅延セグ木を実装しようと思う。ちなみに遅延セグ木なしでも解けるらしい(それはそう)。

Fは知らんけどヤバそう。

感想

  • 明日から朝にやることにする。
  • 自明な問題は解説書かんでもいいね。

  1. RatedでE通してる人は331人だった。そんな多くないか?