活動日記 day 33

活動内容 :
コンテスト (チーム戦)
コンテスト : Virtual Arena: Room 3394

A - Selection of Participants of an Experiment

全探索で解けます。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<climits>
#include<sstream>
#include<deque>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int a[1001]={0};
 
int main() {
  int n;
  while(scanf("%d",&n),n!=0){
    for(int i=0;i<n;++i){
      scanf("%d ",&a[i]);
    }
    int minimum = INT_MAX;
    for(int i=0;i<n;++i){
      for(int j=i+1;j<n;++j){
        if(abs(a[i] - a[j]) < minimum)minimum = abs(a[i] - a[j]);
      }
    }
    printf("%d\n",minimum);
  }
 
  return 0;
}

B - Look for the Winner!
入力を捨てるのを忘れないようにしましょう。

#include <iostream>
#include <stdio.h>
using namespace std;
 
int main()
{
    while (true)
    {
    LABEL:
        int array[30] = {0};
        int n;
        int top = 0;
        int topalpha = 0;
        int next = 0;
        int nextalpha = 0;
        int amari = 0;
        cin >> n;
        if (n == 0)
        {
            return 0;
        }
        char temp;
        for (int i = 0; i < n; i++)
        {
            cin >> temp;
            temp = temp - 65;
            array[temp]++;
 
            //top sagashi
            for (int j = 0; j < 30; j++)
            {
                if (top < array[j])
                {
                    top = array[j];
                    topalpha = j;
                }
            }
 
            //2nd sagashi
            for (int j = 0; j < 30; j++)
            {
                if (next < array[j] && j != topalpha)
                {
                    next = array[j];
                    nextalpha = j;
                }
            }
            amari = n - i - 1;
            char hoge;

            if (top <= next + amari)
            {
                //mada wakaran
                continue;
            }
            else
            {
                //win top or tie
                if (top == next)
                {
                    cout << "TIE" << endl;

                    for (int j = 0; j < amari; j++)
                    {
                        cin >> hoge;
                    }
                    goto LABEL;
                }
                else
                {
                    printf("%c ", 65 + topalpha);
                    printf("%d\n", i + 1);
                    for (int j = 0; j < amari; j++)
                    {
                        cin >> hoge;
                    }
                    goto LABEL;
                }
            }
        }
        printf("TIE\n");
    }
    return 0;
}

E - Arithmetical CAPTCHA
全探索です。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<climits>
#include<sstream>
#include<deque>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<bitset>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int n[5];
char op[] = {'+','-','='};
 
bool check(deque<char> &ops) {
  bool found = false;
  rep(i,3) if( ops[i] == '=' ) { found = true; break; }
  if( !found ) return false;
  set<int> S;
  int v = n[0];
  rep(i,3) {
    if( ops[i] == '+' ) {
      v += n[i+1];
    } else if( ops[i] == '-' ) {
      v -= n[i+1];
    } else {
      S.insert(v);
      v = n[i+1];
    }
  }
  S.insert(v);
  return S.size() == 1;
}
 
bool dfs(int cur,deque<char> &deq) {
  if( cur >= 3 ) {
    return check(deq);
  }
  rep(i,3) {
    deq.push_back(op[i]);
    if( dfs(cur+1,deq) ) return true;
    deq.pop_back();
  }
  return false;
}
 
void compute() {
  deque<char> deq;
  assert( dfs(0,deq) );
  cout << n[0] << " ";
  rep(i,3) {
    cout << deq[i] << " " << n[i+1];
    if( i != 2 ) cout << " ";
  } puts("");
}
 
int main() {
  int T,CNT=1;
  cin >> T;
  while( T-- ) {
    cout << "Case #" << CNT++ << ": ";
    rep(i,4) cin >> n[i];
    compute();
  }
  return 0;
}

コメント：
蟻本を読んでSG定理を復習しようと思います。