kmjp's blog

競技プログラミング参加記です

AtCoder ARC #020 : A - 石を滑らせるゲーム、B - 縞模様

ARC#020に参加。Dを部分点で稼ぎそこそこの順位を得た。
http://arc020.contest.atcoder.jp/tasks/arc020_1
http://arc020.contest.atcoder.jp/tasks/arc020_2

A - 石を滑らせるゲーム

1次元の数直線上で、2人の座標が与えられる。
原点に近いのはどちらか。

絶対値を比較するだけ。

void solve() {
	int f,i,j,k,l,x,y;
	int A,B;
	cin>>A>>B;
	if(abs(A)<abs(B)) _P("Ant\n");
	else if(abs(A)>abs(B)) _P("Bug\n");
	else _P("Draw\n");
}

B - 縞模様

N枚の画用紙が1列に並んでおり、それぞれの色が与えられる。
この画用紙の何枚かを塗り替え、縞模様にしたい。
1枚色を変えるコストがCの時、最小コストを答えよ。

色の種類もNも小さいので、色を2色総当たりで試せばよい。

int N,C;
int A[1001];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>C;
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
	}
	int mi=1<<30;
	
	for(x=0;x<10;x++) {
		for(y=0;y<10;y++) {
			if(x==y) continue;
			j=0;
			FOR(i,N) {
				if(i%2==0) {
					if(A[i]!=x) j+=C;
				}
				else {
					if(A[i]!=y) j+=C;
				}
			}
			mi=min(mi,j);
			
		}
	}
	cout << mi << endl;
}

まとめ

Bで1-originなのに気づかず1WAしてしまった…。