NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ,自然言語処理 (ブログではまだ)。数式の書き方を一気に KaTeX に変えようとして記事を全削除してインポートし直すなどしたので,過去にブックマークされた記事は URL が変わってしまっている可能性があります…….

最近の WA/TLE/MLE/RE 原因

とりあえず今月中は随時更新してみる

1. 誤読

  • 正の数とは限らない入力を正だと思い込んでいた
  • $10^9+7$で割った余りを求めなければならないと思い込んでいた

2. 考察ミス

  • 必要十分条件を考えなければならない場面で十分条件だけ挙げて満足
  • 最小ケースを考慮していなかった
  • 解とその構成方法を示す問題で、解と構成方法が矛盾していた
  • 途中計算の結果が負になった場合を考慮していなかった
  • 最後の地点から初期地点に戻らないといけない問題で、初期地点に戻すコストを考慮していなかった

3. 実装ミス

3-1. 入力受け取り

3-2. solve

  • 小さい順に見ないといけないのにソートし忘れた
  • 配列外参照を起こすスニペットをずっと気づかず使っていた
  • long long にすべき変数を int にしていた
  • 128ビット整数を使うべき変数を long long にしていた

3-3. 出力

  • for 文の手癖が原因で <= とすべきところまで < と書いていた
  • 出力の途中の改行が必要な部分で改行していなかった

AtCoder Regular Contest 104 C - Fair Elevator

問題: C - Fair Elevator

解説: 公式解説

問題概要

$1$ 以上 $2N$ 以下の整数からなる数列 $A = A_1, A_2, \dots A_N$ および $B = B_1, B_2, \dots B_N$ が与えられる。ただし $A$, $B$ は一部の値が欠損している場合がある。$A$, $B$ の欠損した値を適切に埋めて、次の条件をすべて満たすことができるかを Yes または No で答えよ。

  • $1$ 以上 $2N$ 以下の整数が1回ずつ使われる。
  • $A_i < B_i$ である。
  • 区間$\left[ A_i, B_i\right]$ と $\left[ A_j, B_j\right]$ について、区間に重なりがある場合は $B_i - A_i - 1 = B_j - A_j - 1$ である。

解法概要

まず、与えられた入力が初めから条件を満たしていない場合は明らかに No である。例えば、$A_i \gt B_i$ となるような $i$ が初めから存在していたり、入力で同じ整数が2回使われているような場合がこれにあたる。

以下、そうでない場合を考える。

ある $i$ について $A_i = x, B_i = y (\gt x+2)$ だった場合、$A_j = x+1$ であるような $j$ については問題の条件より $B_j = y+1$ である。 同様に、$A_j = x+2$ であるような $j$ については問題の条件より $B_j = y+2$ である。

したがってこの問題は、 $i$ 文字目が整数 $i$ に対応するとして

ABCABC/DEDE/FF/GHIGHI.....

というような (同じ文字を持つものがペアに分かれるイメージ) 区間に $1$ 以上 $2N$ 以下の整数を分けていくような問題になる。

$i+1$ 以上の整数について考えるとき、 $i$ 以下の整数は「矛盾なくペアに分けられる」ということさえわかっていればよく、その分け方を知っている必要はない。したがって、以下のような DP が考えられる。

$\mathit{dp}_{i} =$ ($1$ 以上 $2i$ 以下の整数を矛盾なく $i$ 組のペアに分けることができるか否か?)

更新するときは、 $\mathit{dp}_i = \mathrm{true}$ となるような $i$ からさらに $j$ 組のペアを追加することを考えれば良い。

「矛盾なくペアに分けられる」と一言で書いてしまったが、これは実際に値を埋める必要はなく、今の地点で入ってる値を検査するだけで良い。 詳しい条件はソースコード参照。

