AtCoder Regular Contest #020 B問題 - 縞模様

Source

AtCoder Regular Contest #020
問題文

問題概要

色は全部で $10$ 色あって,$1$ から $10$ の整数で表される.
一列に $N$ 個のセルがあって,$i$ 番目のセルは $A_i$ の色で塗られている.
各セルは,コスト $C$ で好きな色に塗り替えることができる.
縞模様にする最小コストを求める問題.
縞模様とは,全体でちょうど $2$ 色のみが使われていて,隣り合うセルは違う色であるようなものである.

解法

奇数番目のセルの色と,偶数番目のセルの色を何にするかを全部試す.
$O(10^2 N)$.($10$ は色の数を意味する)

Cによるスパゲッティなソースコード

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n,c;
  int in[1000];
  int res, tmp;

  scanf("%d%d",&n,&c);
  res = n;

  rep(i,n) scanf("%d",in+i), in[i]--;

  rep(i,10) rep(j,10) if(i!=j){
    tmp = 0;
    for(k=0;k<n;k+=2) if(in[k]!=i) tmp++;
    for(k=1;k<n;k+=2) if(in[k]!=j) tmp++;
    if(tmp < res) res = tmp;
  }

  res *= c;
  printf("%d\n",res);

  return 0;
}

Current time: 2017年07月23日17時40分25秒
Last modified: 2014年03月30日00時16分55秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC020 ARC_B
トップページに戻る

Logged in as: unknown user (not login)

ログイン: