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: 2024年04月25日18時35分11秒
Last modified: 2014年11月06日13時04分32秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン：