問題の概要

0から9までの整数で構築された配列があります。この配列の部分列として2,0,2,0はいくつありますか？ただし、部分列が重なっていても別に数えます。

解法（一般論）

配列の要素を先頭から順に見ていって、そこから先の4要素が2,0,2,0かを判定すれば良いです。

具体的には、i = 0,1,....,n-4に対して、[i]=2, [i+1]=0, [i+2]=2, [i+3]=0かどうかを判定します。これはfor文の中でif文を4つ書いたりして頑張ると書けます。

後述しますが、C++では事前にstring型にしてしまってから.substr()を使う、pythonではリストのスライスを使うことで、処理を簡略化できます。

実装（C/C++）

C言語では、前述した方法をそのまま適用すれば解けます。

#include <stdio.h>

int main(){
    int n;
    while(scanf("%d", &n)){
        if(n==0)break;
        int v[1005];
        // 入力
        for(int i=0;i<n;i++)scanf("%d", &v[i]);
        // 数える変数
        int ans = 0;
        // 判定
        for(int i=0;i<n-3;i++){
            if(v[i]==2 && v[i+1]==0 && v[i+2]==2 && v[i+3]==0){
                ans++;
            }
        }
        // 出力
        printf("%d\n",ans);
    }
}

実装(C++の別解)

C++でも、C言語と同じようにすれば解けます。

別解としては、先に文字列にしてしまって、.substr(idx, len)を使う方法があります。substr(idx, len)は、文字列の添字idxから、len文字だけ切り取ります。例えば、

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s = "abcde";
    // 1番目の文字から2文字切り取る
    string sub = s.substr(1, 2);
    cout<<sub<<endl;
    // "bc"が出力される
}

です。

これを使うと、以下のように書けます。

#include <iostream>
#include <string>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        if(n==0)break;
        int v[1005];
        // 入力
        for(int i=0;i<n;i++)cin>>v[i];
        string s = "";
        // 文字列化
        for(int i=0;i<n;i++){
            s += '0'+v[i];
        }
        int ans = 0;
        // 判定
        for(int i=0;i<n-3;i++){
            // 添字iから4文字切り取る
            if(s.substr(i, 4) == "2020"){
                ans++;
            }
        }
        cout<<ans<<endl;
    }
}

判定は楽になりますが、文字列に直す処理がめんどくさいので、プラマイゼロって感じです。

実装（python）

pythonは、デフォルトで入力を文字列として受け取るので、非常に楽です。一部を切り取るのもスライス[:]でできます。

この場合に気をつけないといけないのは，文字列には空白も含むので，切り取る長さは7文字になることです．また，for文の範囲もnまでではなく，len(文字列)までになることに注意です．（以下のコードでは，スライスが配列外参照しないことを利用して，forの範囲は少しサボっています．）

while True:
    n = int(input())
    if n == 0:
        break
    # 入力
    s = input()
    ans = 0
    # 判定
    for i in range(len(s)):
        # 7文字切り取る
        if s[i:i+7] == "2 0 2 0":
            ans += 1
    print(ans)

もし、整数のリストに直したとしても、スライスで一撃です。

while True:
    n = int(input())
    if n == 0:
        break
    # 入力
    v = list(map(int, input().split()))
    ans = 0
    # 判定
    for i in range(n):
        # 4要素切り取る
        if v[i:i+4] == [2,0,2,0]:
            ans += 1
    print(ans)

A問題みたいに，特に計算量を考えなくて良い場合はpythonのがサクッと書けて良いかもしれない．

gotutiyan’s blog

ICPC 2020-A カウントダウンアップ2020 解説

問題の概要

解法（一般論）

実装（C/C++）

実装(C++の別解)

実装（python）