ソースコード

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n, -1), b(n, -1);
    for(int i=0;i<n;++i) {
        cin >> a[i] >> b[i];
    }

    // 使用済みの数字はチェックしておいて、
    // あとで「ペアになるべき数字が他の場所で使われていないか?」の判定に使う
    vector<bool> used(2*n+1, false);
    // 最初からすでにおかしくない? をチェック
    for(int i=0;i<n;++i) {
        if((a[i] != -1 && used[a[i]]) || (b[i] != -1 && used[b[i]])) {
            cout << "No" << endl;
            return 0;
        }
        if(a[i] != -1 && b[i] != -1 && a[i] > b[i]) {
            cout << "No" << endl;
            return 0;
        }
        if(a[i] != -1) used[a[i]] = true;
        if(b[i] != -1) used[b[i]] = true;
    }

    vector<bool> dp(n+1, false);
    dp[0] = true;
    for(int i=0;i<n;++i) { // すでに決まっているペア数
        if(!dp[i]) continue;
        for(int j=1;j<=n-i;++j) { // j ペア分追加できるか見る
            if(dp[i+j]) continue;
            // 2*i+1, 2*i+2, ..., 2*i+2*j-1, 2*i+2*j を正しく配置できる?
            bool ok = true;
            for(int k=0;k<n&&ok;++k) { // 追加して矛盾しないかどうか一通り見て回る
                // a は今注目している範囲の中か?
                bool in_a_range = (2*i+1 <= a[k]) && (a[k] <= 2*i+j);
                // b は今注目している範囲の中か?
                bool in_b_range = (2*i+j+1 <= b[k]) && (b[k] <= 2*i+2*j);
                // 両方値が設定済み
                if(a[k] != -1 && b[k] != -1) {
                    // 今注目している範囲に片方だけおさまっていたら OUT
                    if(in_a_range ^ in_b_range) ok = false;
                    // 今注目している範囲内で、かつ差が j 以外でも OUT
                    if(in_a_range && in_b_range && b[k] - a[k] != j) ok = false;
                }
                // a 設定済み (b は問わない)
                if(a[k] != -1) {
                    // a なのに b が入るべき範囲内に入っていたら OUT
                    if(2*i+j+1 <= a[k] && a[k] <= 2*i+2*j) ok = false;
                    // a が今注目している範囲の中で、かつペアになるはずのものが他の場所で使用済みだったら OUT
                    if(in_a_range && b[k] != a[k]+j && used[a[k]+j]) ok = false;
                }
                // b 設定済み (a は問わない)
                if(b[k] != -1) {
                    // b なのに a が入るべき範囲内に入っていたら OUT
                    if(2*i+1 <= b[k] && b[k] <= 2*i+j) ok = false;
                    // b が今注目している範囲の中で、かつペアになるはずのものが他の場所で使用済みだったら OUT
                    if(in_b_range && a[k] != b[k]-j && used[b[k]-j]) ok = false;
                }
            }
            dp[i+j] = ok;
        }
    }
    cout << (dp[n] ? "Yes" : "No") << endl;
}

所感

これは AC までいかなくともキーになる考え (1 から 2n までを ABCABC DEDE みたいな区間に分ける問題に言い換えられる) は気づきたかった。 解説チラ見してからも条件の考慮もれがたくさんあって、自分のこういうところが PG BATTLE で危ないんだよなあと思った。

それはそれとして問題自体は好き。最近、区間 DP 得意になりたい。

AtCoder Beginner Contest 173 F - Intervals on Tree

問題: F - Intervals on Tree

公式解説: 解説 pdf

問題概要

$N (\leq 2 \times 10^5)$ 頂点の無向木がある。整数 $1 \leq L \leq R \leq N$ について,関数 $f(L, R)$ を次のように定義する。

  • $S$ を$L$ 以上 $R$ 以下の番号のついた頂点からなる集合とする。頂点集合 $S$ と両端が $S$ に属する辺からなる部分グラフの連結成分の数を $f(L, R)$ とする。

$\sum_{L=1}^{N} \sum_{R=L}^N f(L, R)$ を求めよ。

解法概要

コンテスト中は「木を根付き木と考えて連結成分の値となりうる回数について全方位木 DP とか……?」と考えて泥沼に陥ってしまった (これでも解けないわけではない? わからん) が,もっとシンプルに考えられる。

両端が $S$ に属する辺を1本使うと,頂点集合 $S$ を使った部分グラフの連結成分の数は必ず 1 つ減る。つまり,辺を使わない場合の連結成分 (= 頂点) 数の合計から,各辺が使われることによって減る連結成分の数の合計を引けば良い。

辺が1本もない場合を考えてみる。辺がない場合の連結成分の個数は頂点数に等しいので

$\sum_{L=1}^{N} \sum_{R=L}^N (R-L+1)$

$= \sum_{L=1}^{N} \sum_{r=1}^{N+1-L} r$

($m = N + 1 - L$ として)

$= \sum_{L=1}^{N} \sum_{r=1}^{m} r = \sum_{L=1}^{N} \frac{m(m+1)}{2} = \frac{1}{2} ( \frac{1}{6}N(N+1)(2N+1) + \frac{N(N+1)}{2} )$

($L = 1$ のとき $m = N + 1 - 1 = N$, $L = N$ のとき $m = N + 1 - N = 1$).

ここから,各辺によって連結成分が減らされる回数の合計を求めたい。これは,例えば辺 $(u, v)$ があって $u \lt v$ の場合,この辺によって連結成分が減らされる回数は $u (n+1-v)$ 回である。これは, $u$ が含まれるような $L$ の選び方は $u$ 通り,$v$ が含まれるような $R$ の選び方は $n+1-v$ 通りあるので,$u$ と $v$ が両方含まれる $S$ の選び方の通り数が $u (n+1-v)$ 通りとなるためである。これをすべての辺について計算して,先ほど求めた辺がない場合の連結成分の個数の合計から引けば良い。

ソースコード

#include <iostream>
#include <algorithm>

using namespace std;

using ll =  long long;

int main() {
    ll n, u, v;
    cin >> n;
    ll ans = (n * (n+1) * (2*n+1) / 6 + n * (n+1) / 2) / 2;
    for(int i=0;i<n-1;++i) {
        cin >> u >> v;
        ans -= min(u, v) * (n - max(u, v) + 1);
    }
    cout << ans << endl;
}

所感

発想次第でとてもシンプルになる問題。オーバーフローにだけ注意。