yukicoder No.29 - パワーアップ

Source

ニコニコミュニティ
問題文

問題概要

アイテム $1$ から $10$ までの $10$ 種類のアイテムが存在する.
$N$ 匹の敵がいて,それぞれ倒すと $3$ 種類のアイテムが手に入る.どのアイテムが手に入るかは与えられる.
同じアイテムを $2$ 個,あるいは,なんでも良いから合計でアイテムを $4$ 個消費することで $1$ 回パワーアップすることができる.
パワーアップできる回数の最大値を求める問題.

解法

それぞれのアイテムが何個手に入るかを数える.
同じアイテムが $2$ 個以上手に入るなら,それらを優先的に使い,$1$ 個余ったもの同士を使い,$4$ 個使うパワーアップを行う.

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

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int N;
int A[1000];

int main(){
  int i, j, k;
  int res = 0;

  scanf("%d",&N);
  rep(i,3*N){
    scanf("%d",&k);
    A[k]++;
  }

  k = 0;
  rep(i,1000){
    res += A[i]/2;
    k += A[i]%2;
  }
  res += k / 4;

  printf("%d\n",res);

  return 0;
}

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

#include<bits/stdc++.h>
using namespace std;

int mask, i, k, res;
int main(){
  scanf("%*d");
  while(~scanf("%d",&i)) k++, mask ^= 1<<i;
  printf("%d\n",k/2 - (__builtin_popcount(mask)+2)/4);
  return 0;
}

Current time: 2017年07月21日13時30分20秒
Last modified: 2014年11月06日13時04分32秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: