A. XXXXX (Codeforces Round #649 Div. 2)

問題はちゃんと読みましょう。問題はちゃんと読みましょう。

問題

https://codeforces.com/contest/1364/problem/A

問題概要

配列aと非負整数xが与えられる。aの部分列で（ここでaの部分列とはaの先頭と末尾からいくつかの（0やすべてを含む）要素を取り除いたものとする）、和がxで割り切れないもののうち、最も長いものの長さを答えよ。

そのような部分列が存在しない場合は-1と回答せよ。

考察

まずaのすべての要素がxの倍数であった時、どの部分列をとっても和はxの倍数になるので、-1と答えます。

次にaのすべての要素の和がxの倍数ではない時、これはaそのものでよいのでnを答えます。

すべての要素の和がxの倍数のときは、aからxの倍数でないものを一つ取り除けば和がxの倍数でなくなるのでそれをするのですが、この問題の部分列の定義により先頭または末尾からしか要素を取り除くことができません。よって、aを先頭と末尾から確認していって、xの倍数でないものに先に到達できる方をxの倍数でないものまで取り除いたものが答えとなります。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, x;
        cin >> n >> x;
        vector<int> a(n);
        bool ok = false;
        int r = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            a[i] %= x;
            // 一つでもxで割り切れない要素があれば解がある
            if (a[i] != 0) ok = true;
            r += a[i];
            r %= x;
        }
        if (!ok) {
            cout << -1 << endl;
        } else if (r != 0) {
            cout << n << endl;
        } else {
            int ans;
            // 先頭からチェック
            for (int i = 0; i < n; i++) {
                if (a[i] != 0) {
                    // 見つかったところまでを取り除く
                    ans = n - (i + 1);
                    break;
                }
            }
            // 末尾からチェック
            for (int i = n - 1; i >= 0; i--) {
                if (a[i] != 0) {
                    // 見つかったところまでを取り除く、先頭からの答えと比較する
                    ans = max(ans, n - (n - i));
                    break;
                }
            }
            cout << ans << endl;
        }
    }
}

Div. 2のA問題にしては結構重めですね。（なので500ではなく750なのでは、という話をTwitterで見かけました）

私の失敗

部分列の定義部分を引用します。

An array a is a subarray of an array b if a can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

私はこれを by deletion of several (possibly, zero or all) elements あたりまで読んで、「あーはいはい元の列からいくつかの要素を抜いたやつね」とかいって読み飛ばしており、任意の要素が抜けると思い込み、和がxで割り切れるケースで無条件にn - 1を出力してWAを出して、しばらく悩んでいました。

悩んでもわからなかったので、BとCを通した後、この問題に戻ってきて問題文をよく読んでようやく ... from the beginning and ... from the end のくだりに気がついて、すべてを察しました。

それならそれで consecutive 的な単語をどこかに入れといてよー、と思ったりもしましたが、まあちゃんと読まなかった私が悪いですね。はい。

まとめ

問題はちゃんと読みましょう。特に用語の定義が書かれている部分ははしょらずちゃんと読みましょう。