ACM-ICPC World Finals 2016 M解法

M: What Really Happened on Mars?

問題

t個のタスクがある。各タスクは命令の列で、命令は3種類

  1. compute : 1クロック消費する。
  2. lock k : リソースkをロックする
  3. unlock k : リソースkをアンロックする

各タスクiは開始の時刻t_iと優先度p_iを持ち、時刻になると先頭の命令から順に実行可能になる。
実行中のタスクから最も優先度の高いタスクを選んでそれを実行することに成る。

優先度について、各リソースはceiling priority (cp)を持つ。
リソースjのcp_jは「リソースjを(過去・未来問わず)ロックする命令を持つタスクのp_iの最大値」である。

実行中のタスクとは開始時刻が現在時刻以前で、まだ実行されていない命令を持つものである。

各実行中のタスクiのcurrent priority (s) とは後述の方法で決定される。

以下の方法で次に実行するタスクの命令を決定する。

  1. 実行中のタスクを列挙する
  2. 実行中のタスクのsを決定する。s_i はp_i以上である。また、タスクiの次の命令がlock kで、次のリソースkがロックされているかcp_jがp_i以上のリソースjがロックされているときのいずれかを満たすならばiはブロックされているという。ブロックしているタスクのs_iはp_iとブロックされているタスクのs_lの最大値である。
  3. ブロックされていない実行中のタスクでs_iが最大の物の命令を実行する

s_iは定義が循環しているが一意に定まる。
この手順を繰り返して全ての命令が終了する時刻を求めよ。

制約

タスク <= 20
リソース <= 20
各命令数 <= 100

解法

ブロックされている関係を列挙し、止まるまで更新し続けるとcurrent priorityは一意に求まる。
ただそれだけの問題。

まとめると、

  • タスクi :
    • p_i : タスク固有の優先度
    • t_i : タスクの開始時刻
    • s_i : タスクのcurrent priority。実行中に限り、s_i := max { p_i, { s_j : タスクiはタスクjをブロックする} }
  • リソースk :
    • cp_k : ceiling priority。 cp_k := max { p_i : タスクiの命令にlock kが存在する }
  • ブロック :
    • 「タスクiがタスクjをブロックする」iff (i、jが実行中) && (iの次のタスクがlock k) && ((タスクjがリソースkをロックしている) || ((タスクjがリソースlをロックしている) && (cp_l >= p_i)))

コード

#include<cassert>
#include<stack>
#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; }

char buf[99];

int N, R;
int start[21], priority[21];
vector<pair<char, int> > work[21]; // (op, val)
int iter[21];
int ceiling[21];
int lock[21];
int running[21];
int current[21];
bool blocked[21];
int ans[21];
pair<int, int> ord[21];

int main() {
    while ( scanf("%d%d", &N, &R) != EOF) {
	if (N+R == 0) break;

	memset(ceiling, 0, sizeof ceiling);
	memset(ans, 0, sizeof ans);
	memset(running, 0, sizeof running);
	memset(iter, 0, sizeof iter);

	REP (i, N) {
	    work[i].clear();

	    int len;
	    scanf("%d%d%d", start+i, priority+i, &len);
	    REP (j, len) {
		scanf("%s", buf);
		int val = atoi(buf+1);
		if (buf[0] != 'C') val--;

		work[i].push_back(make_pair(buf[0], val));
		if (buf[0] == 'L') amax(ceiling[val], priority[i]);
	    }
	    ord[i] = make_pair(priority[i], i);
	}


	sort(ord, ord+N); reverse(ord, ord+N);
	memset(lock, -1, sizeof lock);

	int cnt = -10;
	int I = -1, P = -1;
	bool updated = true;
	int finished = 0;

	while (true) {
	    if (finished == N) break;
	    assert(cnt < 10000000);

	    REP (i, N) if (start[i] <= cnt && running[i] == 0) { running[i] = 1; updated = true; }

	    if (true) {
		memset(current, -1, sizeof current);
		memset(blocked, 0, sizeof blocked);

		REP (i, N) {
		    int pri = ord[i].first;
		    int s = ord[i].second;
		    if (running[s] == 1 && current[s] < pri) {
			current[s] = pri;

			stack<int> S; S.push(s);
			while (!S.empty()) {
			    s = S.top(); S.pop();
			    assert(current[s] == pri);

			    pair<char, int> op = work[s][iter[s]];
			    if (op.first == 'L') {
				if (lock[op.second] != -1) {
				    blocked[s] = true;
				    int k = lock[op.second];
				    assert(k != s);
				    if (current[k] < pri) {
					current[k] = pri;
					S.push(k);
				    }
				}
				REP (j, R) if (lock[j] != -1 && lock[j] != s && ceiling[j] >= pri) {
				    blocked[s] = true;
				    int k = lock[j];
				    if (current[k] < pri) {
					current[k] = pri;
					S.push(k);
				    }
				}
			    }
			}
		    }
		}

		I = -1; P = -1;
		REP (i, N) if (running[i] == 1 && !blocked[i] && P < current[i]) {
		    I = i;
		    P = current[i];
		}

		int zz = 0;
		REP (i, N) if (running[i] == 1 && !blocked[i] && P == current[i]) zz++;
		assert(zz < 2);
		updated = false;
	    }

	    if (I == -1) {
		++cnt;
		continue; 
	    }

	    pair<char, int> &op = work[I][iter[I]];
	    if (op.first == 'C') {
		op.second--;
		cnt++;

		if (op.second == 0) {
		    updated = true;
		    iter[I]++;
		}
	    } else if (op.first == 'L') {
		assert(lock[op.second] == -1);
		updated = true;
		lock[op.second] = I;
		iter[I]++;
	    } else {
		assert(lock[op.second] == I);
		updated = true;
		lock[op.second] = -1;
		iter[I]++;
	    }

	    if (iter[I] == (int)work[I].size()) {
		assert(ans[I] == 0);
		ans[I] = cnt;
		running[I] = 2;
		finished++;
		I = -1;
	    }

	}

	REP (i, N) printf("%d\n", ans[i]);
    }

    return 0;
}

日記

この問題は非常に読みづらい。
私の言語能力に問題があるため、題意の理解も、その和訳・意訳も難しい。
current priorityのパートが確証を得るのは難易度が高いが実装としては問題セットの中でも簡単な方である。