読者です 読者をやめる 読者になる 読者になる

ACM-ICPC World Finals 2016 D解法

D: Clock Breaking

問題

7セグデジタル時計がある。4桁とコロンの2セルの計30箇所のセグの表示がある。
この時計は壊れている可能性があり、各セグは

  1. 正しく動作する
  2. 常に0を表示する
  3. 常に1を表示する

のどれかである。
連続したn分の表示が与えられるので各セグについて、

  1. 正しく動作する
  2. 常に0を表示する
  3. 常に1を表示する
  4. 上の2つ以上に当てはまる

を判定して出力せよ。
与えられるn個の表示がどの時刻にも当てはまらないならそれを指摘せよ。

入出力例を見れば大体問題が理解できる。

解法

全ての時刻に対して、その表示が可能かどうか調べる。
可能ならば各セグはどの動作が可能か調べる。
24h * 60m * n の時刻をマッチさせる。

最初の時刻を一つ選んで、「正しい表示」と「壊れた表示」を比べる。
各セグについてn分見て、「正しい表示が0/1」の時に「壊れた表示が0/1」を出した、というのをメモする。

  • 正0壊0 and 正0壊1 => 矛盾
  • 正1壊0 and 正1壊1 => 矛盾
  • 正0壊1 and 正1壊0 => 矛盾

これらの条件を通り抜けたらその時刻は正当である。

  • 0を表示しなかった => 常に1の可能性あり
  • 1を表示しなかった => 常に0の可能性あり
  • 正0壊1も正1壊0もなかった => 正しく動作している可能性あり

この結果は同時に2つ満たすこともある。

ビット演算で解いたが時間的には配列でも間に合いそう。ただし、配列のほうが実装が楽かと言われると。

コード

#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; }

// .22.
// 0..5
// 0..5
// .33.
// 1..6
// 1..6
// .44.

pair<int, int> pos(int i, bool b) {
    if (i < 28) {
	int k = i % 7;
	static int y0[] = { 1, 4, 0, 3, 6, 1, 4 };
	static int x0[] = { 0, 0, 1, 1, 1, 3, 3 };
	static int y1[] = { 2, 5, 0, 3, 6, 2, 5 };
	static int x1[] = { 0, 0, 2, 2, 2, 3, 3 };
	static int d[] = { 0, 5, 12, 17 };

	if (b) return make_pair(y1[k], x1[k] + d[i / 7]);
	else return make_pair(y0[k], x0[k] + d[i / 7]);
    } else if (i == 28) {
	return make_pair(2, 10);
    } else {
	return make_pair(4, 10);
    }
}

int N;
char buf[7][99];
int D[111];
const int B = (1<<30) - 1;

int Z[10] = {
     1| 2| 4|   16|32|64,
                   32|64,
        2| 4| 8|16|32   ,
           4| 8|16|32|64,
     1|       8|   32|64,
     1|    4| 8|16|   64,
     1| 2| 4| 8|16|   64,
           4|      32|64,
     1| 2| 4| 8|16|32|64,
     1|    4| 8|16|32|64,
};


int M[24][60];

int mask(int h, int m) {
    int r = 0;
    r |= Z[h%10] << 7;
    h /= 10;
    if (h) r |= Z[h];
    r |= Z[m%10] << 21;
    m /= 10;
    r |= Z[m] << 14;
    r |= 1 << 28;
    r |= 1 << 29;
    return r;
}

void set(int mask, char c='X') {
    REP (i, 7) REP (j, 21) buf[i][j] = '.';
    REP (i, 30) if (mask & (1<<i)) REP (b, 2) {
	pair<int, int> p = pos(i, b);
	buf[p.first][p.second] = c;
    }
}
void show() {
    REP (i, 7) eprintf("%s\n", buf[i]);
}

int main() {
//    REP (j, 7) REP (i, 21) buf[j][i] = '.';
//    REP (i, 30) {
//	REP (b, 2) {
//	    pair<int, int> p = pos(i, b);
//	    buf[p.first][p.second] = 'x';
//	}
//    }
//    REP (j, 7) puts(buf[j]);

    scanf("%d", &N);
    REP (i, N) {
	REP (j, 7) scanf("%s", buf[j]);
	REP (k, 30) {
	    pair<int, int> p = pos(k, 0);
	    if (buf[p.first][p.second] == 'X') D[i] |= 1 << k;
	    buf[p.first][p.second] = ' ';
	}
    }


    REP (h, 24) {
	REP (m, 60) {
	    M[h][m] = mask(h, m);
//	    set(M[h][m]); show(); eprintf("\n");
	}
    }


    int cnt = 0;
    int ans[3] = {};

    REP (h_, 24) REP (m_, 60) {
	int W[2][2] = {};
	int h = h_, m = m_;
	REP (i, N) {
	    int mk = M[h][m];
	    W[0][0] |= ~mk & ~D[i];
	    W[0][1] |= ~mk &  D[i];
	    W[1][0] |=  mk & ~D[i];
	    W[1][1] |=  mk &  D[i];

	    m++;
	    if (m == 60) {
		m = 0;
		h++;
		if (h == 24) h = 0;
	    }
	}
	
	if ((B & W[0][0] & W[0][1]) || (B & W[1][0] & W[1][1]) || (B & W[0][1] & W[1][0])) {
	} else {
	    cnt++;

	    ans[0] |= B & ~W[0][1] & ~W[1][1];
	    ans[1] |= B & ~W[0][0] & ~W[1][0];
	    ans[2] |= B & ~W[0][1] & ~W[1][0];
	}
    }


    if (cnt == 0) {
	puts("impossible");
    } else {
	REP (i, 7) REP (j, 21) buf[i][j] = '.';
	REP (i, 30) REP (b, 2) {
	    pair<int,int> p = pos(i, b);
	    VI v;
	    REP (k, 3) if (ans[k] & (1<<i)) v.push_back(k);
	    if (v.size() == 1u) {
		buf[p.first][p.second] = "01W"[v[0]];
	    } else if (v.size() == 0u) {
		buf[p.first][p.second] = ' ';
	    } else {
		buf[p.first][p.second] = '?';
	    }

	}

	REP (i, 7) puts(buf[i]);
    }

    return 0;
}

日記

7セグの定数を大量に埋め込む必要がある正直面倒。
ICPCらしいような気もする。