ACM-ICPC World Finals 2016 K解法

K: String Theory

問題

文字列について、先頭と末尾が「'」(シングルクォート) で、間にアルファベットのみが0文字以上あるものを1-quotationと定義する。
k > 1について、先頭と末尾がちょうどk個のシングルクォートで、間には「(k-1)-quotationとシングルクォートを含まない文字の二種類の、合わせて0個以上の任意の順番の連結」であるものと定義する。
文字列Sが与えられるが k-quotation のkを求めよ。
複数ある場合は最大、存在しない場合はそれを指摘し出力せよ。
Sは連続したシングルクォートのみ切り出して、その長さを持って与えられる。
例えば「3 2 5」が入力で与えられた時はSは '''(任意のアルファベット列)''(任意のアルファベット列)''''' を意味する。

制約

n <= 100
a_i <= 100

解法

連続したシングルクォートは100以下なので解も100以下。
例えばa_0 = 99のとき、50と49に分けるなどが考えられる。
全てのkについて、両端から貪欲に取っていき、kを1づつ減らし、残りは1-quotationということにすればよい。

コーナーケースとして、

• シングルクォートの個数の合計が奇数
• 「1 1 1 1」などは1-quotationになれない
• 1-quotation になれるのは 「2」と「1 1」のみ

コード

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }


int N, A[111], B[111];
bool ok(int K) {
    REP (i, N) B[i] = A[i];

    int k = K;
    REP (i, N) {
	if (k == 0) break;
	if (B[i] < k) return false;
	B[i] -= k;
	k--;
	if (B[i]) i--;
    }
    if (k) return false;
    k = K;
    for (int i=N; i--; ) {
	if (k == 0) break;
	if (B[i] < k) return false;
	B[i] -= k;
	k--;
	if (B[i]) i++;
    }
    return k == 0;
}

int main() {
    scanf("%d", &N);
    REP (i, N) scanf("%d", A+i);

    int c = 0;
    REP (i, N) c += A[i];

    for (int i=A[0]; i>0 && c % 2 == 0; i--) {
	if (ok(i)) {
	    if (i != 1 || c == 2) {
		printf("%d\n", i);
		return 0;
	    }
	}
    }

    puts("no quotation");
    return 0;
}