競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

CodeChef April long Challenge 2015 Broken Telephone(BROKPHON)

注:この記事はCodeChef終了後に更新しています。

たぶん一番簡単です。正答数も一番高いです。

- 問題概要

N人で壊れた電話を使って数字の伝言ゲームをする。壊れている電話は正しく数字を伝えることができない。
ゲーム終了後にN人にインタビューをし、どの数字を伝えられたかを教えてもらう。
正しく伝えることができなかったもしくは正しく聞き取ることができなかった人の人数を答えなさい。という問題です。

- 解法

壊れている電話の数を出力せよという問題と同義です。
隣接した人で数字が異なる箇所の個数を答えるだけなのでO(N)です。

- ソースコード

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
 
using namespace std;
 
 
int main(void){
 
	int T, N, A;
	int misheard, p;
	bool miss;
	cin >> T;
	while (T){
		misheard = 0; miss = false;
		cin >> N;
		cin >> p;
		for (int i = 1; i < N; i++){
			cin >> A;
			if (A != p){
				if (miss == false)misheard++;
				misheard++;
				miss = true;
			}
			else miss = false;
			p = A;
		}
		cout << misheard << endl;
		T--;
	}
 
	return(0);
}