公式

C - 交通渋滞の報告 / Traffic Jam Report 解説 by MMNMM

この問題は、それぞれの渋滞ブロックの長さを求めることができれば解くことができます。

渋滞ブロックの長さを求める方法はいろいろありますが、この解説では連長圧縮（ランレングス圧縮）のアルゴリズムを意識した実装について解説します。

連長圧縮と連長圧縮を求めるアルゴリズムについて

列 \(X=(x _ 1,x _ 2,\ldots)\) に対する連長圧縮とは、\(X\) で連続する要素をまとめて個数と組にしたものです。 例えば、列 \((1,1,1,2,2,3,3,3,3)\) を連長圧縮したものは \(((1,3),(2,2),(3,4))\) となります。

厳密には、\(X=(x _ 1,x _ 2,\ldots)\) の連長圧縮は \(2\) つ組の列 \(((x ^ \prime _ 1,c _ 1),(x ^ \prime _ 2,c _ 2),\ldots,)\) であって以下の条件を満たすものです。

  • \(x ^ \prime _ i\ne x ^ \prime _ {i + 1}\)
  • \(\displaystyle\sum _ {j=1} ^ {i-1}c _ j\lt k\le\sum _ {j=1} ^ ic _ j\) なら \(x _ k=x ^ \prime _ i\)

連長圧縮は、以下のようなアルゴリズムで求めることができます。

  • はじめ、\(p\leftarrow x _ 1,c\leftarrow0\) と初期化する。
  • \(i=1,2,\ldots\) について以下を繰り返す。
    • \(p\ne x _ i\) なら、末尾に \((p,c)\)を追加し、\(c\leftarrow0\) と更新する。
    • \(p\leftarrow x _ i,c\leftarrow c+1\) と更新する。
  • 列を全て読み終わったら、末尾に \((p,c)\) を追加する。

列の最後に番兵を置いておくことで、最後の追加処理をなくすこともできます。

この問題は以下のようにして解くことができます。

  • はじめ、\(c _ 1\leftarrow0,\text{ans}\leftarrow0\) と初期化する。
  • \(i=1,2,\ldots,N\) について以下を繰り返す。
    • \(S _ i=0\) かつ \(c _ 1\ge K\) なら、\(\text{ans}\leftarrow\text{ans}+1\) と更新する。
    • \(S _ i=0\) なら \(c _ 1\leftarrow0\) と更新する。
    • \(S _ i=1\) なら \(c _ 1\leftarrow c _ 1+1\) と更新する。
  • 列を全て読み終わったときに \(c _ 1\ge K\) なら、\(\text{ans}\leftarrow\text{ans}+1\) と更新する。

上で述べた連長圧縮を求めるアルゴリズムと比較すると、\(c _ 1\) は \(p=1\) のとき \(c\) 、\(p\ne1\) のとき \(0\) となる値だと考えることができます。 これは、今見ている渋滞ブロックの長さだと思うこともできます。

同様に、列の最後に番兵を置いておくことで最後の処理をなくすこともできます。

実装例は以下のようになります。

#include <iostream>
using namespace std;

int main(){
    int N, K;
    cin >> N >> K;

    int c = 0, ans = 0;
    for (int i = 0; i < N; ++i) {
        int S;
        cin >> S;
        if (S == 0) {
            if (c >= K) { // 渋滞ブロックの長さが K 以上なら
                ++ans; // 答えを増やす
            }
            c = 0;
        } else { // S = 1 なら
            ++c; // 渋滞ブロックの長さを増やす
        }
    }
    if (c >= K) {
        ++ans;
    }

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

N, K = map(int, input().split())
S = list(map(int, input().split())) + [0] # 番兵を置いておく

c = 0
ans = 0
for s in S:
    if s == 0:
        if c >= K: # 渋滞ブロックの長さが K 以上なら
            ans += 1 # 答えを増やす
        c = 0
    else: # s = 1 なら
        c += 1 # 渋滞ブロックの長さを増やす

print(ans)

投稿日時:
最終更新: