AOJ2032 Online Quiz System - nanikakaのAOJ航海日誌

概要

オンラインクイズゲームシステムのシミュレートを行い、サーバとクライアント間のデータ通信量を答えよ。
プレイヤー数はM、問題数はNである。
クライアント側のプログラムは全て同じである。
全問題文は事前にダウンロードされており、このデータ通信量はシミュレートに含めなくてよい。
システムは次のように動く

最初の問題文が表示される。プレイヤーは制限時間内に解答する。その後2番目の問題が表示される。これがN問繰り返される。N問繰り返されたらゲームが終了する。

各問題フェーズでは、プレイヤーは他のプレイヤーに関する情報が送信される。
プレイヤーが解答提出をしていない場合: 解答した人物が通知される
プレイヤーが解答提出を済ませている場合: 他の人がなんという解答をしたかが通知される

各問題フェーズが始まるとき、サーバは a synchronization packet for problem-start を全プレイヤーに送り、同時にポーリングを開始する。ポーリング開始から1000ms毎に、サーバはその時刻以前(strictly)にプレイヤーから解答を受け取っていないかを調べる。あれば全プレイヤーに次のような通知を送る。
解答未提出のプレイヤー: 新たにサーバが受け取った分に関して、notificaton packet type Aを送る
新たに解答を提出したプレイヤー: 厳密にこの時間以前に受け取った分に関して、他人の解答をnotificaton packet type Bにて送る。このパケットに自分自身の解答は含まれない
解答提出済みのプレイヤー: 新たにサーバが受け取った分に関して、notification packet type Bを送る
これらのパケットには他人の情報が1件以上含まれていなければならない。さもなければ、そのパケットは破棄される。
a synchronization packet for problem-startが送られてから20000ms経ったとき、必要ならtype A, type Bのパケットを送信したあと、problem-endパケットを全プレイヤーに送り、その問題を終了する。

プレイヤーはproblem-startを受け取った後、problem-endを受け取るまで、answer packetを送って解答を送ることができる。

1 <= M, N <= 100

解法

シミュレーションをがんばります。
ただこの問題はちょっとひどい所があって、遅延についてほとんど説明がないことです。
入力の説明を見ると急に、クライアント毎にdelay timeという値があるのですが、これがシミュレートにどう影響を及ぼすか書かれていないのです。いや、問題文の最初の方に、「In particular, much attention should be paid to the delay on receiving packets.」と書いてあることはあるんですが、シミュレート問題なんだからもっと具体的に書いておいて欲しかった。
結論からいうと、遅延はサーバから送信するときと受信するとき、両方で起こります。これを踏まえて入力で
P T A
と来たときを考えてみます。Tはクライアントがproblem-startを受け取ってからサーバへ送信したときのクライアント側の時間のことです。クライアントはこのproblem-startを受信するときに既にD遅延しており、サーバへ送信するときに更にDだけ遅延するので、結局、サーバ内時間で、この解答パケットを受け取るのはT + 2*Dになります。このことさえ気を付ければあとはシミュレートをガリガリ書くだけだと思います。

ソース

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

//Online Quiz System
public class AOJ2032 {

	int WORK = 0, START = 1, END = 2, SUBMIT = 3;
	
	class E implements Comparable<E>{
		int type, t, id;
		public E(int type, int t, int id) {
			this.type = type;
			this.t = t;
			this.id = id;
		}
		public int compareTo(E o) {
			return t!=o.t?t-o.t:type-o.type;
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		boolean[] just = new boolean[100], sub = new boolean[100];
		int[] L = new int[100], send = new int[100], rev = new int[100], delay = new int[100];
		for(boolean H=true;;H=false){
			int M = sc.nextInt(), N = sc.nextInt();
			if((M|N)==0)break;
			if(!H)System.out.println();
			Arrays.fill(send, 0); Arrays.fill(rev, 0);
			for(int i=0;i<M;i++)delay[i]=sc.nextInt();
			while(N--!=0){
				Arrays.fill(L, 0); Arrays.fill(just, false); Arrays.fill(sub, false);
				PriorityQueue<E> q = new PriorityQueue<E>();
				q.add(new E(START, 0, -1)); q.add(new E(END, 20000, -1));
				for(int t=1000;t<=20000;t+=1000)q.add(new E(WORK, t, -1));
				int k = sc.nextInt();
				while(k--!=0){
					int id = sc.nextInt(), t = sc.nextInt(), len = sc.next().length();
					q.add(new E(SUBMIT, t+delay[id]*2, id));
					L[id] = len;
				}
				while(!q.isEmpty()){
					E e = q.poll();
					if(e.type==START){
						for(int i=0;i<M;i++)rev[i]+=3;
					}
					else if(e.type==END){
						for(int i=0;i<M;i++)rev[i]+=4; break;
					}
					else if(e.type==SUBMIT){
						just[e.id] = sub[e.id] = true;
						send[e.id] += 5+L[e.id];
					}
					else{
						int newly = 0, submit = 0, allsize = 0, newlysize = 0;
						for(int i=0;i<M;i++){
							if(just[i])newly++;
							if(just[i])newlysize+=L[i];
							if(sub[i])submit++;
							if(sub[i])allsize+=L[i];
						}
						for(int i=0;i<M;i++){
							if(!sub[i]){
								if(0<newly){
									rev[i]+=4+newly;
								}
							}
							else if(just[i]){
								if(1<submit){
									rev[i]+=4+2*(submit-1)+allsize-L[i];
								}
							}
							else{
								if(0<newly){
									rev[i]+=4+2*newly+newlysize;
								}
							}
						}
						Arrays.fill(just, false);
					}
				}
			}
			int ress = 0, resr = 0;
			for(int i=0;i<M;i++){
				ress+=rev[i]; resr+=send[i];
			}
			System.out.println(ress+" "+resr);
			for(int i=0;i<M;i++)System.out.println(send[i]+" "+rev[i]);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2032().run();
	}
}